Cryptology ePrint Archive: Report 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 f