Zehn Jahre Desktop-Computer, Single-Core-Quantenverschlüsselungsalgorithmus in einer Stunde geknackt, Kryptograph: Es kommt zu plötzlich

Zukünftige Quantencomputer könnten die moderne Kryptographie schnell durchbrechen. Deshalb haben Mathematiker und Kryptografen nach geeigneten neuen Verschlüsselungsalgorithmen gesucht, um Quantencomputerangriffen zu widerstehen. Diese neue Generation kryptografischer Algorithmen, die Quantencomputerangriffen auf bestehende kryptografische Algorithmen widerstehen können, wird als „Post-Quanten-Kryptografie (PQC, Postquanten-Kryptografie)“-Algorithmus bezeichnet.

Aber kürzlich haben Forscher der Universität Leuven in Belgien herausgefunden, dass ein vielversprechender PQC-Verschlüsselungsalgorithmus in nur 1 Stunde vollständig geknackt werden kann (Teilversion dauert nur 4 Minuten). knacken). Das Problem ist, dass dieser Rekord nicht von einem High-End-Computer aufgestellt wurde, sondern von einem Desktop-Computer mit einer zehn Jahre alten CPU, die auf einem einzigen Kern läuft. Forscher sagen, dass dieser jüngste und überraschende Misserfolg die vielen Hürden verdeutlicht, die die Post-Quanten-Kryptographie überwinden muss, bevor sie eingeführt werden kann.

Papierlink: https://eprint.iacr.org/2022/975#🎜 🎜#

Theoretisch können Quantencomputer schnell Probleme lösen, für deren Lösung herkömmliche Computer viel Zeit benötigen würden. Beispielsweise stützt sich die moderne Kryptographie stark auf die extremen Schwierigkeiten, mit denen klassische Computer bei der Bewältigung komplexer mathematischer Probleme wie der Faktorisierung großer Zahlen konfrontiert sind. Und Quantencomputer könnten im Prinzip Algorithmen ausführen, die eine solche Verschlüsselung schnell knacken könnten.

Um dieser Bedrohung zu begegnen, haben Kryptographen auf der ganzen Welt 20 Jahre damit verbracht, Post-Quanten-Verschlüsselungsalgorithmen zu entwickeln. Diese Algorithmen basieren auf neuen mathematischen Problemen, die sowohl für Quantencomputer als auch für klassische Computer schwer zu lösen sind.

Seit Jahren untersuchen Forscher an Institutionen wie dem National Institute of Standards and Technology (NIST), welche PQC-Algorithmen zu neuen Standards werden sollen, die die Welt übernehmen kann. Die Agentur gab 2016 bekannt, dass sie Kandidaten für PQC-Algorithmen sucht und erhielt 2017 82 Vorschläge. Anschließend, nach drei Überprüfungsrunden, kündigte NIST vier Algorithmen an, die bald zum Standard werden werden, und vier weitere, die als mögliche Kandidaten in die nächste Überprüfungsrunde eintreten werden.

Die Überprüfung ist noch nicht einmal abgeschlossen, und einer der Konkurrenten ist ausgefallen und wurde durch einen 10 Jahre alten Desktop kompromittiert. Der Algorithmus heißt SIKE (Supersingular Isogeny Key Encapsulation) und wurde von Microsoft, Amazon, Cloudflare und anderen untersucht. Christopher Peikert, Kryptograph an der University of Michigan, Ann Arbor, sagte: „Dieser Angriff kam so plötzlich, dass es sich um eine Wunderwaffe handelte (eine Lösung mit äußerster Wirksamkeit).“ ist der SIKE-Algorithmus?

SIKE ist eine Familie von PQC-Algorithmen mit elliptischen Kurven. „Elliptische Kurven sind seit langem Gegenstand der Untersuchung von Mathematikern“, sagt Dustin Moody, Mathematiker am NIST. „Sie werden durch eine Gleichung ähnlich y^2 = x^3 + Ax + B beschrieben, wobei A und B Zahlen sind. Eine elliptische Kurve kann beispielsweise y^2 = x^3 + 3x + 2 sein.“ 🎜 🎜#

