Cube attack

Attack

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.{{cite web

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, a 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 230 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 230, and conjecture that these techniques may extend to breaking 1100 of Trivium's 1152 initialization rounds and "maybe even the original cipher". this is the best attack known against Trivium.

The attack is, however, embroiled in two separate controversies. Firstly, Daniel J. Bernstein{{cite web

Secondly, Dinur and Shamir credit Michael Vielhaber's "Algebraic IV Differential Attack" (AIDA) as a precursor of the Cube attack.{{cite journal 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.)

References