💻 computer science

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

Dit artikel presenteert een machine-gecontroleerd bewijs in Lean 4 dat een universele "1-bitsbarrière" voor gemaskerde Barrett-reductie in post-kwantumcryptografie vaststelt, door aan te tonen dat de interne draadkaarten een pre-afbeeldingscardinaliteit van maximaal twee hebben, waardoor een verlies van min-entropy van maximaal één bit wordt gegarandeerd en de constructie van veilige composities van Prime-Field-PINI voor ML-KEM en ML-DSA mogelijk wordt gemaakt.

Oorspronkelijke auteurs: Ray Iskander, Khaled Kirah

Gepubliceerd 2026-04-28

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Ray Iskander, Khaled Kirah

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Plaatje: Digitale Geheimen Beschermen

Stel je voor dat je een hoogbeveiligde kluis (een computerchip) bouwt om digitale geheimen te bewaren. Om ervoor te zorgen dat niemand de geheimen kan stelen door te luisteren naar het stroomverbruik of elektromagnetische golven (een "side-channel attack"), gebruik je een techniek die maskering heet.

Denk aan maskering als het plaatsen van je geheime getal in een doos, en het toevoegen van een willekeurig, verschuivend getal voordat je het aan de wereld laat zien. Als je dit perfect doet, ziet een afluisteraar alleen willekeurige ruis en leert hij niets over je geheim.

Dit paper richt zich op een specifiek, lastig onderdeel van het vergrendelingsmechanisme van de kluis, genaamd Barrett-reductie. In de wereld van Post-Quantum Cryptografie (de nieuwe wiskunde die nodig is om toekomstige supercomputers te stoppen) is deze stap essentieel maar rommelig. De auteurs wilden weten: Als we hier maskering toepassen, is de kluis dan echt veilig, of laat een klein scheurtje een beetje informatie lekken?

Het Probleem: De "Twee-Deuren"-Val

De meeste delen van de kluis (zoals de "Butterfly"-stadia die in het paper worden genoemd) zijn als een perfecte gang: voor elk geheim dat je invoert, is er precies één willekeurig pad dat het naar de uitgang kan nemen. Het is een perfecte 1-op-1-match.

Echter, Barrett-reductie is anders. Het heeft een "voorwaardelijke" stap. Stel je een gang voor met een splitsing in de weg:

Deur A: Als het geheim klein is, ga je links.
Deur B: Als het geheim groot is, ga je rechts.

De auteurs ontdekten dat vanwege deze splitsing, één enkele uitvoerwaarde op de draad kan worden gegenereerd door twee verschillende willekeurige maskers in plaats van slechts één.

De Angst: Als een aanvaller de uitvoer ziet, zou hij kunnen denken: "Aha! Het kan van Masker A of Masker B komen. Ik heb het ingeperkt!"
De Realiteit: De auteurs bewezen dat het nooit meer dan twee kan zijn. Het is nooit drie, vier of honderd. Het is strikt 0, 1 of 2.

De "1-Bit Barrière"

Het paper noemt deze ontdekking de 1-Bit Barrière.

Hier is de analogie:
Stel je voor dat je een wachtwoord moet raden.

Perfecte Veiligheid: Je hebt 1.000.000 mogelijke wachtwoorden, en de aanvaller heeft geen idee welke het is.
Het Barrett-lek: Door het "Twee-Deuren"-effect kan de aanvaller beseffen: "Het is óf Wachtwoord A óf Wachtwoord B." Hij heeft het veld ingeperkt van 1.000.000 naar slechts 2.

In wiskundige termen kost het het inperken van een veld tot 2 mogelijkheden precies 1 bit aan veiligheid (aangezien $2^1 = 2$ ).

De Claim: De auteurs bewezen dat Barrett-reductie nooit meer dan deze 1 bit lekt. Het is een "conservatief" plafond. In veel gevallen is het lek eigenlijk minder dan 1 bit, omdat sommige uitvoeren onmogelijk te bereiken zijn (het "0"-geval), wat eigenlijk goed is voor de veiligheid.

