💻 computer science

GCD: Garbled, Corrected, Demonstrandum -- Fixing and Proving Go's Extended GCD Implementation

Diese Arbeit identifiziert und behebt zwei kritische Abweichungen in der Implementierung des erweiterten euklidischen Algorithmus in Go, welche die RSA-Schlüsselerzeugung gefährden, beweist anschließend die Korrektheit und Terminierung des korrigierten Codes unter Verwendung der Verifizierungswerkzeuge Gobra und Lean und demonstriert dabei, wie KI-Agenten bei der Verfeinerung formaler Beweise unterstützen können.

Ursprüngliche Autoren: Linard Arquint

Veröffentlicht 2026-06-05

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Linard Arquint

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie bauen einen hochsicheren digitalen Tresor (wie sie für Online-Banking oder sichere Nachrichten verwendet werden). Um diesen Tresor zu sperren und zu entsperren, benötigen Sie einen sehr spezifischen, komplexen mathematischen Schlüssel. In der Welt der Informatik wird dieser Schlüssel mit einem Rezept namens Extended Greatest Common Divisor (GCD) Algorithmus generat.

Dieses Papier handelt von einem Forscherteam, das in die „Küche“ der Programmiersprache Go (einem populären Werkzeug zum Bau von Software) gegangen ist, um zu prüfen, ob das Rezept für diesen Schlüssel korrekt befolgt wurde. Sie fanden heraus, dass das Rezept leicht verändert worden war, und sie haben es korrigiert, während sie gleichzeitig mathematisch bewiesen haben, dass die neue Version perfekt funktioniert.

Hier ist die Geschichte ihrer Entdeckung, unterteilt in einfache Teile:

1. Der „Copy-Paste“-Fehler

Die Go-Entwickler wollten ihre Software aktualisieren, um strengen staatlichen Sicherheitsstandards zu entsprechen. Dazu haben sie ein Rezept aus einer vertrauenswürdigen, bekannten Quelle namens BoringSSL (einer sicheren Bibliothek, die von Google verwendet wird) genommen und es nach Go „portiert“ (übersetzt).

Stellen Sie sich das wie einen berühmten Koch vor, der Ihnen ein geheimes Kuchenrezept gibt. Sie entscheiden sich, das Rezept in Ihrer eigenen Handschrift neu zu schreiben, um es leichter lesbar zu machen. Das Papier behauptet, dass die Go-Entwickler beim Umschreiben versehentlich zwei wichtige Schritte geändert haben.

Das Problem: Das Originalrezept hatte eine strikte Regel: „Wenn Sie diese zwei Zahlen addieren und das Ergebnis zu groß ist, müssen Sie von beiden Zahlen zur exakt gleichen Zeit einen spezifischen Betrag abziehen.“ Dies verhindert, dass der Kuchen in sich zusammenbricht.
Der Bug: Die Go-Version führte diese „zu groß“-Prüfung separat für jede Zahl durch. Es war, als würde man Mehl und Zucker unabhängig voneinander prüfen. Dies zerstörte das mathematische Gleichgewicht (die „Invarianten“), das garantiert, dass der Schlüssel korrekt ist.
Die Überraschung: Drei verschiedene menschliche Experten überprüften den Code und übersahen diesen Fehler. Er war so subtil, dass er durch das Netz glitt.

2. Die „Zu groß“-Zutat

Das zweite Problem betraf die Größe der erlaubten Zutaten.

Die Regel: Das Originalrezept besagte: „Die erste Zutat muss immer kleiner als die zweite sein.“
Die Änderung: Die Go-Version erlaubte es der ersten Zutat, größer als die zweite zu sein.
Die Lösung: Die Forscher mussten den Code für dieses Problem nicht ändern. Stattdessen mussten sie den „Beweis“ (die mathematische Garantie) aktualisieren, um zu zeigen, dass das Rezept auch mit größeren Zutaten funktioniert.

3. Der magische Detektiv (Gobra)

Um zu beweisen, dass sie die Bugs behoben hatten, nutzten die Forscher ein Werkzeug namens Gobra.

Die Analogie: Stellen Sie sich einen superstrengen, hyperaufmerksamen Roboter-Inspektor vor. Sie füttern ihn mit dem Code und einer Liste von Regeln (Spezifikationen). Der Roboter führt den Code nicht nur aus; er simuliert jeden möglichen Weg, auf dem der Code ablaufen könnte, und prüft jeden einzelnen Pfad, um sicherzustellen, dass er niemals gegen die Regeln verstößt.
Das Ergebnis: Der Roboter bestätigte, dass der Code, sobald der „Synchronisations-Bug“ behoben wurde, zu 100 % korrekt war. Tatsächlich lief der neue Code, da die Korrektur unnötige Schritte entfernte, sogar 24 % schneller als die fehlerhafte Version.

4. Der KI-Assistent

Die Forscher haben die ganze schwere Arbeit nicht allein erledigt. Sie nutzten einen KI-Agenten (ein intelligentes Computerprogramm), um ihnen zu helfen.

Wie es funktionierte: Die KI agierte wie ein unermüdlicher Lehrling. Wenn der Roboter-Inspektor (Gobra) sagte: „Dieser Teil ergibt keinen Sinn“, schlug die KI Änderungen an den Regeln oder dem Code vor.
Der Haken: Die KI ging anfangs davon aus, dass der Code perfekt sei, und versuchte, die Mathematik passend zu machen. Die menschlichen Forscher mussten der KI sagen: „Nein, der Code ist tatsächlich falsch; suche nach dem Unterschied.“ Sobald die KI dies verstand, wurde sie unglaublich hilfreich, indem sie Korrekturen vorschlug und half, die mathematischen Beweise zu schreiben.

5. Das Fazit

Das Papier kommt zu drei Hauptlektionen:

Selbst Experten machen subtile Fehler: Drei menschliche Prüfer übersahen einen kritischen Bug, den ein formaler Beweis-Tool fand.
Formale Verifikation ist mächtig: Die Verwendung eines Werkzeugs wie Gobra ist wie eine mathematische Garantie dafür, dass Ihr Code funktioniert, anstatt nur zu hoffen, dass er funktioniert, weil er einige Tests bestanden hat.
KI ist ein großartiger Partner: KI kann Menschen helfen, diese komplexen Beweise zu schreiben, aber Menschen müssen die KI dennoch anleiten, den Code zu hinterfragen, anstatt ihn einfach nur zu akzeptieren.

Kurz gesagt: Die Forscher fanden einen verborgenen Fehler in einem kritischen Sicherheitsalgorithmus in der Go-Standardbibliothek, behoben ihn, bewiesen mathematisch, dass die Korrektur funktioniert, und zeigten, dass die Korrektur die Software sogar schneller gemacht hat. Dies taten sie durch eine Kombination aus menschlicher Einsicht, automatisierten Beweiswerkzeugen und KI-Unterstützung.

Technisches Resümee: GCD: Garbled, Corrected, Demonstrandum

Problemstellung

Die Arbeit befasstst sich mit der Korrektheit und Verifizierung der Implementierung des erweiterten euklidischen Algorithmus (Extended GCD) innerhalb der Go-Standardbibliothek (crypto/internal/fips140/bigmod). Diese Implementierung ist kritisch für die RSA-Schlüsselpaargenerierung, eine fundamentale Komponente für TLS, SSH und PGP. Die Go-Implementierung wurde in Go 1.24 eingeführt, um die FIPS 140-3-Konformität nativ zu unterstützen und die Abhängigkeit von BoringSSL zu ersetzen.

Die Autoren identifizierten eine kritische Diskrepanz: Obwohl der Go-Code als direkter Port der BoringSSL-Implementierung (die mittels des Rocq-Proof-Assistants Fiat Cryptography formal verifiziert ist) deklariert wurde, enthielt die Go-Version subtile Abweichungen. Diese Abweichungen wurden von drei separaten Code-Reviews nicht erkannt. Die Abweichungen brachen die mathematischen Invarianten des Algorithmus, was potenziell die Korrektheit der Berechnung des modularen Inversen, das für RSA-Private-Keys erforderlich ist, gefährdete. Darüber hinaus erlaubte die Go-Implementierung einen größeren Eingabebereich als die bewiesene BoringSSL-Version, was die bestehenden Beweisannahmen ungültig machte.

Methodik

Die Autoren verwendeten einen deduktiven Programmverifikationsansatz unter Verwendung von Gobra, einem auf Separation Logic basierenden Verifizierer für Go. Die Methodik umfasste:

Formale Spezifikation: Die Autoren formalisierten die natürlichen Sprachspezifikationen der Go-Funktionen (extendedGCD, InverseVarTime, GCDVarTime) in Gobra-Spezifikationen, einschließlich Vorbedingungen, Nachbedingungen und Schleifeninvarianten.
Abweichungsanalyse: Durch den Versuch, den bestehenden Go-Code gegen die aus dem BoringSSL-Beweis abgeleiteten Spezifikationen zu verifizieren, identifizierten die Autoren zwei Hauptklassen von Abweichungen:
- Unsynchronisierte Subtraktionen: Die Go-Implementierung aktualisierte die Bézout-Koeffizienten ( $A, B, C, D$ ) unabhängig basierend auf lokalen Bedingungen, während die Referenzimplementierung synchronisierte Reduktionen erforderte, um die Schleifeninvarianten aufrechtzuerhalten.
- Erweiterung des Eingabebereichs: Die Go-Implementierung erlaubte Eingaben, bei denen $a \ge n$ gilt, was die Vorbedingung $a < n$ der ursprünglichen Beweisführung verletzte.
Beweiskonstruktion:
- Code-Fix: Die Autoren schlugen einen Fix für die unsynchronisierten Subtraktionen vor, um die Go-Logik mit den mathematischen Invarianten in Einklang zu bringen.
- Anpassung des Beweises: Sie portierten den bestehenden BoringSSL-Beweis von Rocq nach Gobra. Für die Abweichung im Eingabebereich lockerten sie die Invarianten und Nachbedingungen, um den Fall $a \ge n$ abzudecken, und bewiesen, dass der GCD-Wert korrekt bleibt, selbst wenn die Eigenschaft des modularen Inversen in diesem spezifischen Fall nicht gilt.
- Hybride Verifizierung: Für nicht-lineare arithmetische Lemmata, die der Z3 SMT-Solver (der von Gobra verwendet wird) nicht handhaben konnte, nutzten die Autoren den Lean Proof-Assistant, um zentrale Lemmata zu beweisen und diese als trusted Lemmata in Gobra zu importieren.
KI-gestützte Verifizierung: Die Autoren nutzten einen KI-Agenten (Anthropics Claude Code), um Invarianten und Lemmata iterativ basierend auf den Fehlermeldungen von Gobra zu verfeinern, was den manuellen Aufwand bei der Konstruktion des Beweises erheblich reduzierte.

Zentrale Beiträge

Fehlerentdeckung: Die Arbeit deckt zwei subtile, aber kritische Abweichungen in der Go-Implementierung des Extended GCD auf, welche die algorithmischen Invarianten brechen. Diese Fehler waren in Code enthalten, der mehrfache Reviews durchlaufen hatte und als direkter Port einer verifizierten Implementierung deklariert war.
Leistungsoptimierung: Der vorgeschlagene Fix für die Abweichung der unsynchronisierten Subtraktion stellt nicht nur die Korrektheit wieder her, sondern führt auch zu einer durchschnittlichen Geschwindigkeitssteigerung von 24 % (geometrisches Mittel), indem unnötige Speicherallokationen und redundante Operationen im Schleifenkörper eliminiert werden.
Formale Verifizierung von Go-Krypto: Die Autoren verifizieren erfolgreich die korrigierte Go-Implementierung, deren Terminierung und deren Korrektheit gegenüber formalen Spezifikationen mittels Gobra. Dies ist die erste formale Verifizierung dieser spezifischen Komponente in der Go-Standardbibliothek.
Portierung und Generalisierung des Beweises: Sie portierten erfolgreich einen Beweis von Rocq (Fiat Cryptography) nach Gobra und generalisierten ihn, um den breiteren Eingabebereich der Go-Implementierung abzudecken.
KI in der Verifizierung: Die Arbeit demonstriert die Effektivität von KI-Agenten bei der Erleichterung der formalen Verifizierung, indem sie autonom auf Spezifikationen iterieren und die Ursachen von Beweisfehlern identifizieren (z. B. durch den Vorschlag, dass die unabhängige Koeffizientenreduktion das Problem war).

Ergebnisse

Korrektheit: Die korrigierte Implementierung wurde erfolgreich in 16,9 Sekunden auf einem Standard-Laptop verifiziert. Die Verifizierung deckt die Funktion extendedGCD und deren Clients InverseVarTime und GCDVarTime ab.
Leistung: Benchmarks über verschiedene Limb-Größen (64 bis 8192 Bits) zeigten, dass die verifizierte Implementierung konsistent schneller ist als die ursprüngliche. Die durchschnittliche Beschleunigung betrug 23,98 %, mit Verbesserungen zwischen 15,6 % und 36 %, abhängig von der Eingabegröße. Die Beschleunigung wird auf In-place-Updates und die Eliminierung intermediärer Pufferallokationen zurückgeführt.
Offenlegung und Auswirkungen: Die Autoren meldeten die Abweichungen den Go-Kryptographie-Maintainern. Die Maintainer bestätigten, dass die Abweichungen theoretisch zu falschen modularen Inversen führen könnten, jedoch defensive Prüfungen im RSA-Schlüsselgenerierungscode diese Fehler abfangen und einen Fehler zurückgeben würden, anstatt einen falschen Schlüssel zu erzeugen, was die Auswirkung auf die Verfügbarkeit statt auf die Sicherheit beschränkt. Die Fixes befinden sich zur Aufnahme in die Go-Standardbibliothek in der Prüfung.
Kontinuierliche Integration: Aufgrund der schnellen Verifizierungszeit wurde der Beweis in den Continuous-Integration-Workflow (CI) des Projekts integriert, um zukünftige Abweichungen automatisch zu prüfen.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass ihre Arbeit drei primäre Erkenntnisse hervorhebt:

Subtile Bugs in geprüftem Code: Selbst gut durchgeprüfter Code, insbesondere wenn er als direkter Port einer verifizierten Implementierung deklariert ist, kann subtile Bugs enthalten, die Invarianten brechen.
Die Kraft der formalen Verifizierung: Formale Verifizierung ist ein mächtiges Werkzeug, um diese Arten von Fehlern aufzudecken, die durch Tests und manuelle Reviews übersehen werden könnten.
Rolle von KI-Agenten: KI-Agenten können die Verifizierung effektiv unterstützen, indem sie iterativ Invarianten und Lemmata basierend auf dem Feedback des Verifizierers verfeinern, wobei eine menschliche Aufsicht für die abschließende Bereinigung und das strukturelle Verständnis notwendig bleibt.

Die Autoren betonen, dass ihre Arbeit die Lücke zwischen der Implementierung und ihrem Beweis schließt. Indem sie den Go-Code direkt verifizieren, anstatt sich auf die Existenz eines Beweises für eine andere Implementierung (BoringSSL) zu verlassen, stellen sie sicher, dass der in der Produktion laufende Code mathematisch fundiert ist. Sie merken zudem an, dass sie sich auf trusted Funktionen für Low-Level-Bitoperationen verlassen, das Gesamtargument der Korrektheit jedoch in kleine, überprüfbare Komponenten unterteilt ist, was das Vertrauen in die Zuverlässigkeit des Systems erhöht.