Cube attack

The cube attack is a method of cryptanalysis applicable to a wide variety of symmetrickey 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.
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 8bit to 1bit Sboxes, 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^{30} 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^{30}, 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^{[update]} 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,000bit LFSRbased stream cipher existed, and claims that the attack on reducedround 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 smalldegree 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.)
References
 ^ Dinur, Itai; Shamir, Adi (20090126) (PDF). Cube Attacks on Tweakable Black Box Polynomials. Cryptology ePrint Archive. ePrint 20090126:174453. http://eprint.iacr.org/2008/385.
 ^ ^{a} ^{b} Bruce Schneier (20080819). "Adi Shamir's Cube Attacks". http://www.schneier.com/blog/archives/2008/08/adi_shamirs_cub.html. Retrieved 20081204.
 ^ Daniel J. Bernstein (20090114). "Why haven't cube attacks broken anything?". http://cr.yp.to/cubeattacks.html. Retrieved 20090227.
 ^ Michael Vielhaber (20071028). "Breaking ONE.FIVIUM by AIDA an Algebraic IV Differential Attack". http://eprint.iacr.org/2007/413.
 ^ Michael Vielhaber (20090223). "Shamir's "cube attack": A Remake of AIDA, The Algebraic IV Differential Attack". http://hsbremerhaven.de/Binaries/Binary10017/AIDA_Shamir.pdf.
Cryptography Categories: Cryptographic attacks
Wikimedia Foundation. 2010.
Look at other dictionaries:
Cube (disambiguation) — A cube is a shape in three dimensions. It may also refer to: Contents 1 People 2 Math and science 3 Entertainment … Wikipedia
Cosmic Cube — The Titan Thanos holds the Cosmic Cube (the entity Death looks on in the background). Interior artwork from Captain Marvel 28 (Sept. 1973). Art by Jim Starlin. Publicatio … Wikipedia
Ant Attack — Infobox VG title = Ant Attack developer = Sandy White publisher = Quicksilva designer = engine = Softsolid 3D released = 1983 (Spectrum), 1984 (Commodore 64) genre = Action game modes = Single player ratings = N/A platforms = ZX Spectrum,… … Wikipedia
Necker Cube — The Necker Cube: a wire frame cube with no depth cues. The Necker Cube is an optical illusion first published as a rhomboid in 1832 by Swiss crystallographer Louis Albert Necker.[1] … Wikipedia
White Cube — is one of the most prominent contemporary commercial art galleries in the world.Factdate=November 2007 It is based in Hoxton Square in the East End of London. It represents Damien Hirst, Tracey Emin and many other internationally recognised… … Wikipedia
I:Cube — Nicolas Chaix alias I:Cube est un musicien français de musique électronique agissant dans divers domaines comme la house, le downtempo ou l ambient. Sommaire 1 Biographie 2 Discographie partielle 2.1 Albums … Wikipédia en Français
Coppersmith's Attack — describes a class of attacks on the public key cryptosystem RSA based on Coppersmith s theorem (see below). The public key in the RSA system is a tuple of integers (N,e), where N is the product of two primes p and q. The secret key is given by an … Wikipedia
Sudden Attack — Infobox VG title = Sudden Attack developer = flagiconRepublic of Korea GameHi publisher = Netmarble (PC) designer = GameHi engine = Jupiter Game Engine released = July 21 2005 genre = First person shooter modes = Multiplayer ratings = 15+ (no… … Wikipedia
Trivium (Algorithmus) — Struktur von Trivium Trivium ist eine synchrone Stromchiffre, die einen Kompromiss zwischen einfacher und performanter Umsetzbarkeit in Hardware und effizienter Implementierung in Software darstellt. Trivium wurde von den beiden belgischen… … Deutsch Wikipedia
Gradius Collection — Desarrolladora(s) Konami Distribuidora(s) Konami Plataforma(s) PSP Fecha(s) de lanzamiento … Wikipedia Español