Der E2-Algorithmus

E2 – der "Efficient Encryption" Algorithmus -- ist eine symmetrische Blockchiffre, die von Nippon Telegraph und Telephone Corporation (NTT) entwickelt wurde als Kandidat für den Advanced Encryption Standard. Die Entwickler des Algorithmus – Kazumaro Aoki, Masayuki Kanda, Tsutomu Matsumoto, Shiho Moriai, Kazuo Ohta, Miyako Ookubo, Youichi Takashima und Hiroki Ueda – haben sich die folgende Ziele gesetzt:

· E2 sollte resistent sein gegen

o Brute-Force-Angriffen,

o Differentielle Kryptoanalyse,

o Lineare Kryptoanalyse,

o Higher-Order Differential Attack

o Interpolation Attack

o Partitioning Attack und

o Related-Key Attack.

· Die Geschwindigkeit der Verschlüsselung und Entschlüsselung von E2 sollte schneller sein als die des Single-DES.

E2 ver- und entschlüsselt 128-bit Daten mit Schlüsselgrößen von 128-, 192- und 256-bit. Der Algorithmus besteht aus einem Datenrandomisierungsteil und einem Schlüsselgenerator-Teil.

Die Datenrandomisierung wird in einer Feistel-Chiffre-Struktur realisiert mittels einer 12-rundige Wiederholung der F-Funktion, einer initialen Transformation (IT-Funktion) und einer finalen Transformation (FT-Funktion). Schlüsselgeneration wird erreicht durch eine 9-rundige Wiederholung der G-Funktion.

Die Entwickler waren der Meinung, dass schon eine 9-rundige Wiederholung der F-Funktion genug Sicherheit bieten würde gegen Brute-Force-Angriffe, differentielle/lineare Kryptoanalyse, higher order differential attack und interpolation attack, aber haben eine zusätzliche Steigerung der Sicherheit erhofft durch hinzufügen der komplizierten IT- und FT-Funktionen und Erhöhung der Runden von 9 auf 12. Sie behaupteten, dass es keine verkürzte Angriffsmöglichkeiten auf den Algorithmus gäbe und dass E2 nur für eine Brute-Force-Angriff anfällig wäre. E2 soll also mit einem 192- bzw. 256-bit Schlüssel sicherer sein als Triple-DES.

Deren ANSI C Implementierung von E2 erreichte schon 30M-bits-pro-Sekunde auf einem Pentium Pro (200 MHz), während eine typische Implementierung in C von DES erreichte nur 28M-bits-pro-Sekunde auf einem DEC Alpha 8400 (300 MHz).

Nach einer Beschreibung des E2-Algorithmus, werden die Ergebnisse einer Analyse des Algorithmus durch NIST vorgeführt. Schließlich wird eine Einführung in die Problematik von Brute-Force-Angriffen versucht.

2 Der E2-Algorithmus

Die globale Struktur des Algorithmus basiert auf die Feistel-Chiffre, aufgrund ihrer Bekanntheit und stetiges Widerstand gegen Angriffe und wegen ihrer Symmetrie (das Verfahren zum Ver- und Entschlüsseln ist dasselbe).

Zunächst wird das Verfahren zum Ver- und Entschlüsseln behandelt, danach die Schlüsselgeneration (engl. key scheduling) und letztlich die durch den Algorithmus benutzte Funktionen werden erläutert.

2.1 Bemerkung zur Notation

B sei ein Vektorraum, der aus 8-bit (1 Byte) Elementen besteht.

D.h. B := GF(2)⁸

W sei ein Vektorraum, der aus 32-bit (1 Wort) Elementen besteht.

D.h. W := B⁴

H sei ein Vektorraum, der aus 64-bit (1 halber Block) Elementen besteht.

D.h. H := B⁸

M sei der Klartext, M Î H².

C sei der Kryptotext, C Î H².

K sei der Schlüssel, K Î H². H³ bzw. H⁴.

k sei der Rundenschlüssel, k Î H².

2.2 Verschlüsselung

Zuerst erzeugt der Schlüsselgenerator 16 Rundenschlüssel (engl. subkeys) {k₁,k₂,...,k₁₆} (k_i Î B¹⁶) aus einem Geheimschlüssel K. Datenrandomisierung wird erreicht durch eine initiale Transformation IT, eine 12-Runden Feistel-Chiffre mit F-Funktion und eine finale Transformation FT.

