[Datenschleuder] [59]    Abt. wundersame Dinge

Abt. wundersame Dinge Fehler & Folgen RSA(CRT): One strike and you're out! Manchmal sind es die berühmten Randbemerkungen, die kryptographische Erdbeben auslösen sollten. Speziell wenn diese Randbemerkung zwei Tage nach einer wichtigen Veröffentlichung von Arjen Lenstra kommt. Lenstra ist nicht nur einer der Hackerväter von digicrime, sondern auch promovierter Mathematiker und einer der führenden Faktorisierungsforscher. Wenn die Wissenschaftler von Bellcore in ihrem berühmten Artikel "On the Importance of Checking Cryptographic Protocols on Faults" also eine Mail von Lenstra zitieren, ist sicherlich Aufmerksamkeit angesagt. Aber irgendwie scheint es mal wieder niemanden zu interessieren, was sich Hacker/Mathematiker da überlegt haben. Dabei ist die Sache höchst brisant: EINE durch Hardwarefehler unkorrekte RSA-Unterschrift führt mit fast 100%-iger Sicherheit zur Aufdeckung des geheimen RSA-Schlüssels. Der "Angreifer" bekommt die Möglichkeit direkt angezeigt, und die Berechnung ist trivial. Um es wissenschaftlich exakt zu formulieren: Entsteht ein Fehler während des Signierens, tritt er mit hoher Wahrscheinlichkeit zum im Fehlermodell angenommenen Zeitpunkt auf. Er kann als beliebiger Bitfehler angenommen und mit sehr hoher Wahrscheinlichkeit kann das RSA-Modul N mit einem Aufwand von einer Potenzierung mit dem öffentlichen Exponenten, einer Addition und einer GGT-Blidung faktorisiert werden. Aber der Reihe nach: Durch einen altbekannten mathematischen Trick kann man die für das RSA-Verfahren notwendige, aufwendige Potenzierung stark beschleunigen. Statt die RSA-Signatur E=m^d MOD N direkt modulo N zu berechnen, rechnet man die beiden Werte E[p] =m^d MOD p und E[q]=m^d MOD q, wobei p und q die beiden Primfaktoren von N sind. Nach dem Chinesischen Restsatz (Chinese Remainder Theorem) existieren nämlich zwei einfach und nur einmal im voraus bestimmbare Werte a und b mit a = 1 MOD p, a = 0 MOD q bzw b = 0 MOD p, b= 1 MOD q. Mit diesen beiden Zahlen gilt E=aE[p]+bE[q] MOD N. Diese ist offensichtlich deutlich effizienter als die direkte Potenzierung modulo N, da die Operationen mit deutlich kürzeren Zahlen durchgeführt werden können. Bruce Schneier empfiehlt in seinem Standardwerk "Angewandte Kryptographie" (1996) dieses Vorgehen und auch die RSAREF-Referenzimplementierung von RSASDI und PGP verwenden das CRT. Sind p und q ungefähr gleich groß, halbiert sich ungefähr die Länge der Zwischenergebnisse. Dies ist natürlich für Chipkarten mit beschränktem Speicherplatz von ganz besonderem Vorteil. Die Signaturzeit wird nach Angaben der Chipkartenhersteller mindestens halbiert. FAMEX -Zahlen aus einem Philipsprospekt (Mai 1997) Schlüssel-Bits, 512, 768, 1024, 2048 Straightforward (ms), 140, 410, 805, 18200 Chinese Remainder (ms), 56, 164, 322, 2156 Gehen wir nun davon aus, daß entweder bei der Berechnung von E[p] oder von E[q] ein Fehler auftritt. Diese Annahme ist, da diese Berechnungen die zeitlich aufwendigsten Abschnitte des Algorithmus sind, sehr realistisch. Nun ist mit hoher Wahrscheinlichkeit N kein Teiler von (M-F^e), wobei e der zur Verifikation der Signatur benötigte öffentliche Exponent ist. Dann gilt aber GGT(M-F^e,N)=q. Somit kann man den RSA-Modul N(=pq) faktorisieren und so einfach den geheimen Schlüssel d berechnen. Kurz gesagt ist das der kryptographische Super-GAU. Witzig dabei ist, daß der einfache Anwender, der zur Kontrolle der Signatur M=E^e ausrechnen muß, direkt auf den Fehler hingewiesen wird. In der Orginalarbeit von Dan Boneh, Richard DeMillo und Lipton vom 26. September 1995 gingen die Autoren noch davon aus, daß für ihren Angriff eine korrekte UND eine fehler-hafte RSA-Signatur der selben Nachricht M von Nöten sind. Hier traten dann die profes-sionellen Abwiegler auf den Plan. Durch Ergänzung der Nachricht (beispielsweise mit Zeitstempeln) würde schon seit längerem erreicht, daß niemals die gleiche Nachricht zweimal unterzeichnet wird. Wenn nur eine fehlerhafte Unterschrift benötigt wird, hilft dies zunächst nichts. Allenfalls durch das Hinzufügen von Zufallszeichen (random padding) aus einem kryptographisch starken Zufallsgenerator, kann, da dann die eigentlich unterschriebene Nachricht M' nicht bekannt ist, der Lenstra-Angriff verhindert werden. Dies bedarf aber möglicherweise einer Protokollanpassung und weiterer Forschung. Bis dahin muß das nochmalige Verifizieren der Signatur vor der Ausgabe dringend empfohlen werden. Bei der großen Chipkarten-konferenz ";Technologie '97" Mitte Juni interessierte sich leider so gut wie keiner der Experten für diese Sicherheitslücke. Um es nochmals festzuhalten: Entsteht zufällig, durch von Hackerhand hinzugefügten physikalischen Streß oder einen INDEL-Prozessor, eine fehlerhafte RSA Ausgabe, kann mit einem 8080 und ein paar Millisekunden der geheime RSA-Schlüssel bestimmt werden. Also für alle noch mal die Hackanleitung: Wenn einem eine fehlerhafte RSA-Unterschrift F präsentiert wird, einfach mal GGT(M-F^e, N) ausrechnen. Fast sicher hat man dann einen Faktor des RSA-Moduls gefunden. Wenn man dann noch einen kurzen Blick in ein beliebiges Kryptographiebuch zur Bestimmung des geheimen Schlüssels d aus p und q wirft, dürfte man einen Hauptgewinn gemacht haben. Rüdiger Weis, ruediger.weis@rz.uni-mannheim.de www.informatik.uni-mannheim.de/~rweis/ rsacrt/ SET auch durch The security protocol for safeguarding credit-card transactions on the Internet may have to be changed because the underlying cryptography is too easy to decode and too difficult to upgrade. Steve Mott, senior vice president of electronic commerce and new ventures for MasterCard International, said it could take hackers as little as a year to break the industry's standard encryption code, which is supposed to render credit-card numbers unreadable to outsiders on the Internet. For that reason, the consortium of technology companies and creditors that has spent two years years developing the Secure Electronic Transaction (SET) protocol may switch to a faster encryption system called Elliptic Curve, which is produced by <Certicom Corp>. The first complete version of SET, known as SET 1.0, will be available to software makers June 1 with core cryptography provided by RSA Data Security, a unit of Security Dynamics Technologies Inc <SDTI.O>. "RSA is a very good starting point. But we suspect that in a year or two, the Kevin Mitnicks of the world will start to figure out ways to hack it," Mott said, referring to Mitnick, a notorious computer hacker. "The only way you scale an RSA is to add a lot more bits. You add a lot more bits and it becomes more complex software in terms of the interaction of the transaction messages. That's part of what's taken SET so long to start with," he said. Mott told that the Elliptic Curve system would make a better encryption core. In fact, he said it would have been chosen in the first place if developers had been known about it. "It will fit on a chip card. I think its 160 bits equals security to 1,024 bits of RSA," the credit industry executive said. "We anticipate putting it intosome SET 1.0 pilots in the very near future this year in the U.S." Far from being disturbed by the possibility of hackers getting through the current SET cryptography, Mott said SET's developers would "give them an award and a ribbon and then embody whatever they did as part of the improvements" in the next version of security standards. "The current version for SET is as safe as anybody can make it," he said. (Nach 09.04.1997/Reuter)

[Datenschleuder] [59]    Abt. wundersame Dinge