Okay - some people have been making some rather brazen claims about the ability to crack a PDF document which uses the AES 128 bit key to encrypt the content. I am not sure if they are truly psychic (one plausible way to crack AES), but doing such using a brute force attack is probably not going to work without a bit of luck. To understand how complex AES is, let's explore how the key is derived and what it means to "break" or "crack" encryption.
The AES standard has a fixed block size of 128 bits and a key size of either 128, 192 or 256 bits. The key is expanded using Rijndael's key schedule in which most of AES calculations are done in a special finite field. Operates on a 4 x —4 array of bytes (the State) and uses four distinct steps to encrypt.
1. AddRoundKey - each byte of the state is combined with the round key; each round key is derived from the cipher key using a key schedule (simple).
2. SubBytes - SubBytes is a non-linear substitution step where each byte is replaced with another according to a lookup table. In order to add non-linearity to the key, the Galois Field (GF) is used to derive the inverse function of 2 to the power of 8. This has been credited with keeping things unlinear.
3. ShiftRows - a transposition step where each row of the state is shifted cyclically a certain number of steps.
4. MixColumns - a mixing operation which operates on the columns of the state, combining the four bytes in each column using a linear transformation. This provides diffusion in the final cipher in conjunction with ShiftRows. Each column is treated as a polynomial over GF(28) and is then multiplied modulo x4 + 1 with a fixed polynomial c(x) = 3x3 + x2 + x + 2.
The final round replaces the MixColumns stage with another instance of AddRoundKey.
To give you an idea of the complexity of the resulting decryption process, to crack a 128 bit key would take approximately 3.4 x 10^38 guesses assuming the correct key was the last one you tried. To place this in perspective, is estimated that if a DES key generator were able to discover 1 DES key per second, it would take 149 thousand-billion (149 trillion) years to crack a single 128 bit AES key. As a side note, most physicists accept that the universe is approximately 20 billion years old.
As Homer Simpson would say - "D'oh!!!".
What people who are claiming to "break" AES have to use as a metric is a methodology which is anything faster than an exhaustive search for all the keys, also referred to as a "brute force" attack. There is another type of attack methodology called a "side channel attack which does not operate on the actual cipher but on mechanisms around it. There have been two claims of success in breaking AES using side channel attacks. You should note that both of these required access to an application running on the same machine.
Anyone still feel they can get the $500 I offered for cracking the document?
