**Cube Attacks on Tweakable Black Box Polynomials**

*Itai Dinur and Adi Shamir*

**Abstract: **Almost any cryptographic scheme can be described by
\emph{tweakable polynomials} over $GF(2)$, which contain both
secret variables (e.g., key bits) and public variables (e.g.,
plaintext bits or IV bits). The cryptanalyst is allowed to tweak
the polynomials by choosing arbitrary values for the public
variables, and his goal is to solve the resultant system of
polynomial equations in terms of their common secret variables. In
this paper we develop a new technique (called a \emph{cube
attack}) for solving such tweakable polynomials, which is a major
improvement over several previously published attacks of the same
type. For example, on the stream cipher Trivium with a reduced
number of initialization rounds, the best previous attack (due to
Fischer, Khazaei, and Meier) requires a barely practical
complexity of $2^{55}$ to attack $672$ initialization rounds,
whereas a cube attack can find the complete key of the same
variant in $2^{19}$ bit operations (which take less than a second
on a single PC). Trivium with $735$ initialization rounds (which
could not be attacked by any previous technique) can now be broken
with $2^{30}$ bit operations. Trivium with $767$ initialization
rounds can now be broken with $2^{45}$ bit operations, and the
complexity of the attack can almost certainly be further reduced to about
$2^{36}$ bit operations. Whereas previous attacks were heuristic,
had to be adapted to each cryptosystem, had no general complexity
bounds, and were not expected to succeed on random looking
polynomials, cube attacks are provably successful when applied to
random polynomials of degree $d$ over $n$ secret variables
whenever the number $m$ of public variables exceeds $d+log_dn$.
Their complexity is $2^{d-1}n+n^2$ bit operations, which is
polynomial in $n$ and amazingly low when $d$ is small. Cube
attacks can be applied to any block cipher, stream cipher, or MAC
which is provided as a black box (even when nothing is known about
its internal structure) as long as at least one output bit can be
represented by (an unknown) polynomial of relatively low degree in
the secret and public variables.

**Category / Keywords: **Cryptanalysis, algebraic attacks, cube attacks, tweakable black box polynomials, stream ciphers, Trivium.

**Publication Info: **A slightly shorter version appears in Eurocrypt 2009

**Date: **received 13 Sep 2008, last revised 26 Jan 2009

**Contact author: **itai dinur at weizmann ac il

**Available format(s): **PDF | BibTeX Citation

**Note: **The Trivium results are updated, and the paper is revised according to several reviews.

**Version: **20090126:174453 (All versions of this report)

**Short URL: **ia.cr/2008/385

[ Cryptology ePrint archive ]