Full-Key Recovery and Forgery from One MQOM v2.1 Signature

Stellen Sie sich vor, Sie versuchen, eine geheime Nachricht an einen Freund zu senden, aber Sie leben in einer Welt, in der eines Tages Supercomputer (genannt Quantencomputer) existieren könnten. Diese zukünftigen Maschinen könnten die meisten Schlösser, die wir heute verwenden, um unsere Geheimnisse zu bewahren, knacken. Um dem vorzubereugen, bauen Wissenschaftler neue, superstarke digitale Schlösser, die „Post-Quantum-Signaturen“ genannt werden. Denken Sie an diese wie an ein spezielles Wachssiegel auf einem Brief. Selbst wenn ein Dieb einen magischen Hammer hat, der normale Schlösser zertrümmert, sollte dieses neue Wachssiegel aus einem Material bestehen, das standhalten kann.

Eines der vielversprechendsten neuen Schlösser, die getestet werden, heißt MQOM. Es funktioniert ein wenig wie ein riesiges, komplexes Rätsel. Um einen Brief zu signieren, verwendet der Absender ein geheimes „Zeugen“ (einen verborgenen Schlüssel), um ein mathematisches Problem mit vielen Variablen zu lösen. Um zu beweisen, dass er das Problem gelöst hat, ohne das Geheimnis zu verraten, nutzt er einen cleveren Trick namens „MPC-in-the-head“. Stellen Sie sich vor, der Absender tut so, als wäre er ein ganzes Team von Menschen, von denen jeder ein winziges Stück des Geheimnisses hält. Sie spielen ein Spiel, bei dem sie gerade genug offenlegen, um zu beweisen, dass das Team das Rätsel gemeinsam gelöst hat, aber nicht genug, um die eigentlichen Geheimnisstücke zu verraten. Wenn die Mathematik stimmt, ist die Signatur gültig. Wir kümmern uns darum, weil wir, falls diese neuen Schlösser einen verborgenen Riss haben, unsere zukünftige digitale Sicherheit gefährdet sein könnte, noch bevor wir dort ankommen.

Lassen Sie uns nun über die Geschichte in dieser Arbeit sprechen. Ein Forscher namens José Luis Delgado hat eine spezifische Version dieses MQOM-Schlosses (Version 2.1) genau untersucht und einen überraschend einfachen Weg gefunden, es zu knacken. Die Arbeit argumentiert, dass, wenn ein Angreifer nur eine einzige gültige Signatur des Systems erhält, er den gesamten geheimen Schlüssel herausfinden und neue Signaturen für jede beliebige Nachricht fälschen kann. Es ist, als ob ein Dieb einmal zusieht, wie Sie Ihre Haustür öffnen, und dieser eine Blick ausreicht, um einen Generalschlüssel zu bauen, der jedes Schloss in Ihrem Haus öffnet.

So funktioniert der „Zaubertrick“: Stellen Sie sich vor, der geheime Schlüssel ist eine lange, verborgene Schatzkarte. Das MQOM-System versteckt diese Karte innerhalb eines riesigen Baumes aus Ästen. Wenn Sie eine Nachricht signieren, zeigt Ihnen das System einen Pfad nach oben auf den Baum zu einem bestimmten verborgenen Blatt (einem Punkt auf der Karte), aber es hält das Blatt selbst bedeckt. Es gibt Ihnen jedoch auch einen „Geschwisterpfad“ – eine Liste der Äste neben dem verborgenen Blatt. Da der Baum so aufgebaut ist, können Sie durch die Kenntnis der Äste neben dem Blatt genau bestimmen, was das verborgene Blatt sein müsste, wenn Sie ein kleines Präfix der geheimen Karte kennen würden.

