interesting paper on eprint archive

Perry E. Metzger perry at
Fri Jun 22 10:25:16 EDT 2007

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.

     Abstract. We describe a new simple but more powerful form of linear
     cryptanalysis. It appears to break AES (and undoubtably other
     cryptosystems too, e.g. SKIPJACK). The break is ``nonconstructive,''
     i.e. we make it plausible (e.g. prove it in certain approximate
     probabilistic models) that a small algorithm for quickly determining
     AES-256 keys from plaintext-ciphertext pairs exists -- but without
     constructing the algorithm. The attack's runtime is comparable to
     performing $64^w$ encryptions where $w$ is the (unknown) minimum
     Hamming weight in certain binary linear error-correcting codes
     (BLECCs) associated with AES-256. If $w < 43$ then our attack is
     faster than exhaustive key search; probably $w < 10$. (Also there
     should be ciphertext-only attacks if the plaintext is natural English.)

Perry E. Metzger		perry at

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list