Improving Heuristic Guess and Determine Attack on TIPSY and SNOW 1.0 Stream Ciphers

Guess and determine attacks are general attacks on stream ciphers. These attacks are classified into ad-hoc and Heuristic Guess and Determine (HGD) attacks. One of the Advantages of HGD attack algorithm over ad-hoc attack is that it is designed algorithmically for a large class of stream ciphers while being powerful. In this paper, we use auxiliary polynomials in addition to the original equations as the inputs to the HGD attack on TIPSY and SNOW 1.0 stream ciphers. Based on the concept of guessed basis, the number of guesses in both HGD attack and the improved one on TIPSY is six, however the attack complexity is reduced from O(2102)to O(296). This amount is equal to that of ad-hoc attack, but the size of the guessed basis is improved from seven to six. Also, the complexity of GD attack on SNOW 1.0 of heuristic one with the guessed basis of size 6 and ad-hoc attack with the guessed basis of size 7areO(2202) and O(2224), respectively. However, the complexity and the size of guessed basis of the improved HGD attack are reduced to O(2160) and 5, respectively.