Keyless Signature Infrastructure (KSI) – Een alternatief op PKI voor digitale handtekeningen?

Posted on: 22/03/2016 by: Kristof Verslype

Een public key infrastructure, of kortweg PKI, wordt algemeen gezien als de enige manier om digitale handtekeningen te plaatsen. Toch heeft Estland al acht jaar een alternatief dat luistert naar de naam Keyless Signature Infrastructure, of kortweg KSI. Hoe werkt het en wat zijn de voor- en nadelen?

We beginnen dit artikel met de voorwaarden waaraan een handtekeningschema moet voldoen, vervolgens bespreken we beknopt hoe een public key infrastructure gebruikt kan worden voor het plaatsen en verifiëren van digitale handtekeningen. Daarna gaan we dieper in op een alternative aanpak die gebruik maakt van een Keyless Signature Infrastructure. Ten slotte worden beiden vergeleken.

Eigenschappen digitale handtekeningen

In het algemeen moet een schema voor digitale handtekeningen aan drie eigenschappen voldoen:

  • De integriteit van het ondertekende bericht moet gegarandeerd worden. Anders gezegd, indien het bericht gewijzigd wordt, al is het maar een komma, zal de handtekening niet meer geldig zijn. Het is voor een derde onmogelijk om een nieuwe geldige handtekening te genereren.
  • De authenticiteit van het bericht wordt gegarandeerd door de handtekening, wat wil zeggen dat de verifieerder van de handtekening een hoge graad van vertrouwen heeft in de identiteit van de ondertekenaar.
  • De onweerlegbaarheid van een handtekening houdt in dat de ondertekenaar achteraf niet kan ontkennen dat hij de handtekening geplaatst heeft.

Public Key Infrastructure (PKI)

In dit klassieke scenario beschikt de ondertekenaar over een private sleutel en een bijhorend certificaat. Het certificaat is publiek gekend en bevat naast persoonlijke gegevens zoals bijvoorbeeld naam, rijksregisternummer en land ook een publieke sleutel. Dit alles is ondertekend door een vertrouwde partij, die we de CA of certification authority noemen. Door het vertrouwen in die certification authority hebben we er ook vertrouwen in dat de link tussen identiteit en publieke sleutel in het certificaat correct is (authenticiteit).

Naast het algoritme om het publiek-privaat sleutelpaar te genereren zijn er twee algoritmes van belang: Het ondertekenalgoritme en het verifieeralgoritme zoals geïllustreerd in figuur 1. In het ondertekenalgoritme generereert een ondertekenaar met zijn private sleutel een handtekening voor een specifiek bericht. De ondertekenaar berekent daartoe de hashwaarde van het bericht, wat een unieke fingerprint is met een vaste, korte lengte. Vervolgens doet hij op die hashwaarde een cryptografische operatie die zijn private sleutel vereist. (Met de publieke sleutel kan enkel de inverse berekend worden). Het resultaat is de handtekening, die samen met het bericht en eventueel het certificaat naar de ontvanger gestuurd wordt. De ontvanger kan nu met het verifieeralgoritme nagaan of de handtekening geldig is. Met behulp van de publieke sleutel berekent hij op de handtekening de inverse van de eerder vermeldde cryptografische operatie. Het resultaat daarvan moet gelijk zijn aan de door de ontvanger berekende hashwaarde van het bericht.

Public Key Infrastructure (PKI)

 

Figuur 1: De algoritmes voor het ondertekenen van berichten en het verifiëren van handtekeningen

Een certificaat heeft maar een beperkte geldigheidsperiode (vb. 5 jaar) en zal dus vroeg of laat vervallen. En bij het nieuwe certificaat hoort bovendien een nieuwe private en publieke sleutel. Ook kan een certificaat gerevokeerd worden wanneer de eigenaar bijvoorbeeld zijn private sleutel verloren is of denkt dat iemand anders die heeft kunnen kopiëren. Telkens wanneer een digitale handtekening geverifieerd wordt, moet dus ook nagegaan worden of het certificaat nog geldig is. De PKI stelt daarom een lijst (online OCSP of offline CRL) ter beschikking met alle gerevoceerde certificaten, waartegen het certificaat bij elke verificatie gecheckt moeten worden.

