💻 computer science

Machine-Checked Cardinality Bounds for Masked Barrett Reduction: A 1-Bit Side-Channel Leakage Barrier in Post-Quantum Cryptographic Hardware

Dieser Beitrag präsentiert einen in Lean 4 maschinell verifizierten Beweis für eine universelle „1-Bit-Schranke" bei maskierter Barrett-Reduktion in der Post-Quanten-Kryptographie, der nachweist, dass seine internen Drahtabbildungen eine Urbild-Kardinalität von höchstens zwei aufweisen, wodurch ein Min-Entropieverlust von höchstens einem Bit garantiert und die Konstruktion sicherer Prime-Field-PINI-Kompositionen für ML-KEM und ML-DSA ermöglicht wird.

Ursprüngliche Autoren: Ray Iskander, Khaled Kirah

Veröffentlicht 2026-04-28

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Ray Iskander, Khaled Kirah

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

Das große Ganze: Digitale Geheimnisse schützen

Stellen Sie sich vor, Sie bauen einen hochsicheren Tresor (einen Computerchip), um digitale Geheimnisse zu speichern. Um sicherzustellen, dass niemand die Geheimnisse stehlen kann, indem er den Stromverbrauch oder elektromagnetische Wellen abhört (ein „Seitenkanalangriff"), verwenden Sie eine Technik namens Maskierung.

Denken Sie an Maskierung so: Sie legen Ihre geheime Zahl in eine Box und fügen eine zufällige, sich ständig ändernde Zahl hinzu, bevor Sie sie der Welt zeigen. Wenn Sie dies perfekt tun, sieht ein Lauscher nur zufälliges Rauschen und erfährt nichts über Ihr Geheimnis.

Dieses Papier konzentriert sich auf einen spezifischen, kniffligen Teil des Tresorschlusses, der Barrett-Reduktion genannt wird. In der Welt der Post-Quanten-Kryptographie (die neue Art von Mathematik, die benötigt wird, um zukünftige Supercomputer aufzuhalten), ist dieser Schritt essenziell, aber unübersichtlich. Die Autoren wollten wissen: Wenn wir hier Maskierung einsetzen, ist der Tresor wirklich sicher, oder lässt ein winziger Riss ein wenig Information durch?

Das Problem: Die „Zwei-Türen"-Falle

Die meisten Teile des Tresors (wie die im Papier erwähnten „Butterfly"-Stufen) sind wie ein perfekter Flur: Für jedes Geheimnis, das Sie hineingeben, gibt es genau einen zufälligen Pfad, den es zum Ausgang nehmen kann. Es ist eine perfekte 1-zu-1-Übereinstimmung.

Barrett-Reduktion ist jedoch anders. Sie hat einen „bedingten" Schritt. Stellen Sie sich einen Flur mit einer Gabelung vor:

Tür A: Wenn das Geheimnis klein ist, gehen Sie links.
Tür B: Wenn das Geheimnis groß ist, gehen Sie rechts.

Die Autoren entdeckten, dass aufgrund dieser Gabelung ein einzelner Ausgangswert auf dem Draht durch zwei verschiedene zufällige Masken erzeugt werden könnte, anstatt nur durch eine.

Die Angst: Wenn ein Angreifer den Ausgang sieht, könnte er denken: „Aha! Es könnte von Maske A oder Maske B gekommen sein. Ich habe es eingegrenzt!"
Die Realität: Die Autoren bewiesen, dass es niemals mehr als zwei sein können. Es sind niemals drei, vier oder hundert. Es sind strikt 0, 1 oder 2.

Die „1-Bit-Barriere"

Das Papier nennt diese Entdeckung die 1-Bit-Barriere.

Hier ist die Analogie:
Stellen Sie sich vor, Sie raten ein Passwort.

Perfekte Sicherheit: Sie haben 1.000.000 mögliche Passwörter, und der Angreifer hat keine Ahnung, welches es ist.
Das Barrett-Leck: Aufgrund des „Zwei-Türen"-Effekts könnte der Angreifer feststellen: „Es ist entweder Passwort A oder Passwort B." Er hat das Feld von 1.000.000 auf nur 2 eingegrenzt.

In mathematischen Begriffen kostet das Eingrenzen eines Feldes auf 2 Möglichkeiten genau 1 Bit Sicherheit (da $2^1 = 2$ ).

Die Behauptung: Die Autoren bewiesen, dass die Barrett-Reduktion niemals mehr als dieses 1 Bit verrät. Es ist eine „konservative" Obergrenze. In vielen Fällen ist das Leck tatsächlich weniger als 1 Bit, da einige Ausgaben unerreichbar sind (der „0"-Fall), was für die Sicherheit eigentlich eine gute Sache ist.

Das „Maschinengeprüfte" Versprechen

Warum sollten wir diesem vertrauen? Normalerweise werden Sicherheitsbeweise auf Papier geschrieben und von Menschen überprüft, die Fehler machen können.

Der Ansatz des Papiers: Die Autoren verwendeten ein Computerprogramm namens Lean 4, um den Beweis zu schreiben.
Die Analogie: Anstatt dass ein Mensch sagt: „Ich denke, diese Brücke ist sicher", bauten sie einen Roboter, der jede einzelne Schraube, jeden Balken und jede Schraube der Logik des Brückendesigns überprüfte. Der Roboter meldete „Null Fehler" (oder „Null sorry", in Computersprache).
Das Ergebnis: Dies ist nicht nur eine Theorie; es ist ein mathematisch verifiziertes Zertifikat, das für jeden Modul (jede Größe einer geheimen Zahl) funktioniert, der in aktuellen Standards wie ML-KEM und ML-DSA verwendet wird.

Warum der „Adams Bridge"-Chip scheiterte

Das Papier erklärt auch, warum ein bestimmtes Chipdesign namens Adams Bridge in früheren Studien als anfällig befunden wurde.

Der Fehler: Die Chipdesigner legten eine frische zufällige Maske zwischen die „Butterfly"-Stufen (die sicheren Flure), vergessen aber, eine frische Maske zwischen die „Barrett"-Stufen (die kniffligen Zwei-Türen-Räume) zu legen.
Die Folge: Ohne diese frische Maske könnten die kleinen 1-Bit-Lecks aus den Barrett-Stufen sich aufsummieren und vervielfachen, wodurch ein winziger Riss zu einem massiven Loch wird.
Die Lehre: Das Papier beweist, dass wenn Sie tatsächlich frische Masken zwischen jede Stufe legen, die 1-Bit-Barriere hält und das gesamte System sicher bleibt.

Zusammenfassung der Ergebnisse

Die Trichotomie: Die Mathematik hinter der Barrett-Reduktion ist überraschend einfach. Für jede Ausgabe ist die Anzahl der Wege, dorthin zu gelangen, immer 0, 1 oder 2. Niemals mehr.
Das 1-Bit-Limit: Das bedeutet, dass die maximale Information, die ein Angreifer von einem einzelnen Draht in diesem Prozess stehlen kann, 1 Bit beträgt.
Der Beweis: Dies wurde von einem Computerbeweisassistenten (Lean 4) mit null Fehlern verifiziert, was es zu einem Goldstandard-Garant für Hardware-Designer macht.
Die Lösung: Um das gesamte System sicher zu halten, müssen Hardware-Designer sicherstellen, dass sie die zufälligen Masken zwischen jeder Stufe der Berechnung aktualisieren. Wenn sie dies tun, schützt die „1-Bit-Barriere" die gesamte Pipeline.

Kurz gesagt: Die Autoren fanden einen winzigen, unvermeidbaren Riss in der Mathematik eines bestimmten Verschlüsselungsschritts, bewiesen genau, wie groß dieser Riss ist (nicht größer als 1 Bit), und zeigten, wie man den Rest des Tresors abdichtet, damit der Riss keine Rolle spielt.

1. Problemstellung

Post-Quantum-Kryptographie (PQC)-Standards wie ML-KEM (FIPS 203) und ML-DSA (FIPS 204) stützen sich stark auf Number Theoretic Transform (NTT)-Pipelines. Diese Pipelines bestehen aus linearen „Butterfly"-Stufen und nichtlinearen Modulo-Reduktionsstufen, die typischerweise mittels Barrett-Reduktion implementiert werden.

Während bestehende formale Verifikationsframeworks (ISW, t-SNI, PINI, DOM) starke Garantien für boolesches Maskieren über $GF(2)$ bieten, fehlen maschinell geprüfte Charakterisierungen für arithmetisches Maskieren über Primkörpern ( $\mathbb{Z}_q$ ), speziell für die Barrett-Reduktion.

Die Lücke: Hardware-Implementierungen (z. B. das „Adams Bridge"-Design) leiden häufig unter Seitenkanalangriffen, da die nichtlineare bedingte Subtraktion in der Barrett-Reduktion die affine Struktur bricht, die von Standard-Kompositionstheoremen vorausgesetzt wird.
Die Frage: Unter arithmetischem Maskieren erster Ordnung, wie lautet die genaue Leckage-Schranke der internen Leitungen einer Barrett-Reduktionsschaltung? Frühere Werkzeuge konnten keine universelle, maschinell geprüfte Antwort liefern, was zu Unsicherheiten bei der FIPS 140-3-Zertifizierung führte.

2. Methodik

Die Autoren wenden einen formalen Verifikationsansatz unter Verwendung des Lean 4-Beweisassistenten und der Mathlib-Bibliothek an.

Formalisierung: Sie definieren die Barrett-interne Leitungsmapping algebraisch über $\mathbb{Z}_q$ (wobei $q$ der Modul ist). Die Abbildung $f_x(m)$ nimmt ein Geheimnis $x$ und eine zufällige Maske $m$ entgegen und erzeugt einen Ausgangswert basierend auf einer Zwei-Branch-Struktur, die durch eine bedingte Subtraktion bestimmt wird.
Beweisstrategie: Anstatt spezifische Instanzen zu simulieren, beweisen sie universelle Theoreme, die für alle $q > 0$ und Verschiebungsparameter $s$ gelten.
Schlüsselkonzept: Sie analysieren die Kardinalität der Urbilder: Für ein festes Geheimnis $x$ und einen spezifischen Ausgangswert $v$ , wie viele verschiedene Masken $m$ könnten $v$ erzeugt haben?
Werkzeugkette: Das Artefakt enthält 12 bewiesene Ergebnisse mit keinem sorry (keine unvollständigen Beweise), wodurch jeder Schritt vom Lean-Kernel verifiziert wird.

3. Hauptbeiträge

A. Der Trichotomie-Theorem

Das Papier beweist, dass die Barrett-interne Leitungsmapping eine dreiwertige Urbildstruktur aufweist. Für jedes Geheimnis $x$ und jeden Ausgangswert $v$ ist die Anzahl der Masken $m$ , sodass $f_x(m) = v$ gilt, exakt 0, 1 oder 2.

Mechanismus: Die bedingte Subtraktion erzeugt zwei affine Zweige (Translationen in $\mathbb{Z}_q$ ). Das Urbild eines beliebigen Wertes ist eine Teilmenge von höchstens zwei Kandidaten: $\{x - v, x - v + r\}$ , wobei $r = 2^s \mod q$ .
Universalität: Dies gilt für jeden Modul $q$ und jede Verschiebung $s$ , unabhängig von spezifischen PQC-Parametern.

B. Die 1-Bit-Barriere

Basierend auf der Trichotomie stellen die Autoren eine universelle Leckage-Schranke auf:

Max-Multiplizität: Da die maximale Anzahl von Masken, die einen einzelnen Ausgangswert erzeugen, 2 beträgt, ist die maximale Wahrscheinlichkeit, einen spezifischen Ausgangswert zu beobachten, $2/q$ .
Min-Entropie-Schranke: Die bedingte Min-Entropie $H_\infty(\text{output} \mid x)$ ist nach unten durch $\log_2(q) - 1$ beschränkt.
Interpretation: Barrett-Reduktion gibt unter Seitenkanalprobing erster Ordnung maximal 1 Bit Min-Entropie pro interner Leitung preis. Dies ist eine „konservative" Schranke, da viele Ausgangswerte unerreichbar sind (Urbildanzahl = 0), was bedeutet, dass die tatsächliche Leckage oft strikt weniger als 1 Bit beträgt.

C. Das PF-PINI-Framework

Die Autoren führen Prime-Field PINI (PF-PINI) ein, eine neue Sicherheitsmetrik für arithmetische Gadgets über $\mathbb{Z}_q$ :

Definition: Ein Gadget ist PF-PINI( $k$ ), wenn die Urbild-Kardinalität durch $k$ beschränkt ist.
Instantiierungen:
- Butterfly-Stufen: Erfüllen PF-PINI(1) (perfekte Bijektion, keine Leckage über die Maske hinaus).
- Barrett-Reduktion: Erfüllt PF-PINI(2) (die 1-Bit-Barriere).
Kompositionsbeobachtung: Sie beobachten (obwohl noch nicht formal bewiesen), dass, wenn Pipeline-Stufen durch frische Inter-Stage-Maskierung getrennt sind, die maximale Multiplizität der zusammengesetzten Pipeline $\max(k_1, k_2)$ beträgt. Dies impliziert, dass sich die 1-Bit-Barriere durch die gesamte NTT-Pipeline fortpflanzt.

4. Ergebnisse und Analyse

Maschinell geprüfte Beweise: Das Artefakt enthält 12 verifizierte Theoreme, einschließlich der Trichotomie, Schärfe-Beweise (die zeigen, dass die Anzahl = 2 erreichbar ist) und PF-PINI-Instantiierungen.
Support-Lücken-Entdeckung: Die Analyse zeigt „unerreichbare" Ausgangswerte (Urbildanzahl = 0). Dies ist ein Sicherheitsmerkmal und kein Fehler, da es die effektive Information des Angreifers reduziert.
Adams Bridge Fallstudie: Das Papier analysiert die Hardware-Implementierung „Adams Bridge":
- Intra-Stage-Ausfall: Frühere Arbeiten (Papiere 1 & 2) zeigten Schwachstellen aufgrund von Share-Interaktion ohne Zwischenmaskierung.
- Inter-Stage-Ausfall: Dieses Papier identifiziert, dass Adams Bridge versagt, frische Maskierung zwischen den Stufen anzuwenden. Folglich gilt die PF-PINI-Kompositionsschranke nicht, was dazu führt, dass sich die Leckage multipliziert ( $k_1 \times k_2$ ), anstatt durch das Maximum beschränkt zu bleiben ( $\max(k_1, k_2)$ ). Dies erklärt, warum das Design anfällig ist, obwohl die 1-Bit-Barriere für einzelne Barrett-Gates existiert.
Quantitative Auswirkungen:
- Für ML-KEM ( $q=3329$ ): Leckage $\le 1$ Bit (Min-Entropie $\ge 10,70$ Bits).
- Für ML-DSA ( $q=8.380.417$ ): Leckage $\le 1$ Bit (Min-Entropie $\ge 21,99$ Bits).

5. Bedeutung

Zertifizierungsbereitschaft: Die 1-Bit-Barriere bietet Hardware-Designern ein universelles, maschinell geprüftes Zertifikat. Es ermöglicht Evaluatoren, Barrett-basierte Implementierungen für FIPS 140-3 zu zertifizieren, ohne spezifische Parametersätze erneut zu verifizieren.
Design-Leitfaden: Es klärt auf, dass die primäre architektonische Anforderung für Sicherheit frische Inter-Stage-Maskierung ist. Wenn dies implementiert wird, kompromittiert die nichtlineare Natur der Barrett-Reduktion die Sicherheit der NTT-Pipeline nicht über einen vernachlässigbaren Verlust von 1 Bit hinaus.
Methodologischer Wandel: Das Papier verlagert die Seitenkanalanalyse von empirischen Simulationen und SAT-basierten Prüfungen hin zu kernel-verifizierten algebraischen Beweisen und setzt einen neuen Standard für die PQC-Hardwareverifikation.
Abschluss des Fünf-Papiere-Programms: Diese Arbeit schließt die Lücke, die von früheren Papieren der Reihe offen gelassen wurde, und bewegt sich von der Werkzeugkonstruktion (Papier 1) und Angriffsquantifizierung (Papier 2) zu algebraischen Grundlagen (Papier 3), linearer Komposition (Papier 4) und schließlich zur nichtlinearen Charakterisierung (Papier 5).

6. Einschränkungen und zukünftige Arbeiten

Kompositions-Beweis: Die Behauptung, dass $\max(k_1, k_2)$ für zusammengesetzte Pipelines mit frischer Maskierung gilt, ist derzeit eine Beobachtung und kein formaler Satz.
Höherstufiges Maskieren: Die Ergebnisse beschränken sich auf Maskierung erster Ordnung ( $t=1$ ). Höherstufige Sicherheit erfordert die Analyse gemeinsamer Urbilder über mehrere Leitungen hinweg.
Entropie-Formalisierung: Obwohl die algebraische Schranke bewiesen ist, hängt die informationstheoretische Min-Entropie-Schranke von Standarddefinitionen ab, die noch nicht vollständig in Mathlib integriert wurden.
Andere Reduktionen: Die Ergebnisse sind spezifisch für Barrett-Reduktion; Montgomery- und Schoolbook-Reduktionen erfordern eine separate Analyse.

Zusammenfassend stellt dieses Papier fest, dass Barrett-Reduktion unter arithmetischem Maskieren erster Ordnung fundamental sicher ist und pro Leitung nicht mehr als 1 Bit Information preisgibt, sofern zwischen Pipeline-Stufen frische Maskierung angewendet wird. Dies bietet eine rigorose mathematische Grundlage für die Sicherung der PQC-Hardware der nächsten Generation.