AIDA, die Algebraische IV DifferentialAttacke
BIVIUM A/B und (792/1152)stel TRIVIUM gebrochen, wie weiter?
AIDA -die Algebraische IV DifferentialAttacke- bricht BIVIUM (A&B) in wenigen Minuten und errechnet einen TRIVIUM-Teilschlüssel bei einer reduzierten Setuplänge von 792 = 11/16*1152. Wir sehen uns an, was hinter AIDA steckt (DNF,ANF,IEP,RMT, d.h. Disjunktive und Algebraische Normalform, Ein/Ausschließungsprinzip, (Schnelle) Reed-Muller-Transformation), welche Ergebnisse bisher vorliegen und was AIDA für zukünftige Stromchiffren bedeutet. Die sogenannte "Cube attack" (Dinur/Shamir) von 2008 ist eine Whlg der AIDA-Idee (von 2007), in anderen Worten, ein Plagiat. Wer sich für die "cube attack" interessiert, kommt hier voll auf seine/ihre Kosten.
Jedes Bit einer Kryptofunktion $f$ (das vorletzte Bit von AES nach 7 Runden, die 793. Ausgabe der Stromchiffre TRIVIUM usw.) kann wie jede Boolesche Funktion in disjunktiver und algebraischer Normalform geschrieben werden, nämlich so:
$$ f = \bigvee{I\subset{1,\dots,n1}} \bigg(v_I^\land\ol v_{\ol I}^\land \land\big(\bigoplus{J\subset{1,\dots,n2}} d{I,J}kJ^\land\ol k_{\ol J}^\land\big)\bigg) = \bigoplus{I\subset{1,\dots,n1}} \bigg(v_I^\land \land\big(\bigoplus{J\subset{1,\dots,n2}} a{I,J}kJ^\land\big)\bigg),$$ wobei $f$ von den offenen Bits $v1,\dots,v{n1}$ (IV, Klartext) und den Schlüsselbits $k1,\dots, k_{n_2}$ abhängt.
Für Nicht-TeXies sieht f mit v1,v2,v3 und k1,k2,k3 als ANF etwa so aus:
f=1(a00+a01k1+a02k2+a03k1k2+a04k3+a05k1k3+a06k2k3+a07k1k2k3) +v1(a10+a11k1+a12k2+a13k1k2+a14k3+a15k1k3+a16k2k3+a17k1k2k3) +v2(a20...) +v1v2(a30...) +v3(a40...) +v1v3(a50...) +v2v3(a60...) +v1v2v3(a70...).
also 8*8 Koeffizienten a00 bis a77, die wir nicht kennen. Die aij sind entweder Null oder Eins, binär. Bei je 80 IV und Schlüsselbits gibt es 2^80 * 2^80 solche Zahlen.
Nehmen wir an, in einer Zeile, etwa die Zeile v1v2 mit a30..a37, wären alle Koeffizienten Null bis auf a34, also f= ...+ v1v2(k3) +..., wobei die ... alle weiteren Zeilen beschreiben. Wären wir in der Lage, die Zeilen einzeln auszuwerten, hätte diese Zeile mit v1=v2=1 den Wert k3, d.h. der Zeilenwert ist gleich einem Schlüsselbit!
AIDA: Wir können eine einzelne Zeile auswerten, indem wir die dort gegebenen IV-Bits, in unserem Beispiel v1 und v2, durch alle Möglichkeiten laufen lassen, also hier v1=0,v2=0 und v1=1,v2=0 und v1=0,v2=1 und v1=0,v2=1. Die Summe der 4 Ergebnisse des Kryptoalgorithmus an der gegebenen Stelle mit Funktion f ist dann direkt Schlüsselbit k3.
Bei "realen" Attacken reichen 2 IV-Bits nicht aus, wir liegen bei TRIVIUM inzwischen bei 36 aus den 80 möglichen Bits, haben also 2^36 Simulationen, deren Gesamtsumme ein Schlüsselbit ergibt.
Wie finden wir solche "einfachen" Zeilen in f? Salopp: Durch Rumprobieren, bis es klappt.
Warum hat dieses Nadel-im-Heuhaufen Problem Aussicht auf Erfolg? Weil wir durch Anwenden der Schnellen Reed-Muller-Transformation viele, viele Zeilen auf einmal untersuchen. Mit z.B. 2^40 Simulationen könnten wir 16 mal 2^36, also 16 Zeilen mit 36 IV Bits untersuchen. Wir können aber auch, mit demselben Aufwand, alle (40 36) (Binomialkoeffizient, Pascalsches Dreieck, also 4039*3837/123*4=91390 Zeilen gleichzeitig untersuchen, das ist 5700 mal besser als der Faktor 16 im Aufwand.
Was können wir bisher damit attackieren? a) BIVIUM A&B wird in 1 DualCore-Minute vollständig gebrochen. b) TRIVIUM hat eine Vorperiode von 1152 Schritten zum Mischen der IV und Schlüsselbits. Volles TRIVIUM ist wohl vor AIDA sicher. TRIVIUM mit 792 Mischungen (das sind 11/16 von 1152) kann angegriffen werden, da immer noch Schlüsselbits linear in einer ANF-Zeile sichtbar werden. Das ist die höchste bislang mögliche Vorperiode, die einen Angriff erlaubt.
Redner: Vielhaber
EventID: 3825
Event: SIGINT 2010 des Chaos Computer Club [CCC]
Ort: KOMED; Im Mediapark 7; 50670 Köln; Deutschland
Sprache: deutsch
Beginn: 23.05.2010 12:00:00 +02:00
Lizenz: CC-by-nc-sa
Loading...
![Das überwachte Netz [SIGINT10]](//s.ytimg.com/yt/img/pixel-vfl3z5WfW.gif)
57:03
Das überwachte Netz [SIGINT10]by CCCdeVideos304 views
Link to this comment:
All Comments (0)