Paper 2008/169

Understanding Phase Shifting Equivalent Keys and Exhaustive Search

Côme Berbain, Aline Gouget, and Hervé Sibert

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.

Note: Updated to reflect changes in Report 2008/128 as of April 16th, 2008.

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. not published
Keywords
cryptanalysisphase-shifting equivalent keysstream cipherDecim v2GraineSTREAM
Contact author(s)
herve sibert @ nxp com
History
2008-04-17: last of 2 revisions
2008-04-15: received
See all versions
Short URL
https://ia.cr/2008/169
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/169,
      author = {Côme Berbain and Aline Gouget and Hervé Sibert},
      title = {Understanding Phase Shifting Equivalent Keys and Exhaustive Search},
      howpublished = {Cryptology ePrint Archive, Paper 2008/169},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/169}},
      url = {https://eprint.iacr.org/2008/169}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.