O.J. Simpson Warren D. Smith
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).
*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:
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.
Example: a signal that is one 75% of the time and zero 25% has M=0.75 and U=0.5.
A "balanced" (50-50) signal has U=0; a constant bit has unbalance U=1.
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.")
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.
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.
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.
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
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,
A way to build a big (but secure) S-box.
2N input bits. K output bits (1≤K<N).
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.
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.
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.
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.)