Het vorige deel van de reeks kwantumcomputers & cryptografie ging in op de bedreiging die krachtige kwantumcomputers op termijn kunnen vormen voor de moderne publieke sleutelcryptografie. Dit vierde en laatste deel bespreekt hoe we ons daartegen kunnen wapenen met behulp van kwantumresistente cryptografie.

Publieke sleutelcryptografie is steeds gebouwd op veronderstellingen. De huidige generatie publieke sleutelcryptografie steunt op wiskundige problemen waarvan men veronderstelt dat een computer ze niet op een efficiënte wijze kan oplossen. Momenteel is publieke sleutelcryptografie grotendeels gebouwd op ofwel het RSA probleem, ofwel het discrete logaritme probleem voor elliptische krommen (ECDLP). Deze wiskundige problemen zijn inderdaad moeilijk voor een klassieke computer, maar een voldoende krachtige kwantumcomputer kan ze helaas een pak efficiënter oplossen.

Daarom heeft het Amerikaanse NIST, National Institute of Standards and Technology, momenteel een standaardisatieprocedure voor kwantumresistente cryptografische algoritmes lopen. Dergelijke algoritmes steunen op problemen die ook voor een krachtige kwantumcomputer moeilijk zijn. Ze maken zelf geen gebruik van kwantumcomputers en zijn dus bruikbaar met behulp van klassieke computers. De standaardisatieprocedure van het NIST bestaat uit twee luiken: Public-key Encryption and Key-establishment Algorithms enerzijds en Digital Signature Algorithms anderzijds. De procedure loopt over meerdere jaren en de tweede ronde werd onlangs voltooid. 

Verschillende principes

Er zijn een aantal principes waarop kwantumresistente cryptografie gebouwd kan worden. We besparen u de wiskundige details, maar geven toch een kort overzicht van de drie principes die het vaakst gebruikt werden door de ingestuurde NIST kandidaat-algoritmes.

Lattice-based cryptografie is de meest beloftevolle groep. De meeste NIST inzendingen zijn op het principe van lattices (roosters, traliewerken) gebaseerd. Het laat zowel vercijfer- als handtekeningschema’s toe. NTRUEncrypt is het gekendste encryptiealgoritme dat op dit principe steunt. Het werd ontwikkeld en gepatenteerd in 1996. In 2017 werd het in het publieke domein geplaatst. Ondertussen wordt het ondersteund door onder meer de populaire crypto-library BouncyCastle. De sleutels zijn langer dan de hedendaagse cryptografie gebaseerd op ECDLP, maar wel doorgaans korter dan RSA sleutels. Een belangrijke eigenschap is dat het efficiënter is dan zowel ECDLP als RSA, wat natuurlijk zeer interessant is. Bovendien heeft lattice-based cryptografie eigenschappen die interessante mogelijkheden bieden voor geavanceerde cryptografie, waaronder homomorfe encryptie en functionele encryptie. Niet oninteressant is dat in 1999 ook NTRUSign voorgesteld werd, het broertje van NTRUENcrypt voor digitale handtekeningen. Dat bleek helaas al snel, in 2000, onveilig te zijn. Niettemin zijn er ondertussen meerdere andere voorstellen voor digitale handtekeningen gebaseerd op dit principe.

Code-based cryptografie vormt de tweede grootste groep in de lijst van NIST inzendingen. Het oudste algoritme in deze groep werd door Robert McEliece reeds in 1978 voorgesteld en is daarmee één van de oudste algoritmes voor publieke sleutelencryptie, bijna even oud als RSA. Deze groep heeft de reputatie enorm grote publieke sleutels te vereisen, waardoor het de facto onbruikbaar zou worden. Voor het algoritme van McEliece was dit inderdaad het geval: Er worden publieke sleutels tot 8,4MB aanbevolen. Toch zijn er ondertussen modernere code-based voorstellen, waarbij de publieke sleutel slechts enkele kilobytes groot is voor het hoogste veiligheidsniveau (256 bit security) [22]. Dit is weliswaar nog steeds meer dan bij zowel RSA als EC (elliptische krommen) voor hetzelfde veiligheidsniveau. Tijdens de tweede ronde vielen een aantal code-based voorstellen af door de ontdekking van nieuwe aanvallen.

