The cube attack is a method of cryptanalysis applicable to a wide variety of symmetric-key algorithms, published by Itai Dinur and Adi Shamir in a September 2008 preprint.
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.
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.
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.
Vielhaber claims, for instance, that the linear polynomials in the key bits that are obtained during the attack will be unusually sparse.