M' wird wie folgt berechnet, wobei M der Klartext ist:

M' = IT(M,k₁₃,k₁₄)

M' wird in L₀ und R₀aufgeteilt, d.h. M' = (L₀,R₀), wobei L₀,R₀ Î H. Für r = 1 bis 12 wird wie folgt weiter berechnet:

R_r = L_r-₁ Å F(R_r-₁, k_r)

L_r = R_r-₁

Sei C' die Verkettung von R₁₂ und L₁₂, d.h. C' = (R₁₂,L₁₂). Der Kryptotext wird schließlich durch

C = FT(C', k₁₆, k₁₅)

berechnet.

2.3 Entschlüsselung

Zuerst werden 16 Rundenschlüssel erzeugt. Die Datenrandomisierung wird durch eine initiale Transformation IT, gefolgt von einer 12-Runden Feistel-Chiffre mit F-Funktion und eine finale Transformation FT erreicht.

Sei C der Kryptotext.

C' = IT(C,k₁₆,k₁₅)

C' wird aufgeteilt in (R₁₂,L₁₂). Für r = 12 bis 1 wird wie folgt weiter berechnet:

L_r-₁ = R_r Å F(L_r,k_r)

R_r-₁ = L_r

Sei M' die Verkettung von L₀ und R₀, d.h. M' = (L₀,R₀). Der Klartext M wird schließlich durch

M = FT(M',k₁₃,k₁₄)

berechnet.

Abbildung 1: Ver- und Entschlüsselung

2.4 Der Schlüsselgenerator

Aus einem Geheimschlüssel K = (K₁,K₂,K₃,K₄), wobei K_i Î H, i = 1,...,4, werden 16 Rundenschlüssel wie folgt erzeugt:

v_-1 = 0123456789abcdef_(hex)

(L₀,(Y₀,v₀)) = G(K,v_-1)

(L_i₊₁,(Y_i₊₁,v_i+1)) = G(Y_i,v_i) (i = 0,1,...,7)

(l_4i,l_4i+1,l_4i+2,l_4i+3) = L_i₊₁ (i = 0,1,...,7)

(t_i⁽⁰⁾,t_i⁽¹⁾,...,t_i⁽⁷⁾) = l_i(i = 0,1,...,31)

(i = 0,1,...,15)

wobei L_i, Y_i Î H⁴, l_i,v_i Î H und t_i^(j) Î B.

Für 128-bit Geheimschlüssel werden K₃ und K₄ auf konstante Werte wie folgt gesetzt:

K₃ = S(S(S(v_-1)))

K₄ = S(K₃)

Für 192-bit Geheimschlüssel wird nur K₄ = S(S(S(S(v_-1)))) gesetzt.

2.5 Die IT-Funktion

Die initiale Transformation wird wie folgt definiert:

IT: H² ´ H² ´ H² ® H²

(X,A,B) BP((XÅA) ÄB)

Der Binäroperator Ä ist definiert als

Y = XÄB, mit X,Y,BÎ H²

wobei

und BP ist eine Byte-Permutation BP: W⁴ ® W⁴.

2.6 Die F-Funktion

Wird wie folgt definiert:

F: H ´ H² ® H

(X,(K⁽¹⁾,K⁽²⁾))Y = BRL(S(P(S(X Å K⁽¹⁾)) Å K⁽²⁾))

Abbildung 2: Die F-Funktion

2.7 Die FT-Funktion

Die finale Transformation ist die Inverse der IT-Funktion, d.h.

X = FT(IT(X,A,B),A,B)

2.8 Die BRL-Funktion

Die Byte-Rotate-Left-Funktion wird wie folgt definiert:

BRL: H ® H

(b₁, b₂,...,b₈) (b₂,..., b₈, b₁)

2.9 Die S-Funktion

Die S-Funktion ist Teil der F-Funktion und wird mittels s-Boxen definiert:

S: H ® H

(x₁, x₂,...,x₈) (s(x₁), s(x₂),...,s(x₈))

2.10 Die s-Boxen

Die s-Funktion wird wie folgt definiert:

s: B ® B

x Affine(Power(x,127),97,225)

wobei

Power(x,e) = x^e in GF(2⁸)

Affine(y,a,b) = ay + b (mod 2⁸)

2.11 Die P-Funktion

Die P-Funktion ist Teil der F-Funktion und wird mittels einer Matrizengleichung definiert:

P: H ® H

wobei die Matrix P wie folgt gegeben ist:

Diese Matrix kann auch mittels der folgenden Formel berechnet werden:

wobei t_ij das Element der i-ten Reihe und j-ten Spalte in der Matrix P.

2.12 Die G-Funktion

Die G-Funktion ist Teil des Schlüsselgenerators und wird wie folgt definiert:

G: H⁴ ´ H ® H⁴ ´ (H⁴ ´ H)

((X₁, X₂, X₃, X₄),U₀) ((U₁, U₂, U₃, U₄),( Y₁, Y₂, Y₃, Y₄),V)

wobei

Y_i = f(X_i) (i = 1,2,3,4)

U_i = f(U_i_-1) ÅY_i (i = 1,2,3,4)

V = U₄

Abbildung 3: Die G-Funktion

2.13 Die f-Funktion

Die f-Funktion ist Teil der G-Funktion und wird wie folgt definiert:

f : H ® H

X P(S(X))

3 NIST-Evaluierung des E2-Algorithmus

Obwohl die Evaluierung des NIST (National Institute of Standards and Technology) keine gravierende Sicherheitsmangel bei E2 feststellen könnte, wurde der Algorithmus nicht in der zweiten Runde des AES-Wettbewerbs aufgenommen. Die Gründe hierfür waren

seine Langsamkeit im Vergleich zu Rijndael und Twofish,
ein fehlender on-the-fly Schlüsselgenerator, der eine Implementierung auf low-end Smart-Cards ausschliest und
ein hoher Bedarf an ROM.

Die Beurteilung wird unten weiter erläutert.

3.1 32-bit-Leistung

Da nur einfache RISC-Operationen benutzt wurden, sollte die Leistung des Algorithmus ziemlich gleich sein über verschiedener Prozessortypen. Die Geschwindigkeit wurde als angemessen eingestuft mit 410 clocks per block in Assembler-Sprache (E2 war damit die 4. schnellste auf dem Pentium und die 6. schnellste auf dem Pentium Pro/II) und eine einheitliche Leistung über verschiedene 32-bit CPUs.

3.2 Smart-Card-Leistung

Das Erzeugen von Rundenschlüssel on-the-fly wurde explizit durch die Entwickler des E2-Algorithmus ausgeschlossen (da sie es als ein Sicherheitsrisiko einschätzten) und daher benötigte die Rundenschlüssel 256 Bytes von RAM. Insgesamt braucht der Algorithmus also ungefähr 300 Bytes von RAM, was der Größteil der herkömmlichen Smart-Card-CPUs ausschließt. Daher wäre E2 nicht akzeptabel als ein vebreiteter Smart-Card-Standard. NIST schätzte, dass der Code und die Tabellen in weniger als 2K von ROM reinpassen sollte.

3.3 Hardware-Leistung

Die Hardware-Implementierung von E2 ist aufwendig: eine parallel Version benötigt sechszehn 256-Byte ROMs. Multiplikation wird nur in den initialen und finalen Transofrmationen gebraucht, aber dafür muss ein komkpletter Multiplikationsschaltkreis eingebaut werden, der aber nur wenig benutzt wird. Die NIST-Untersucher waren der Meinung, dass Hardware-Überlegungen nicht von höchster Wichtigkeit für die E2-Entwickler waren. Die für die Speicherung der Rundenschlüssel benötigte 256 Bytes von RAM führte auch zu einer Vergrößerung der Hardware.

4 Brute-Force-Angriffe

Es werden viele Metriken benutzt und Abschätzungen gemacht um heraus zu stellen, wie sicher ein Algorithmus tatsächlich ist. Gerade wegen der Komplexität dieser Algorithmen, sind diese Abschätzungen (z.B. bezüglich des Linear Differential Attack, Higher Order Attack, usw.) oft sehr subjektiv. Aber eine Angriffsmöglichkeit besteht immer: die des Brute-Force-Angriffs. Die Debatte um Brute-Force-Angriffe zentriert auf dem DES-Algorithmus [Schneier1996] und dies ist wiederum interessant für den E2-Algorithmus, da die Entwickler den Algorithmus selber in der Kategorie von DES klassifizieren (aufgrund seiner Feistel-Chiffre-Struktur).

In diesem Abschnitt wird der Brute-Force-Angriff näher untersucht und einige interessante Ideen von Bruce Schneier vorgestellt.

4.1 Prinzipien eines Brute-Force-Angriffs

Typischerweise ist ein Brute-Force-Angriff ein known-plaintext Angriff: d.h. es wird ein (Ausschnitt des) Kryptotexts und des dazugehörenden Klartexts benötigt. Weiterhin beeinflüssen zwei Parameter die Geschwindigkeit eines Brute-Force-Angriffs:

1. Die Anzahl der zu untersuchenden Schlüssel.

2. Die Geschwindigkeit, mit der jeden Schlüssel untersucht wird.

Obwohl die Schlüssel eines bestimmten Algorithmus vielleicht 10-mal schneller getestet werden können als die eines anderen, kann dieser Faktor ignoriert werden, da wir uns im Bereich von extrem grossen Zahlen bewegen.

4.2 Hardware-Brute-Force-Angriff

Ein Brute-Force-Angriff kann optimal in Hardware implementiert werden, besonders wenn parallele Prozessoren eingesetzt werden, da jeder Prozessor eine Untermenge des Schlüsselraums untersuchen kann. In 1994 untersuchte Michael Wiener wie teuer es wäre, spezialisierte Hardware für einen Brute-Force-Angriff zusammen zu stellen. Er entwarf spezialisierte Prozessoren, Platinen und Gehäuse (engl. racks) für einen Angriff auf DES. Wiener schätzte, dass man für US $ 1 Million ein Gerät zusammenbauen könnte, das einen 56-bit DES-Schlüssel in durchschnittlich 3,5 Stunden (maximal 7 Stunden) knacken könnte. Und der Preis/Geschwindigkeit-Verhältnis ist linear. Mit einkalkulieren von Moore's Law ist die unten angegebene Tabelle 1 schon eine konservative Einschätzung.

Kosten (US $)	Länge der Schlüssel (bits)
Kosten (US $)	40	56	64	80	112	128
100.000	2 s	35 h	1 J	70.000 J	10¹⁴ J	10¹⁹ J
1 Million	0,2 s	3,5 h	37 Tage	7.000 J	10¹³ J	10¹⁸ J
10 Million	0,02 s	21 min	4 Tage	700 J	10¹² J	10¹⁷ J
100 Million	2 ms	2 min	9 h	70 J	10¹¹ J	10¹⁶ J
1 Milliarde	0,2 ms	13 s	1 h	7 J	10¹⁰ J	10¹⁵ J
10 Milliarde	0,02 ms	1 s	5,4 min	245 Tage	10⁹ J	10¹⁴ J
100 Milliarde	2µs	0,1 s	32 s	24 Tage	10⁸ J	10¹³ J
1 Billion	0,2 µs	0,01 s	3 s	2,4 Tage	10⁷ J	10¹² J
10 Billion	0,02 µs	1 ms	0,3 s	6 h	10⁶ J	10¹¹ J

Tabelle 1: Geschätzte Durchschnittszeit für einen Hardware- Brute-Force-Angriff in 1995

4.3 Software-Brute-Force-Angriff

Ohne sonderangefertigte Hardware und hochparallele Rechner, sind Brute-Force-Angriffe bedeutend schwieriger. Ein Software-Angriff ist ungefähr 1000-mal langsamer als ein Hardware-Angriff. Aber das Internet stellt gerade ein riesiges Netzwerk von Computern bereit, die ein riesiges Potential an Rechenkraft darstellen. Die weltweite Computerausstattung wurde 1996 auf 200 Millionen Computer – von Cray-Mainframes bis Subnotebooks – geschätzt. Auch wenn es möglich wäre, diese gesamte Rechenkraft zum knacken einen 128-bit Schlüssel zu koordinieren, und jeder Computer eine Million Verschlüsselungen pro Sekunde durchführen könnte, würde es immerhin die millionfache des Alters des Universums dauern bis zum Gewinnen des Schlüssels.

4.4 Die chinesische Lotterie

Quisquater und Desmedt haben die chinesische Lotterie als hochparalleles Kryptoanalysesystem vorgeschlagen. Stellen wir uns vor, dass in jedem verkauften Radio und Fernseher ein brute-force, Millionen-Tests-pro-Sekunde Chip eingebaut würde. Jeder Chip wird programmiert, automatisch nach dem Empfang des Klartext/Kryptotext-Paars per Funk eine unterschiedliche Menge von Schlüsseln zu untersuchen. Eine Zeit wird vereinbart, zu der jedes Gerät eingeschaltet wird zum Empfang der Daten. Nach einiger Zeit (siehe Tabelle 2) erscheint der Schlüssel auf dem Display, und der 'Gewinner' meldet sich bei der entsprechenden Stelle. Das Verfahren wäre einfacher, wenn jedes Gerät Zufallschlüssel probiert, aber dadurch wäre der Angriff 39% langsamer.

Land	Bevölkerung	Anzahl Fernsehr/Radio	Dauer
Land	Bevölkerung	Anzahl Fernsehr/Radio	56-bit	64-bit
China	1.190.431.000	257.000.000	280 s	20 h
U.S.A.	260.714.000	739.000.000	97 s	6,9 h
Iraq	19.890.000	4.730.000	4,2 h	44 d
Israel	5.051.000	3.640.000	5,5 h	58 d

Tabelle 2: Chinesische Lotterie Angriffeinschätzung

4.5 Thermodynamische Grenze

Eine Folge des 2. Gesetzes der Thermodynamik ist, dass eine gewisse Energie benötigt wird zur Darstellung von Information. Das Setzen eines einzigen Bits durch Änderung des Zustands eines Systems bedarf mindestens kT Energie, wobei T die absolute Temperatur des Systems und k die Boltzmankonstante sind.

Da k = 1,38 ´ 10^-16 erg/°Kelvin und die Umgebungstemperatur des Universums 3,2°K beträgt, würde ein idealer Computer mit einer Betriebstemperatur von 3,2°K ungefähr 4,4 ´ 10^-16 erg aufbrauchen pro Setzen oder Löschen eines Bits. Sollte man der Computer kälter als die kosmische Hintergrundsstrahlung betreiben wollen, müsste man mehr Energie in eine Wärmepumpe investieren.

Die jährliche Energieausgabe der Sonne ist ungefähr 1,21 ´ 10⁴¹ erg, was genug Energie wäre um ungefähr 2,7 ´ 10⁵⁶ einzelne Bitänderungen auf dem idealen Computer zu erreichen (genug um einen 187-bit Zähler durch alle Werte durchlaufen zu lassen). Sollte man eine Dyson-Sphäre um die Sonne bauen und ihre gesamte Energie für 32 Jahre aufsammeln, hätte man genug Kraft um einen Computer bis 2¹⁹² zählen zu lassen (aber ohne irgendwelche andere Berechnungen).

Hätte man eine Supernova als Energiequelle (10⁵¹ erg in einem Jahr), könnte der Computer bis 2²¹⁹ zählen.

Aus diesen Berechnungen kann man schliessen, dass ein Brute-Force-Angriff gegen einen 256-bit Schlüssel unmöglich wäre, es sei denn Computer werden nicht aus Materie konstruiert und existieren irgendwo anders als im Raum.

5 Quellen

Gladman, B.

AES Algorithm Efficiency,

http://fp.gladman.plus.com/cryptography_technology/aes/index.htm

Nechvatal, J.; Barker, E.; Dodson, D.; Dworkin, M.; Foti, J.; Roback, E.

Status Report on the First Round of the Development of the Advanced Encryption Standard,

http://csrc.nist.gov/encryption/aes/round1/r1report.htm

Nippon Telegraph and Telephone Corporation,

Specification of E2 – a 128-bit Block Cipher,

http://info.isl.ntt.co.jp/e2/E2spec.pdf

Nippon Telegraph and Telephone Corporation,

Supporting Document on E2 (Updated),