There have been several attacks on AES-256 in the last few months, referred to as the "Luxembourg Attacks". I had hoped to write about the attack announced in June before I went on summer holiday, but ran short on time - and then another attack was announced in July. It is the first attack that I wish to address here to emphasize some points I made in an earlier post.
In May I wrote about the topic of AES-256 and Reputational Risk where I argued that the huge 256-bit key makes it possible for someone to construct an attack which has "big savings" over exhaustive search yet still does not effectively change the margin of security. What suffers in this case is the reputation of AES-256, and the post concluded with
Imagine you posed the following question to a group of top physicists. You asked them to present you with ideas for new research projects where they could assume that the budget included all the money that we have, all the money that has ever been, and the total financial assets of the world for the next 10 million years. Would the resulting proposals be credible?
AES-256 puts cryptanalysts on the same research agenda.
So the first Luxembourg attack gives you an example of the type of arguments that can be proposed when working with 256-bit keys. The attack needs to work with 2^{119} plaintext/ciphertext pairs, requiring about 2^{77} storage, all to yield 156 bits of the key. The remaining 100 unknown bits of the key are guessed, at an average cost of 2^{99} encryptions. This guessing step is hardly worth mentioning as compared to the main 2^{119} computation, since it represents something like one part in a million of the total work.
Some Details of the Attack
The basis of the attack is called differential cryptanalysis (DC), a powerful attack method that gained widespread popularity in the late 80's, and was standard fare by the time AES was announced. In this attack the cryptanalyst finds a pair of values (~P, ~C) such that two plaintexts P1 and P2 of difference ~P = P1 + P2 are biased towards producing ~C as the difference C1 + C2 of their corresponding ciphertexts (here the difference operator + usually means XOR but it varies according to how the key is combined internally in a cipher). In short, plaintexts of difference ~P produce ciphertexts of difference ~C with some probability that is much higher than 2^{-N} where N is the block size of the cipher. Given such a pair of differences (~P, ~C) an attacker can use statistical methods to gain information about parts of the key that were used in the last or next to last round for example. The remaining bits are then guessed.
DC is typically quite data intensive. Even though plaintexts of difference ~P may be biased towards producing ciphertexts of difference ~C, this may only happen with probability 2^{-50} for example, which sounds quite low but it is much higher than you would expect for a 128-bit block cipher. Therefore the attacker will need to obtain 2^{50} plaintext pair encryptions of difference ~P to get on average just one ciphertext pair of difference ~C. Part of a successful DC attack is designing a filtering strategy to discard most ciphertext pairs that don't have ~C as a difference before they are spuriously used as the basis to give information about some part of the key. So a large number of encryptions are needed, where the majority will be winnowed away, leaving a precious few that lead to information about the key.
In the first Luxembourg attack (LA1), the basic DC attack is upgraded to a boomerang attack which eliminates the need to thread the differences (~P, ~C) to each other through all the intermediate rounds of the cipher. LA1 also uses related keys to coerce differences into a desired form - in the vanilla DC attack we are trying to keep plaintext differences in a known state, but by using related keys, the key can also be used to bring the internal state of the cipher into a known difference.
The basic step of LA1 is to obtain 2^{61} encryptions of specially crafted quartets (4 related values), and then combine these values amongst themselves to generate the required internal differences. It is this combination process and its associated filtering which drives up the cost of the attack to 2^{119}. The result is that the remaining unfiltered quartets identify all but 100 bits of the key which, as we mentioned above, can be guessed at a small marginal cost.
Luxembourg 2.0
Even though the attack has unrealistic resource requirements, it works on the full-version of AES-256, which is a significant result – something that no other researchers has been able to do – and that’s not due to lack of trying. And the reputation of AES-256? Well the Register for example reported that LA1 represents an improvement over brute force search for AES-256. Well even that is debatable since you need a huge amount of plaintext/ciphertext encrypted under several keys to mount the attack, while brute force needs just a few blocks to execute. What’s in the future then? Well I guess its here already in the second Luxembourg attack, which is on my reading list.
Related Posts
Posts
1 comment:
Why you don't try mens trousers for your outlook?
Post a Comment