Post-kwantumcryptografie - nieuw algoritme "verdwenen in 60 minuten"

We hebben geschreven over PQC, een afkorting van post-kwantumcryptografie, meerdere malen eerder.

Voor het geval je alle media-opwinding van de afgelopen jaren over zogenaamde kwantumcomputing hebt gemist...

… het is (als u me wilt vergeven wat sommige experts waarschijnlijk als een roekeloze oversimplificatie zullen beschouwen) een manier om computerapparatuur te bouwen die de meerdere mogelijke uitkomsten van een berekening tegelijk.

Met veel zorg, en misschien een beetje geluk, betekent dit dat je sommige soorten algoritmen kunt herschrijven om het juiste antwoord te vinden, of op zijn minst een hele reeks foute antwoorden correct kunt weggooien, zonder elke mogelijke uitkomst te proberen en te testen een voor een.

Er zijn twee interessante cryptanalytische versnellingen mogelijk met behulp van een kwantumcomputer, ervan uitgaande dat een voldoende krachtige en betrouwbare daadwerkelijk kan worden geconstrueerd:

• Grover's kwantumzoekalgoritme. Als u een willekeurig geordende reeks antwoorden wilt doorzoeken om te zien of de uwe op de lijst staat, verwacht u in het slechtste geval de hele lijst door te bladeren voordat u een definitief antwoord krijgt. Als u bijvoorbeeld de 128-bits AES-decoderingssleutel wilt vinden om een ​​document te ontcijferen, moet u de lijst met alle mogelijke sleutels doorzoeken, te beginnen bij 000..001, ..2, ..3, enzovoort, helemaal tot aan FFF..FFF (16 bytes waard) FF), om er zeker van te zijn dat het probleem wordt opgelost. Met andere woorden, je moet budget hebben om ze alle 2 te proberen¹²⁸ mogelijke sleutels voordat u de juiste sleutel vond, of vaststelde dat er geen was. Het algoritme van Grover beweert echter, gegeven een kwantumcomputer die groot en krachtig genoeg is, dezelfde prestatie te kunnen leveren met de vierkantswortel van de gebruikelijke inspanning, dus het kraken van de code, in theorie, in slechts 2⁶⁴ probeert in plaats daarvan.
• Shor's kwantumfactorisatie-algoritme. Verschillende hedendaagse coderingsalgoritmen vertrouwen op het feit dat het vermenigvuldigen van twee grote priemgetallen snel kan worden gedaan, terwijl het zo goed als onmogelijk is om hun product terug te delen in de twee getallen waarmee je bent begonnen. Om hier een idee van te krijgen, probeer 59×87 te vermenigvuldigen met pen en papier. Het kan een minuutje duren voordat het eruit is (5133 is het antwoord), maar zo moeilijk is het niet. Probeer nu de andere manier. Verdeel, laten we zeggen, 4171 terug in zijn twee factoren. Veel moeilijker! (Het is 43×97.) Stel je nu voor dat je dit doet met een getal van 600 cijfers lang. Losjes gesproken zit je vast met het proberen om het 600-cijferige getal te delen door elk mogelijk priemgetal van 300 cijfers totdat je de jackpot wint, of ontdekt dat er geen antwoord is. Het algoritme van Shor belooft dit probleem echter op te lossen met de logaritme van de gebruikelijke inspanning. Dus het ontbinden van een aantal van 2048 binaire cijfers zou slechts twee keer zo lang moeten duren als het ontbinden van een 1024-bits getal, niet twee keer zo lang als het ontbinden van een 2047-bits getal, wat een enorme versnelling betekent.

De dreiging tegengaan

De dreiging van het algoritme van Grover kan eenvoudig worden tegengegaan door de grootte van de getallen die u gebruikt te vergroten door ze te kwadrateren, wat betekent dat u het aantal bits in uw cryptografische hash of uw symmetrische coderingssleutel verdubbelt. (Met andere woorden, als u denkt dat SHA-256 op dit moment in orde is, zou het gebruik van SHA-512 in plaats daarvan een PQC-bestendig alternatief bieden.)

Maar het algoritme van Shor kan niet zo gemakkelijk worden tegengegaan.

Een publieke sleutel van 2048 bits zou exponentieel groter moeten worden, niet alleen door kwadrateren, zodat je in plaats van een sleutel van 2×2048=4096 bits ofwel een nieuwe sleutel nodig hebt met de onmogelijke grootte van 2²⁰⁴⁸ stukjes…

…of je zou een compleet nieuw soort post-kwantum-encryptiesysteem moeten gebruiken waarop het algoritme van Shor niet van toepassing was.

Welnu, de Amerikaanse normeringsinstantie NIST heeft een PQC “concurrentie” sinds eind 2017.

Het proces stond open voor iedereen, alle deelnemers zijn welkom, alle algoritmen zijn openlijk gepubliceerd en openbaar onderzoek is niet alleen mogelijk, maar actief aangemoedigd:

Oproep om voorstellen in te dienen. [Gesloten 2017-11-30]. […] Het is de bedoeling dat de nieuwe cryptografiestandaarden voor openbare sleutels een of meer aanvullende niet-geclassificeerde, openbaar gemaakte digitale handtekeningen, codering met openbare sleutels en algoritmen voor het vaststellen van sleutels specificeren die wereldwijd beschikbaar zijn en in staat zijn gevoelige overheidsinformatie te beschermen tot ver in de nabije toekomst, ook na de komst van kwantumcomputers.

Na drie rondes van inzendingen en discussies, NIST aangekondigd, op 2022-07-05, dat het met onmiddellijke ingang vier algoritmen had gekozen die het als "standaarden" beschouwde, allemaal met heerlijk klinkende namen: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON en SPHINCS+.

