Paper 2007/248

1. AES seems weak. 2. Linear time secure cryptography

Warren D. Smith

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.) 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 trapdoor, it could be very easy for them to convince us of that. But if none exist, then it is probably infeasibly difficult for them to convince us of \emph{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 $Q_n$ containing $\le c n$ two-input logic gates and operating in $\le c \log n$ gate-delays, where the three $c$s denote (possibly different) positive constants and $Q_n$ is constructible in polynomial$(n)$ time. At the end we give tables of useful binary codes.

Note: This research was inspired by my wondering how to achieve any privacy in view of the NSA's known project to wiretap and database all emails from everybody to everybody forever... ...which is a rather important matter if anybody wants democracy and freedom as I understand those notions. If the government instantly knows where everybody is and what they think, and can arrest anybody and hold them forever without notification, charges, or trial, then that government has essentially total power and the people none. Why are we rapidly approaching that status, and what can we do about it? This is paper #100 at http://www.math.temple.edu/~wds/homepage/works.html and it is rather important at least in some eyes. You are warned that the meaning of "break" may not be quite what you expected... Dan Bernstein broke the AES cryptosystem if the attacker is allowed to get plaintext-ciphertext-time triples, and Bernstein's is a very real break in situations in which the attacker can get timing information. My break is nastier since it doesn't require any timing information, but it probably is of much less practical importance. But in a theoretical sense, to some eyes, it's devastating. The paper then discusses how to build cryptosystems immune to my, Bernstein's, and "differential" attacks simultaneously, proving a fundamental theorem that this is possible and in linear (i.e. optimal) time. [I thank Ron Rivest for some useful comments. Other cryptographers have also been notified but none of them provided any significant comments so far (June 2007). Also Markus Grassl checked a lot of my error correcting codes tabulated and provided a few of his own.]