Guess And Determine Attack On Stream Cipher And Its Applications

Stream cipher, which is an important branch of symmetric cryptography, has manyimportant applications in many areas. Correlation attack and algebraic attack produce aserious threat to the security of the traditional stream cipher which is based on the linearfeedback shift register. In February2004, Europe launched the eSTREAM project to callfor stream ciphers worldwide. After three phases of evaluation, only seven candidateciphersleft: GrainV1,MickeyV2,Trivium,HC-128,Salsa20/12,SosemanukandRabbit.From the result, one can imply that non-linear driver and non-linear iteration have becomeaninternationalmainstreamdirectionsofdesigningstreamcipher. Thestudyonthissevenciphers will be an important trend of the international field of cipher cryptanalysis.In the paper, we first summarize the exiting guess and determine attack on Sose-manuk. Then we describe Sosemanuk from the view point of bit-level and find a kindof equation system about its internal states. Based on this finding, an improved word-oriented guess and determine attack on Sosemanuk is proposed. This improved attackutilities the Groebner basis method to solve the equation system, and can determine theother5words of the internal state by guessing just7words, and thus the time complexityis O(2192).Secondly, we give a guess and determine attack on GMR-2stream ciphers. GMR-2,which is used in the satellite phones, have been reconstructed by Driessen et al. recently.We find the KEY application’s weakness of the GMR-2cipher. For this weakness we re-describe the process of this cipher. The strategy of our new attack is based on the conceptof Dynamic Guess and Determine Attack. The most interesting idea is that the evolutionof guessing part of the internal state is changed dynamically according to the intermediateprocess. Thisattackneedsonlyoneframe(15bytes)ofthekeystreamoftheGMR-2cipherand the time complexity is O(228) on average. The64-bit session key can be obtained inaround700seconds on laptop.