Hallo Steem-Welt,
heute geht es weiter mit den ersten Anwendungen von den Grundlagen der letzten beiden Posts.
Da der Bereich der Symmetrischen Kryptographie etwas größer ist, werde ich das Kapitel in mehrere Posts unterteilen.
Wer meine ersten Posts verpasst hat, kann diese hier nachlesen:
Teil 1 : Einleitung & klassische Kryptographie
Teil 2 : Modulare Arithme*tik
Symmetrische Kryptographie
Symmetrische Chiffren ermöglichen das Sicherheitsziel Confidentiality (Vertraulichkeit).
Stromchiffren
Bild: Stromchiffre synchron (& asynchron)
m - Klartext-Bits
c - Chiffrat-Bits
s - Schlüsselstrom (völlig zufällig generiert)
Asynchron dann, wenn s durch c beeinflusst wird
Definition 7: Stromchiffre
Eine Stromchiffre verschlüsselt Bits einzeln, dazu wird ein Schlüsselstrom (s0...sn) generiert,
der XOR mit dem Klartext verknüpft wird. (Bitweise Addition)
Bei synchronen Stromchiffren hängt der Schlüsselstrom nur von dem Schlüssel k ab.
Bei asynchronen Stormchifren zusätzlich von dem erzeugten Chiffrat.
Berechnung für mi, ci und si jeweils ∈{0,1}
Verschlüsselung: ci=encsi(mi) ≡ mi + si mod 2
Entschlüsselung: mi=decsi(ci) ≡ ci + si mod 2
Beispiel:
m = 0011 0011
k = 01 => si = 01010101
c = 0110 0110
0110 1111 0000 0101
0011 1010 0101 0000 58 80
Linear Feedback Shift Register
Bild: LSFR mit Grad 3
Funktion: Bausteine S1,S2,S0 sind FlipFlops, die einen Bit pro Takt "speichern" und nach rechts weitergegeben werden
Die Rückkopplung(Feedback) setzt sich aus dem Ausgabestrom der FlipFlops.
An S0 liegt der tatsächliche Schlüsselstrom
Definition 8: Linear Feedback Shift Register (LFSR)
Ein LFSR mit Grad m besteht aus:
- m getakteten Speicherbausteinen (Flipflops)
- Rückkopplungspfad
Mit jedem Takt wird ein Schlüsselstrombit si von dem LFSR generiert.
Beispiel: LFSR - Zustände der Flipflops und Output
Gegeben sind - p2 ist geschlossen (1)
- p1 ist offen (0)
- p0 ist geschlossen (1)
Berechnung zur Bestimmung des "überübernächsten" Bits am Eingang
s_i+3 ≡ 1 * s_i+2 + 0 * s_i+1 + 1*s_i mod 2
=> s_i+1 ≡ s_i+2 + s_i mod 2
Weiterhin gegeben sind Initialisierungswerte s2=1, s1=0, s0=1
Takt: FF2 FF1 FF0=s
0 1 0 1
1 0 1 0 Hinweis: FF2 wird zu FF1, FF1 wird zu FF0
2 0 0 1 FF2 wird durch XOR mit FF2 und FF0 des vorgängers gebildet
3 1 0 0
4 1 1 0
5 1 1 1
6 0 1 1
7 1 0 1
8 0 1 0
Definition 9: maximale Sequenzlänge
Die maximale Sequenzlänge eines LFSRs mit Grad m (Anzahl der Speicherbausteine) ist (2^m)-1.
Definition 10: Generelle Formel für Sequenz
Die generelle Forml für die Ausgabesequenz von LFSR mit Grad m:
Si + m ≡ ∑ pi * si+j mod 2 (von j=0, bis m-1)
mit si, pj ∈ {0,1}; ∀ i >= 0
Kryptoanalyse von LFSRs:
Geg: Grad m=3 des LFSR
2m Bits des Chiffrestroms si
Ges: Rückkopplungspfad p0, p1, p2
i=0: p2*s(-1) + p1*s(-2) + p0*s(-3) ≡ s0 mod 2
i=1: p2*s(0) + p1*s(-1) + p0*s(-2) ≡ s1 mod 2
i=2: p2*s(1) + p1*s(0) + p0*s(-1) ≡ s2 mod 2
i=3: p2*s(2) + p1*s(1) + p0*s(0) ≡ s3 mod 2
i=4: p2*s(3) + p1*s(2) + p0*s(1) ≡ s4 mod 2
i=5: p2*s(4) + p1*s(3) + p0*s(2) ≡ s5 mod 2
Dieses Gleichungssystem zeigt die Berechnungsvorschriften für das nächste Schlüsselstrombit , dass in den
ersten FlipFlop zurückgekoppelt wird, nicht die Ausgabe !
Die Ausgabe ist erst nach m+1 Schritten später sichtbar
Notwendige Bedingungen für eine maximale Sequenzlänge (2^m)-1
- Anzahl der Rückkopplungen (pi=1) ist gerade
- p0 = 1
Beispiel: Analyse LFSR mit Grad m=3
Gegeben: Grad m=3, 2m Ausgabestrom, si=(011100)
i=3 : p2*s2 + p1*s1 + p0*s0 ≡ s3 mod 2
i=4 : p2*s3 + p1*s2 + p0*s1 ≡ s4 mod 2
i=5 : p2*s4 + p1*s3 + p0*s2 ≡ s5 mod 2
=> (1) p2*1 + p1*1 + p0*0 ≡ 1 mod 2
(2) p2*1 + p1*1 + p0*1 ≡ 0 mod 2
(3) p2*0 + p1*1 + p0*1 ≡ 0 mod 2
<=> (1) p2 + p1 ≡ 1 mod 2
(2) p2 + p1 ≡ 0 mod 2
(3) p1 + p0 ≡ 0 mod 2
=> (1) + (2): p0 ≡ 1 mod 2
p0 -> (3): p1 ≡ 1 mod 2
p1 -> (2): p2 ≡ 0 mod 2
=> x³ + x + 1
Rivest Cipher 4 (RC4)
RC4 besteht aus 2 Algorithmen:
- Key scheduling algorithm (KSA)
Vorbereitung eines internen Feldes S[], in Abhängigkeit des Schlüssels
FOR i FROM 0 to 255
S[i]=i
END
j = 0
FOR i FROM 0 to 255
j = (j+S[i] + key[i mod keylength]) mod 255
SWAP(S[i], S[j])
END
- Pseudo-Random Generation Algorithm (PRGA)
Generieren von Schlüsselstrom X(jeweils ein Wort, Wortgröße W=8 bit)
i, j = 0
WHILE(Keystream required)
i = (i+1) mod 256
j=(j+S[i]) mod 256
SWAP(S[i],S[j])
X = S[S[i]+S[j] mod 256]
OUTPUT X
END
Die Ver- & Entschlüsselung geschieht durch XOR-Verknüpfung von Klartext (mi) mit dem Schlüsselstrom (Xi).
=> Ci = mi XOR Xi
Die Größe des Schlüsselraums von RC4(W=8Bit) ist die Anzahl der möglichen Permutationen von S[]:
256! ≂ 2¹⁶⁸⁴ ≂ 10⁵⁰⁷
Eine verbesserte Version, die die ersten 256 Output-bytes X verwirft, heißt Alleged RC4 (Arcfour)
Kryptoanalyse von RC4 am Beispiel von WEP
RC4 in WEP: C = RC4(iv||key) (m) ||: konkatenieren
Der initialisierungsvektor IV (24Bit) ändert sich mit jedem Paket und wird im Klartext übertragen: IV||C
Definition 13: Jenkins Krrelation
Robert J. Jenkins hat im Jahre 1996 folgende Beobachtung für S[ ] in der PRGA gemacht:
Pr(S[S[i]+S[j]]+S[j]=i) = 2/256
Die Wahrscheinlichkeit 2/256 ist doppelt so hoch, wie erwartet
Mit X(i-1) = S[S[i]+S[j] mod 256] wissen wir, dass
Pr(X(i-1)+S[j]=i)=2/256
<=> Pr(S[j]= i - X(i-1)) = 2/256
Definition 14:Angriff von Klein
Andreas Klein schlug 2005 folgenden Angriff auf WEP vor:
F(Key[0],...,Key[n-1], X(n-1)) = Key[n] = S⁻¹[n-X(n-1)-(S[n]+j(n-1) mod 256)]
S⁻¹ gibt Position im Array aus
Bekannt sind die ersten n Bytes des Schlüssels Key[], sodass die KSA bis zu dem Schritt n-1 simuliert werden können.
i(n) ≡ i(n-1) + 1 mod 256
=> i(n) ≡ n
j(n) ≡ j(n-1) + s[n] + key[n] mod 256
=> key[n] ≡ j(n) - (S[n] + j(n-1)) mod 256
j(n) fehlt für die Berechnung von key[n]. Mit Pr= 2/256 steht n-X(n-1) an Position j(n) in S[]
Wir suchen den Wert n-X(n-1) im Feld S(256+n)[] (Umkehrung der PRGA: Ŝ⁻¹[n-X(n-1)]).
Die Position (Index) ist dsa gesuchte j(n).
Wegen der geringen Wahrscheinlichkeit wird der Angriff auf viele WEP-Chiffrate durchgeführt und statistisch ausgewertet.
Beispiel:
WEP-Verschlüsselung mit key[0...7] = [12,111,28,107,226,211,232,247] und x2 = 251.
Gesucht ist key[3]
1. KSA Simulation
i0 = 0, j0 = 12 => Position 0 & 12 wird getauscht
i1 = 1, j1 = 124 => Position 1 & 124 wird getauscht
i2 = 2, j2 = 154 => Position 2 & 154 wird getauscht
i3 = 3, j3 = ?
2. Klein-Angriff (erfolgreich)
F(key[0],...,key[n-1], X(n-1)) = key[n] ≡ S⁻¹[n-X(n-1)] - (S[n]+j(n-1)) mod 256
=> F(12,111,28,251) = key[3] ≡ S⁻¹[3-X2]-(S[3]+j2)
≡ S⁻¹[3-251] -(3+154)
≡ S⁻¹[8] - 157 S⁻¹[8] ist NICHT IMMER =8 !!!
≡ 8-157
≡ 107 mod 256
Vielen Dank fürs Lesen! Wenn es euch gefallen hat, lasst mir gerne einen Vote und entsprechend Feedback da :)
Ausblick
Im nächsten Eintrag wird das Kapitel der symmetrischen Kryptographie dann fortgesetzt.