 | This article may be too technical for most readers to understand.(January 2014) |
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, 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". 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,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.)
In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.
The Data Encryption Standard is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryptography.
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can affect the resultant difference at the output. In the case of a block cipher, it refers to a set of techniques for tracing differences through the network of transformation, discovering where the cipher exhibits non-random behavior, and exploiting such properties to recover the secret key.
In cryptography, the International Data Encryption Algorithm (IDEA), originally called Improved Proposed Encryption Standard (IPES), is a symmetric-key block cipher designed by James Massey of ETH Zurich and Xuejia Lai and was first described in 1991. The algorithm was intended as a replacement for the Data Encryption Standard (DES). IDEA is a minor revision of an earlier cipher Proposed Encryption Standard (PES).
A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).
In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.
In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers. Linear cryptanalysis is one of the two most widely used attacks on block ciphers; the other being differential cryptanalysis.
In cryptography, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext, thus ensuring Shannon's property of confusion. Mathematically, an S-box is a nonlinear vectorial Boolean function.
The GOST block cipher (Magma), defined in the standard GOST 28147-89, is a Soviet and Russian government standard symmetric key block cipher with a block size of 64 bits. The original standard, published in 1989, did not give the cipher any name, but the most recent revision of the standard, GOST R 34.12-2015, specifies that it may be referred to as Magma. The GOST hash function is based on this cipher. The new standard also specifies a new 128-bit block cipher called Kuznyechik.
In cryptography, FEAL is a block cipher proposed as an alternative to the Data Encryption Standard (DES), and designed to be much faster in software. The Feistel based algorithm was first published in 1987 by Akihiro Shimizu and Shoji Miyaguchi from NTT. The cipher is susceptible to various forms of cryptanalysis, and has acted as a catalyst in the discovery of differential and linear cryptanalysis.
In cryptography, DES-X is a variant on the DES symmetric-key block cipher intended to increase the complexity of a brute-force attack. The technique used to increase the complexity is called key whitening.
In cryptography, LOKI89 and LOKI91 are symmetric-key block ciphers designed as possible replacements for the Data Encryption Standard (DES). The ciphers were developed based on a body of work analysing DES, and are very similar to DES in structure. The LOKI algorithms were named for Loki, the god of mischief in Norse mythology.
In cryptography, the eXtended Sparse Linearization (XSL) attack is a method of cryptanalysis for block ciphers. The attack was first published in 2002 by researchers Nicolas Courtois and Josef Pieprzyk. It has caused some controversy as it was claimed to have the potential to break the Advanced Encryption Standard (AES) cipher, also known as Rijndael, faster than an exhaustive search. Since AES is already widely used in commerce and government for the transmission of secret information, finding a technique that can shorten the amount of time it takes to retrieve the secret message without having the key could have wide implications.
In cryptography, MUGI is a pseudorandom number generator (PRNG) designed for use as a stream cipher. It was among the cryptographic techniques recommended for Japanese government use by CRYPTREC in 2003, however, has been dropped to "candidate" by CRYPTREC revision in 2013.
A self-shrinking generator is a pseudorandom generator that is based on the shrinking generator concept. Variants of the self-shrinking generator based on a linear-feedback shift register (LFSR) are studied for use in cryptography.
A nonlinear-feedback shift register (NLFSR) is a shift register whose input bit is a non-linear function of its previous state.
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.
Grain is a stream cipher submitted to eSTREAM in 2004 by Martin Hell, Thomas Johansson and Willi Meier. It has been selected for the final eSTREAM portfolio for Profile 2 by the eSTREAM project. Grain is designed primarily for restricted hardware environments. It accepts an 80-bit key and a 64-bit IV. The specifications do not recommend a maximum length of output per pair. A number of potential weaknesses in the cipher have been identified and corrected in Grain 128a which is now the recommended cipher to use for hardware environments providing both 128bit security and authentication.
In cryptography, an alternating step generator (ASG) is a cryptographic pseudorandom number generator used in stream ciphers, based on three linear-feedback shift registers. Its output is a combination of two LFSRs which are stepped (clocked) in an alternating fashion, depending on the output of a third LFSR.
Orr Dunkelman is an Israeli cryptographer and cryptanalyst, currently a professor at the University of Haifa Computer Science department. Dunkelman is a co-director of the Center for Cyber Law & Privacy at the University of Haifa and a co-founder of Privacy Israel, an Israeli NGO for promoting privacy in Israel.
