FAQ on the attacks
Q.: Is this the first cryptanalytic result on the full AES?
A.: Yes. The most advanced previous attacks worked for reduced versions only: 10 rounds (out of 12) of AES-192, 10 rounds (out of 14) of AES-256.
Q.: Is this attack practical?
A.: No. Even after improvements we are still over 2^100 encryptions, which is beyond the computational power of the human kind. Moreover this attack works in a related key attack model which assumes a more powerful attacker than the single key model.
Q.: What is the related key attack model?
A.: In this model the attacker can observe the results of the encryption/decryption process under different secret keys. The attacker knows (or even chooses) the relation between the different keys, but does not know the keys themselves. For example, a relation can be as simple as a XOR with a known constant: K_B = K_A xor C, or more complicated as K_B = F(K_A) where F is an arbitrary function chosen by the attacker. In the real life such relations can happen due to hardware faults or due to poorly designed security protocols.
Q.: In your CRYPTO paper you show a practical attack on AES-256 in an open-key model -- what does it mean?
A.: It means that AES-256 is practically broken as a hash function and thus can not be used as a "plug-and-play" in various provably secure constructions.
Q.: Should I continue to use AES-192 and AES-256?
A.: Yes. Our attacks do not pose any immediate threat to the use of AES, but keep an eye on progress in cryptanalysis.
Q.: Does it mean that AES-256 is weaker than AES-128?
A.: Theoretically, yes. Practically, they both still provide a comfortable level of security.
Q.: How does this affect AES-128?
A.: We do not know how to attack the full AES-128 with this idea. However, we expect progress in the cryptanalysis of reduced versions of AES-128.
Q.: Can this weakness be fixed?
A.: The weakness can be fixed, though it would require a serious change in the design. In particular the part of the cipher which is called key-schedule has to be re-designed. It can be also fixed by increasing the number of rounds for all the versions, but it would make the cipher much slower.
Q.: How this can effect the SHA-3 competition and the AES-based hash function submissions there?
A.: Few submissions use AES as it is, so we do not expect that many functions will suffer from the attacks. However, the underlying ideas could be used for the cryptanalysis of some AES-like candidates.
Q.: How this weakness was discovered? Why it was not discovered during the AES competition and not discovered in the last 10 years?
A.: The weakness was discovered when we looked at AES as a hash function, and tried to find weaknesses that are specific for hash functions. We think that most cryptographers used only blockcipher-oriented techniques, against which AES was well protected by the designers. Another reason is that AES-256 probably received less cryptanalytic attention than AES-128, this being a bit ironic since it is supposed to protect much more sensitive information than AES-128.
Q.: Can you briefly describe what properties of the cipher lead to this weakness?
A.: The AES key is used several times during the encryption after it has been expanded via a process called key-schedule. We have discovered that a small change in the key causes a small change in the encryption process and can be canceled out with high probability thus allowing the attacker to control propagation of the differences. We call such cancelation a local collision (a notion from the hash function cryptanalysis). Several consecutive local collisions can be glued together into a longer 7-round difference propagation pattern (also called differential characteristic or differential trail) which has very high probability -- something no cryptanalyst could dream of before. We call this trail a magic AES-256 trail.