Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes

Stellen Sie sich das Internet als eine riesige, geschäftige Stadt vor, in der jeder versucht, geheime Nachrichten zu versenden. Um diese Nachrichten vor neugierigen Augen zu schützen, verwenden wir digitale Schlösser, die Verschlüsselung genannt werden. Lange Zeit haben Wissenschaftler diese Schlösser unter Verwendung komplexer mathematischer Rätsel gebaut, die einfach zu erstellen, aber unglaublich schwer zu lösen sind, wenn man nicht den Schlüssel besitzt. Vor kurzem wurde eine neue Art von Schloss vorgeschlagen, die eine spezielle Art von Mathematik verwendet, die mit Zahlengittern und dem „Rang“ (was nur ein schicker Begriff dafür ist, wie viel Information tatsächlich in dem Gitter steckt) zu tun hat. Die Schöpfer dieses neuen Schlosses dachten, sie hätten eine Schicht aus „Rauschen“ hinzugefügt – wie das Rauschen auf einem Radio –, um die wahre Form des Schlosses zu verbergen, sodass es für jeden, der versucht einzubrechen, wie ein zufälliges Chaos aussieht. Sie behaupteten, dieses neue Design sei so sicher, dass selbst ein superschneller Quantencomputer es nicht knacken könnte, und sie versprachen, es würde winzig und effizient sein, perfekt für die Zukunft der sicheren Kommunikation.

Doch genau wie ein Zaubertrick, der auf einer bestimmten Fingerfertigkeit beruht, hatte dieses neue Schloss einen verborgenen Fehler. Ein Forscher namens Thai Hung Le entdeckte, dass das „Rauschen“ die geheime Form nicht so gut verbarg, wie alle dachten. Durch eine geschickte Mischung aus Raten und algebraischer Detektivarbeit fand der Forscher einen Weg, die Schichten des statischen Rauschens abzuschält und die ursprüngliche, verborgene Struktur darunter freizulegen. Es ist, als hätte jemand ein Kartenhaus mit einem geheimen Bauplan gebaut, es in Nebel gehüllt, und dann festgestellt, dass man den Bauplan immer noch schwach erkennen kann, wenn man den Nebel nur aus dem richtigen Winkel betrachtet. Diese Entdeckung ist eine große Sache, denn sie bedeutet, dass die neuen Schlösser nicht so sicher sind wie beworben, und die Menschen, die sie entworfen haben, müssen ihre Baupläne überdenken, bevor sie damit beginnen, unsere Daten zu schützen.

Die große Entdeckung des Papers

In diesem Paper präsentiert Thai Hung Le eine neue Methode, um die „Enhanced Gabidulin Matrix Code“ (EGMC) Verschlüsselungsverfahren zu brechen. Diese Verfahren wurden kürzlich als ein Weg eingeführt, sehr kleine, effiziente Verschlüsselungsschlüssel zu erstellen, die Angriffen durch zukünftige Quantencomputer standhalten könnten. Die Sicherheit dieser Verfahren beruhte auf der Idee, dass, wenn man ein spezielles, strukturiertes Zahlengitter nimmt und zufällige Zeilen und Spalten hinzufügt (das „Rauschen“), es unmöglich wird, zwischen dem echten Code und einem völlig zufälligen Chaos zu unterscheiden.

Der Autor zeigt, dass diese Annahme falsch ist. Anstatt zu versuchen, jede mögliche Möglichkeit, das Rauschen zu entfernen, durch Brute-Force zu testen (was ewig dauern würde), führt das Paper einen „Hybrid“-Angriff ein. Stellen Sie sich vor, Sie versuchen, ein bestimmtes Muster in einem riesigen, zerstückelten Mosaik zu finden. Der alte Weg war, die Position jeder einzelnen Kachel zu erraten. Diese neue Methode ist klüger: Sie rät die Position von nur einer einzigen Reihe von Kacheln und nutzt dann die Mathematik, um sofort zu bereenchnen, wo der Rest der Kacheln liegen muss.

Das Paper beschreibt zwei Hauptwege, dies zu tun:

1. Das Erraten der Spalten: Der Angreifer rät, wie die Spalten des Gitters vertauscht wurden, und nutzt dann die Algebra, um zu berechnen, wie die Zeilen vertauscht wurden.
2. Das Erraten der Zeilen: Der Angreifer rät, wie die Zeilen des Gitters vertauscht wurden, und löst dann die Spalten.

Sobald der Angreifer die Vertauschung herausgefunden hat, kann er das zufällige Rauschen entfernen und die ursprüngliche, verborgene Struktur offenlegen. Das Paper beweist, dass diese Struktur ein „Gabidulin-Code“ ist, eine Art von mathematischem Rätsel, das eigentlich recht einfach zu lösen ist, sobald man das geheime Muster kennt.

Was das Paper tatsächlich bricht

Der Autor findet nicht nur einen kleinen Riss; er zertrümmert das ganze Fenster. Das Paper demonstriert, dass dieser Angriff gegen alle 16 der vorgeschlagenen Parametersätze der EGMC-Verschlüsselungsverfahren funktioniert. Das bedeutet, dass jede Version des Schlosses, die zur Verwendung vorgeschlagen wurde, nun als gebrochen gilt.

Um Ihnen ein Gefühl für die Effektivität zu geben, betrachtet das Paper einen spezifischen Satz von Zahlen, der eigentlich eine 128-Bit-Sicherheit bieten sollte (ein Standardniveau an Sicherheit). Der Autor zeigt, dass sein Angriff das Sicherheitsniveau auf nur 35 Bit reduziert. In der Welt der Verschlüsselung ist das so, als würde man von einem Tresor mit einer Millionstelligen Kombination zu einem Schloss übergehen, das ein Kind in Sekunden knacken kann.

Das Paper liefert ein konkretes Beispiel für diese Kraft: Mit ihrer Methode waren die Forscher in der Lage, den geheimen Schlüssel für dieses 128-Bit-Sicherheitsniveau in weniger als 10 Minuten zu rekonstruieren. Dies war nicht nur eine theoretische Idee; sie haben tatsächlich ein Computerprogramm entwickelt, um dies zu tun.

Was das Paper ausschließt

Es ist wichtig anzumerken, was dieses Paper nicht aussagt. Der Autor erklärt, dass frühere Versuche, diese Codes zu brechen, auf „kombinatorischen“ Methoden beruhten, bei denen sowohl die Zeilen- als auch die Spaltenvertauschungen gleichzeitig geraten werden. Das Paper argumentiert, dass dieser alte Weg im Vergleich zu ihrem neuen „Hybrid“-Ansatz zu langsam und ineffizient ist.

Darüber hinaus argumentiert das Paper dagegen, dass es ausreichen würde, die Parameter einfach größer zu machen (mehr Rauschen hinzuzufügen), um das Problem für alle Fälle zu lösen. Der Autor zeigt, dass für bestimmte Typen dieser Codes – speziell wenn einer der Rauschfaktoren (entweder die Anzahl der zusätzlichen Zeilen oder die Anzahl der zusätzlichen Spalten) Null ist – der Angriff so schnell wird, dass er in „Polynomialzeit“ abläuft. Das bedeutet, dass der Angriff in diesen spezifischen Fällen selbst dann noch schnell genug sein wird, um das Schloss zu knacken, egal wie sehr man die Größe des Schlosses erhöht. Der einzige Weg, dies potenziell zu beheben, wäre laut dem Paper, das grundlegende Design so zu ändern, dass beide Rauschfaktoren ungleich Null und groß genug sind, um den Angriff zu stoppen, aber der Autor warnt, dass dies die Schlüssel und Nachrichten zu groß und damit unbrauchbar machen könnte.

Wie sicher sind sie sich?

Das Paper ist sehr zuversichtlich in seinen Ergebnissen. Der Autor hat nicht nur geraten; er hat einen vollständigen mathematischen Beweis für die Funktionsweise seines Angriffs geliefert und diesen durch eine funktionierende Computerimplementierung untermauert. Er stellt explizit fest, dass sein Angriff alle vorgeschlagenen Versionen des Schemas bricht. Er vergleicht seine Ergebnisse auch mit früheren Angriffen und zeigt dabei auf, dass seine Methode signifikant schneller und leistungsfähiger ist. Das Paper kommt zu dem Schluss, dass die EGMC-Verschlüsselungsverfahren nicht mehr sicher für den Einsatz sind und die Sicherheitsgemeinschaft zu anderen Designs übergehen muss.