Gezinkte Primzahlen ermöglichen Hintertüren in Verschlüsselung
Ein Forscherteam hat aufgezeigt, dass man durch geschickte Konstruktion einer Primzahl eine Hintertür in Verschlüsselungsverfahren einbauen kann. Nicht auszuschließen, dass dies bei etablierten Verfahren längst passiert ist.
(Bild: Gerald Himmelein)
Es klingt zuerst wie Mathematik für Nerds: Einem Forscherteam ist die Berechnung eines diskreten Logarithmus bezüglich einer 1024-bittigen Primzahl gelungen – in nur zwei Monaten Rechenzeit auf 2000 bis 3000 Kernen. Doch die Bedeutung des Papers A kilobit hidden SNFS discrete logarithm computation von Fried, Gaudry, Heninger und Thomé reicht viel weiter. Es zeigt nämlich auf, dass sich mit Hilfe geschickt konstruierter Primzahlen eine Hintertür in Verschlüsselungsverfahren einbauen lässt, die nach heutigem Stand der Forschung niemand entdecken kann. Ihrem Konstrukteur ermöglicht sie jedoch das unbemerkte Knacken der Verschlüsselung. Das wirft die Frage auf, ob das nicht längst geschehen ist und beispielsweise die NSA gezinkte Primzahlen in Verschlüsselungsstandards eingeschmuggelt hat.
Diskrete Logarithmen
Etliche aktuelle Verschlüsselungsverfahren, etwa der DSA-Algorithmus für digitale Signaturen oder der Diffie-Hellman-Schlüsseltausch beim HTTPS-Verbindungsaufbau, beruhen darauf, dass diskrete Logarithmen schwer zu berechnen sind. So schwer, dass selbst ein Angreifer mit Supercomputern Jahrtausende brauchen würde. Grundbaustein dieser Verfahren ist eine große Primzahl, die allgemein bekannt ist, und man führt alle Rechenoperationen modulo dieser Primzahl aus. Zu einem Exponenten a eine Potenz ga (mod p) zu berechnen, ist leicht, aber die Umkehrung – von gegebenem ga auf a zurückzuschließen – extrem schwierig.
Der beste bekannte Algorithmus hierfür nennt sich Number Field Sieve (NFS) und seine Komplexität, also die zu erwartende Rechenzeit in Abhängigkeit von der Größe der Primzahl p, ist gut erforscht. Daher weiß man, dass Primzahlen der Länge 1024 Bit bei der heute zur Verfügung stehenden Rechenleistung für viele Zwecke noch sicher genug sind: Aktuelle Schätzungen gehen davon aus, dass allenfalls ein Angreifer mit Spezialhardware im Wert von einigen hundert Millionen US-Dollar eine Chance hätte – eine Organisation wie die NSA etwa.
Schnelles Spezialsieb
Es gibt aber einen Algorithmus mit wesentlich geringerer Laufzeit, das Special Number Field Sieve (SNFS). Er benötigt als "geheime Zutaten" zwei irreduzible Polynome, die mit der Primzahl in einem ganz bestimmten mathematischen Zusammenhang stehen müssen. Man kann nun zunächst die geheimen Zutaten konstruieren und dann eine zu diesen passende Primzahl finden. Für diese Primzahl lassen sich dann mit dem SNFS-Algorithmus sehr viel schneller diskrete Logarithmen berechnen als mit dem normalen NFS – wenn man denn die geheimen Zutaten hat. Der umgekehrte Weg von einer x-beliebigen Primzahl p zu den geheimen Zutaten existiert nicht beziehungsweise man weiß, dass es ihn nur in sehr wenigen, seltenen Fällen gibt.
Man kann einer Primzahl also in der Regel nicht ansehen, ob sie "gezinkt" ist, also aus den geheimen Zutaten für einen SNFS-Algorithmus konstruiert wurde. Für verlässliche Kryptografie ist es deshalb wichtig, dass die verwendeten Primzahlen nachweisbar zufällig sind. Der Digital Signature Standard FIPS 186-4 des US-amerikanischen National Institute of Standards and Technology (NIST) beschreibt beispielsweise im Anhang ein Verfahren zur Erzeugung einer pseudo-zufälligen Primzahl aus einem Startwert (Seed) und empfiehlt, diesen zusammen mit der Primzahl zu veröffentlichen, um ihre Herkunft zu dokumentieren. Doch das ist nur eine Empfehlung, und so ist von den in freier Wildbahn vorkommenden Primzahlen nur in den wenigsten Fällen eine solche glaubwürdige Herkunft dokumentiert.
Rekordberechnung
Um die Machbarkeit eines Krypto-Angriffs mit gezinkten Primzahlen zu demonstrieren, konstruierten Fried et al. die geheimen Zutaten für einen SNFS-Algorithmus und eine dazu passende, 1024-bittige Primzahl, die allen üblichen kryptografischen Anforderungen genügt. Sie berechneten dann einen diskreten Logarithmus modulo dieser Primzahl – eine Aufgabe, die mit den ihnen zur Verfügung stehenden Ressourcen und dem normalen NFS-Algorithmus Jahrhunderte gedauert hätte. So aber konnten sie in mehreren Schritten auf Clustern aus 2000 bis 3000 Kernen die Berechnung in etwas mehr als zwei Monaten vollenden, was etwa 385 CPU-Jahren entspricht.
1024 Bit ade
Diese Forschung dokumentiert, dass es an der Zeit ist, sich von 1024-Bit-Primzahlen zu verabschieden und zu solchen mit mindestens 2048 Bit überzugehen. Diese sind selbst dann sicher, wenn sie gezinkt sind, denn auch der SNFS-Algorithmus hätte dann eine jahrhundertelange Laufzeit.
Lesen Sie auch zu dem Thema:
(bo)