Die Arbeit entdeckte, dass das System zusätzlich eine „Commitment“ hinterlässt, was wie ein versiegelter Umschlag ist, der das verborgene Blatt enthält. Der Forscher erkannte, dass sie durch die Kombination des Geschwisterpfades (der Äste) mit dem versiegelten Umschlag eine einzige, riesige Gleichung aufschreiben können. Diese Gleichung hat eine Unbekannte: das kleine Präfix der geheimen Karte. Der Angreifer muss nicht die ganze Karte erraten; er muss nur diese eine Gleichung lösen, um dieses kleine Präfix zu finden.

Sob also dieses Präfix, liefert Ihnen die bereits vorhandene Signatur ein „Korrektur-Suffix“ – eine kleine Notiz, die besagt: „Hier ist der Rest der Karte, der zum Präfix passt, den du gerade gefunden hast.“ Indem der Angreifer das Präfix und die Notiz zusammenfügt, rekonstruiert er die gesamte geheime Karte (den vollständigen Signierschlüssel). Mit diesem Schlüssel kann er jede neue Nachricht signieren, und das System wird dies als echt akzeptieren.

Die Arbeit rät nicht nur, dass dies funktioniert; sie hat die Mathematik und die Computerarbeit tatsächlich durchgeführt, um zu beweisen, dass es so ist. Sie berechneten genau, wie viel Rechenleistung erforderlich wäre, um diese Gleichung für die verschiedenen Sicherheitsstufen des Schlosses (genannt Kategorien I, III und V) zu lösen. Sie fanden heraus, dass für alle drei Kategorien der Aufwand, der zur Lösung erforderlich ist, geringer ist als das Sicherheitslimit, das NIST für diese Schlösser festgelegt hat.

Für die einfachste Stufe (Kategorie I) dauert der Angriff etwa $2^{142,335112}$ Operationen. Für die mittlere Stufe (Kategorie III) dauert es etwa $2^{206,774558}$ oder $2^{206,988658}$ Operationen, je nachdem, wie viel der Karte sie scannen. Für die härteste Stufe (Kategorie V) dauert es etwa $2^{271,794162}$ Operationen. In jedem Fall ist die Anzahl der Schritte, die ein Angreifer benötigt, niedriger als die Anzahl der Schritte, die das Schloss eigentlich erfordern sollte, um sicher zu sein.

Die Forscher haben sich nicht nur mit der Mathematik begnügt. Sie haben ein Computerprogramm gebaut, das den Angriff tatsächlich durchführt. Sie nahmen eine echte Signatur, lösten die Gleichung, stellten den exakten geheimen Schlüssel Byte für Byte wieder her und nutzten diesen Schlüssel dann, um eine brandneue Nachricht zu signieren. Der Verifizierer des Systems prüfte die neue Signatur und sagte: „Ja, dies ist gültig!“ Dies bewies, dass der Angriff in der realen Welt funktioniert, nicht nur auf dem Papier.

Die Arbeit untersuchte auch, ob die Änderung einiger Einstellungen das Problem lösen würde. Sie fanden heraus, dass das bloße Hinzufügen eines „Salzes“ (einer Zufallszahl) zum Prozess zwar die Zahlen in der Gleichung ändert, den Angriff aber nicht stoppt. Die Gleichung existiert weiterhin; sie sieht nur etwas anders aus. Um dies wirklich zu beheben, müssten die Designer ändern, wie der Baumpfad mit dem Geheimnis zusammenhängt, wie das Blatt committet wird oder wie die Korrekturnotiz generiert wird.

Kurz gesagt zeigt diese Arbeit, dass das aktuelle MQOM-Schloss ein Loch hat, das groß genug ist, um hindurchzugehen. Sie verwandelt eine einzige Signatur in einen Generalschlüssel, der es einem Angreifer ermöglicht, Nachrichten mit weniger Aufwand zu fälschen, als das Schloss zu leisten vorgesehen war. Der Autor hat seine Codes und Ergebnisse geteilt, damit andere ihre Arbeit überprüfen können, und legt nahe, dass die Designer von MQOM diese spezifischen Teile des Systems patchen müssen, bevor es als sicher für die Zukunft betrachtet werden kann.