Im Jahr 1985 „fanden Mathematiker einen Weg, kryptografische Systeme mit elliptischen Kurven zu erstellen, die heute weit verbreitet sind“, sagte Moody. „Diese Kryptosysteme mit elliptischen Kurven sind jedoch anfällig für Angriffe von Quantencomputern.“ Man geht davon aus, dass diese neue Idee nicht anfällig für Angriffe von Quantencomputern ist.

Diese neue Methode basiert auf der Frage: Wie fügt man zwei Punkte auf einer elliptischen Kurve hinzu, um einen weiteren Punkt auf der elliptischen Kurve zu erhalten? Das „Isogenie“ im Namen des Algorithmus bedeutet Homologie, eine Abbildung von einer elliptischen Kurve auf eine andere, die das Additionsgesetz bewahrt.

„Wenn man diese Zuordnung komplex genug macht, besteht die Herausforderung der Datenverschlüsselung darin, dass es bei gegebenen zwei elliptischen Kurven schwierig ist, den Unterschied zwischen ihnen zu finden Homologie, ", sagte der Co-Autor der Studie, Thomas Decru, ein mathematischer Kryptograph an der Universität Leuven in Belgien.

SIKE ist eine Form der homologiebasierten Kryptographie, die auf dem Schlüsselaustauschprotokoll Super Singular Homology Diffie-Hellman (SIDH) basiert. „SIDH/SIKE ist eines der frühesten praktischen herkunftsbasierten Verschlüsselungsprotokolle“, sagte Decru.

Eine Schwäche von SIKE ist jedoch diese: Damit es funktioniert, muss es der Öffentlichkeit zusätzliche Informationen zur Verfügung stellen, nämlich Hilfsdrehpunkte. „Gegner versuchen seit einiger Zeit, diese zusätzlichen Informationen auszunutzen, konnten sie jedoch nicht nutzen, um SIKE zu besiegen“, sagte Moody. „Aber dieses neue Papier hat einen Weg gefunden, indem es einige ziemlich fortgeschrittene mathematische Methoden verwendet.“

Um diesen neuen Angriff zu erklären, sagte Decru, dass elliptische Kurven zwar eindimensionale Objekte seien, elliptische Kurven in der Mathematik jedoch als zweidimensionale oder beliebige andere dimensionale Objekte visualisiert werden könnten. Man kann auch Homologe zwischen diesen verallgemeinerten Objekten erstellen.

Durch die Anwendung eines 25 Jahre alten Theorems nutzt der neue Angriff die von SIKE bereitgestellten zusätzlichen Informationen, um eine zweidimensionale Homologie zu konstruieren. Diese Homologie kann dann verwendet werden, um den Schlüssel zu rekonstruieren, den SIKE zum Verschlüsseln der Nachricht verwendet.

„Das Überraschendste für mich ist, dass dieser Angriff aus dem Nichts zu kommen schien“, sagte Jonathan Katz, Kryptograph an der University of Maryland, College Park. Obwohl er nicht an der neuen Forschung beteiligt war, sagte er: „Es gab nur sehr wenige Ergebnisse, die darauf hinwiesen, dass SIKE irgendwelche Schwächen aufweist, und dieses Ergebnis bringt plötzlich einen völlig verheerenden Angriff auf SIKE mit sich, weil es den vollständigen Schlüssel findet. Und der wurde schnell gefunden.“ ohne Quantencomputing. „

