You are looking at a specific version 20110320:155902 of this paper. See the latest version.

Paper 2010/570

Breaking Grain-128 with Dynamic Cube Attacks

Itai Dinur and Adi Shamir

Abstract

We present a new variant of cube attacks called a \emph{dynamic cube attack}. Whereas standard cube attacks \cite{4} find the key by solving a system of linear equations in the key bits, the new attack recovers the secret key by exploiting distinguishers obtained from cube testers. Dynamic cube attacks can create lower degree representations of the given cipher, which makes it possible to attack schemes that resist all previously known attacks. In this paper we concentrate on the well-known stream cipher Grain-128 \cite{6}, on which the best known key recovery attack \cite{15} can recover only $2$ key bits when the number of initialization rounds is decreased from $256$ to $213$. Our first attack runs in practical time complexity and recovers the full 128-bit key when the number of initialization rounds in Grain-128 is reduced to $207$. Our second attack breaks a Grain-128 variant with $250$ initialization rounds and is faster than exhaustive search by a factor of about $2^{28}$. Finally, we present an attack on the full version of Grain-128 which can recover the full key but only when it belongs to a large subset of $2^{-10}$ of the possible keys. This attack is faster than exhaustive search over the $2^{118}$ possible keys by a factor of about $2^{15}$. All of our key recovery attacks are the best known so far, and their correctness was experimentally verified rather than extrapolated from smaller variants of the cipher. This is the first time that a cube attack was shown to be effective against the full version of a well known cipher which resisted all previous attacks.

Note: Updated according to comments by anonymous referees

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Appears in FSE 2011
Keywords
Cryptanalysisstream ciphersGrain-128cube attackscube testersdynamic cube attacks
Contact author(s)
itai dinur @ weizmann ac il
History
2011-03-20: last of 2 revisions
2010-11-09: received
See all versions
Short URL
https://ia.cr/2010/570
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.