De eerste (CRYSTALS-KYBER) wordt gebruikt als wat a . wordt genoemd Sleutelovereenkomstmechanisme (KEM), waarbij twee uiteinden van een openbaar communicatiekanaal op een veilige manier een eenmalige privé-coderingssleutel verzinnen om de gegevens van een sessie vertrouwelijk uit te wisselen. (Simpel gezegd: snoopers krijgen gewoon geraspte kool, zodat ze het gesprek niet kunnen afluisteren.)

De andere drie algoritmen worden gebruikt voor: Digitale handtekeningen, waardoor u ervoor kunt zorgen dat de gegevens die u aan uw kant hebt gekregen, exact overeenkomen met wat de afzender aan de andere kant heeft ingevoerd, waardoor manipulatie wordt voorkomen en de integriteit wordt gewaarborgd. (Simpel gezegd: als iemand probeert de gegevens te corrumperen of ermee te rotzooien, weet je het.)

Meer algoritmen nodig

Tegelijkertijd met de aankondiging van de nieuwe normen, kondigde NIST ook een: vierde ronde van zijn concurrentie, waardoor nog eens vier algoritmen naar voren worden geschoven als mogelijke alternatieve KEM's. (Vergeet niet dat we op het moment van schrijven al drie goedgekeurde algoritmen voor digitale handtekeningen hebben om uit te kiezen, maar slechts één officiële KEM.)

Deze waren: BIKE, Classic McEliece, HQC en SIKE.

Intrigerend, de McEliece-algoritme werd al in de jaren 1970 uitgevonden door de Amerikaanse cryptograaf Robert Mc Eliece, die stierf in 2019, ruim nadat de wedstrijd van NIST al aan de gang was.

Het sloeg echter nooit aan, omdat het enorme hoeveelheden sleutelmateriaal vereiste in vergelijking met het populaire alternatief van de dag, het Diffie-Hellman-Merkle-algoritme (DHM, of soms gewoon DH).

Helaas is een van de drie Round Four-algoritmen, namelijk: SIKE, lijkt te zijn gebarsten.

In een hersenkraker, getiteld: EEN EFFICINTE SLEUTELHERSTEL-AANVAL OP SIDH (VOORLOPIGE VERSIE), lijken de Belgische cryptografen Wouter Castryk en Thomas Decru een dodelijke slag toe te brengen aan het SIKE-algoritme

Mocht je het je afvragen, SIKE is de afkorting van Supersingular Isogeny Key Inkapseling, en SIDH staat voor Supersinguliere Isogeny Diffie-Hellman, een specifiek gebruik van de SIKE-algoritme waarbij twee uiteinden van een communicatiekanaal een DHM-achtige "cryptodantie" uitvoeren om een ​​heleboel openbare gegevens uit te wisselen waarmee elk uiteinde een privéwaarde kan afleiden om te gebruiken als een eenmalige geheime coderingssleutel.

We gaan hier niet proberen de aanval uit te leggen; we herhalen gewoon wat de krant beweert, namelijk dat:

Heel losjes gezegd, omvatten de inputs hier de openbare gegevens die zijn verstrekt door een van de deelnemers aan de cryptodance van de sleutelinstelling, samen met de vooraf bepaalde (en daarom algemeen bekende) parameters die in het proces worden gebruikt.

Maar de uitvoer die wordt geëxtraheerd (de informatie waarnaar wordt verwezen als de isogenie hierboven) wordt verondersteld het nooit onthulde deel van het proces te zijn - de zogenaamde privésleutel.

Met andere woorden, alleen op basis van openbare informatie, zoals de gegevens die openlijk worden uitgewisseld tijdens het instellen van de sleutel, beweren de cryptografen de privésleutel van een van de deelnemers te kunnen herstellen.

En als je mijn privésleutel eenmaal kent, kun je gemakkelijk en ondetecteerbaar doen alsof je mij bent, dus het versleutelingsproces wordt verbroken.

Blijkbaar heeft het key-cracking-algoritme ongeveer een uur nodig om zijn werk te doen, met slechts een enkele CPU-kern met het soort verwerkingskracht dat je zou vinden in een alledaagse laptop.

Dat is in strijd met het SIKE-algoritme wanneer het is geconfigureerd om te voldoen aan niveau 1, NIST's basisniveau van coderingsbeveiliging.

Wat te doen?

Niets!

(Dat is het goede nieuws.)

Zoals de auteurs van het artikel suggereren, na te hebben opgemerkt dat hun resultaat nog voorlopig is, "Met de huidige stand van zaken lijkt SIDH volledig te zijn gebroken voor elke openbaar gegenereerde basiscurve."

(Dat is het slechte nieuws.)

Aangezien het SIKE-algoritme echter nog niet officieel is goedgekeurd, kan het nu worden aangepast om deze specifieke aanval te dwarsbomen (iets waarvan de auteurs toegeven dat het mogelijk is), of gewoon helemaal laten vallen.

Wat er uiteindelijk ook met SIKE gebeurt, dit is een uitstekende herinnering aan waarom het proberen om je eigen coderingsalgoritmen uit te vinden vol gevaar is.

Het is ook een duidelijk voorbeeld van waarom propriëtaire versleutelingssystemen die afhankelijk zijn van de geheimhouding van het algoritme zelf om hun veiligheid te handhaven, zijn in 2022 gewoon onaanvaardbaar.

Als een PQC-algoritme zoals SIKE meer dan vijf jaar door experts van over de hele wereld zou zijn overleefd, ondanks dat het specifiek werd onthuld zodat het aan openbare controle kon worden onderworpen...

…dan hoeft u zich niet af te vragen hoe goed uw zelfgemaakte, verborgen coderingsalgoritmen het waarschijnlijk zullen doen wanneer ze in het wild worden vrijgelaten!

---