College Cryptografie Cursusjaar 2006 Moderne systemen
7 januari 2006
1
Blokgeheimschrift Data Encryption Algorithm Cryptoanalyse van DES Alternatieven voor DES Advanced Encryption Standard
ONDERWERPEN
2
• • • •
• •
n-bits→n-bits bijectieve afbeelding maximaal 2n! afbeeldingen mogelijk 64-bits blok, 56 bit sleutel: 256 264! herhaalde encryptie M → C → C 2 → · · · → C p = M fixed point E(M, K) = M antifixed point E(M, K) = M zwakke sleutel E(E(M, K), K) = M whitening M ⊕ Wk = M 0 → · · · → C 0 ⊕ Wk0 = C CBC = Cipher Block Chaining, IV = Initial Vector C0 = IV , Ci = E(Mi ⊕ Ci−1)
Blokgeheimschrift
3
E(M, K): L1, R1 = R0, L0 ⊕ F (R0, K1) L2, R2 = R1, L1 ⊕ F (R1, K2) L3, R3 = R2, L2 ⊕ F (R2, K3) D(C, K):
L2, R2 = R3, L3 ⊕ F (R3, K3) L1, R1 = R2, L2 ⊕ F (R2, K2) L0, R0 = R1, L1 ⊕ F (R1, K1)
Geen bijzondere eisen aan F Meer stappen i.h.a. meer veiligheid Gebalanceerd is # bits L = # bits R
Feistel geheimschrift
L0
R0 F (R0, K1)
R1
L1 F (R1, K2)
L2
R2 F (R2, K3)
R3
L3
4
1973 1975 1978 1980 1991 1993 1997 1998 1999
Initiatief National Bureau of Standards (nu NIST) IBM enige inzender voor DEA/DES Hearings US Senate Committee on Intelligence Hellman Time Memory Tradeoff partiële resultaten in de volgende jaren Biham en Shamir Differential Cryptanalysis Matsui Linear Cryptanalysis Software brute force NIST start ontwikkeling van AES Hardware brute force DES verlengd, waarschijnlijk voor het laatst
Data Encryption Algorithm
5
64 bit input
L0
R0
IP
L1 = R0
L0 ⊕ F (R0, K1)
56 bit sleutel
L2 = R1
L1 ⊕ F (R1, K2)
IP −1
L15 = R14
R15
64 bit output
L16
R16
hoofdschema
Schematisch overzicht
transformatie
6
Ri 32 bits
K 56 bits
48 bits
48 bits
S1 S2 S3 S4 S5 S6 S7 S8
S00 S01 S11 S10
P 32 bits
Complementariteitseigenschap: DES(M, K) = DES(M, K)
Transformatie functie
7
64 bits
•
drop pariteitsbits 64→56
56 bits
•
rotaties 1122222212222221
•
4 zwakke sleutels (00. . . ) (11. . . ) M = E(E(M, K), K)
•
12 halfzwakke sleutels (0101. . . ) (1010. . . ) M = E(E(M, K 0), K)
28 bits
28 bits
ROL
ROL
ROL
2x24 bits K1
2x24 bits K2
ROL
Sleutelschema
8
• • •
56 bit DES niet veilig genoeg meer 2x DES is E(E(M, K1), K2) niet equivalent 112 bits maar slechts 57 bits wegens "meet in the middle" aanval 3X DES is E(D(E(M, K1), K2), K3) EDE-schema Triple DES standaard Drie mogelijkheden: 1. K1 ≠ K2 ≠ K3 2. K1 = K3 ≠ K2 3. K1 = K2 = K3 "DES compatibility mode"
Triple DES
9
Onderwerpen
• • •
• • •
DES controverse Uitputtend zoeken Fysische methoden foutinjectie tijdsduur van operaties analyse van stroomverbruik Time Memory Tradeoff Differentiële cryptoanalyse Lineaire cryptoanalyse
Cryptoanalyse van DES
10
• • • •
National Security Agency (NSA) betrokken bij ontwikkeling Lucifer 128 bits vs. DES 56 bits: verzwakt door NSA? is 16 ronden te weinig? S-doos structuur: valluik ingebouwd? ontwikkelcriteria geheim: verdacht? veel later blijkt: vanwege differentiële cryptoanalyse
•
US Senate Committee on Intelligence (1978) concludeert: DES is more than adequate for its intended applications; IBM invented and designed DES; NSA did not tamper with the design; NSA certified DES free of known statistical/mathematical weakness.
DES controverse
11
•
• •
hardware 1984 256.000 encrypties sec−1 1998 Deep Crack machine, US$ 250.000 2.500.000 sec−1, 37.050 chips parallel, 9 dagen max software 1997 Rocke Verser start internet programma 78.000 deelnemers, 14.000 machines, 18 feb – 17 juni sleutelherkenning ?
DES −1(C, K) = M: door [azAZ09.,?!] 70 uit 256 plausibel DES-UD ≈ 16 bytes, (70/256)16 × 256 ≈ 70.000.000 vals alarm known plaintext, UD ≈ 8 bytes, ≈ 216 vals alarm
Uitputtend zoeken
12
DES vercijfering
DPA = Differential Power Analysis metingen middelen en vergelijken referentiewaarde: sleutelbits
Stroomverbruik analyseren
13
M K1
E(M, K1) C1
C, i = n
M K11
M
E(M, C1) C2
C in tabel?
K1n
E(M, Cn) E1
Cn
Nee
C ← E(M, C), i ← i − 1
K = E i−1(M, K)
Time Memory Tradeoff
14
1991 Biham en Shamir (chosen plaintext) kies pt: C = E(M, K) en C ∗ = E(M ∗, K) met ∆M = M ⊕ M ∗ ∗ ∗ per ronde: (Ri−1 ⊕ Ki ) ⊕ (Ri−1 ⊕ Ki ) = Ri−1 ⊕ Ri−1 = ∆R ∗ onderzoek per S-doos combinaties (Ri−1, Ri−1 ) met ∆R = const Voorbeeld DES 1e substitutie van S1: ∆in = 10002
(A, 2)(2, A) (6, E)(E, 6)
S1
→
∆uit = 10112
(6, D)(D, 6) (B, 0)(0, B)
in
omgekeerd: (∆in, ∆uit ) = (8, B) → (2, A)(A, 2)(6, E)(E, 6)
Differentiële cryptoanalyse
15
L1 ⊕ f {z (R1, K2)} ⊕ f (R3, K4) B.v. 4-stap Feistel: L4, R4 = R3, | L3 =R2
∗ f (R , K ) ⊕ f (R , K2) 1 2 1 ∗ 0 {z } ⊕ R0 | ∆ = f (R3, K4) ⊕ f (R3 , K4) = L1 ⊕ 4
uit speciale ∆M
De speciale ∆M heet een karakteristiek. Invoerverschil wordt over meerdere mogelijkheden verdeeld, dus per M slechts kans op gewenst verschil. Dan ook "bingo!" Voor DES p ≤ 14/64 per S-doos, karakteristiek 1960000016 op 3 dozen heeft p = 0.004274, na 13 ronden p ≈ 2−47. Plus wat andere trucs → iets beter dan uitputtend zoeken.
Karakteristieke verschillen
16
• • • • • • •
Precies genoeg (16) ronden gegeven beste karakteristiek. Permutatie na S-dozen blijkbaar zo gekozen dat kans op goede karakteristieken minimaal. Volgorde S-dozen bijna optimaal, met b.v. . . . S1S7S4 . . . karakteristiek met p = 2−43 over 15 ronden. Substituties in S-dozen optimaal. Geen 4 substituties per S-doos verzwakt aanzienlijk. Eerst R ⊕ Ki en dan 32 → 48 verzwakt. Onafhankelijke subsleutels verbetert nauwelijks.
Conclusie: DES optimaal tegen differentiële cryptoanalyse. Bevestiging door Coppersmith (lid IBM’s DES-team).
Resultaten
17
1993 Matsui (known plaintext) M[m1, m2, . . .] ⊕ C[c1, c2, . . .] = K[k1, k2, . . .] met kans p ~M · M ~ (X ~M bit selector voor M) M[m1, m2, . . .] = X Itereerbare karakteristiek-combinatie van Matsui: R[15] ⊕ F (R, K)[7, 18, 24] = K[22]
p = 42/64
R[29] ⊕ F (R, K)[15] = K[44]
p = 30/64
R[15] ⊕ F (R, K)[7, 18, 24, 29] = K[22]
p = 12/64
Totaal p = 0, 5 + 1, 19 × 2−22 → ±247 paren pt-ct nodig.
Lineaire cryptoanalyse
18
• • • • • • • • • •
newDES (Scott, 1985) (geen variant van DES) Feal (Shimizu en Miyaguchi, NTT Japan, 1987) IDEA (Lai en Massey, ETH Zürich, 1990) LOKI (Brown, Pieprzyk, Seberry, Australië, 1990) Skipjack (NSA, 1985–1990) escrowed encryption standard GOST (Gosudarstvennyi Standard Soyuza SSR, USSR) Blowfish (Schneier, Counterpane Inc, 1994) RC5 (Rivest, RSA Laboratories, 1994) TEA (Wheeler en Needham, Univ. Cambridge, 1994) enzovoorts, enzovoorts
Alternatieven voor DES
19
Lai en Massey, ETH Zürich (1990)
IDEA
•
Blok=64 bits, K=128 bits, R8+
•
⊕, ê mod 216, mod (216 + 1)
•
16 bit units – 16 bit processoren
•
cryptoanalyse tot 4–5 rondes
•
Daemen (1993) groepen met 223, 251, 263 zwakke sleutels
20
w1
G
w2
w3
w4
g-hoog
g-laag ki
F A 64 bits, 80 bit sleutel init-8xA-8xB-8xA-8xB
teller
ki+1
B
w1
G
ki+2
F w2
w3
w4 teller
Declassificatie door NSA 1998
Skipjack
F
ki+3
F 4x G-functie
21
A
B S[0]
S[i+1]
RC5
S[1]
Rivest, RSA Laboratories (1994)
•
Afgebeeld is een halve ronde
•
RC5-w/r/b parametrisatie: blok 2w, 12 rondes, 16 byte sleutel
•
ê/ë = plus/minus mod22w
•
/ = data afhankelijke rotaties
•
K = [0 . . . b − 1] → S[0 . . . 2r + 1]
22
NIST oproep voor AES 12 sept 1997, programma van eisen:
• • • • •
ongeclassificeerde, publiekelijk bekende algoritme overal en zonder royalties beschikbaar symmetrisch 128 bits blokgeheimschrift sleutel 128, 192, 256 bits naar keuze gebruiker efficiënt te implementeren (smartcard b.v.)
Start finale 15 april 1999 met MARS (IBM, Coppersmith), RC6 (RSA Labs, Rivest), RIJNDAEL (Daemen, Rijmen), SERPENT (Anderson, Knudsen, Biham), Twofish (Schneier e.a.) 2 okt 2000 RIJNDAEL winnaar
Advanced Encryption Standard
23
• • • • •
voorloper is het SQUARE geheimschrift geen Feistel geheimschrift maar inverteerbaar door de gekozen (algebraïsche) operaties blok/sleutel naar keuze 128/192/256 bits whitening-stap voorafgaand aan vercijferrondes 10/12/14 rondes met elk 4 fasen: ByteSub ShiftRow MixColumn AddRoundKey
Rijndael
24
b0 b4 b8 b12
b0 b4 b8 b12
b0 b4 b8 b12
b1 b5 b9 b13
b1 b5 b9 b13
b1 b5 b9 b13
b2 b6 b10 b14
b2 b6 b10 b14
b2 b6 b10 b14
b3 b7 b11 b15
b3 b7 b11 b15
b3 b7 b11 b15
ByteSub
ShiftRow
MixColumn
AddRoundKey: bi0 = bi ⊕ ki,r
Rijndaelschema
r = 1, . . . , 10/12/14
25
•
byte B = (abcdef gh) in GF (28) is ax 7 + bx 6 + cx 5 + dx 4 + ex 3 + f x 2 + gx + h
a, . . . ∈ {0, 1}
•
B1 + B2 = (a1 + a2 mod 2)x 7 + (b1 + b2 mod 2)x 6 . . .
•
B1 × B2 = (a1x 7 + . . .)(a2x 7 + . . .) mod (x 8 + x 4 + x 3 + x + 1)
•
ByteSub operatie uit twee stappen opgebouwd: (1) inverse B → B −1 en (2) lineaire transformatie M· B + C
•
praktisch: implementeer tabel S[B=0–255] voor ByteSub
ByteSub
26
• • •
kolommen zijn vectoren (b0, b1, b2, b3) etc. kolomvector als polynoom b0x 3 + b1x 2 + b2x + b3 etc. vermenigvuldig met f = (3x 3 + x 2 + x + 2) mod (x 4 + 1) praktisch: vermenigvuldig met (circulant) matrix 02 b00 0 b1 01 = b0 01 2 b30 03
•
03 02 01 01
01 03 02 01
01 b0 01 b1 03 b2 02 b3
voor inverse f −1 = (11x 3 + 13x 2 + 9x + 14) mod (x 4 + 1)
MixColumn
27
•
128 bits en white + 10 rondes → 1408 subsleutel bytes
•
kettingberekening maakt "on the fly" generatie mogelijk
•
steeds 4 byte woord wi = wi−1 ⊕ wvor ige
•
per ronde aanvullende rotatie met ByteSub substitutie en combinatie met rondeteller
•
extra bewerkingen bij 256 bit sleutel
AddRoundKey
r onde
28
