http://eprint.iacr.org/2007/248.pdf """ We describe a new simple but more power- ful form of linear cryptanalysis. It appears to break AES (and undoubtably other cryptosystems too, e.g. SKIP- JACK). The break is "nonconstructive," i.e. we make it plausible (e.g. prove it in certain approximate probabilis- tic models) that a small algorithm for quickly determining AES-256 keys from plaintext-ciphertext pairs exists b but without constructing the algorithm. The attack's runtime is comparable to performing 64w encryptions where w is the (unknown) minimum Hamming weight in certain bi- nary linear error-correcting codes (BLECCs) associated with AES-256. If w < 43 then our attack is faster than ex- haustive key search; probably w < 10. (Also there should be ciphertext-only attacks if the plaintext is natural En- glish.) ... AES's current status. In view of both (a) Bernstein's tim- ing attack, (b) our nonconstructive argument for a cracking algorithm, (c) the possibility of a "'trapdoor," we believe that 1. AES should be abandoned 2. cryptosystems provably immune to these attacks should be investigated, and 3. our argument for crack-existence, since it is nonrigor- ous5 , should be investigated more carefully. ... 3.6 Now get paranoid Suppose AES-256's designers had evilly arranged matters so that some "code of the code" (known to them) unexpectedly, contained a remarkably low-weight word (known to them), with say, w 10. That would constitute a trapdoor enabling cracking it with much smaller eo,ort 64w . If w = 10, they could crack AES with 6410 = 260 pc-pairs. If w = 7 then AES-256 would be as easy to crack as the cited attacks on DES (only 242 pc-pairs needed)! This could be the case even if the random codes approxima- tion underlying our crude analysis in B'3.3 was invalid. ... 4 What now? Obviously, B'2's strengthened form of linear cryptanalysis will attack a wide variety of secret key cryptosystems, not just AES-256, and will quite often raise the worry that there might exist some intentionally or unintentionally inserted "trap- door." I currently see no feasible way for AES's designers to disprove the existence of this kind of trapdoor. And Bern- stein's cache-timing attack [4] seems applicable against es- sentially any system that employs Sboxes. That's a lot of territory. In short, almost every secret key cryptosystem yet proposed is now busted or at least suspect. We need to design new kinds of cryptosystems immune to both kinds of attack. """