The Lazy Genius

Security News & Brain Dumps from Xavier Ashe, a Bit9 Client Partner

AES seems weak

Posted by Xavier Ashe on June 22, 2007

We describe a new simple but more powerful form of linear cryptanalysis. It appears to break AES (and undoubtedly 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.)

Even if this break breaks due to the underlying models inadequately approximating the real world, we explain how AES still could contain “trapdoors” which would make cryptanalysis unexpectedly easy for anybody who knew the trapdoor. If AES’s designers had inserted such a trap door, it could be very easy for them to convince us of that.  But if none exist, then it is probably infeasible difficult for them to convince us of that.

We then discuss how to use the theory of BLECCs to build cryptosystems provably
1. not containing trapdoors of this sort,
2. secure against our strengthened form of linear cryptanalysis,
3. secure against “differential”cryptanalysis,
4. secure against D.J.Bernstein’s timing attack.

Using this technique we prove a fundamental theorem: it is possible to thus-encrypt n bits with security 2^cn , via an circuit Qn containing < cn two-input logic gates and operating in < c log n gate-delays, where the three cs denote (possibly different) positive constants and Qn is constructible in polynomial(n) time. At the end we give tables of useful binary codes.

Interesting paper from Warren D. Smith (pdf).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: