Paul Kotscher
e-mail: paul@cryptography.com

() die Übersetzung Olga Bukschewa, Pawel Semjanow, 1998.
e-mail: psw@ssl.stu.neva.ru? subject=timing attack

Die Thesen. Akkurat die Zahl der Zeit, die für die Operationen mit den geschlossenen Schlüsseln notwendig ist messend, kann der Übeltäter die ständige Kennziffer der Stufe im Schema Diffi-Chellmana, факторизованные die Schlüssel in RSA finden, sowie, und andere криптосистемы aufbrechen. Wenn das angegriffene System verwundbar ist, so kann der Angriff preiswert in der Rechenbeziehung sein und wird für sie häufig sein, nur der bekannte chiffrierte Text gefordert zu werden. Die existierenden Systeme sind potentiell verwundbar, криптомаркеры (tokens), netz- криптосистемы und andere Anlagen aufnehmend, wo der Angreifer fähig ist, die genug genauen Abmessungen der Zeit zu machen. Es sind die Methoden für die Verhinderung des Angriffes auf die Systeme RSA und Diffi-Chellmana vorgestellt. Einige криптосистемы sollen für den Schutz vor solchen Angriffen revidiert sein, und die neuen Protokolle und die Algorithmen sollen die Mittel für die Verhinderung der Angriffe von der vorübergehenden Analyse (timing attacks) aufnehmen.

Die Stichwörter: vorübergehend die Analyse, криптоанализ, RSA, Diffi-Chellman, DSS.

Криптосистемы verwenden verschiedene Zahl der Zeit für die Bearbeitung verschiedener Eingangsdaten häufig. Die Gründe es nehmen die Optimierung nach der Zeit, des Treffens in кэш, der Instruktion des Prozessors (als die Multiplikation und die Teilung) auf, die die fixierte Zahl der Takte, sowie anderes nicht haben. Die Geschwindigkeit hängt vom Schlüssel der Chiffrierung und der Eingangsdaten (des geöffneten oder chiffrierten Textes) gewöhnlich ab. Während es bekannt ist, dass eigentlich die vorübergehenden Kanäle die Daten oder die Schlüssel durch das geschützte Perimeter der Bearbeitung versäumen können, sagt die Intuition vor, dass die vorübergehenden Charakteristiken nur die unbedeutenden Informationen über криптосистеме (des Typs хэммингского des Gewichts des Schlüssels öffnen können). Jedoch ist der Angriff, der hier vorgestellt ist, fähig, die Messungen der Zeit in den verwundbaren Systemen für den Verbleib des ganzen geheimen Schlüssels zu verwenden.

In den Algorithmen Diffi-Chellmana DH [2] und RSA [8] muss man R=y^x mod n ausrechnen, wo n - bekannt ist, und y kann vom Abfangen gefunden sein. Das Ziel des Angreifers - den geheimen Schlüssel x zu finden. Für die Verwirklichung des Angriffes ist es notwendig, dass das Opfer y^x mod n für einige Bedeutungen y ausrechnet, wo y, n und die Zeit der Berechnungen dem Angreifenden bekannt sind. (Wenn wird sich geheim des Ausstellers x für jede Operation ändern, der Angriff wird) nicht ansprechen. Die notwendigen Informationen und die Zeit der Berechnungen können vom passiven Abhören bekommen sein, da der Angreifer die Mitteilungen aufzeichnen kann, die dem Ziel des Angriffes geschickt werden und, die Zeit des Erhaltens der Antwort für jeden y zu messen.

Der Angriff kann bei einer beliebigen Realisierung des Algorithmus der modularen Errichtung in die Stufe verwirklicht sein, wo die Zeit der Berechnung fixiert nicht ist, aber es ist zuerst besser, den gewöhnlichen Algorithmus der Berechnung R = y^x mod n, wo x - die Länge w das Bit zu betrachten:

    Let s0 = 1. 
    For k = 0 upto w-1: 
      If (bit k of x) is 1 then 
        Let Rk = (sk Ћ y) mod n. 
      Else 
        Let Rk = sk. 
      Let sk+1 = Rk2 mod n. 
    EndFor. 
    Return (Rw-1). 
:

Der Angriff wird erlauben, wer die Bits 0 weiß. (b-1), das Bit b zu finden. Um dem Aussteller vollständig zu bekommen, muss man mit b gleich 0 beginnen und, den Angriff wiederholen, bis aller des Ausstellers bekannt sein wird.

Da erste b das Bit bekannt sind, kann der Angreifer erste b der Iterationen des Zyklus ausrechnen und, die Bedeutung s_b finden. Die nächste Iteration wird das erste unbekannte Bit fordern. Wenn dieses Bit in 1 bestimmt ist, so wird R_b = (s_bЋy) mod n ausgerechnet sein. Wenn das Bit der Null gleich ist, wird die Multiplikation versäumt sein.

Wir betrachten zuerst Angriff für den folgenden hypothetischen Fall. Wenn auch das angegriffene System die sehr schnelle Funktion der modularen Multiplikation, aber verwendet die viel большее die Zeit, als die ganze Funktion der modularen Errichtung in die Stufe manchmal konsumiert. Dann werden für einige Bedeutungen s_b und y die Berechnungen R_b = (s_bЋy) mod n außerordentlich langsam sein, und, das Wissen über die Realisierung des angegriffenen Systems verwendend, kann der Angreifer bestimmen, diese welchen Bedeutungen. Wenn die Zeit der Berechnung der ganzen Funktion der modularen Errichtung in die Stufe wenig ist, aber sollte dabei R_b ausgerechnet werden ist = (s_b* y) mod n langsam, so ist es das Bit b, offenbar, 0 gleich. Im Gegenteil, wenn lang nach der Zeit der Berechnung R_b = (s_bЋy) mod n immer zur langsamen modularen Errichtung in die Stufe bringen, es ist das Bit, wahrscheinlich, ist in 1 bestimmt. Kaum wird das Bit b bekannt sein, angreifend kann prüfen, dass die volle Zeit der Operationen langsam jedees Mal, wenn es s_b+1 = R²_b mod n erwartet wird, langsam zu sein. Diese Annahmen können verwendet werden und ist weiter, um die folgenden Bits zu finden.

Wenn das Bit b falsch erraten ist, werden die Bedeutungen, die für R_{k> = b} ausgerechnet werden auch falsch sein, wird weiter das Ergebnis, im Allgemeinen, zufällig. Die Zeit, die für die Multiplikation nach dem Fehler nicht gefordert wird wird auf voll die Zeit der Errichtung in die Stufe widergespiegelt werden. Der Angriff hat die Eigenschaft "die Entdecken des Fehlers" so; nach der falschen Annahme über die Bedeutung des Bits wird keiner bedeutsamen Korrelation beobachtet werden.

Die Eigenschaft "die Entdecken des Fehlers" kann für ihre Korrektion verwendet werden. Zum Beispiel, der Angreifer kann die Liste wahrscheinlichst zwischen- der Aussteller neben mit der Bedeutung, der entsprechenden richtigen Wahrscheinlichkeit unterstützen. Der Angriff dauert für den einzigen wahrscheinlichsten Kandidaten. Wenn die laufende Bedeutung falsch ist, wird es neigen, in der Liste der wahrscheinlichsten Bedeutungen herabzufallen, während das Richtige erhöht werden sollte. Die Methoden der Korrektur der Fehler vergrössern das notwendige Gedächtnis und die Prozessorzeit, aber dabei verringern die Zahl der notwendigen Bedeutungen wesentlich.

Den Angriff kann man wie das Problem der Erkennung der Signale deuten. "Das Signal" besteht aus den Variationen der Messung der Zeit für bekannt das Bit, "den Lärm" - aus den Fehler der Messung der Zeit und der Variationen der Messung der Zeit für die Unbekannten das Bit. Die Eigenschaften "des Signals" und "des Lärms" bestimmen die Zahl der Abmessungen der Zeit, die für den Angriff gefordert werden. Wenn auch es j der Mitteilungen y₀, y₁ bekommen ist., y_j-1 und ihnen die entsprechenden Messungen der Zeit T₀, T₁., T_j-1. Die Wahrscheinlichkeit, dass die Annahme x_b für erste b das Bit richtig, proportional ist, wo

t (y_i, x_b) - die Zeit, die für erste b die Iterationen des Zyklus вычсиления y_i^x mod n mit der Nutzung das Bit x_b gefordert wird,

F - erwartet фунция die Verteilungen der Wahrscheinlichkeit T-t (y, x_b) nach allen Bedeutungen y und richtig x_b. Da F wie die Verteilung werojatnostiT_i-t (y_i, x_b bestimmt ist), wenn es x_b, so richtig ist es ist es die beste Funktion für die Voraussage T_i-t (y_i, x_b). Werden beachten, dass die Messungen der Zeit und die Zwischenbedeutungen s für die Verbesserung der Einschätzung F verwendet werden können.

Bei der richtigen Annahme für x_b-1 gibt es zwei mögliche Bedeutungen für x_b. Die Wahrscheinlichkeit, dass x_b - richtig ist, und x_b ' - falsch, kann wie gefunden sein

In der Praxis ist diese Formel nicht sehr nützlich, da die Suche F die viel zu großen Bemühungen fordern wird.

Zum Glück gibt es keine Notwendigkeit, F auszurechnen. Jede Beobachtung der Zeit besteht aus, wo t_i - die Zeit, die für die Multiplikationen und die Errichtung in die Stufe für das Bit i gefordert wird, und e den Fehler der Messung aufnimmt, die Zeit auf инкремент des Zyklus die Annahme x_b u.ä. Habend, kann der Angreifer für jede Bedeutung y¹ ausrechnen. Wenn es x_b richtig ist, so diese Zeit aus T abziehend, werden wir bekommen. Da die Zeiten der modularen Multiplikation von einander und vom Fehler der Messung nicht abhängen, wird die Dispersion nach allen beobachteten Bedeutungen, erwartet, wird Var (e) + (w-b) Var (t) gleich sein. Jedoch wenn nur erste c <b das Bit richtig erraten sind, die erwartete Dispersion wird Var (e) + (w-b+2c) Var (t). Die Iterationen mit den richtigen Annahmen verringern die erwartete Dispersion auf Var (t), jede Iteration nach der falschen Annahme vergrössert die Dispersion auf Var (t). Die Dispersionen auszurechnen es ist leicht, und es gewährleistet die gute Weise der Identifizierung des richtigen Bits.

Es ist jetzt möglich, die Zahl der Bedeutungen, die für den Angriff gefordert werden zu bewerten. Wir werden vermuten, dass der Angreifer j der genauen Zeiten der Messung und zwei Annahmen bezüglich erster b der Bits der w-Bit- Bedeutung, ein richtig und andere - falsch mit dem ersten Fehler im Bit c hat. Für jede Annahme kann die Zeit der Messung mit nachgeprüft sein. Wenn solche Verifizierung die kleinere Dispersion hat, so ist es die richtige Annahme. Es ist möglich, t_i mit der Nutzung der unabhängigen standardmäßigen normalen Variabelen zu approximieren. Wenn Var (e) unbedeutend ist, die erwartete Wahrscheinlichkeit der Richtigkeit der Annahme

X und Y - normal zufällig variabel mit dem Gesetz (0, 1). Da j verhältnismäßig groß, mit dem Gesetz (0,) eben ungefähr normal sind. Von hier aus, wo Z - standardmäßig normal zufällig variabel. Die Integration für den Verbleib der Wahrscheinlichkeit der richtigen Annahme gibt, wo - das Gebiet unter der standardmäßigen normalen Kurve von bis zu x. Die geforderte Zahl der Bedeutungen j so proportional zur Länge die Aussteller w. Die Zahl der Messungen kann verringert sein, wenn der Angreifer solche Eingangsdaten wählen kann, um экстремумы der Zeit in jenen Bits die Aussteller zu haben, die es interessieren.

Auf der Abb. 1 ist die Verteilung der Ausführung der modularen Multiplikation 10⁶ Male gezeigt. Dazu wurde das Paket RSAREF [10] auf 120-MHz den Computer Pentium von den Wespen MS-DOS verwendet. Die Verteilung war aufgebaut, die Zeit einer Million Berechnungen (aЋb mod n messend), wo sich a und b wie das Ergebnis der tatsächlichen Operationen der modularen Errichtung in die Stufe mit den zufälligen Eingangsdaten ergaben. In der Qualität n wurde die erste 512-Bit- einfache Zahl aus dem Demonstrationsprogramm der Methode Diffi-Chellmana des Paketes RSAREF verwendet. Alle am meisten abweisenden Bedeutungen der Messungen (die mehr 1300 мкс eingenommen haben) waren abgelehnt. Die Verteilung in der Abb. 1 hat das Matt. Die Erwartung Њ = 1167.8 мкс und die standardmäßige Abweichung = 12.01 мкс. Der Fehler der Messung ist klein; die Tests wurden zweimal durchgeführt und der mittlere Unterschied zwischen den Messungen hat weniger 1 мкс gebildet. RSAREF verwendet eine und derselbe Funktion für die Errichtung ins Quadrat und der Multiplikation; so haben die Zeiten der Errichtung ins Quadrat und der Multiplikation die identischen Verteilungen.

RSAREF rechnet im Voraus y² mod n und y³ mod n aus und bearbeitet sofort zwei Bits. Allen, die 512-Bit- modulare Errichtung in die Stufe mit der zufälligen Kennziffer der Stufe aus 256 Bit fordert 128 Iterationen des Zyklus der modularen Multiplikation und die Gesamtmenge der Handlungen der modularen Multiplikation und der Errichtung ins Quadrat ungefähr 352, da jede Iteration zwei Handlungen der Errichtung ins Quadrat und, wenn jedes zwei Bits nicht 0, eine Multiplikation erfüllt. Der Angriff kann für diesen Fall korrigiert sein, um ein Paar das Bit hinzuzufügen und, vier Bedeutungen des Kandidaten in jeder Position die Aussteller anstelle zwei zu bewerten.

Da modular der Multiplikation die meiste Zahl der allgemeinen Zeit konsumieren, wird es erwartet, dass die Verteilung der Zeit mit dem Gesetz (Њ,), wo Њ> = 1167.8Ћ352 = 411065.6 мкс und = 225 мкс ungefähr normal sein wird. Die Zeichnung 2 zeigt die Messungen aus 5000 tatsächlichen Handlungen, die den selben Computer und die Module n verwenden, wo die Verteilung mit Њ = 419,901 мкс und = 235 мкс erhalten wurde.

Bei 250 Messungen der Zeit die Wahrscheinlichkeit, dass die Subtraktion der Zeit der richtigen Iteration aus jeder Bedeutung die allgemeine Dispersion zur großen Größe verringern wird, als die Subtraktion der falschen Iteration, von der Formel, wo j=250, b=1, c=0 und w=127 bewertet wird. (Es Gibt 128 Iterationen des Zyklus in RSAREF für die Aussteller in 256 Bit, aber die erste Iteration wird) ignoriert. Die richtigen Annahmen werden mit der Wahrscheinlichkeit so erwartet. 5000 Bedeutungen aus der Zeichnung 2 waren auf 20 Gruppen nach 250 in jeder geteilt, und es wurden die Dispersionen, die bei der Subtraktion der Zeit für die falschen und richtigen Iterationen des Zyklus bekommen werden, für jedes 127 Paare das Bit verglichen. Aus 2450 Tests, in 2168 Dispersion nach der Subtraktion der Zeit des falschen Zyklus war grösser, als nach der Subtraktion der Zeit richtig, die Wahrscheinlichkeit 0.885 gebildet. Die ersten Bits sind für die Analyse am meisten schwierig, aber je nach der Vergrößerung b soll sich die Wahrscheinlichkeit verbessern. (Die Tests verwendeten diese Eigenschaft) nicht. Es ist wichtig, zu bemerken, dass die genauen Messungen der Zeit verwendet wurden; die Fehler der Messungen mit der verhältnismäßig großen Abweichung werden im Vergleich zur Zeit der Berechnung der modularen Errichtung in die Stufe, den Umfang des Abrufes vergrössern.

Der Angriff in der Rechenbeziehung ist sehr einfach. Unter Anwendung von RSAREF, der Angreifer soll vier Varianten für jedes Paar das Bit bewerten. So soll der Angreifer nur viermal большее die Zahl der Handlungen, die vom Opfer erfüllt werden (nicht einschließlich die Zeit, ausgegeben vergebens auf die falschen Annahmen) machen.

Die Mehrheit der Variationen der Zeit in der modularen Multiplikation ruft die Kürzung der modularen Operationen gewöhnlich herbei. Die Multiplikation Montgomerys [6] entfernt die Notwendigkeit der Kürzung mod n und daraufhin neigt, die Bedeutsamkeit der vorübergehenden Charakteristiken zu verringern. Jedoch bleiben einige Variationen doch. Wenn das bleibende "Signal" von den Fehlern der Messung nicht verdunkelt wird, wären die Dispersion in t_b sowohl die Dispersion proportional verringert als auch hätte der Angriff noch angesprochen. Jedoch wenn der Fehler der Messung e groß, so wird die geforderte Zahl der Bedeutungen proportional zunehmen.

