💻 computer science

Prime-Field PINI: Machine-Checked Composition Theorems for Post-Quantum NTT Masking

Dit artikel presenteert de eerste machine-gecontroleerde compositiestellingen voor arithmetische masking over priemvelden, waarbij wordt aangetoond dat verse willekeurige masking tussen pijplijnstappen de beveiliging onafhankelijk maakt van eerdere stappen, en worden deze formele resultaten gebruikt om een kritieke masking-fout tussen stappen in Microsoft's Adams Bridge PQC-versneller te diagnosticeren.

Oorspronkelijke auteurs: Ray Iskander, Khaled Kirah

Gepubliceerd 2026-04-29

📖 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

Stel je voor dat je probeert een geheim bericht door een fabrieksassemblagelijn te sturen. Het bericht is gevoelig, dus je wilt niet dat iemand die de lijn observeert erachter komt wat het is. Om het te beschermen, breek je het bericht in stukken en meng je elk stuk met een willekeurige "ruis" (een masker) voordat het naar het volgende station gaat. Dit heet maskering.

In de wereld van computersbeveiliging zijn er twee hoofdtypen ruis:

Booleaanse Ruis: Net als het omzetten van schakelaars (aan/uit). We hebben al een perfect regelboek voor hoe we deze schakelaars veilig kunnen stapelen.
Aritmetische Ruis: Net als het optellen van getallen op een klok (waarbij 12 + 1 = 1). Dit is wat moderne "Post-Quantum" cryptografie gebruikt. Tot nu toe hadden we geen regelboek voor het veilig stapelen van deze op getallen gebaseerde maskers.

Dit artikel levert dat ontbrekende regelboek. Hier is het verhaal van wat ze ontdekten, eenvoudig uitgelegd.

1. Het Probleem: Het "Lekkende" Midden

Stel je een tweestaps fabriekslijn voor:

Station A: Neemt je geheim, voegt wat ruis toe en geeft het door.
Station B: Neemt wat Station A doorgaf, voegt meer ruis toe en stuurt het eindresultaat.

De onderzoekers ontdekten een gevaarlijke fout in hoe deze stations waren verbonden in een beroemde Microsoft-beveiligingschip (genaamd "Adams Bridge").

In het defecte ontwerp gaf Station A zijn ruizige resultaat direct door aan Station B. Vanwege hoe de wiskunde werkt (specifiek een stap genaamd "Barrett-reductie", wat een complexe manier is van delen), was de "ruis" die uit Station A kwam niet perfect willekeurig. Het had een patroon.

De Analogie: Stel je voor dat Station A een blender is. Het mengt je geheim met ijs. Maar vanwege de manier waarop de bladen draaien, zijn de ijsklontjes die eruit komen iets ongelijkmatig – sommige plekken hebben meer ijs, sommige minder. Als een spion (een hacker) precies tussen Station A en Station B staat en de ijsklontjes telt, kunnen ze een deel van je geheim raden. Dit heet een Kantelkanaal-aanval (Side-Channel Attack).

2. De Oplossing: Het "Vers Masker" (Het Vernieuwingsargument)

Het grote "Aha!"-moment van het artikel is verrassend simpel. Ze bewezen dat als je een vers, gloednieuw willekeurig masker tussen Station A en Station B invoegt, het probleem direct verdwijnt.

De Analogie:

Zonder de fix: Station A geeft een iets ongelijkmatige hoop ijs door aan Station B. Station B probeert het te repareren, maar de ongelijkmatigheid zit er al in.
Met de fix: Station A geeft zijn ongelijkmatige hoop door aan een "Reset-knop". Deze knop giet de hoop in een gigantische, perfect gemengde emmer vers water (het nieuwe masker). Nu, wanneer Station B een schep uit die emmer neemt, is het weer perfect willekeurig.

Het artikel bewijst wiskundig dat dit vers masker het geheugen van Station A volledig wist. Het maakt niet uit of Station A rommelig of perfect was; zodra het vers masker wordt toegepast, is de draad die naar Station B leidt perfect uniform. De beveiliging van de hele lijn hangt dan alleen af van hoe goed Station B is.

3. De "1-Bit Barrière"

De onderzoekers ontdekten dat voor de specifieke wiskunde die in deze chips wordt gebruikt (Barrett-reductie), de ruis nooit op zichzelf perfect willekeurig is. Het heeft een "lek" van maximaal 1 bit informatie.

Denk eraan als een muntstuk dat iets verzwaard is. Het is geen eerlijke munt; het landt iets vaker op "Kop".
Dit is geen fout in het ontwerp; het is een fundamentele eigenschap van de wiskunde. Het artikel noemt dit de "1-Bit Barrière".
Echter, het artikel bewijst dat als je de "Vers Masker"-truc tussen de fasen gebruikt, dat 1-bit lek verborgen zit in de verse ruis en nutteloos wordt voor een spion.

4. Het Bewijs: Machine-gecontroleerd

De auteurs schreven dit niet zomaar op papier; ze gebruikten een computerprogramma genaamd Lean 4 om elke stap van hun logica te controleren.

