Currently Being Moderated
lesliexu

Is AES-128 and AES-256 broken?

Posted by lesliexu in The Data Stack on Mar 26, 2010 5:36:14 PM

At RSA conference 2010 in San Francisco, the cryptographer panel consisting of legends such as Ron Rivest of MIT, Adi Shamir, and former NSA director Brian Snow cited one of the highlights from 2009 was the fact that both AES-128 and AES-256 have been broken. It took a lot of people by surprise that these two modes could be broken and the next logical question to ask would be is it no longer useful for data protection?

 

In reality, these attacks are fathomed by the academics, like researching a solution to a problem that hopefully will never be used. Some background on the three modes of AES - each with a different key length of 128, 192, and 256 bit, correspond to 10, 12, and 14 rounds. A round produces an intermediate state during the process of converting plaintext to cipher text and vice versa.


By 2006, the best known attacks were on 7 rounds for 128-bit keys, 8 rounds for 192-bit keys, and 9 rounds for 256-bit keys. For cryptographers, a cryptographic "break" is something faster than an “exhaustive search” - selecting an appropriate key length depends on the feasibility of performing a “brute force attack”. A brute force attack is a strategy to break encrypted data that involves exhaustively traversing the search space of possible keys until the correct key is found.

 

Another attack was blogged by Bruce Schneier[1] on July 30, 2009 and released as a preprint[2] on August 3, 2009. This new attack is against AES-256 that uses only two related keys which requires the cryptanalyst to have access to plaintexts encrypted with multiple keys that are related in a specific way.

The computation time required is 2^39 time to recover the complete 256-bit key of a 9-round version; 2^45 time for a 10-round version; 2^70 time for a 11-round version. 256-bit AES uses 14 rounds, so these attacks aren't effective against full AES.

 

We talked about the AES-256 attacks. What about AES-128? In November 2009, the first known-key distinguishing attack against a reduced 8-round version of AES-128 was released as a preprint.[3] It works on the 8-round version of AES-128, with a computation complexity of 2^48. The attack exploits the 256 bit key schedule. A key schedule is an algorithm that, given the key, calculates the subkey for these rounds.


In summary, the academics have found ways to “attack” AES-128 and AES-256 faster than an exhaustive search, but not against the full AES. Though the computation times are much faster than exhaustive search, these attacks require related keys, and are  non-practical, and do not seem to pose any real threat to the security of AES-based systems. In the real world, by applying obfuscating or “disguising” techniques on the code and data to be encoded, attacks are made less effective as it is more difficult to determine when one has succeeded in breaking [4].


[1]Bruce Schneier (2009-07-30). "Another New AES Attack". Schneier on Security, A blog covering security and security technology. http://www.schneier.com/blog/archives/2009/07/another_new_aes.html. Retrieved 2010-03-11. 

 

[2]Alex Biryukov; Orr Dunkelman; Nathan Keller; Dmitry Khovratovich; Adi Shamir (2009-08-19). "Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds". http://eprint.iacr.org/2009/374. Retrieved 2010-03-11. 

 

[3]Henri Gilbert; Thomas Peyrin (2009-11-09). "Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations". http://eprint.iacr.org/2009/531. Retrieved 2010-03-11.

 

[4] http://en.wikipedia.org/wiki/Advanced_Encryption_Standard

Comments

Filter Blog

By author:
By date:
By tag: