Cube attack

A revised version of this preprint was placed online in January 2009,[1] and the paper has also been accepted for presentation at Eurocrypt 2009.

A cipher is vulnerable if an output bit can be represented as a sufficiently low degree polynomial over GF(2) of key and input bits; in particular, this describes many stream ciphers based on LFSRs.[2] DES and AES are believed to be immune to this attack.[2] It works by summing an output bit value for all possible values of a subset of public input bits, chosen such that the resulting sum is a linear combination of secret bits; repeated application of this technique gives a set of linear relations between secret bits that can be solved to discover these bits. The authors show that if the cipher resembles a random polynomial of sufficiently low degree then such sets of public input bits will exist with high probability, and can be discovered in a precomputation phase by "black box probing" of the relationship between input and output for various choices of public and secret input bits making no use of any other information about the construction of the cipher.

The paper presents a practical attack, which the authors have implemented and tested, on a stream cipher on which no previous known attack would be effective. Its state is a 10,000 bit LFSR with a secret dense feedback polynomial, which is filtered by an array of 1000 secret 8-bit to 1-bit S-boxes, whose input is based on secret taps into the LFSR state and whose output is XORed together. Each bit in the LFSR is initialized by a different secret dense quadratic polynomial in 10, 000 key and IV bits. The LFSR is clocked a large and secret number of times without producing any outputs, and then only the first output bit for any given IV is made available to the attacker. After a short preprocessing phase in which the attacker can query output bits for a variety of key and IV combinations, only 2³⁰ bit operations are required to discover the key for this cipher.

The authors also claim an attack on a version of Trivium reduced to 735 initialization rounds with complexity 2³⁰, and conjecture that these techniques may extend to breaking 1100 of Trivium's 1152 initialization rounds and "maybe even the original cipher". As of December 2008 this is the best attack known against Trivium.

The attack is, however, embroiled in two separate controversies. Firstly, Daniel J. Bernstein [3] disputes the assertion that no previous attack on the 10,000-bit LFSR-based stream cipher existed, and claims that the attack on reduced-round Trivium "doesn't give any real reason to think that (the full) Trivium can be attacked". He claims that the Cube paper failed to cite an existing paper by Xuejia Lai detailing an attack on ciphers with small-degree polynomials, and that he believes the Cube attack to be merely a reinvention of this existing technique.

Secondly, Dinur and Shamir credit Michael Vielhaber's "Algebraic IV Differential Attack" (AIDA) as a precursor of the Cube attack.[4] Dinur has stated at Eurocrypt 2009 that Cube generalises and improves upon AIDA. However, Vielhaber contends that the cube attack is no more than his attack under another name.[5] It is, however, acknowledged by all parties involved that Cube's use of an efficient linearity test such as the BLR test results in the new attack needing less time than AIDA, although how substantial this particular change is remains in dispute. It is not the only way in which Cube and AIDA differ. Vielhaber claims, for instance, that the linear polynomials in the key bits that are obtained during the attack will be unusually sparse. He has not yet supplied evidence of this, but claims that such evidence will appear in a forthcoming paper by himself entitled "The Algebraic IV Differential Attack: AIDA Attacking the full Trivium". (It is not clear whether this alleged sparsity applies to any ciphers other than Trivium.)