International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Understanding Phase Shifting Equivalent Keys and Exhaustive Search

Côme Berbain
Aline Gouget
Hervé Sibert
Search ePrint
Search Google
Abstract: Recent articles~\cite{kucuk,ckp08,isobe,cryptoeprint:2008:128} introduce the concept of phase shifting equivalent keys in stream ciphers, and exploit this concept in order to mount attacks on some specific ciphers. The idea behind phase shifting equivalent keys is that, for many ciphers, each internal state can be considered as the result of an injection of a key and initialization vector. This enables speeding up the standard exhaustive search algorithm among the $2^n$ possible keys by decreasing the constant factor of $2^n$ in the time complexity of the algorithm. However, this has erroneously been stated in~\cite{isobe,cryptoeprint:2008:128} as decreasing the complexity of the algorithm below $2^n$. In this note, we show why this type of attacks, using phase shifting equivalent keys to improve exhaustive key search, can never reach time complexity below $2^n$, where $2^n$ is the size of the key space.
  title={Understanding Phase Shifting Equivalent Keys and Exhaustive Search},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / cryptanalysis, phase-shifting equivalent keys, stream cipher, Decim v2, Grain, eSTREAM},
  note={not published 13986 received 15 Apr 2008, last revised 17 Apr 2008},
  author={Côme Berbain and Aline Gouget and Hervé Sibert},