(Folie 1)
hierzu bitte auch den zweiten Foliensatz ansehen, die den Beispiel-Chiffre beschreiben
Blockchiffren bestehen aus zwei allgemeinen Komponenten
Konkret werden diese realisiert durch
In unserem Beispiel-Chiffre haben wir dies zwar klein und anschaulich, aber doch als ein realitätsnahes Modell, wie heute moderne Chiffren arbeiten.
unsere Konfusion-Operation ist XOR (Exklusiv-ODER), dargestellt durch ein Plus mit Kreis (siehe Folie 1 untere Hälfte)
XOR hat die schöne Eigenschaft, dass ein weiteres Addieren die Operation rückgängig macht
(hier jetzt + ohne den umschließenden Kreis)
C = P + K
P = C + K, weil aus C=P+K sofort C+K=P+K+K folgt, aber K+K=0
das Mittel der Wahl ist eine Substitutionsbox oder kurz S-Box
eine Substitution ist eine Ersetzung
mathematisch ist eine Ersetzung eine bijektive Funktion S(), also wenn S(x)=y ist, dann wird x durch y ersetzt. Es kann auch eindeutig S^(-1)(y)=x bestimmt werden. Wenn die Funktion nicht injektiv wäre, gäbe es für S^(-1) mehrere Möglichkeiten, aber wir wollen ja eindeutig auf den ursprünglichen Klartext zurückschließen können.
eine beliebte Kombination dieser Vorgänge ist das Ausführen beider Techniken nacheinander in mehreren Runden. Wir nähern uns dieser Konstruktion nun langsam Schritt für Schritt und besprechen Cipher ONE, der genau einen Schritt dieser Art durchführt.
Cipher ONE hat einen Schlüssel von 8 Bits, der in zwei Teile k0 und k1 aufgeteilt werden kann und dieser ist auf Seite 1 im Handout beschrieben, bitte die S-Box beachten und die Beschreibung des Algorithmus für E(). Beachten Sie auch die Entschlüsselungsfunktion D(), die in umgekehrter Reihenfolge die Schritte rückgängig macht. Man sieht schon, wie sich das Konzept auf mehrere Runden verallgemeinern lässt.
Wir brauchen hierfür zwei Schlüsselteile, weil es mit einer Operation mit "+" beginnt und abschließt. Merken Sie sich diese Technik, mit dieser Operation zu beginnen ist eine gute Maßnahme, die Sicherheit eines Blockchiffre zu erhöhen Key Whitening.
Versuchen Sie den Algorithmus in Formeln auszudrücken, also wie entsteht der Chiffretext c, ohne das Handout des Smartboard-Anschriebs zu sehen.
c = (... irgendwas mit Nachricht m und der Funktion S ...)
Dann stellen Sie die Formeln nach m um
m = (... irgendwas mit Chiffretext c und der Umkehrfunktion S^(-1) ...)
Was Sie auf der rechten Seite von m sehen, ist der ALgorithmus zum Entschlüsseln
Und schauen Sie jetzt nochmal auf den Smartboard-Anschrieb, um Ihre Ausdrücke mit den dort beschriebenen zu vergleichen (untere Hälfte von Folie 1).
(zweiter Teil)
Diese Gleichungen lassen nun zwei Attacken zu:
Dies führt uns zu
[Folie 2]
Wir nehmen an, dass wir Plaintext-Ciphertext-Paare (kurz: PTCT) gegeben haben und daraus den Key berechnen wollen. Man nennt dies eine known-plaintext-attack. Dieser Fall ist in realen Anwendungen gar nicht so selten. Denken Sie an die immer gleichen Header von Office-Dateien, HTML-Dateien, XML-Dateien, SMTP-Mailheader usw...
Dadurch weiß man, dass der erste Teil der Nachricht der verschlüsselte Header ist.
Ein PTCT hat also vier Ausgangsdaten
Die beiden Gleichungen für m0 und m1 werden addiert und k0, ein Teil des Keys, fällt raus. Wir brauchen nur noch die 2^4 Möglichkeiten des Teilschlüssels k1 zu testen, bis wir die richtige Differenz gefunden haben. Mehrere Teilschlüssel können passen. Danach nutzen wir noch die Gleichung für u, um k0 auszurechnen, für jedes gefundene k1 gibt es ein gefundenes k0. Bei nur einem PTCT ist nicht klar, welcher Schlüssel (k0,k1) nun der richtige ist. Dieses prüft man einfach mit dem nächsten PTCT (m2,c2),(m3,c3).
Dadurch kann man die Schlüsselraumsuche in machbare Größenordnungen bringen.
[Folie 3]
Aus dem vorangegangenen Abschnitt ergibt sich der Grund, warum Designer eines Blockchiffre auf mehrere Runden setzen. Die Zusammenhänge setzen sich zwar genauso fort, aber der Angreifer weiß die zwischenzeitlichen Zustände nicht.
Schauen wir auf Cipher TWO (Seite 2 des zweiten Foliensatzes).
Mit Mitteln aus dem letzten Abschnitt können wir etwas über v und x herausfinden. Aber die notwendige Brücke zwischen beiden, nämlich w liegt völlig im Unklaren. Man kann dies auf dieser Folie [Folie 3 des Smartboard-Anschriebs] sehen. Außer .... es gibt noch einen weiteren Trick. Dieser wird im folgenden beschrieben.
Der Trick besteht darin, dass das anfängliche Addieren von k0 bei beiden Messages des PTCT herausfällt, sobald man die Differenz bildet. Es ist m0 + k0 + m1 + k0 wieder dasselbe wie vorher, nämlich m0 + m1. Aber wir brauchen die S-Box im ersten Schritt. Das führt von den echten Ergebnissen S(m0+k0) natürlich wieder weg. Aber wir können notieren, wie häufig eine Input-Differenz m0+m1 zu einer Output-Differenz c0+c1 führt. Wenn sich dort keine Unterschiede zeigen (sprich: statistisch ist alles gleichverteilt), dann lässt sich daraus nichts ableiten und die differentielle Kryptoanalyse kann abgebrochen werden. Ist aber für die Input-Differenz d=m0+m1 sehr häufig die gleiche Output-Differenz d'=c0+c1 sichtbar, dann kann man aus der Häufigkeit schließen, dass der richtige Teilschlüssel geraten wurde.
Der Pseudocode, um diese Differenzen zu zählen, steht auf der Folie. Dies ist das zentrale Hilfsmittel für alle Varianten der Technik der differentiellen Analyse.
(wir schreiben hexadezimale Zahlen nun wie in der Programmiersprache C beginnend mit 0x..., dadurch können wir in diesem 4-Bit-Blockchiffre einen Registerwert mit einer Hexziffer darstellen)
wir betrachten den Klartext m=0x7 der mit einem unbekannten Schlüssel k=(k0,k1,k2) zu c=0x1 verschlüsselt wird.
Wir haben folgende PTCT zur Verfügung (da wir hier alle Blocks aufzählen können, haben wir alle existierenden PTCT zur Verfügung, wir wählen natürlich die Eingangsdifferenz 0xf, d.h. die beiden PTs addiert ergeben 0xf.
PT CT PT CT 0 a f c 1 f e 3 2 0 d 6 3 e c 2 4 4 b 9 5 d a b 6 8 9 7 7 1 8 5 8 5 7 1 9 7 6 8 a b 5 d b 9 4 4 c 2 3 e d 6 2 0 e 3 1 f f c 0 a
Wir zählen die S^{-1}(c0+k2)+S^{-1}(c1+k2)$ diese sollten mit den Output-Differenzen d'=m0+m1=0xf übereinstimmen. Wenn es der falsche Key k2 ist, dann haben wir eine Gleichverteilung, d.h. Übereinstimmung in 2/16 aller Fälle. (Beachten Sie, 1/16 kann nicht vorkommen, weil m1+m2=m2+m1, d.h. einen Treffer gibt es immer mindestens zweimal.
Wir probieren das nun für verschiedene k2 aus und zählen folgende
Häufigkeiten.
count[00]= 0 count[08]= 4 count[01]= 2 count[09]= 2 count[02]= 0 count[0a]=10 count[03]= 0 count[0b]= 6 count[04]= 2 count[0c]= 2 count[05]= 4 count[0d]= 2 count[06]= 4 count[0e]= 0 count[07]=10 count[0f]= 0
Aus der DDT wissen wir: bei richtigem Key ist die Häufigkeit bei 10/16, dies liefert die Kandidaten k2=0x7 und k2=0xa.
Dadurch kann man die Runde mit k2 weglassen und wir sind bei cipher ONE angelangt.
Schließlich finden wir gültige Schlüssel, die m=0x7 in c=0x1 transformieren. Einer von diesen ist der verwendete Schlüssel k=0x53a.