Ze schreven 18 specifieke bewijzen.
De computer verifieerde ze allemaal met nul fouten en nul "ik doe dit later"-notities (genaamd "sorry stubs").
Dit betekent dat de wiskunde rotsvast is. Het is niet alleen een theorie; het is een geverifieerd feit.

5. De Diagnose: Waarom Microsoft's Chip Kwetsbaar Was

Het team paste hun nieuwe regelboek toe op Microsoft's "Adams Bridge"-chip.

De Bevinding: De chip had twee fasen (Butterfly en Barrett) maar geen vers masker tussen hen in.
Het Resultaat: De draad die deze twee fasen verbond, was "lekkend". Het was niet uniform. Dit bevestigde waarom andere onderzoekers deze chip al succesvol hadden gehackt via stroomanalyse (het meten van elektriciteitsgebruik).
De Fix: Het artikel schrijft een simpele fix voor: Voeg één extra willekeurige getallengenerator en één aftrekkingsstap toe tussen de fasen. Dit maakt de tussenliggende draad perfect veilig.

Samenvatting

Dit artikel lost een ontbrekend stukje van de puzzel op voor veilige computerchips.

Het Probleem: Bij het koppelen van wiskundige bewerkingen kan de "ruis" die wordt gebruikt om geheimen te verbergen rommelig worden en in het midden informatie lekken.
De Fix: Voeg tussen elke stap een vers, willekeurig "reset" toe.
Het Bewijs: Ze gebruikten een computer om te bewijzen dat deze reset de middelste draad perfect veilig maakt, ongeacht hoe rommelig de eerste stap was.
De Toepassing: Ze toonden precies aan waarom een beroemde Microsoft-chip kwetsbaar was en hoe je het met een simpele architecturale wijziging kunt repareren.

Kortom: Als je een geheim door een meerstapsproces wilt verbergen, vertrouw dan niet alleen op de vermomming van de eerste stap. Gooi tussen elke stap een nieuwe vermomming, en het geheim blijft veilig.

1. Probleemstelling

Het artikel adresseert een kritieke lacune in de formele beveiligingsverificatie van Post-Quantum Cryptografie (PQC) hardware, specifiek voor Number Theoretic Transform (NTT) implementaties die worden gebruikt in NIST-standaarden (ML-KEM en ML-DSA).

De Context: Hardware-implementaties van NTT vertrouwen op aritmetische masking over priemvelden ( $\mathbb{Z}_q$ ) om weerstand te bieden tegen zijkanalaanvallen zoals Differential Power Analysis (DPA).
De Lacune: Waar Booleaanse masking (over $GF(2^n)$ ) een volwassen composiettheorie heeft (NI, SNI, PINI) met machine-gecontroleerde bewijzen, mist aritmetische masking over priemvelden vergelijkbare compositiestellingen.
Het Specifieke Probleem: Bij aritmetische masking interageren bewerkingen zoals modulaire reductie (bijvoorbeeld Barrett-reductie) op niet-triviale wijze met masks. In tegenstelling tot Booleaanse XOR, waarbij masking de uniformiteit perfect behoudt, kan aritmetische masking leiden tot niet-uniforme uitverdelingen (multipliciteit > 1).
De Kwetsbaarheid: Eerdere empirische analyses en structurele studies identificeerden kwetsbaarheden in Microsoft's "Adams Bridge" PQC-versneller, waarbij tussenliggende draden tussen pijplijnstages niet-uniform waren, wat DPA-aanvallen mogelijk maakte. Een formele theoretische verklaring voor waarom dit gebeurt en hoe dit via compositiestellingen opgelost kan worden, ontbrak echter.

2. Methodologie

De auteurs maken gebruik van formele verificatie met de Lean 4 bewijshulp om compositiestellingen voor aritmetische masking af te leiden en te bewijzen.

Formeel Model: Zij definiëren een kwantitatieve beveiligingsmetriek genaamd PF-PINI(k) (Prime-Field Probe Isolating Non-Interference).
- In tegenstelling tot binaire beveiligingsnoties (veilig/onveilig), meet PF-PINI de multipliciteit van uitgangswaarden ten opzichte van de maskerruimte.
- $k=1$ impliceert een perfect uniforme verdeling.
- $k=2$ impliceert een maximale multipliciteit van 2, wat tot 1 bit informatie per draad lekt.
Het "Renewal Argument": Het kern theoretische inzicht is dat het toepassen van een vers willekeurig masker tussen twee pijplijnstages de beveiligingsparameter ( $k_1$ ) van de eerste stage volledig "wist" van de tussenliggende draad, ongeacht hoe niet-uniform de uitgang van de eerste stage was.
Hardware Bridging: De auteurs overbruggen formeel de kloof tussen abstracte algebraïsche modellen ( $\mathbb{Z}_q$ ) en hardware-trouwe natuurlijke getallenrekenkunde (Nat) die wordt gebruikt in RTL-ontwerpen, specifiek voor Barrett-reductie.
Verificatieomvang: Het volledige werk bestaat uit 18 machine-gecontroleerde stellingen met zero sorry stubs (geen onbewezen aannames), wat garanties op hoog niveau van zekerheid biedt.

