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
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.]
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
- 2007-06-20: 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} }