AES may have been broken. Serpent, too. Or maybe not. In either case, there's no need to panic. Yet. But there might be soon. Maybe.
---Bruce Schneier---

Some words for...
The Advanced Encryption Standard (AES)

The Advanced Encryption Standard (AES) is a new Federal Information Processing Standard (FIPS) Publication that specifies a cryptographic algorithm for use by U.S. Government organizations to protect sensitive (unclassified) information.

So, the AES is really a cryptographic algorithm named Rijndael and was selected during a U.S. Government contest in October 2000 among the following algorithms : MARS, RC6, Rijndael, Serpent, and Twofish.

The AES specifies three key sizes: 128, 192 and 256 bits. In decimal terms, this means that there are approximately:

3.4 x 1038 possible 128-bit keys;

6.2 x 1057 possible 192-bit keys; and

1.1 x 1077 possible 256-bit keys.

In comparison, DES keys are 56 bits long, which means there are approximately 7.2 x 1016 possible DES keys. Thus, there are on the order of 1021 times more AES 128-bit keys than DES 56-bit keys.

The numbers above indicate that using brute force to crack something encrypted with the AES will require *many* times the estimated age of the universe. And if you knew something so important that someone could wait, let's say, 5 times the age of universe to decrypt it, you should consider something better than encrypting it with AES and leaving it in your Palmtop :-)

What changed since the contest

The story goes like this: Nicolas Courtois and Josef Pieprzyk published a paper in which they showed how the Rijndael (AES) algorithm could be written as an overdefined system of multivariate quadratic equations (MQ). And some time ago a paper was published at the Eurocrypt by Shamir (Adi Shamir, the S in the RSA algorithm) in which he described the subexponential way to find a solution for the MQ systems described above. That meant that, increasing the rounds at the Rijndael algorithm, the security would not grow exponentially.

Exactly on the XL method of Shamir was based the technique (XSL) that Nicolas Courtois and Josef Pieprzyk described in their paper, which with the help of a cipher called BES, isomorphic to AES for some subsets of plaintexts, is able to launch an attack at AES with a 2100 complexity1. And as Bruce Schneier, one of the most famous cryptanalysts today says, "the attack against AES can only now get better". And if someone comes up with a 280 complexity attack against the AES... it is only a matter of years...

1 2100 complexity means, that by using brute force, we have to check 2100 possible keys.