Cryptology ePrint Archive: Report 2008/169

Understanding Phase Shifting Equivalent Keys and Exhaustive Search

Côme Berbain and 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.

Category / Keywords: secret-key cryptography / cryptanalysis, phase-shifting equivalent keys, stream cipher, Decim v2, Grain, eSTREAM

Publication Info: not published

Date: received 15 Apr 2008, last revised 17 Apr 2008

Contact author: herve sibert at nxp com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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

Version: 20080417:074811 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]