Der Angriff dauerte mehr als zehn Jahre und das Knacken dauerte vier Minuten. Mit einem Algorithmus, der auf der oben genannten neuen Angriffsmethode basierte, fanden Forscher heraus, dass eine Maschine mit einem Computer ausgestattet war, der dauerte zehn Jahre“ Es dauert nur mindestens 4 Minuten, bis ein Desktop-Computer mit einer „alten“ CPU (Intel Algorithmus, der den NIST-Quantensicherheitsstandard 62 Minuten erfüllt. Diese Experimente werden auf einem Kern der CPU ausgeführt.

„Normalerweise ereignen sich schwerwiegende Angriffe auf kryptografische Systeme kurz nachdem das System vorgeschlagen wurde oder wenn das System zum ersten Mal die Aufmerksamkeit aller auf sich zieht. Mit der Zeit werden die Angriffe nach und nach stärker oder schwächen das System deutlich ab. Aber es gab sie.“ Keine Warnung für diesen Angriff, und das Kryptosystem sei plötzlich völlig kaputt, sagte Peikert: „Seitdem SIDH zum ersten Mal vorgeschlagen wurde, gab es bis zu diesem vollständigen Durchbruch fast keine Fortschritte.“ Forscher testen SIKE seit mehr als einem Jahrzehnt. Einer der Gründe, warum SIKE nicht als Standard ausgewählt wurde, war die Sorge, dass es zu neu und nicht ausreichend erforscht sei. Steven Galbraith, Mathematiker an der University of Auckland, sagte: „Die Leute waren besorgt, dass SIKE einem größeren Angriff ausgesetzt sein könnte, und es stellte sich heraus, dass sie Recht hatten.“ Warum wurde also bisher keine Schwachstelle in SIKE entdeckt? Galbraith glaubt, dass ein wichtiger Grund darin besteht, dass der neue Angriff „sehr fortgeschrittene Mathematik anwendet“. Katz stimmte zu und sagte: „Ich vermute, dass es weniger als 50 Menschen auf der Welt gibt, die sowohl über die zugrunde liegende Mathematik von PQC als auch über die erforderlichen Kryptographiekenntnisse verfügen.“ Darüber hinaus sagte David Joseph, ein Kryptograf beim PQC-Startup Sandbox AQ, sagte einmal: „Sowohl aus Sicht der Umsetzung als auch aus theoretischer Sicht ist das gleiche Ursprungsproblem „notorisch schwierig“, was die Wahrscheinlichkeit erhöht, dass seine grundlegenden Mängel später entdeckt werden.“ Darüber hinaus „sollte auch beachtet werden.“ „Bevor das NIST mehrere Screening-Überprüfungsrunden durchführte, standen viele PQC-Algorithmen für die Analyse zur Verfügung, sodass die Forschungsanstrengungen verstreut waren. Nach mehreren Screening-Runden konnten sich die Forscher auf eine kleine Anzahl von Algorithmen konzentrieren“, sagte Joseph.

David Jao, einer der Erfinder von SIKE und Professor an der University of Waterloo in Kanada, sagte: „Ich denke, dieses neue Ergebnis ist eine erstaunliche Arbeit, und ich gebe den Autoren das höchste Lob. Zuerst habe ich war skeptisch gegenüber dem Knacken von SIKE. Traurig, weil es mathematisch eine so elegante Lösung ist und eine Schwäche gefunden. Es hat über 10 Jahre gedauert, bis sie die Schwäche gefunden haben, was ungewöhnlich ist, aber ansonsten nicht über den Bereich des gewöhnlichen wissenschaftlichen Fortschritts hinausgeht“, fügte David Jao hinzu.

Nach Jaos Meinung ist es gut, dass SIKE jetzt geknackt wurde, schließlich wurde es noch nicht weit verbreitet.

Was bedeutet es, wenn SIKE geknackt ist?

SIKE ist der zweite NIST-PQC-Kandidatenalgorithmus, der dieses Jahr geknackt wurde. Im Februar dieses Jahres gab Ward Beullens, Kryptograph bei IBM Research in Zürich, bekannt, dass er seinen Laptop zum Knacken des Rainbow-Algorithmus verwenden könne, der an der dritten Runde der NIST-Überprüfung teilnahm. „Dies deutet darauf hin, dass alle PQC-Optionen weiterer Untersuchungen bedürfen“, sagte Katz.

Moody wies jedoch darauf hin, dass SIKE zwar geknackt wurde, andere auf Homologie basierende Kryptosysteme wie CSIDH oder SQIsign jedoch nicht geknackt wurden „Tot, aber das ist bei weitem nicht der Fall, und ich denke, es gibt noch viel mehr zu lernen in der homologiebasierten Kryptographie“, sagte Decru.

Darüber hinaus spiegelt diese neue Arbeit möglicherweise nicht das Niveau der PQC-Forschung des NIST wider. Wie Decru feststellte, war SIKE das einzige homologiebasierte Kryptosystem unter den 82 Vorschlägen, die NIST erhalten hatte, und Rainbow war unter diesen Einreichungen der einzige multivariate Algorithmus.

Die Algorithmen, die vom NIST als „Standards“ übernommen werden oder in die vierte Überprüfungsrunde gehen, basieren auf mathematischen Ideen, die von Kryptographen seit langem untersucht und analysiert werden Zeit. sagte Galbraith. „Es garantiert nicht, dass sie sicher sind, es bedeutet nur, dass sie Angriffen länger standhalten.“ Moody stimmte zu und bemerkte, dass „immer einige erstaunliche Durchbrüche gefunden werden, um Kryptosysteme zu knacken. Das Beste, was wir über jedes Kryptosystem sagen können, ist, dass nach einer Weile.“ „

„Unsere Programme sind so konzipiert, dass sie Angriffe und Cracks zulassen“, sagte Moody. „Wir haben sie in jeder Evaluierungsrunde gesehen. Nur so kann man Vertrauen in die Sicherheit gewinnen.“ Galbraith stimmte zu und stellte fest, dass Studien wie diese „funktionieren“.

Trotzdem denke ich, dass der Niedergang von Rainbow und SIKE mehr Menschen dazu bringen wird, ernsthaft darüber nachzudenken, ob es einen Bedarf für irgendwelche Probleme gibt, die im NIST-Post-Quantum auftreten „Gewinner erstellen Backup-Pläne“, sagte Decru. „Es könnte zu riskant sein, sich ausschließlich auf ein mathematisches Konzept oder Schema zu verlassen. Dies ist auch die eigene Denkweise von NIST – ihr Hauptschema basiert wahrscheinlich auf Gitterkryptographie (gitterbasiert), aber sie wollen ein Nicht-Gitter-Kryptographieschema, um Decru vorzubereiten.“ stellte fest, dass andere Forscher mit der Entwicklung neuer Versionen von SIDH/SIKE begonnen haben, von denen sie glauben, dass sie diese neue Art von Angriff verhindern könnten. „Ich hatte erwartet, was passieren würde, wenn die Angriffe eskalierten und die Leute versuchten, SIDH/SIKE zu patchen“, sagte Decru.

Alles in allem zeigt sich, dass der Ausgangspunkt dieses neuen Angriffs ein Theorem ist, das „überhaupt nichts mit Kryptographie zu tun hat“ und „die Notwendigkeit offenbart“. für rein mathematische Grundlagenforschung zum Verständnis der Kryptographie. „Systembedeutung“, sagte Galbraith.

Decru stimmt zu: „In der Mathematik ist nicht alles sofort auf eine reale Situation anwendbar.“ Das bedeutet nicht, dass wir nicht zulassen sollten, dass die Forschung zu diesen obskureren Themen führt.“

Das obige ist der detaillierte Inhalt vonZehn Jahre Desktop-Computer, Single-Core-Quantenverschlüsselungsalgorithmus in einer Stunde geknackt, Kryptograph: Es kommt zu plötzlich. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!