Multivariate cryptografie is de derde grootste groep in de lijst van NIST inzendingen. Opnieuw werden zowel vercijfer- als handtekeningschema’s gebaseerd op dit principe ingezonden. Het principe werd voor het eerst voorgesteld in 1988, maar in 1995 bleek dit eerste voorstel onveilig te zijn. Ondertussen zijn er tal van andere multivariate cryptografische schema’s voorgesteld.  Eentje ervan is LUOV, de NIST inzending van de KU Leuven voor het luik digitale handtekeningen. Voor het hoogste veiligheidsniveau – 256 bit security – bedraagt de lengte van de publieke en private LUOV-sleutel respectievelijk 82.0 KB en 32 bytes. Een handtekening is 440 bytes lang. Met andere woorden heeft LUOV grote publieke sleutels, maar wel kleine digitale handtekeningen, die weliswaar nog steeds langer zijn dan digitale handtekeningen gebaseerd op ECDLP. Helaas overleefde LUOV de tweede NIST selectieronde niet doordat ondertussen nieuwe aanvallen gevonden waren, onder meer tegen LUOV. Die LUOV zwakheden zijn misschien wel te verhelpen, maar volgens het NIST toont het wel aan dat de innovatie in LUOV ten opzichte van reeds bestaande algoritmes nog te nieuw is om het tot standaard te verheffen.

Samengevat heeft het NIST de moeilijke opdracht om een keuze te maken uit een hele set van kandidaten met erg uiteenlopende eigenschappen, en dit in een context waarbij er geregeld nieuwe zwakheden ontdekt worden.

Standaardisatie

Het NIST heeft, zoals reeds vermeld, een standaardisatieproject voor kwantumresistente cryptografie lopen, bestaande uit twee luiken: Public-key Encryption and Key-establishment Algorithms  enerzijds en Digital Signature Algorithms anderzijds. In december 2016 publiceerde het NIST een call for proposals, waarop tot eind november 2017 gereageerd kon worden. Er werden 82 kandidaat-algoritmes ingezonden, waarvan er 69 weerhouden werden. Na de eerste ronde waren er 26 overblijvers: 17 voor Public-key Encryption and Key-establishment Algorithms  en 9 voor Digital Signature Algorithms.

De tweede ronde werd afgerond op 22 juli 2020, waarbij de zeven finalisten bekend gemaakt werden, alsook de acht alternatieve voorstellen. Onder de vier finalisten voor het eerste luik (encryptie en key-establishment) vinden we o.a. CRYSTALS-KYBER van IBM en SABER van de KU Leuven. Bij de finalisten voor digitale handtekeningen vinden we opnieuw een IBM inzending, genaamd CRYSTALS-DILITHIUM. De KU Leuven inzending, LUOV, werd, zoals reeds vermeld, niet weerhouden wegens te prematuur.

Er wordt verwacht dat de derde ronde 12 tot 18 maand zal duren, wat hopelijk zal resulteren in nieuwe standaarden. Vijf van de zeven finalisten zijn lattice-based, en dus gebaseerd op (ruwweg) hetzelfde wiskundige principe. Bovendien valt niet uit te sluiten dat er alsnog fundamentele zwakheden ontdekt zullen worden na de NIST standardisatie. Daarom zal er nog een vierde ronde komen om na te gaan of er ook uit de acht alternatieve kandidaten gestandaardiseerd kan worden om zo over alternatieven, gebaseerd op andere principes, te beschikken mocht dit ooit nodig zijn.

De inzendingen kunnen, net zoals de huidige generatie algoritmes voor publieke sleutelcryptografie, gewoon op klassieke computers uitgevoerd worden. Na de publicatie van de nieuwe NIST standaarden moeten de gekozen algoritmes geïntegreerd worden in bestaande cryptografische library’s zoals OpenSSL, libssh en BouncyCastle. Pas dan kunnen de kwantumresistente algoritmes gebruikt worden in – bestaande of nieuwe – toepassingen in productie. Er bestaan weliswaar reeds libraries met kwantumresistente cryptografische algoritmes. In de eerste plaatst denken we dan aan het Open Quantum Safe (OQS) project, dat een implementatie bevat van – op het moment van schrijven op één na – alle NIST finalisten. OQS stelt duidelijk dat deze implementaties momenteel enkel dienen voor prototyping en het evalueren van de algoritmes. Het is inderdaad mogelijk dat sommige van deze algoritmes alsnog fouten bevatten en minder veilig zijn dan aanvankelijk aangenomen, mogelijks ook ten aanzien van klassieke computers.