Das chinesische Theorem über die Reste (WER) auch wird häufig verwendet, um die Operationen in RSA zu optimieren. Bei ihrer Nutzung werden y mod p und y mod q, wo y - die Mitteilung zuerst ausgerechnet. Diese ursprünglichen Schritte können verwundbar für die vorübergehenden Angriffe sein. Elementar- von ihnen besteht darin, dass man die Bedeutungen y wählen muss, die nah zu p oder q sind, und, die Messungen der Zeit verwendend, aufzuklären, ob die vermutete Bedeutung weniger, als die tatsächliche Bedeutung p (oder q ist). Wenn es y - weniger ist, als p, so ist die Berechnung y mod p, während es nicht wenn y, als p mehr ist, so ist für die Berechnung y mod p die Subtraktion p wenigstens einmal notwendig notwendig. Auch, wenn die Mitteilung, als p ein bisschen mehr ist, y wird mod p die ersten Nullbits haben, dass die Zeit verringern kann, die für den ersten Schritt der Multiplikation gefordert wird. Die Besonderheiten der vorübergehenden Charakteristiken hängen von der Realisierung ab. Die modulare Funktion der Kürzung RSAREF mit dem 512-Bit- Modul auf dem Computer Pentium mit y, gewählt zufällig zwischen 0 und 2p, nimmt durchschnittlich 42.1 мкс, wenn y <p, und 73.9 мкс, wenn y> p ein. Die Zeit der Messung für viele y kann für die konsequente Approximation p verwendet werden.

Es ist in einigen Fällen möglich, den Angriff auf RSA mit WER zu verbessern, wenn bekannt zu verwenden (nicht gewählt) den chiffrierten Text, die Zahl der geforderten Mitteilungen verringernd und möglich die Angriffe auf die digitalen Unterschriften RSA machend. Die Kürzung der modularen Operationen wird von der Subtraktion einiger Module sofort erfüllt, und die Variationen der Zeit, die man verwenden kann, entstehen auf Kosten von verschiedener Zahl der Schritte "des Vergleiches-Subtraktion". Zum Beispiel, der Zyklus der Teilung RSAREF erfüllt die ganzzahlige Teilung zwei älteren Zahlen y in die ältere Zahl p, multipliziert p auf privat, schiebt nach links auf die entsprechende Zahl der Zahlen, und dann zieht das Ergebnis aus y. Wenn es das Ergebnis mehr ist, als p (geschoben nach links), so wird die zusätzliche Subtraktion erfüllt. Die Lösung, ob eine zusätzliche Subtraktion im ersten Zyklus des Algorithmus der Teilung zu machen, hängt nur von y (der bekannt ist) und zwei älteren Zahlen p gewöhnlich ab. Vorübergehend kann die Analyse für die Bestimmung der älteren Zahlen p verwendet sein. Zum Beispiel, die volle Übergebühr nach alles Mögliche den Bedeutungen für zwei älteren Zahlen p (oder die wirksameren Methoden) kann die Bedeutung feststellen, für die die beobachtete Zeit am meisten nahe mit der erwarteten Zahl der Handlungen der Subtraktion korreliert. Wie auch im Falle des Angriffes für die Methode Diffi-Chellmana, kaum wird eine Zahl p gefunden sein, können die Messungen der Zeit vielfach verwendet werden, um die nachfolgenden Zahlen zu finden.

Es ist noch nicht bekannt, ob vorübergehend die Analyse verwendet sein kann, um die Errichtung in die Stufe nach dem Modul p und q, erfüllt mit der Hilfe WER unmittelbar anzugreifen.

Der Standard der digitalen Unterschrift (Digital Signature Standart aus, DSS) rechnet s = (k^-1 (H (m) +x Ћ r)) mod q, wo r and q angreifend bekannt sind, k^-1 ist es im Voraus, H (m) - хэш die Mitteilungen, und x - der geheime Schlüssel gewöhnlich ausgerechnet. In der Praxis wird (H (m) + x Ћ r) mod q zuerst ausgerechnet, und dann wird auf k^-1 (mod q) multipliziert.

