Cube attack


Cube attack

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.

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 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". 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.)

References


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.Fact|date=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 = flagicon|Republic 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


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.