Full-Key Recovery and Forgery from One MQOM v2.1 Signature

Stel je voor dat je een geheime boodschap naar een vriend probeert te sturen, maar je leeft in een wereld waar superkrachtige computers (quantumcomputers) op een dag zouden kunnen bestaan. Deze toekomstige machines zouden de meeste sloten die we vandaag de dag gebruiken om onze geheimen te beschermen, kunnen kraken. Om hiervoor te worden voorbereid, bouwen wetenschappers nieuwe, supersterke digitale sloten die "post-quantum signatures" worden genoemd. Denk aan deze als een speciaal soort waszegel op een brief. Zelfs als een dief een magische hamer heeft die normale sloten kan verbrijzelen, is deze nieuwe waszegel gemaakt van een materiaal dat er juist voor zou moeten zorgen dat het standhoudt.

Een van de meest veelbelovende nieuwe sloten die wordt getest, is een systeem genaamd MQOM. Het werkt een beetje als een gigantische, complexe puzzel. Om een brief te ondertekenen, gebruikt de verzender een geheim "getuige" (een verborgen sleutel) om een wiskundig probleem met veel variabelen op te lossen. Om te bewijzen dat ze de puzzel hebben opgelost zonder het geheim te onthullen, gebruiken ze een slimme truc genaamd "MPC-in-the-head". Stel je voor dat de verzender doet alsof hij een heel team van mensen is, die elk een klein stukje van het geheim vasthouden. Ze spelen een spel waarbij ze net genoeg onthullen om te bewijzen dat het team de puzzel samen heeft opgelost, maar niet genoeg om de eigenlijke stukjes van het geheim te onthullen. Als de wiskunde klopt, is de handtekening geldig. We geven hierom omdat als deze nieuwe sloten een verborgen barst hebben, onze toekomstige digitale veiligheid voordat we er zelfs maar zijn, kan instorten.

Laten we het nu hebben over het verhaal in dit artikel. Een onderzoeker genaamd José Luis Delgado heeft nauwkeurig gekeken naar een specifieke versie van dit MQOM-slot (versie 2.1) en heeft een verrassend eenvoudige manier gevonden om het te breken. Het artikel betoogt dat als een aanvaller slechts één geldige handtekening van het systeem krijgt, hij de volledige geheime sleutel kan achterhalen en nieuwe handtekeningen kan vervalsen voor elk gewenst bericht. Het is alsof een dief één keer zag hoe je de voordeur opendeed, en die ene inkijk alleen al genoeg was voor hen om een mastersleutel te maken die elk slot in je huis opent.

Hier is hoe de "magische truc" werkt, uitgelegd via een verhaal. Stel je voor dat de geheime sleutel een lange, verborgen schatkaart is. Het MQOM-systeem verbergt deze kaart binnen een gigantische boom gemaakt van takken. Wanneer je een bericht ondertekent, laat het systeem je een pad omhoog in de boom zien naar een specifieke verborgen blad (een plek op de kaart), maar het houdt het blad zelf bedekt. Echter, het geeft je ook een "sibling path" — een lijst van de takken naast het verborgen blad. Vanwege de manier waarop de boom is gebouwd, kun je, als je de takken naast het blad kent, precies uitrekenen wat het verborgen blad zou zijn als je een klein prefix van de geheime kaart zou kennen.

Het artikel ontdekte dat het systeem ook een "commitment" achterlaat, wat een verzegelde envelop is die het verborgen blad bevat. De onderzoeker realiseerde zich dat door de sibling path (de takken) te combineren met de verzegelde envelop, zij een enkele, gigantische vergelijking konden opschrijven. Deze vergelijking heeft één onbekende: het kleine prefix van de geheime kaart. De aanvaller hoeft niet de hele kaart te raden; ze hoeven alleen deze ene vergelijking op te lossen om dat kleine prefix te vinden.

Zodra ze dit prefix hebben gevonden, geeft de handtekening die ze al hebben een "correction suffix" — een klein briefje dat zegt: "Hier is de rest van de kaart om bij het prefix te passen dat je zojuist hebt gevonden." Door het prefix en het briefje aan elkaar te plakken, reconstrueert de aanvaller de volledige geheime kaart (de volledige ondertekeningssleutel). Met deze sleutel kan de aanvaller elk nieuw bericht ondertekenen, en het systeem zal dit als echt accepteren.

Het artikel raadt niet alleen dat dit werkt; ze hebben ook de wiskunde gedaan en het computerwerk uitgevoerd om te bewijzen dat het zo is. Ze hebben precies berekend hoeveel rekenkracht het zou kosten om deze vergelijking op te lossen voor de verschillende sterkte niveaus van het slot (de zogenaamde categorieën I, III en V). Ze vonden dat voor alle drie de categorieën, de inspanning die nodig is minder is dan de beveiligingslimiet die NIST voor deze sloten heeft ingesteld.

Voor het makkelijkste niveau (Categorie I) duurt de aanval ongeveer $2^{142.335112}$ operaties. Voor het middelste niveau (Categorie III) duurt het ongeveer $2^{206.774558}$ of $2^{206.988685}$ operaties, afhankelijk van welk deel van de kaart ze scannen. Voor het moeilijkste niveau (Categorie V) duurt het ongeveer $2^{271.794162}$ operaties. In elk geval is het aantal stappen dat de aanvaller moet zetten lager dan het aantal stappen dat het slot volgens de bedoeling nodig had om veilig te zijn.

De onderzoekers stopten niet alleen bij de wiskunde. Ze bouwten een computerprogramma dat de aanval daadwerkelijk uitvoerde. Ze namen een echte handtekening, losten de vergelijking op, herstelden de exacte geheime sleutel byte voor byte, en gebruikten die sleutel vervolgens om een gloednieuw bericht te ondertekenen. De verifieerder van het systeem controleerde de nieuwe handtekening en zei: "Ja, dit is geldig!" Dit bewees dat de aanval in de echte wereld werkt, en niet alleen op papier.

Het artikel keek ook naar of het veranderen van sommige instellingen het probleem zou oplossen. Ze vonden dat het simpelweg toevoegen van een "salt" (een willekeurig getal) aan het proces de getallen in de vergelijking verandert, maar de aanval niet stopt. De vergelijking bestaat nog steeds; hij ziet er alleen iets anders uit. Om dit echt op te lossen, zouden de ontwerpers de manier waarop het pad van de boom zich tot het geheim verhoudt, hoe het blad wordt gecommitteerd, of hoe het correctiebriefje wordt gegenereerd, moeten veranderen.

Kortom, dit artikel laat zien dat het huidige versie van het MQOM-slot een gat heeft waar je zo doorheen kunt lopen. Het verandert een enkele handtekening in een mastersleutel, waardoor een aanvaller berichten kan vervalsen met minder inspanning dan het slot bedoeld was te weerstaan. De auteur heeft de code en resultaten gedeeld zodat anderen hun werk kunnen controleren, en suggereert dat de ontwerpers van MQOM deze specifieke onderdelen van het systeem moeten patchen voordat het als veilig voor de toekomst kan worden beschouwd.