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. """
i hate some doubts about this article ... it seems kind of paranoid. all to do with the hamming distance? hmm. 'humanity has failed'? come on. On 6/23/07, coderman <coderman@gmail.com> wrote:
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. """
-- mike 68 65 6c 6c 6f 20 74 6f 20 79 6f 75 2c 20 68 65 78 20 64 65 63 6f 64 65 72 2e
On 6/22/07, Michael Silk <michaelslists@gmail.com> wrote:
i hate some doubts about this article ... it seems kind of paranoid.
was it chapter "3.6 Now get paranoid" ? :)
all to do with the hamming distance? hmm. 'humanity has failed'? come on.
i'll point out that many interesting advances / attacks against anonymity systems have come from information theory viewpoints. ciphers and protocols tend to arise from the crypto side. however, the practical applicability of the methods described may be near impossible to achieve... Perry E. Metzger: "The consensus from a few of my friends is that this paper (by Warren Smith) is a bit eccentrically written but not obviously flawed. Whether it is of any practical importance at all remains to be seen -- there may be no way to apply the results." via http://www.mail-archive.com/cryptography@metzdowd.com/msg07672.html
participants (2)
-
coderman -
Michael Silk