[Infowarrior] - Crypto: Cube Attacks on Tweakable Black Box Polynomials

[Richard Forno]

Cryptology ePrint Archive: Report 2008/385

Cube Attacks on Tweakable Black Box Polynomials

Itai Dinur and Adi Shamir

http://eprint.iacr.org/2008/385

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,  
and by extrapolating our experimentally verified complexities for  
various sizes, we have reasons to believe that cube attacks will  
remain faster than exhaustive search even for $1024$ initialization  
rounds. 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. In particular, they can be easily and  
automatically combined with any type of side channel attack that leaks  
some partial information about the early stages of the encryption  
process (which can typically be represented by a very low degree  
polynomial), such as the Hamming weight of a byte written into a  
register.

Category / Keywords: secret-key cryptography / Cryptanalysis,  
algebraic attacks, cube attacks,

Date: received 13 Sep 2008, last revised 14 Sep 2008

Contact author: itai dinur at weizmann ac il

Available formats: PDF | BibTeX Citation

Version: 20080914:160327 (All versions of this report)

http://eprint.iacr.org/2008/385