De "Machine-Checked" Belofte

Waarom moeten we dit vertrouwen? Meestal worden beveiligingsbewijzen op papier geschreven en door mensen gecontroleerd, die fouten kunnen maken.

De Aanpak van het Paper: De auteurs gebruikten een computerprogramma genaamd Lean 4 om het bewijs te schrijven.
De Analogie: In plaats van dat een mens zegt: "Ik denk dat deze brug veilig is," bouwden ze een robot die elke enkele bout, balk en schroef van de ontwerplogica van de brug controleerde. De robot rapporteerde "Zero Errors" (of "Zero sorry", in computertermen).
Het Resultaat: Dit is niet zomaar een theorie; het is een wiskundig geverifieerd certificaat dat werkt voor elke modulus (elke grootte van een geheim getal) die wordt gebruikt in huidige standaarden zoals ML-KEM en ML-DSA.

Waarom de "Adams Bridge"-chip faalde

Het paper legt ook uit waarom een specifiek chipontwerp genaamd Adams Bridge in eerdere studies kwetsbaar bleek te zijn.

De Fout: De chipontwerpers plaatsten een vers willekeurig masker tussen de "Butterfly"-stadia (de veilige gangen), maar vergeten een vers masker te plaatsen tussen de "Barrett"-stadia (de lastige twee-deurenkamers).
Het Gevolg: Zonder dat verse masker konden de kleine 1-bit-lekken uit de Barrett-stadia stapelen en vermenigvuldigen, waardoor een klein scheurtje veranderde in een enorm gat.
De Les: Het paper bewijst dat als je wel verse maskers tussen elke stap plaatst, de 1-bit barrière standhoudt en het hele systeem veilig blijft.

Samenvatting van Bevindingen

De Trichotomie: De wiskunde achter Barrett-reductie is verrassend eenvoudig. Voor elke uitvoer is het aantal manieren om daar te komen altijd 0, 1 of 2. Nooit meer.
De 1-Bit Limiet: Dit betekent dat de maximale informatie die een aanvaller uit één enkele draad in dit proces kan stelen 1 bit is.
Het Bewijs: Dit is geverifieerd door een computerbewijshulp (Lean 4) met nul fouten, wat het een gouden standaard-garantie maakt voor hardwareontwerpers.
De Oplossing: Om het hele systeem veilig te houden, moeten hardwareontwerpers ervoor zorgen dat ze de willekeurige maskers tussen elke stap van de berekening verversen. Als ze dat doen, beschermt de "1-Bit Barrière" de hele pijplijn.

Kortom: De auteurs vonden een klein, onvermijdelijk scheurtje in de wiskunde van een specifieke encryptiestap, bewezen precies hoe groot dat scheurtje is (niet groter dan 1 bit), en toonden aan hoe de rest van de kluis verzegeld moet worden zodat het scheurtje er niet toe doet.

1. Probleemstelling

Post-Quantum Cryptografie (PQC)-standaarden zoals ML-KEM (FIPS 203) en ML-DSA (FIPS 204) zijn sterk afhankelijk van Number Theoretic Transform (NTT)-pipelines. Deze pipelines bestaan uit lineaire "butterfly"-stages en niet-lineaire modulaire reductiestages, die doorgaans worden geïmplementeerd met Barrett-reductie.

Hoewel bestaande formele verificatiekaders (ISW, t-SNI, PINI, DOM) sterke garanties bieden voor Booleaanse masking over $GF(2)$, ontbreken er machine-gecontroleerde karakterisering voor aritmische masking over priemvelden ( $\mathbb{Z}_q$ ), specifiek voor Barrett-reductie.

De Kloof: Hardware-implementaties (zoals het "Adams Bridge"-ontwerp) lijden vaak aan zijkanalengevoeligheid omdat de niet-lineaire conditionele aftrekking in Barrett-reductie de affiene structuur doorbreekt die wordt verondersteld door standaard compositiestellingen.
De Vraag: Onder eerste-orde aritmische masking, wat is de precieze leksgrens van de interne draden van een Barrett-reductiekring? Eerdere tools konden geen universeel, machine-gecontroleerd antwoord geven, wat leidde tot onzekerheid bij de FIPS 140-3-certificering.

2. Methodologie

De auteurs hanteren een formele verificatiebenadering met behulp van de Lean 4 bewijshulp en de Mathlib-bibliotheek.

Formalisatie: Ze definiëren de Barrett-interne draadmapping algebraïsch over $\mathbb{Z}_q$ (waarbij $q$ de modulus is). De mapping $f_x(m)$ neemt een geheim $x$ en een willekeurige masker $m$ en produceert een output gebaseerd op een twee-branch-structuur die wordt bepaald door een conditionele aftrekking.
Bewijsstrategie: In plaats van specifieke instanties te simuleren, bewijzen ze universele stellingen die gelden voor alle $q > 0$ en verschuivingsparameters $s$ .
Kernconcept: Ze analyseren de pre-afbeeldingscardinaliteit: voor een vast geheim $x$ en een specifieke outputwaarde $v$ , hoeveel verschillende maskers $m$ konden $v$ hebben geproduceerd?
Toolchain: Het artifact bevat 12 bewezen resultaten met zero sorry (geen onvolledige bewijzen), waarbij elke stap kernel-geverifieerd is door Lean.

3. Belangrijkste Bijdragen

A. De Trichotomie-stelling

Het artikel bewijst dat de Barrett-interne draadmapping een drie-waardige pre-afbeeldingsstructuur vertoont. Voor elk geheim $x$ en elke output $v$ is het aantal maskers $m$ waarvoor $f_x(m) = v$ exact 0, 1 of 2.

Mechanisme: De conditionele aftrekking creëert twee affiene branches (translaties in $\mathbb{Z}_q$ ). De pre-afbeelding van elke waarde is een deelverzameling van maximaal twee kandidaten: $\{x - v, x - v + r\}$ , waarbij $r = 2^s \mod q$ .
Universaliteit: Dit geldt voor elke modulus $q$ en verschuiving $s$ , onafhankelijk van specifieke PQC-parameters.

B. De 1-Bit Barrière

Op basis van de trichotomie stellen de auteurs een universele leksgrens vast:

Max-Multipliciteit: Aangezien het maximale aantal maskers dat een enkele output produceert 2 is, is de maximale kans om een specifieke outputwaarde waar te nemen $2/q$ .
Min-Entropiegrens: De conditionele min-entropie $H_\infty(\text{output} \mid x)$ is ondergrens door $\log_2(q) - 1$ .
Interpretatie: Barrett-reductie lekt maximaal 1 bit min-entropie per interne draad onder eerste-orde probing. Dit is een "conservatieve" grens omdat veel outputwaarden onbereikbaar zijn (pre-afbeeldingsaantal = 0), wat betekent dat de werkelijke lekkage vaak strikt minder dan 1 bit is.

C. Het PF-PINI Kader

De auteurs introduceren Prime-Field PINI (PF-PINI), een nieuwe veiligheidsmetriek voor aritmische gadgets over $\mathbb{Z}_q$ :

Definitie: Een gadget is PF-PINI( $k$ ) als de pre-afbeeldingscardinaliteit begrensd is door $k$ .
Instantiaties:
- Butterfly-stages: Voldoen aan PF-PINI(1) (perfecte bijectie, nul lekkage buiten het masker).
- Barrett-reductie: Voldoet aan PF-PINI(2) (de 1-Bit Barrière).
Compositie-observatie: Ze observeren (hoewel nog niet formeel bewezen) dat als pipeline-stages worden gescheiden door verse inter-stage masking, de maximale multipliciteit van de samengestelde pipeline $\max(k_1, k_2)$ is. Dit impliceert dat de 1-Bit Barrière zich door de gehele NTT-pipeline voortplant.

4. Resultaten en Analyse

Machine-gecontroleerde Bewijzen: Het artifact bevat 12 geverifieerde stellingen, waaronder de trichotomie, strakheidsbewijzen (waaruit blijkt dat tellen=2 haalbaar is) en PF-PINI-instantiaties.
Ontdekking van Support-gaten: De analyse onthult "onbereikbare" outputwaarden (pre-afbeeldingsaantal = 0). Dit is een veiligheidsfunctie, geen bug, omdat het de effectieve informatie van de aanvaller vermindert.
Adams Bridge Case Study: Het artikel analyseert de "Adams Bridge" hardware-implementatie:
- Intra-stage falen: Eerdere werken (Paper 1 & 2) toonden kwetsbaarheden aan door share-interactie zonder tussenliggende masking.
- Inter-stage falen: Dit artikel identificeert dat Adams Bridge faalt in het toepassen van verse masking tussen stages. Bijgevolg is de PF-PINI compositiegrens niet van toepassing, waardoor lekkage kan vermenigvuldigen ( $k_1 \times k_2$ ) in plaats van begrensd te blijven door het maximum ( $\max(k_1, k_2)$ ). Dit verklaart waarom het ontwerp kwetsbaar is, ondanks dat de 1-Bit Barrière bestaat voor individuele Barrett-poorten.
Kwantitatieve Impact:
- Voor ML-KEM ( $q=3329$ ): Lekkage $\le 1$ bit (Min-entropie $\ge 10.70$ bits).
- Voor ML-DSA ( $q=8.380.417$ ): Lekkage $\le 1$ bit (Min-entropie $\ge 21.99$ bits).

5. Betekenis

Certificeringsklaarheid: De 1-Bit Barrière biedt een universeel, machine-gecontroleerd certificaat voor hardwareontwerpers. Het stelt beoordelaars in staat Barrett-gebaseerde implementaties voor FIPS 140-3 te certificeren zonder specifieke parameterreeksen opnieuw te verifiëren.
Ontwerpgids: Het verduidelijkt dat de primaire architecturale vereiste voor veiligheid verse inter-stage masking is. Als dit wordt geïmplementeerd, compromitteert de niet-lineaire aard van Barrett-reductie de veiligheid van de NTT-pipeline niet verder dan een verwaarloosbaar verlies van 1 bit.
Methodologische Verschuiving: Het artikel verplaatst zijkanalanalyse van empirische simulatie en SAT-gebaseerde controle naar kernel-geverifieerde algebraïsche bewijzen, waarmee een nieuwe standaard wordt gesteld voor PQC-hardwareverificatie.
Voltooiing van het Vijf-Paper Programma: Dit werk sluit de kloof die door eerdere papers in de serie is achtergelaten, en beweegt van toolconstructie (Paper 1) en aanvalskwantificatie (Paper 2) naar algebraïsche fundamenten (Paper 3), lineaire compositie (Paper 4) en uiteindelijk, niet-lineaire karakterisering (Paper 5).

6. Beperkingen en Toekomstig Werk

Compositiebewijs: De bewering dat $\max(k_1, k_2)$ geldt voor samengestelde pipelines met verse masking is momenteel een observatie, geen formeel theorema.
Hogere-orde Masking: De resultaten zijn beperkt tot eerste-orde masking ( $t=1$ ). Hogere-orde beveiliging vereist het analyseren van gezamenlijke pre-afbeeldingen over meerdere draden.
Entropie Formalisatie: Hoewel de algebraïsche grens is bewezen, rust de information-theoretische min-entropiegrens op standaarddefinities die nog niet volledig zijn opgenomen in Mathlib.
Andere Reducties: De resultaten zijn specifiek voor Barrett-reductie; Montgomery- en schoolbook-reducties vereisen een aparte analyse.

Kortom, dit artikel stelt vast dat Barrett-reductie fundamenteel veilig is onder eerste-orde aritmische masking, waarbij niet meer dan 1 bit informatie per draad wordt gelekt, mits verse masking wordt toegepast tussen pipeline-stages. Dit biedt een rigoureuze wiskundige basis voor het beveiligen van next-generation PQC-hardware.