[Resource Topic] 2008/169: Understanding Phase Shifting Equivalent Keys and Exhaustive Search

Welcome to the resource topic for 2008/169

Understanding Phase Shifting Equivalent Keys and Exhaustive Search

Authors: Côme Berbain, Aline Gouget, Hervé Sibert


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.

ePrint: https://eprint.iacr.org/2008/169

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .