How I broke AES (Advanced Encryption Standard) if I did it

by   O.J. Simpson   Warren D. Smith    http://rangevoting.org/

The paper: http://math.temple.edu/~wds/homepage/works.html #100

We describe a new simple but more powerful form of linear cryptanalysis. It appears to break AES-256 (and undoubtably other cryptosystems too, e.g. SKIPJACK).

The fix: ("fundamental theorem of cryptography"?)

"Nonconstructive break" of AES?? What the heck is that?

*Asterisk: We do not prove, merely make plausible. Why? Proving security of cryptosystems will be impossible at least until can prove P≠NP. Proving crypto-breaking algorithms work also usually is not feasible:


History of DES & AES, brought to you by your government

My verdict: AES should be replaced. Does not live up to goals as cryptosystem suitable for all purposes. Bernstein/Smith's attacks devastate that goal in practice/theory. New approaches needed.


BLECCs = Binary Linear Error Correcting Codes (quick review)


About AES-256


Ingredients of our attack

  1. Matsui's idea: "linear cryptanalysis" (we re-build it, but M's idea)
  2. Combine with theory of BLECCs, introduce "code of the code" concept
  3. The weight w of the min-weight words in Code of the Code is crucial; attack's expected runtime depends exponentially on w
  4. Probabilistic analysis of w for the "worst" code of the code suggests sufficiently small w (highly probably) exists for AES.
  5. The "hint from God" you need to be able to break AES efficiently is: this BLECC (described by generator words) and some of its low weight words.

Linear Cryptanalysis simplified Matsui ingredients (blackboard-aid)


Linear Cryptanalysis Algorithm

  1. Write down the equivalent circuit of the cryptosystem.
  2. Replace all nonlinear S-boxes by "noise"+{best linear approx circuit}.
  3. Use "noise gate mobility" to slide all "noise gates" along wires until reach key-bit inputs.
  4. Use "reversibility" view plaintext & ciphertext bits as "inputs," key bits + "noise" as "outputs".
  5. From plaintext-ciphertext pairs, deduce linear relations (over GF2) satisfied by the Kn+Rn.
  6. Characteristic vectors of the linear equation LHSs generate "code of the code" BLECC by vector XORing. The min-weight binary vectors in this code (fewest #1s) correspond to the sparsest linear relations among the Kn+Rn.
  7. The sparsest relations involve the fewest number of "noise"-bits Rn.
  8. Use "piling-up lemma" & statistics: deduce sparse linear relations among the Kn by averaging out the noise using many plaintext-ciphertext pairs. (If #bits involved in relation=weight=w, noise-unbalance=U, then need order U-2w pairs to get high confidence.)
  9. Deduced enough GF2 linear relations among the key-bits Kn (using, perhaps, many different "codes of the code")? And they are lin-independent enough? Now deduce key itself by Gaussian elimination over GF2.
  10. Declare victory. Code is cracked we know the (extended) key.

"Code of the code," & Boolean "noise" that actually is deterministic

The "noise" bits Rn for good cryptosystems act random, but actually are deterministic (1 if linear approx circuit for Sbox got wrong value disagreeing with true Sbox's bit-value; 0 if got it right). Hence they can be canceled out in linear relations over GF2, by row operations. (I.e. R+R=0 is true if R is deterministic bit, would not have been true for repeated instances of genuine "noise.")

Some linear relations like
K1+R1  +  K3+R3  +  K7+R7            = 1    (weight=3)
           K3+R3  +  K7+R7  +  K9+R9 = 0    (weight=3)
imply by row-ops others such as
K1+R1  +                        K9+R9 = 1    (weight=2)
The left hand sides can be viewed as generator vectors
1 0 1 0 0 0 1 0 0              (weight=3)
0 0 1 0 0 0 1 0 1              (weight=3)
of a BLECC, and the min-weight word in the BLECC is
1 0 0 0 0 0 0 0 1              (weight=2)
For AES we get a [1920, 128, w] binary linear code. Different sets of lin-approximation circuits ⇒ different codes. The minimum distance w is crucial; governs runtime for crack.


Combining GF2-linear relations on key bits to deduce the key

Each plaintext-ciphertext pair yields 128 linear relations among key+noise bits using any given set of Sbox lin-approximation circuits. That's 128 generator words for a BLECC with 2128 codewords, each 1920 bits long. Some of those 2128 binary words hopefully have small weight, i.e. correspond to sparse linear relations involving few "noise bits." We need 1920 (or more) independent linear relations, with noise averaged out of each (and it is only feasibly-fast to average-out noise if lin-reln is sparse) to deduce entire 1920-bit expanded key.


What weight do we expect? Model as "random code." Other randomness assumptions.

Good news:

The crux (but this one is more dubious) conjecture:

If so: then (trivially since 24161>>>21920) tons of them will exist with tiny min-weights w, and their min-weight codewords will have tons of linear independence, and AES is dead meat.


Why is this a "nonconstructive" crack?

I do not know (but God does know) the "hint"

But if ever did know that hint, then I could, from then on, crack arbitrary AES instances by rapidly deducing expanded-keys from order 64w sample plaintext-ciphertext pairs.

And I would know the hint if I did a huge one-time pre-computation or if God told me or if I were the AES-designer and I'd started with this "trapdoor" knowledge and my knowledge then could be written down in at most a few Mbytes


Trapdoor?

A cryptosystem which is easy for its designers to break, but hard for everybody else, is said to have a "trapdoor."

If I give you a generator matrix for a BLECC, it can be very hard for you to know if the BLECC contains a low-weight word, or find it! (NP-hard!) But it would be very easy for me to give you that word, if I felt like revealing it. I.e. if the AES designers have a trapdoor,


How can we build cryptosystems immune to my (& Bernstein's...) nasty attacks? BLECC theory to the rescue!

A way to build a big (but secure) S-box.

2N input bits. K output bits (1≤K<N).

  1. Compute N "intermediate bits" by taking AND (or OR or NAND or NOR...) of disjoint input-bit pairs.
  2. Compute K GF2-linear combinations of these N bits according to the rows of KN Boolean generator matrix for [N,K,D] binary linear code.
  3. Output them.

Security Theorem:

  1. Totally immune to "differential cryptanalysis."
  2. Totally immune to Bernstein "timing attacks" since always same runtime regardless of data.
  3. Fast (can do with wordwide bitshifting, XORing, and ANDing, and ORing) if "cyclic" or "multicyclic" binary code. Also asymptotically fast if use "linear time information theory" BLECC constructions.
  4. Resistant (but not immune) to our "improved linear" cryptanalysis (here) since U<2-D for any linear-approximant to any linear combination of output bits.

Proof: Any nonconstant GF2-linear combo of output bits is a GF2-linear combo of the intermediate bits with weight≥D; every intermediate bit has unbalance=1/2 and all are independent; "piling up lemma" does rest.


"Fundamental theorem of cryptography"

There is an ∞family of polynomial(N)-time constructible logic-circuits QN, where QN encrypts 5N plaintext bits into 5N ciphertext bits, in O(N) bit-operations requiring O(logN) gate-delays, using a 46N-bit enlarged secret key, which achieves security level ≥22D where D>0.04N against all the attacks we've mentioned (and conjecturally we get security against all attacks for some appropriate values of the constants 5, 46, 0.04).

Proof employs the secure S-box above and "linear time info theory" (Justesen, Spielman, Zemor, Barg, etc). Argue even if attacker gets plaintext-ciphertext pairs that come with, as a free extra bonus, all the internal bits at the outputs of all Sboxes inside the encryptor, then still secure.


Is this practical? Sample design.

185749DE CF747EFF 4749F011 8BE9914C 0ADC7233
3B272FC6 EEB7F0FB 7604D328 59457C7E C54C7B2E
86905       (in hexadecimal)       

is the generator of a [511, 175, 95] cyclic (BCH) code. Extend it with overall parity check bit to get [512, 175, 96] code. That yields 1024-input, 175-output, Sbox with all unbalances≤2-96 and ≤8 gate delays between each input & output. (Fast in software too since program using wordwide shifts and XORs since cyclic code.) Use in 21 rounds, each round alters 175 message-bits and XORs with 1195 expanded-key-bits, to get cryptosystem for encrypting 1195 bits at once and presumed security level≥2192.


Other stuff (in the paper but not in this talk)



New (upcoming paper!) results by W.D. Smith

Have "universal" secret-key and public-key cryptosystems. These are provably as hard to crack (up to polynomial factors – also will work versus crackers equipped with "quantum computers") as any secret-key (or public-key) crytosystem. The basic idea to build the universal secret-key cryptosystem is you compose every secret-key cryptosystem with algorithm-length≤L. (Make L grow slowly with N.) The resulting function-composition "chain" is at least as strong as its "strongest link." (Warning: actually tougher than it just sounded to make this work, need to be careful on the definitions and the construction. But I've done it so it can be done.)