3. Belangrijkste Bijdragen

Het artikel levert zes primaire bijdragen:

Het Renewal Theorem (Stelling 4.1): Bewijst dat als een vers willekeurig masker wordt toegepast tussen twee stages ( $G_1 \to G_2$ ), de tussenliggende draad perfect uniform wordt. De verzameling maskersparen die een specifieke tussenliggende waarde produceren, heeft een kardinaliteit van precies $q$ , onafhankelijk van de beveiligingsparameter van $G_1$ .
Positieve Compositiestelling (Stelling 4.4): Demonstreert dat een twee-staps pijplijn met vers masking voldoet aan PF-PINI( $k_2$ ). De beveiliging van de samengestelde uitgang hangt alleen af van de parameter van de tweede stage ( $k_2$ ); de zwakte van de eerste stage ( $k_1$ ) wordt volledig gewist.
Negatieve Compositiestellingen (Stellingen 5.1–5.3): Bewijst dat zonder vers masking, de tussenliggende draad de multipliciteit van de eerste stage ( $k_1$ ) behoudt. Als $k_1 > 1$ , is de draad niet-uniform, wat een noodzakelijke voorwaarde creëert voor DPA-aanvallen.
Algebraïsch-Hardware Brug (Stelling 6.1): Bewijst formeel dat de algebraïsche Barrett-reductie-map equivalent is aan de hardware-trouwe Nat-rekenkundemap onder standaard scope-voorwaarden ( $q \le 2^s$ ). Dit valideert dat de theoretische grenzen direct van toepassing zijn op silicium-implementaties.
Adams Bridge Diagnose: Instantieert de stellingen formeel om Microsoft's Adams Bridge-versneller te diagnosticeren. Het bewijs bevestigt dat het gebrek aan vers inter-stage masking de Barrett-uitgangsdraads niet-uniform laat (PF-PINI(2)), wat het succes van eerdere empirische DPA-aanvallen verklaart.
Universele 1-Bit Barrière: Biedt computationeel bewijs dat de PF-PINI(2) grens universeel is voor modulaire reducties (zowel Barrett als Montgomery), wat wijst op een fundamentele "1-Bit Barrière" voor deze bewerkingen.

4. Belangrijkste Resultaten

Formeel Bewijs van Compositie: Het artikel stelt vast dat vers inter-stage masking de noodzakelijke en voldoende voorwaarde is om aritmetische gadgets veilig te compositeren.
Kwantitatieve Beveiliging:
- Met Vers Masking: De tussenliggende draad is uniform ( $k=1$ ). De uiteindelijke uitgang wordt begrensd door de parameter van de tweede stage ( $k_2$ ).
- Zonder Vers Masking: De tussenliggende draad is niet-uniform (tot $k_1$ ). Deze niet-uniformiteit is de oorzaak van de zijkanallekkage die bij empirische aanvallen werd waargenomen.
Adams Bridge Oplossing: De diagnose bevestigt dat het toevoegen van een enkel vers willekeurig maskerregister en een aftrekbewerking tussen de Butterfly- en Barrett-stages in de Adams Bridge-pijplijn de DPA-kwetsbaarheid op tussenliggende draden zou elimineren zonder de beveiligingsparameter van de uiteindelijke uitgang te veranderen.
Beschikbaarheid van Artefacten: De volledige Lean 4 broncode, inclusief 18 stellingen en een reproductiescript, is publiek beschikbaar, wat onafhankelijke verificatie van de bewijzen mogelijk maakt.

5. Betekenis

Eerste Machine-Gecontroleerde Aritmetische Compositie: Dit is het eerste werk dat machine-gecontroleerde compositiestellingen biedt voor aritmetische masking over priemvelden, waarmee een belangrijke theoretische leemte in PQC-hardwarebeveiliging wordt opgevuld.
Brug tussen Theorie en Praktijk: Door formele algebraïsche bewijzen te koppelen aan hardware-trouwe rekenkunde, biedt het artikel een rigoureuze basis voor het verifiëren van real-world siliciumontwerpen, verder gaand dan empirische testen.
Ontwerprichtlijn: Het vestigt een duidelijke, bewijsbare ontwerpregel voor PQC-hardware: Plaats altijd vers masking tussen pijplijnstages. Deze eenvoudige architecturale wijziging garandeert dat de beveiliging van de samengestelde pijplijn uitsluitend wordt bepaald door de zwakste schakel in de laatste stage, niet in de tussenliggende.
Convergentie van Bewijs: Het formele bewijs sluit perfect aan bij drie onafhankelijke eerdere analyses (empirische vermogensanalyse, code-review en structurele afhankelijkheidsanalyse), waarmee wordt bevestigd dat de geïdentificeerde architecturale fout in de Adams Bridge-versneller inderdaad de oorzaak is van de kwetsbaarheid.

Samenvattend biedt dit artikel de wiskundige en formele verificatie-ruggengraat die nodig is om beveiligde, compositabele en zijkanalbestendige hardware-versnellers te ontwerpen voor het nieuwe tijdperk van Post-Quantum Cryptografie.