A Key Recovery Attack with Equivalent Keys of Stream Cipher

摘要

If the ciphertexts generated from different keys are equivalent, these keys are called equivalent keys. In a stream cipher, since a ciphertext is generated by XORing a plaintext to a keystream, the key which generates a phase shifted keystream can also be called equivalent key. In this paper, we propose a key recovery attack using the phase shifted equivalent keys. Our attack is a new cryptanalysis method on stream ciphers. We show effectiveness of our attack by applying it to Grain v1. In Grain v1, our attack can recover an 80-bit key with time complexity of 2{sup}79 by using chosen IVs. This time complexity is lower than 2{sup}80 of exhaustive key search.