Paper 2008/385
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^{d1}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.
Note: The Trivium results are updated, and the paper is revised according to several reviews.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. A slightly shorter version appears in Eurocrypt 2009
 Keywords
 Cryptanalysisalgebraic attackscube attackstweakable black box polynomialsstream ciphersTrivium.
 Contact author(s)
 itai dinur @ weizmann ac il
 History
 20090126: revised
 20080914: received
 See all versions
 Short URL
 https://ia.cr/2008/385
 License

CC BY
BibTeX
@misc{cryptoeprint:2008/385, author = {Itai Dinur and Adi Shamir}, title = {Cube Attacks on Tweakable Black Box Polynomials}, howpublished = {Cryptology ePrint Archive, Paper 2008/385}, year = {2008}, note = {\url{https://eprint.iacr.org/2008/385}}, url = {https://eprint.iacr.org/2008/385} }