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 AES256 keys from plaintextciphertext 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 errorcorrecting codes (BLECCs) associated with AES256. If $w < 43$ then our attack is faster than exhaustive key search; probably $w < 10$. (Also there should be ciphertextonly 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 thusencrypt $n$ bits with security $2^{cn}$, via an circuit $Q_n$ containing $\le c n$ twoinput logic gates and operating in $\le c \log n$ gatedelays, 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 plaintextciphertexttime 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.]
Metadata
 Available format(s)
 PDF PS
 Publication info
 Published elsewhere. The FIGURE (1 page PDF) is at http://www.math.temple.edu/~wds/homepage/LinGates.pdf
 Contact author(s)
 warren wds @ gmail com
 History
 20070620: received
 Short URL
 https://ia.cr/2007/248
 License

CC BY
BibTeX
@misc{cryptoeprint:2007/248, author = {Warren D. Smith}, title = {1. {AES} seems weak. 2. Linear time secure cryptography}, howpublished = {Cryptology {ePrint} Archive, Paper 2007/248}, year = {2007}, url = {https://eprint.iacr.org/2007/248} }