Wenn die Funktion der modularen Kürzung zur fixierten Zeit nicht erfüllt wird, soll die Zeit der vollen Unterschrift mit der Zeit die Berechnungen (x Ћ r mod q) korrelieren. Angreifend kann und kompensieren die Zeit ausrechnen, die für die Berechnung H (m) gefordert wird. Da H (m) ungefähr den selben Umfang hat, dass auch q, seine Addition den unwesentlichen Einfluss auf die Zeit der modularen Kürzung leistet. Die am meisten bedeutsamen Bits x Ћ r werden von erstem in der modularen Kürzung gewöhnlich verwendet. Sie hängen von r ab, der, und von am meisten bedeutsam das Bit der geheimen Bedeutung x bekannt ist. So soll die Korrelation zwischen den Bedeutungen der älteren Bits x und der allgemeinen Zeit der modularen Kürzung existieren. Größt der Wahrscheinlichkeit nach den Bedeutungen verwendend, kann der Angreifer versuchen, die älteren Bits x zu identifizieren. Je grösser wird das Bit x bekannt sein, desto es mehr ist und das Bit x Ћ r wird bekannt sein, angreifend zulassend, immer mehr der Iterationen des Zyklus der modularen Kürzung zu modeln, alle neuen Bits x angreifend. Wenn es k^-1 - im Voraus ausgerechnet ist, fordern die Unterschriften DSS nur 2 Operationen der modularen Multiplikation, potentiell erzeugend vorübergehend den Lärm, der abgefiltert sein soll.

Der offensichtlichste Weg der Verhinderung der Angriffe von der vorübergehenden Analyse besteht darin, dass alle Handlungen genau einem und dasselbe временя einnehmen. Leider, es findet häufig kompliziert statt. Die Bildung der Software, die besonders platformo-unabhängig ist, so wurde damit es zur fixierten Zeit erfüllt, es ist, weil die Optimierung des Compilers sehr schwierig, die Treffen in programm- кэш, die Zeit der Ausführung der Instruktionen und andere Faktoren können die unerwarteten Schwingungen während der Erfüllung beitragen. Wenn für den Verzug der zurückgegebenen Ergebnisse bis zu einer bestimmten Zeit die Schaltuhr verwendet wird, so können die Faktoren als "die Antwort des Systems" (responsiveness) oder des Energieverbrauchs zu den Merkmalen des tatsächlichen Abschlusses der Operation immer noch dienen. Auch zeigen einige Betriebssysteme das Prozent der Nutzung ЦПУ vom Prozess. Außerdem, die Realisierungen mit der fixierten Zeit werden langsam; Die Mehrheit оптимизаций kann nicht verwendet sein, da alle Handlungen die Zeit, der Erfüllung der langsamsten Operation einnehmen sollen. (Die Anmerkung: wenn der unverbindliche Schritt R_i = (s_i Ћ y) mod n, immer zu erfüllen, so darf man nicht solche Realisierung erfüllt in die fixierte Zeit nennen, da angreifend die vorübergehenden Charakteristiken der Errichtung ins Quadrat und der nachfolgenden Handlungen des Zyklus verwenden kann).

Anderes Herangehen besteht darin, die Messungen der Zeit so unexakt zu machen, damit der Angriff unerfüllbar wurde. Die zufälligen Verzüge, die zum Prozess beigefügt sind, werden die notwendige Zahl des chiffrierten Textes für den Angreifer vergrössern, aber er kann es von der Vergrößerung der Zahl der Messungen überwinden. Die geforderte Zahl der Bedeutungen wird wie das Quadrat des Lärms grob bewertet. Zum Beispiel, wenn die modulare Errichtung in die Stufe, deren vorübergehende Charakteristiken die standardmäßige Abweichung 10 мс haben, für 1000 Messungen der Zeit aufgebrochen sein kann, die Ergänzung des zufälligen normal verteilten Verzuges mit der standardmäßigen Abweichung wird ungefähr = 10⁷ Bedeutungen in 1 Sekunde fordern. (Die Anmerkung: der Verzug soll etwas Sekunden, damit ihre standardmäßige Abweichung in 1 Sekunde wäre) sein. Obwohl 10⁷ Bedeutungen - mehr sind, als die meiste mögliche Zahl der Bedeutungen, die man sammeln kann, den Faktor der Sicherheit in 10⁷ genug adäquat gewöhnlich nicht angenommen wird.

