AIDA, die Algebraische IV DifferentialAttacke

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.

Hardware (GPUs, FPGAs): AIDA läßt sich einfach auf GPUs und FPGAs umschreiben. Bis Mai werden zu GPUs erste Ergebnisse vorliegen (CUDA, OpenCL).

Und dann doch noch etwas Mathe: Die Disjunktive Normalform sieht so aus:

$$ f = \bigvee{I\subset{1,\dots,n1}} (v_I^\land\ol v_{\ol I}^\land \land(\bigoplus{J\subset{1,\dots,n2}} d{I,J}kJ^\land\ol k_{\ol J}^\land)),$$ wobei $\lor,\land,\oplus$ die logiscehn Operationen ODER, UND und XOR sind. $vI^\land =\land{i\in I} v_i$ und $\overline k{\ol J}^\land =\land{j\in {1,\dots,n_2}\backslash J}\ol kj, kj=1-k_j$. $d{I,J},a{I,J}\in \ff_2$ schließen den Term aus (falls 0) oder ein (falls 1).

Unser Beispiel mit ni := 1-vi, xi := 1-ki, die negierten IV und Schlüsselbits: f =n1n2n3(d00x1x2x3+d01k1x2x3+d02x1k2x3+d03k1k2x3+d04x1x2k3+d05k1x2k3+d06x1k2k3+d07k1k2k3) +v1n2n3(d10x1x2x3+d11k1x2x3+d12x1k2x3+d13k1k2x3+d14x1x2k3+d15k1x2k3+d16x1k2k3+d17k1k2k3) +n1v2n3(d20...) +v1v2n3(d30...) +n1n2v3(d40...) +v1n2v3(d50...) +n1v2v3(d60...) +v1v2v3(d70...). m.a.W.: die Koeffizienten heißen jetzt dij statt aij und alle Variablen von v1 bis k3 kommen überall vor, entweder direkt oder negiert.

Jeder Koeffizient dij läßt sich direkt mit einer einzigen Simulation bestimmen, indem nämlich alle Bits so gesetzt werden, wie sie bei dij auftreten: ki,vi=1, ni,xi als Null. Beispiel: d14 steht bei dem Term v1n2n3 d14 x1x2k3 und ergibt sich durch Simulation mit v1=1, v2=v3=0, k1=k2=0,k3=1.

AIDA nutzt nun das Ein-/Ausschließungsprinzip, es gilt $a{I,J}=\oplus{M\subset I} d_{I,J}$, d.h. alle bei aij vorhandenen IV Bits laufen durch alle Wertekombinationen, die Summe der entsprechenden dmj (der Simulationen) ist dann aij.

Wenn erstmal viele lineare Zeilen (mit einem oder mehreren Schlüsselbits, aber alles linear) vorleigen, kann per Gauss das lineare Gleichungssystem gelöst werden und die Chiffre ist gebrochen.

AIDA [2] wurde ein Jahr später von Dinur und Shamir [1] "neu erfunden" und dann "cube attack" genannt, ein klares Plagiat.

Ergebnisse:

1. AIDA attackiert erfolgreich TRIVIUM mit reduziertem Vorlauf von 792 [4]. Lineares AIDA wird TRIVIUM mit voller Vorlauflänge 1152 aber nicht brechen [3].

2. AIDA bricht BIVIUM-A und -B vollständig in wenigen Minuten [5]. SAC-Solver und ähnliche bisherige Attacken brauchen Stunden oder Tage dafür.

3. Die Schnelle Reed-Muller Transformierte beschleunigt AIDA um einen Faktor von etwa 5000 [3].

4. Das "Wellenfrontmodell" [3] als Linearitätstest benötigt nur noch d+13 Simulationen für d IV-Variablen (z.B. d=3 im Beispiel, d=36 gegen TRIVIUM-792), währed der BLR -Test [1] 3(d+1)+1 Simulationen braucht.

5. Algebraische Normalformen können mithildfe der Schnellen Reed-Muller-T. in Nlog(N) statt N*N Schritten erechnet werden, mit N=2^n, n=Anzahl der Variablen [3].

Literatur:

1. I.Dinur, A.Shamir, Cube attacks on tweakable black box polynomials eprint.iacr.org/2008/385

2. M. Vielhaber, Breaking One.Fivium by AIDA an Algebraic IV Differential Attack eprint.iacr.org/2007/413

3. M.Vielhaber, Speeding up AIDA, the Algebraic IV Differential Attack, by the Fast Reed-Muller Transform Proc.~ISKE 2009, Heerlen, Belgium.

4. M. Vielhaber, AIDA vs. TRIVIUM 793:1152, Final Score 980:1152 Eurocrypt 2009, http://eurocrypt2009rump.cr.yp.to

5. M.~Vielhaber, AIDA breaks BIVIUM (A\& B) in 1 DualCoreMinute Crypto 2009, http://rump2009.cr.yp.to

und www.hs-bremerhaven.de/Michael_Vielhaber.html