Cryptography Reference
In-Depth Information
über die reine Mathematik hinausging: Er maß die Zeit, die das Modul zum RSA-
Entschlüsseln benötigte [Koch95]. In einer Chosen-Ciphertext-Attacke lieferten
ihm schon einige Tausend Entschlüsselungsvorgänge genug Informationen, um
den Schlüssel mittels Zeitvergleich rekonstruieren zu können.
Natürlich war mit diesem Angriff, den Kocher
Zeitangriff
(Timing Attack)
nannte, RSA nicht gebrochen. Der Angriff traf schließlich nur die Implementie-
rung, nicht aber das Verfahren an sich. In der Folgezeit entwickelten auch andere
Kryptografen Angriffsmethoden, die die Ausführungszeit oder andere Messwerte
zu Hilfe nahmen, um eine Krypto-Implementierung auszuhebeln. Ein solcher
Angriff, der kryptografisch scheinbar nicht relevante Zusatzinformationen ver-
wendet, wird
Seitenkanalangriff
genannt. Mit dem Aufkommen von Seitenka-
nalangriffen standen Chiffren-Designer und die Hersteller von Krypto-Lösungen
vor völlig neuen Herausforderungen.
17.1.1
Zeitangriffe
Für die von Paul Kocher erfundenen Zeitangriffe benötigt Angreifer Mallory nur
eine vergleichsweise simple Hardwareausstattung. Dennoch sind Zeitangriffe
erstaunlich leistungsfähig, sofern eine Implementierung nicht speziell dagegen
geschützt ist. Besonders gut funktionieren sie gegen asymmetrische Verfahren, da
diese vergleichsweise komplexe Rechenoperationen erfordern, was sich in größe-
ren Rechenzeit-Differenzen niederschlägt. Bei symmetrischen Verfahren hat es
Mallory dagegen deutlich schwerer. Der DES verwendet beispielsweise nur
Exklusiv-oder-Verknüpfungen, Substitutionen und Permutationen - diese Opera-
tionen haben eine konstante Rechenzeit. Auch symmetrische Verfahren, die kom-
plexere arithmetische Operationen vorsehen (etwas der AES), sind meist unkri-
tisch, da die jeweiligen Implementierungen in der Regel mit vorberechneten
Ersetzungstabellen arbeiten.
Beispiele für Zeitangriffe
Die erwähnte Veröffentlichung von Paul Kocher aus dem Jahr 1996 stellte Zeit-
angriffe nicht nur erstmals vor, sondern behandelte gleich auch das nahelie-
gendste Beispiel für einen solchen. Ziel des Angriffs ist die Exponentialfunktion
in einem endlichen Körper. Wenn eine Krypto-Implementierung
a
b
(mod
n
) für
irgendwelche größeren Zahlen
a
,
b
und
n
berechnet, dann geschieht dies fast
immer mit dem sogenannten Square-and-Multiply-Algorithmus. Dieser sieht für
jedes Bit von
b
eine Aktion vor. Hat das gerade bearbeitete Bit den Wert Eins,
dann ist diese Aktion eine Multiplikation, ansonsten eine Quadrierung. Da eine
Multiplikation in diesem Zusammenhang mehr Zeit benötigt als eine Quadrie-
rung, kann Mallory (er kennt
a
,
n
und die Länge von
b
) aus einer Zeitmessung
Rückschlüsse auf die Zahl der Einsen in
b
schließen. Variiert Mallory die Zahl
a
,
dann reichen seine Informationen irgendwann aus, um
b
zu berechnen.
