Cube attack
Encyclopedia
The cube attack is a method of cryptanalysis
applicable to a wide variety of symmetric-key algorithm
s, published by Itai Dinur and Adi Shamir
in a September 2008 preprint. A revised version of this preprint was placed online in January 2009, 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
. DES
and AES
are believed to be immune to this attack. 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". this is the best attack known against Trivium.
The attack is, however, embroiled in two separate controversies. Firstly, Daniel J. Bernstein
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. 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.
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.)
Cryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
applicable to a wide variety of symmetric-key algorithm
Symmetric-key algorithm
Symmetric-key algorithms are a class of algorithms for cryptography that use trivially related, often identical, cryptographic keys for both encryption of plaintext and decryption of ciphertext. The encryption key is trivially related to the decryption key, in that they may be identical or there is...
s, published by Itai Dinur and Adi Shamir
Adi Shamir
Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
in a September 2008 preprint. A revised version of this preprint was placed online in January 2009, 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
Degree of a polynomial
The degree of a polynomial represents the highest degree of a polynominal's terms , should the polynomial be expressed in canonical form . The degree of an individual term is the sum of the exponents acting on the term's variables...
polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
over GF(2)
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
of key and input bits; in particular, this describes many stream ciphers based on LFSRs
Linear feedback shift register
A linear feedback shift register is a shift register whose input bit is a linear function of its previous state.The most commonly used linear function of single bits is XOR...
. DES
Data Encryption Standard
The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...
and AES
Advanced Encryption Standard
Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...
are believed to be immune to this attack. 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
Precomputation
In algorithms, precomputation is the act of performing an initial computation before run time to generate a lookup table that can be used by an algorithm to avoid repeated computation each time it is executed. Precomputation is often used in algorithms that depend on the results of expensive...
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
Trivium (cipher)
Trivium is a synchronous stream cipher designed to provide a flexible trade-off between speed and gate count in hardware, and reasonably efficient software implementation....
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
Daniel J. Bernstein
Daniel Julius Bernstein is a mathematician, cryptologist, programmer, and professor of mathematics at the University of Illinois at Chicago...
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
Xuejia Lai
Xuejia Lai is a cryptographer, currently a professor at Shanghai Jiao Tong University. His notable work includes the design of the block cipher IDEA, the theory of Markov ciphers, and the cryptanalysis of a number of cryptographic hash functions. His book On the Design and Security of Block...
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. 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.
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.)