Een uitdaging in dit model is het geldig houden van digitale handtekeningen voor een langere tijd. Hoe kan een handtekening op een document 20 jaar geldig zijn als het certificaat maar 5 jaar geldig is? En hoe kan een handtekening geverifieerd worden als het certificaat ondertussen gerevoceerd is?

Keyless Signature Infrastructure (KSI)

Enkele jaren terug is echter in Estland een ander model opgedoken dat door de Estse burgers gebruikt wordt en waarbij het ondertekenen en het verifiëren enkel gebruik maakt van hash-functies en dus niet langer van publieke sleutelcryptografie.

De ondertekenaar berekent opnieuw de hashwaarde van het te ondertekenen bericht. Van zodra er een minieme wijziging is van het bericht zal de fingerprint er dus totaal anders uitzien. Vervolgens authenticeert de ondertekenaar zich naar de zogenaamde KSI gateway die zo de identiteit van de ondertekenaar kent. Die authenticatie kan in principe op diverse manieren gebeuren, bijvoorbeeld a.d.h.v. de Belgische elektronische identiteitskaart (die wel nog steeds werkt met een PKI en publieke sleutelcryptografie).

Na de authenticatie stuurt de ondertekenaar de hashwaarde van het te ondertekenen document naar de KSI gateway (zie figuur 2). Deze laatste leert dus geen informatie over de inhoud van het bericht. Nu berekent de KSI gateway de hashwaarde van de ontvangen hashwaarde gecombineerd met de identifier van de burger (vb. INSZ-nummer). Bijvoorbeeld x1 = h(d1|id1) in fig. 2. Op die manier is x1 niet alleen gelinkt aan het oorspronkelijke document, maar ook aan de identiteit van de ondertekenaar. Een andere identifier resulteert immers in een totaal andere waarde voor x1.

De KSI groepeert elke seconde opnieuw alle dergelijke hashwaarden van de laatste seconde. In figuur 2 zijn dit x1, x2, x3 en x4. Deze waarden van de laatse seconde worden paarsgewijs samengenomen en van deze paren wordt opnieuw de hashwaarde berekend (x12=h(x1|x2) en x34=h(x3|x4) in figuur 2). Vervolgens wordt deze stap nog eens overgedaan voor deze nieuw hashwaarden (xtop=h(x12|x34)). We gaan zo door tot we één waarde hebben in de top. Zo kan voor een willekeurig aantal documenten een zogenaamde Merkle tree opgesteld worden, met telkens bovenaan één waarde xtop. Voor grote aantallen ingestuurde hashwaarden zal de Merkle tree uiteraard meer niveaus tellen. Elke seconde wordt de nieuwe xtop waarde gepubliceerd, naast de oudere waarden. Op één dag worden zo dus 60*60*24=86400 xtop-waarden gepubliceerd. Een typische grootte voor één waarde is 256 bit.

ksi

 

Figuur 2: Merkle tree op basis van vier documenten

De handtekening bestaat nu uit de exacte tijd, tot op de seconde (timestamp) waarop het document ondertekend werd, samen met enkele hashwaarden uit de net berekende Merkle tree zodat een verifieerder kan nagaan of het document inderdaad op dat moment door de persoon met die welbepaalde identifier ondertekend werd. In het geval van het document doc2 bestaat de handtekening dus uit x1, x34 en de timestamp.

Een verifieerder van doc2 doet nu het volgende. A.d.h.v. de timestamp vraagt hij de correcte xtop op bij de KSI. Hij berekent, zoals geïllustreerd in figuur 3, d2=h(doc2), x2=h(d2|id2), x12=h(x1|x2) en verifieert of xtop==h(x12|x34). Indien de timestamp, de identifier of het document fout of gewijzigd zijn, zal dit niet het geval zijn, gezien dit resulteert in andere hashwaarden. Authenticiteit, integriteit en onweerlegbaarheid worden zo gegarandeerd.

Figuur 3: Verificatie van een handtekening. De waarden in vet zijn gegeven aan de verifieerder. De rest wordt door hem berekend.

 

Figuur 3: Verificatie van een handtekening. De waarden in vet zijn gegeven aan de verifieerder. De rest wordt door hem berekend.