De NIST standaardisatieprocedure voor kwantumresistente cryptografie is erg complex door de noodzakelijke rigoureuze analyse van elk van de kandidaat-algoritmes. Omdat die procedure meerdere jaren in beslag neemt, is het NIST een eenvoudigere en snellere standaardisatieprocedure gestart om een meer dringende nood aan kwantumresistente digitale handtekeningen te ledigen. Het gaat daarbij om twee hash-based signature schemes, die weliswaar kwantumresistent zijn, maar wel twee belangrijke nadelen hebben: Met één sleutel kan maar een beperkt aantal digitale handtekeningen geplaatst worden en er moet samen met de private sleutel een tellertje bijgehouden worden dat bij elke handtekening verhoogd wordt. Deze schema’s zijn dus niet geschikt voor algemeen gebruik. Een draft van de nieuwe NIST standaard is sinds 19 december 2019 beschikbaar.

NSA

Het IAD is de defensieve tak van de Amerikaanse inlichtingendienst NSA (National Security Agency) . Voorlopig ondersteunt het IAD nog in haar CNSA (Commercial National Security Algorithm) suite zowel RSA als EC voor het beschermen van informatie tot op het allerhoogste niveau – Top secret –, mits voldoende lange sleutels uiteraard. Toch bereidt ze zich voor om op termijn cryptografie gebaseerd op het RSA probleem of op het ECDLP te vervangen door kwantumresistente cryptografie en formuleerde het reeds in 2015 als volgt:

“IAD will initiate a transition to quantum resistant algorithms in the not too distant future. […] For those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition.[…] Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, which has made it clear that elliptic curve cryptography is not the long term solution many once hoped it would be. Thus, we have been obligated to update our strategy.”

De NSA neemt de mogelijkheid dat er op termijn een vreemde mogendheid over een voldoende krachtige kwantumcomputer beschikt dus serieus. Op zijn minst acht ze het risico daarop te groot om er niet op te anticiperen. Ze schrijft zelfs dat kwantumresistente cryptografie essentieel is voor de verdediging van de Verenigde Staten.

Recent sprak de NSA haar vertrouwen uit in lattice-based cryptografie voor algemene toepassingen en hash-based signatures voor bepaalde niche toepassingen.

Hardware ondersteuning

Een HSM (Hardware Security Module) is hardware die toelaat cryptografische operaties uit te voeren met behulp van sleutels die door die HSM zelf beschermd worden en in principe die HSM nooit verlaten. Navraag leert dat de meeste aanbieders van HSMs de NIST standaardisatieprocedure afwachten. Bemerk wel dat HSMs veelal de mogelijkheid  ondersteunen om code van cryptografische algoritmes in te laden, waardoor – mits wat meer werk – toch reeds kwantumresistente cryptografie op HSM’s mogelijk wordt. Het bedrijf Ultimaco profileert zich nog het meeste rond kwantumresistente cryptografie.

Conclusie

Zoals we eerder in onze reeks kwantumcomputers & cryptografie aangaven, is het bouwen van een voldoende krachtige kwantumcomputer die effectief een bedreiging vormt voor de huidige publieke sleutelcryptografie gigantisch complex, misschien zelfs onmogelijk. Of en wanneer een dergelijke computer zal gerealiseerd worden blijft giswerk. Niemand heeft een glazen bol en een doorbraak of nieuw inzicht kan de verwachtingen sterk beïnvloeden in zowel de ene als de andere richting. Dit neemt echter niet weg dat nog heel wat hordes genomen moeten worden.

We zien dan ook geen imminente dreiging. We raden ten eerste aan om de NIST standaardisatieprocedure af te wachten vooraleer over te schakelen naar het gebruik van kwantumresistente cryptografie in productieomgevingen. Ten tweede raden we aan om grote kosten om te migreren naar kwantumresisente cryptografie te vermijden en eerder te opteren voor een geleidelijk migratieproces. Het migreren impliceert immers niet alleen een update van de software, maar ook eventueel hardware (zoals HSMs), het vervangen van alle publieke sleutels en certificaten, enz. Kwantumresistente cryptografie kan zelfs efficiënter zijn dan de huidige cryptografie, wat op zich al een interessante driver kan zijn om langzaam aan te migreren.

Sowieso is het noodzakelijk een goed overzicht te hebben van welke cryptografie waar toegepast wordt om welke data te beschermen. Voor gegevens (in transit of at rest) die meerdere decennia erg gevoelig blijven kan migratie een hogere prioriteit krijgen. Ook dienen systemen voldoende flexibel gebouwd te worden opdat ze relatief vlot aangepast kunnen worden om overweg te kunnen met nieuwe cryptografische bouwblokken. Dit heet crypto agility en is sowieso een best practice, los van een eventuele kwantumdreiging.

---

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.

Bronvermelding afbeeldingen
– https://www.pikist.com/free-photo-ijlpz (Royalty free) 
– https://www.esat.kuleuven.be/cosic/pqcrypto/luov/
– Draft NIST Special Publication 800-208