Zum Glück gibt es auch die beste Lösung. Die Methoden, die für das Verstecken der Unterschriften [1] verwendet werden, können verwendet sein, um das Wissen angreifend der Eingangsdaten zur modularen Funktion der Errichtung in die Stufe zu verhindern. Vor der Berechnung modular die Aussteller, wählen Sie ein zufälliges Paar (v_i, v_f), solche, dass v_f^-1 = v_i^x mod n. Für die Methode Diffi-Chellmana ist es am meisten einfach, zufällig v_i zu wählen, dann, v_f = (v_i^-1) ^x mod n auszurechnen. Für RSA ist es besser, zufällig v_f, gegenseitig einfach zu n zu wählen, dann, v_i = (v_f^-1) ^e mod n, wo e - geöffnet den Aussteller auszurechnen. Vor der modularen Errichtung in die Stufe multipliziert sein, sollen die Eingangsdaten auf v_i (mod n), und später wird das Ergebnis von der Multiplikation auf v_f (mod n) korrigiert. Dabei soll das System die Mitteilungen, die 0 gleich sind (mod n) ablehnen.

Die Berechnung der Inversionen mod n langsam, deshalb nicht praktisch, neu zufällig (v_i, v_f) ein Paar für jede neu die Aussteller zu wählen. Außerdem, die Berechnung v_f = (v_i^-1) ^x mod n kann der vorübergehenden Analyse untergezogen sein. Jedoch nicht sein sollen (v_i, v_f) ein Paar, nochmalig verwendet zu werden, da sie von der vorübergehenden Analyse geöffnet sein können, was geheim dem Aussteller verwundbar macht. Die wirksame Lösung dieses Problems - die Modernisierung v_i and v_f vor jedem Schritt der modularen Errichtung in die Stufe, v_i ' = v_i² and v_f ' = v_f² ausrechnend. Der Gesamtaufwand darauf wird (2 modular возведений ins Quadrat, die im Voraus, das Plus 2 modularer Multiplikationen ausgerechnet sein kann) klein sein. Es ist möglich, zu verwenden und die kompliziertere Modernisierung Paares, die Ordnungen höher 2 verwendend, wird die Multiplikation auf anderes Paar (v_i, v_f) u.ä., aber es die neuen Vorteile nicht hineinlegen.

Wenn (v_i, v_f) im Geheimnis bewahrt wird, so hat der Angreifer keine nützliche Information bezüglich der Eingangsdaten für die Funktion der modularen Errichtung um der Stufe. Also Maximum, dass den Angreifenden erkennen kann, ist eine allgemeine Verteilung der Zeit für die Handlungen der Errichtung in die Stufe. Tatsächlich, diese Verteilungen sind zu normal nah und 2^w der Aussteller darf man nicht unterscheiden. Jedoch könnte die vom Übeltäter speziell entwickelte Funktion der modularen Errichtung in die Stufe die Verteilung mit scharf von den Bergen theoretisch haben, die den Bits die Aussteller entsprechen, und in diesem Fall wird das Verstecken, wahrscheinlich, vorübergehend die Analyse nicht verhindern.

Sogar das Verstecken verwendend, wird die Verteilung die mittlere Zeit der Operation widerspiegeln, dass man, um verwenden kann хаммингский das Gewicht die Aussteller zu finden. Wenn die Anonymität oder wichtig ist wenn die weitere Maskierung gefordert wird, so kann des Ausstellers auf zufällig vor jeder modularen Errichtung in die Stufe multipliziert sein. Wenn es wird, so muss man sich überzeugen, dass der Prozess der Multiplikation die vorübergehenden Charakteristiken nicht hat, die öffnen können. Solche Technik kann und in der Verhinderung der Angriffe nützlich sein, die das Ausfließen der Informationen im Laufe von der modularen Errichtung in die Stufe wegen der elektromagnetischen Ausstrahlungen, der Schwingungen in der Produktivität des Systems, der Veränderungen im Konsum der Energie usw. bis zur Veränderung das Bit die Aussteller in jeder Operation verwenden.