Toch blijft er nog een probleem over. De KSI moet vertrouwd worden gezien deze momenteel nog in staat is om xtop waarden te wijzigen. Daarmee kunnen handtekeningen ongeldig gemaakt worden of kunnen valse handtekeningen in naam van een willekeurige persoon gegenereerd worden. Om dit te vermijden wordt gebruik gemaakt van een hash calendar zoals geïllustreerd in figuur 4. Het komt er op neer dat er een Merkle tree gepubliceerd wordt die onderaan alle tot nog toe gegenereerde xtop waarden bevat. Elke seconde wordt deze Merkle tree dus geactualiseerd. De waarde bovenaan deze Merkle tree noemen we xroot. Deze waarde verandert dus elke seconde aangezien elke seconde er helemaal rechts van de bestaande xtop waarden een nieuwe xtop aan de boom toegevoegd wordt.

Figuur 4: Hash Calendar op basis van een Merkle tree met onderaan alle xtop-waarden en bovenaan de xroot waarde die elke seconde verandert omdat er elke seconde rechtsonder een nieuwe xtop-waarde bijkomt

 

Figuur 4: Hash Calendar op basis van een Merkle tree met onderaan alle xtop-waarden en bovenaan de xroot waarde die elke seconde verandert omdat er elke seconde rechtsonder een nieuwe xtop-waarde bijkomt

Geregeld wordt deze xroot waarde voor een specifiek moment gepubliceerd in bijvoorbeeld media zoals geïllustreerd in figuur 5. Indien een xtop waarde van voor dat moment gewijzigd is of indien er twee verwisseld zijn zal de xroot verschillend zijn van wat er gepubliceerd werd en zal dit dus gedecteerd worden. Bovendien zijn alle xroot waarden, zelfs de meest recente steeds publiekelijk online beschikbaar, waardoor dergelijke wijzigingen niet ongemerkt zullen blijven.

Figuur 5: In de linkerbovenhoek van een krant wordt de x_root voor een specifiek moment gepubliceerd

 

Figuur 5: In de linkerbovenhoek van een krant wordt de x_root voor een specifiek moment gepubliceerd

Hoewel het KSI model wat complexer uit te leggen is, zijn de bouwblokken waar het gebruik van maakt verbazend eenvoudig. In essentie wordt enkel een hash-functie gebruikt.

Aangezien je aldus een publiek consulteerbaare, onwijzigbare ketting hebt van waarden, wordt dit door Guardtime, het bedrijf achter KSI ook een blockchain genoemd, hoewel het niet het gedistribueerde karakter heeft als een blockchain in bitcoin.

Veel cryptografische primitieven zullen sterk verzwakken wanneer quantum computers werkelijkheid worden. Hash functies leiden daar veel minder onder dan bijvoorbeeld RSA, DSA of het modernere ECC, die vandaag meestal gebruikt worden bij digitale handtekeningen op basis van een PKI. Toch wordt momenteel gewerkt aan alternatieven zoals lattice-based cryptografie.

Vergelijking

In onderstaande tabel hebben we getracht de voornaamste verschillen weer te geven. KSI lijkt een erg interessant alternatief op een traditionele PKI dat we misschien wel in overweging moeten nemen gezien onder meer de lagere graad van vertrouwen dat vereist is, de zwakere cryptografische assumpties, alsook de eigenschap dat handtekeningen voor een lange tijd geldig blijven.

  PKI KSI
Cryptografische bouwblokken Asymmetrische sleutels en hash-functies Hash-functies + bouwblokken voor user authenticatie
Geldigheid handtekening Zolang als certificaat geldig Onbeperkt
Creatie handtekening Offline Online
Revocatie check Tijdens verificatie handtekening Tijdens creatie handtekening
Quantum-dreiging Sterk in geval van o.a. RSA en ECC Gematigd
Valse handtekening Vereist private sleutel Vereist authenticatie credentials
Impact hack infrastructuur Catastrofaal, alle certificaten revoceren, alle handtekeningen ongeldig Beperkte schade

Referenties

  • Ahto Buldas, Andres Kroonmaa and Risto Laanoja, Keyless Signatures’ Infrastructure: How to Build Global Distributes Hash-Trees. Secure IT Systems: 18th Nordic Conference, NordSec 2013, Ilulissat, Greenland, October 18-21, 2013, Proceedings.
  • Ahto Buldas, Risto Laanoja, Ahto Truu. Efficient Quantum-Immune Keyless Signatures with Identity. IACR Cryptology ePrint Archive 2014: 321. 2014
  • Guardtime. KSI Blockchain Technology - Blockchain meets Security.
    https://guardtime.com/ksi-technology