Zoals reeds uitgebreid toegelicht in eerdere blogposts, zouden krachtige kwantumcomputers ergens in de toekomst in staat zijn moderne publieke sleutelcryptografie te breken. Het NIST (National Institute for Standards & Technologies) heeft daarom in 2016 een standaardisatieprocedure opgestart. In juli 2022 kondigde dat NIST aan dat het de eerste vier algoritmes geselecteerd heeft: één voor key encapsulation mechanisms (KEM) en drie voor digitale handtekeningen. Wat betekent dit in de praktijk?
De geselecteerde algoritmes moeten nu nog tot standaard verwerkt worden. Het is dus mogelijk dat deze algoritmes onderweg nog wijzigingen zullen ondergaan. De standaarden worden verwacht in 2024.
Deze tekst gaat alvast in op enkele praktische implicaties van de geselecteerde algoritmes, in hun huidige vorm. We beginnen met het algoritme voor KEM, vervolgens bespreken we de drie algoritmes voor Digitale handtekeningen. Daarna gaan we in op enkele aanbevelingen van het Duitse BSI (Bundesambt für Sicherheit in der Informationstechnik).
Key encapsulation mechanisms
Het afspreken van een gedeelde sleutel over een potentieel onveilig kanaal is een cruciaal onderdeel bij het opzetten van TLS verbindingen. Vandaag zijn zowel RSA-2048 (112 bit security) als het modernere Curve25519 (128 bit security) populaire keuzes. Die laatste is gebaseerd op elliptische krommen. Zowel cryptografie gebaseerd op RSA als op elliptische krommen is kwetsbaar voor voldoende krachtige kwantumcomputers.
Kyber werd geselecteerd als kwantumresistent KEM algoritme. Het komt in drie versies: Kyber-512, Kyber-768 en Kyber-1024, wat ruwweg overeenkomt met 128, 192 en 256 bit security. Laat ons eerst even kijken naar Kyber-512, dat in onderstaande tabel, gebaseerd op een blogpost van Cloudflare, vergeleken wordt met RSA-2048 en Curve25519.
Wat meteen opvalt is dat Kyber sleutels een pak groter zijn dan wat we vandaag gewoon zijn. Gerelateerd daarmee neemt ook de data die getransfereerd wordt tijdens de protocoluitvoering aanzienlijk toe.
De performantieresultaten mogen slechts als indicatief geïnterpreteerd worden. Niettemin stellen ze ons in staat een tweede vaststelling te maken; de computationele efficiëntie is een pak beter dan bij Curve25519, wat, als we client-side en server-side combineren, dan weer een pak efficiënter was dan RSA-2048.
Samengevat heeft Kyber aanzienlijk grotere publiek sleutels, moet meer informatie uitgewisseld worden en is het computationeel erg efficiënt.
Het NIST heeft bovendien drie alternatieve kandidaten geselecteerd (BIKE, Classic McEliece en HQC) met als doel daaruit minstens een tweede KEM standaard te destilleren tegen 2028. Dit dient te vermijden dat we wereldwijd met de handen in het haar zitten de dag dat Kyber gekraakt zou worden. Het NIST had trouwens SIKE als vierde alternatieve kandidaat geselecteerd, maar dit werd kort daarna door onderzoekers van de KU Leuven gebroken.
Digitale handtekeningen
Voor digitale handtekeningen is de situatie minder uitgekristalliseerd. Het NIST heeft niet één maar drie algoritmes geselecteerd voor standaardisatie en heeft bovendien een nieuwe standaardisatieronde opgestart in de hoop een beter, generiek toepasbaar algoritme te vinden.
De geselecteerde algoritmes luisteren naar de namen Dilithium, Falcon en SPHINCS. In onderstaande tabel worden deze vergeleken met RSA-2048 en Ed25519, wat hedendaagse algoritmes zijn voor digitale handtekeningen gebaseerd op respectievelijk RSA en op elliptische krommen. In onderstaande tabel hebben alle algoritmes een veiligheidsniveau van ongeveer 128 bits, met uitzondering van het nog steeds erg populaire RSA-2048, wat eerder op 112 bits security gemapt moet worden. SPHINCS+128s en SPHINCS+128f verschillen slechts in de gekozen parameters; respectievelijk worden de handtekeninggrootte en de ondertekentijd geminimaliseerd.
Afgaande op te tabel lijkt Falcon de beste van de drie kwantumresistente algoritmes. Wat de tabel niet toont is dat het veilig implementeren van Falcon enorm complex is en dat bij een nieuwe generatie processoren we daarmee misschien weer van vooraf aan mogen beginnen. Een hoge implementatiecomplexiteit gaat onvermijdelijk gepaard met een grotere kans op bugs en dus op een onveilige implementatie. De grote moeilijkheid is het uitvoeren van bepaalde (floating point) operaties in constante tijd, onafhankelijk van de inputwaarden. Dit moet vermijden dat de reken- (en dus respons-)tijd informatie zou lekken. Deze vereiste speelt echter niet wanneer de digitale handtekeningen offline geplaatst worden, zoals op pdf-documenten of digitale certificaten. In deze gevallen is Falcon dan ook een goede keuze.
Dilithium is computationeel efficiënter en is – in tegenstelling tot Falcon – vrij eenvoudig veilig te implementeren. Helaas resulteert dit algoritme in aanzienlijk grotere publieke sleutels en handtekeningen. Dit zal een impact zal hebben op bijvoorbeeld TLS handshake protocols, om een veilig kanaal tussen twee partijen op te zetten, bijvoorbeeld wanneer u naar een webpagina surft.
SPHINCS, ten slotte, resulteert in enorm grote handtekeningen en ook het handtekenen zelf is erg zwaar. Ook verificatie van digitale handtekeningen is niet geweldig. Het heeft wel als voordeel dat de publieke sleutels erg klein zijn en dat het steunt op een erg solide en goed gekende aanname uit de cryptografie.
X.509 certificaten zijn vandaag de standaard om een publieke sleutel te koppelen aan een identiteit. Op uw eID kaart, bijvoorbeeld, staan twee dergelijke certificaten; het ene stelt u in staat om digitale handtekeningen te plaatsen, het andere laat toe u op een sterke wijze te authenticeren. Ook voor het opzetten van een veilig kanaal beschikt deze website (smalsresearch.be) over een X.509 certificaat. Welk van bovenstaande algoritmes ook toegepast wordt, X.509 certificaten op basis van kwantumresistente cryptografie zullen sowieso een pak groter worden dan wat vandaag het geval is; Een X.509 certificaat bevat immers sowieso een publieke sleutel én een digitale handtekening. Ook voor authenticatie van machines of personen kan onderliggend beroep gedaan worden op algoritmes voor digitale handtekeningen. Dergelijke authenticatie zal, wanneer gemigreerd wordt naar de geselecteerde algoritmes, aan efficiëntie verliezen.
Samengevat is er voor elk van de drie door het NIST geselecteerde algoritmes wel een of ander stevig nadeel. De keuze van het algoritme zal dan ook afhangen van de toepassing. Bovendien zijn deze algoritmes systematisch trager dan wat we vandaag kennen. Dit gebrek aan een efficiënt en generiek bruikbaar kwantumresistent handtekeningschema noopte het NIST ertoe een nieuwe standaardisatieprocedure op te starten. Vergeet niet dat Dilithium, Falcon en SPHINCS in 2016 ingezonden werden en we ondertussen toch weer een aantal jaar verder zijn.
Aanbevelingen
Het Duitse BSI (Bundesambt für Sicherheit in der Informationstechnik) kwam vorig jaar met een aantal aanbevelingen met betrekking tot kwantumresistente cryptografie. Een eerste is die van cryptoagility, waarover het BSI schrijft:
In the development of new and the maintenance of existing applications, particular attention should be paid to making the cryptographic mechanisms as flexible as possible in order to be able to react to all conceivable developments, implement upcoming recommendations and standards and possibly replace algorithms in the future that no longer guarantee the desired level of security (“cryptoagility”).
Een belangrijke eigenschap van de geselecteerde algoritmes is dat dezelfde API als voorheen gebruikt kan worden – weliswaar met andere parameters –, wat migratie alvast vergemakkelijkt.
Meer opmerkelijk is de aanbeveling om voorlopig enkel hybride oplossingen toe te passen:
The quantum computer resistant algorithms that are currently being standardized are not yet analyzed as well as the “classical” algorithms (RSA and ECC). This is especially true with regard to weaknesses that become largely apparent in applications, such as typical implementation errors, possible side-channel attacks, etc. Therefore, the BSI does not recommend using post-quantum cryptography alone, but only “hybrid” if possible, i.e. in combination with classical algorithms.
Dit heeft uiteraard een impact op de bytegroottes, op de getransfereerde datavolumes, en op zowel de performantie als de complexiteit van de oplossingen. Dit is een aanbeveling die wellicht op termijn zal verdwijnen, maar voorlopig maakt het migratie naar kwantumresistentie er niet aantrekkelijker op.
Hoe verder?
Volgens sommige experten – al zijn de meningen verdeeld – moeten we dringend migreren naar kwantumresistente cryptografie en komen de NIST standaarden zelfs wat te laat, ook al is een bedreigende kwantumcomputer nog vele jaren van ons verwijderd. Daarbij wordt verwezen naar een aanval waarbij vandaag vercijferde data verzameld en bewaard worden, met als doel deze te decrypteren eens de (kwantum?)technologie dit toelaat.
Anderzijds is er nog werk aan de winkel is. Het vertrouwen in de nieuwe standaarden moet nog groeien en in het geval van digitale handtekeningen is het NIST nog steeds op zoek naar de heilige graal.
Eens een standaardisatieronde voltooid is, zal het wellicht geïntegreerd worden in allerlei services, producten en libraries, zoals TLS libraries. Services met TLS kwantumbreekbare verbindingen zullen dan vroeg of laat een lagere ranking of strenge aanbevelingen krijgen, bijvoorbeeld bij de erg populaire test van SSL labs of in auditrapporten.
Voorlopig is migreren nog niet aan de orde. Wat wel aan de orde is, is het toepassen van het eerder vermeldde cryptoagility om een latere migratie te faciliteren.
Dit is een ingezonden bijdrage van Kristof Verslype, cryptograaf bij Smals Research. Het werd geschreven in eigen naam en neemt geen standpunt in namens Smals.
Afbeelding: Darwin Falls, Tim DonnellyFollow, CC
Leave a Reply