Vorübergehend kann die Analyse gegen andere криптосистем, einschließlich die Symmetrischen im Prinzip verwendet werden. Zum Beispiel, sich in der Programmrealisierung DES [4] 28-Bit- Bedeutungen Mit und D (rotate) häufig drehen, die Bedingung verwendend, die prüft, ob ein Bit ringsumher eingewickelt sein soll. Die Spielverlängerung, die gefordert wird, dass ausgezeichnet von der Null die Bits zu versetzen, kann auf der Produktivität der Chiffrierung oder auf der Zeit der Vorbereitung (setup) der Schlüssel ein wenig gesagt werden. Die Produktivität der Chiffre kann хаммингский das Gewicht des Schlüssels so zeigen, dass das Bit der Schlüsselinformationen durchschnittlich gewähren wird. IDEA [3] verwendet die Funktion $f () $ mit der Multiplikation nach dem Modul (2¹⁶ + 1), das gewöhnlich zur fixierten Zeit nicht erfüllt werden wird. RC5 [7] wird in Gefahr auf den Bahnsteigen, wo das Bitdrehen zur variabelen Zeit erfüllt wird. Die Treffen in programm- кэш können dem Übeltäter die vorübergehenden Charakteristiken Blowfish [11], SEAL [9], DES und andere der Chiffren geben, wenn die Tabellen im Gedächtnis identisch für jede зашифровки nicht verwendet werden. Ob die zusätzlichen Forschungen, um notwendig sind zu bestimmen es sind die konkreten Realisierungen sind und, wenn es so jenes die Stufe ihrer Verwundbarkeit verwundbar. Für heute detailliert waren nur wenige bestimmte Systeme studiert, und die Angriffe gegen die Multiplikation Montgomeri/wer in den Realisierungen RSA und DSS sind rein theoretisch vorerst. Es können die weiteren Ergänzungen zu den Angriffen auch möglich sein. Der gerade Angriff auf p und q in RSA mit der Nutzung WER wäre besonders wichtig.

Überhaupt, ein beliebiger Kanal, der die Informationen aus dem geschützten Gebiet nach draußen tragen kann soll wie potentiell verwundbar studiert werden. Die vorübergehenden von der Realisierung abhängenden Charakteristiken sind einer solcher Kanäle und manchmal können für das Öffnen der geheimen Schlüssel verwendet werden. Die verwundbaren Algorithmen, die Protokolle und die Systeme sollen revidiert sein, um die Maße der Gegenwirkung der vorübergehenden Analyse und den mit ihm verbundenen Angriffen aufzunehmen.

Ich bin Matt Blaze, Joan Feigenbaum, Martin Hellman, Phil Karn, Ron Rivest und Bruce Schneier für ihre Unterstützung, die nützlichen Kommentare und die Vorschläge über die Verbesserung des Manuskriptes dankbar.

1. D. Chaum, "Blind Signatures for Untraceable Payments," Advances in Cryptology: Proceedings of Crypto 82, Plenum Press, 1983, pp. 199-203.
2. W. Diffie and M.E. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory, EDV-22, n. 6, Nov 1976, pp. 644-654.:
3. X. Lai, On the Design and Security of Block Ciphers, ETH Series in Information Processing V. 1, Konstanz: Hartung-Gorre Verlag, 1992.:
4. National Bureau of Standards, "Data Encryption Standard," Federal Information Processing Standards Publication 46, January 1977.:
5. National Institute of Standards and Technology, "Digital Signature Standard," Federal Information Processing Standards Publication 186, May 1994.:
6. P.L. Montgomery, "Modular Multiplication without Trial Division," Mathematics of Computation V. 44, n. 170, 1985, pp. 519-521.:
7. R.L. Rivest, "The RC5 Encryption Algorithm," Fast Software Encryption: Second International Workshop, Leuven, Belgium, December 1994, Proceedings, Springer-Verlag, 1994, pp. 86-96.:
8. R.L. Rivest, A. Shamir, and L.M. Adleman, "A method for obtaining digital signatures and public-key cryptosystems," Communications of the ACM, 21, 1978, pp. 120-126.:
9. P.R. Rogaway and D. Coppersmith, "A Software-Optimized Encryption Algorithm," Fast Software Encryption: Cambridge Security Workshop, Cambridge, U.K., December 1993, Proceedings, Springer-Verlag, 1993, pp. 56-63.:
10. RSA Laboratories, "RSAREF: A Cryptographic Toolkit," Version 2.0, 1994, available via FTP from rsa.com.:
11. B. Schneier, "Description of a New Variable-Length Key, 64-bit Block Cipher (Blowfish)," Fast Software Encryption: Second International Workshop, Leuven, Belgium, December 1994, Proceedings, Springer-Verlag, 1994, pp. 191-204.

:

¹. Im Artikel wird über die Forderungen nirgends gesagt, die zur Produktivität des Computers angreifenden vorgelegt werden. Aus dieser Phrase kann man die Schlussfolgerung ziehen, dass sie solcher, wie beim angegriffenen Computer sein soll. - die Anm. der Gasse