Van één zaadje tot duizend bladeren - de authenticatieboom van Merkle

De wereld evolueert echter. We kunnen ons nauwelijks een leven voorstellen zonder computer, mobiele telefoon of internet. Het probleem met gewone handtekeningen in deze omgeving is dat ze eenvoudigweg gekopieerd en geplakt kunnen worden van het ene document naar het andere, net als een mooie sticker. Dat is zeer handig wanneer je een document niet wilt printen, enkel wilt signeren en vervolgens weer wilt scannen — we kennen allemaal de strijd van tekenen met een touchpad of computermuis (ik krijg altijd vreemde krabbels in plaats van een handtekening). Maar helaas: als je het kunt kopiëren en plakken, kan iedereen dat doen. En ik wed dat het niet prettig voelt als je op een ochtend wakker wordt en al je aandelen en investeren weg zijn omdat iemand je handtekening heeft vervalst op een schenkingsakte.

Gelukkig is er een oplossing. Al in 1979 bedacht Ralph Charles Merkle een idee voor een digitale handtekening, dat hij beschreef in zijn PhD-thesis "Secrecy, Authentication, and Public Key Systems". Om precies te zijn was het idee van een digitale handtekening niet van hem; hij verbeterde een reeds bestaande Lamport-Diffie 'one-time signature', die op zijn beurt weer een verbeterde versie was van de handtekening van Rabin, zoals Leslie Lamport zelf vermeldt in de beschrijving van zijn rapportage op het Microsoft research forum.

Wat is de Lamport-Diffie one-time signature?

Merkle legt dit uit met een helder voorbeeld. Stel je twee personen voor: Alice, die aandelen bezit, en Bob, een makelaar. Alice wil haar aandeel verkopen, maar Bob kan noch een telefoongesprek, noch een bericht accepteren als bevestiging (aangezien het tegenwoordig zo makkelijk is om iemands stem te deepfaken). Daarom herinneren ze zich dat toen Alice dit aandeel kocht, zij $F(x)=y$ berekende met behulp van een eenrichtingsfunctie (one-way function) en dit naar Bob stuurde. Ze hebben zelfs een contract getekend dat $F$ en $y$ bevatten, maar niet $x$, en zijn overengekomen dat als Alice haar aandeel wil verkopen, zij haar $x$ aan Bob zal onthullen.

Merk op dat $F$ een eenrichtingsfunctie is en dus onomkeerbaar; dit betekent dat er geen andere manier is voor Bob om $x$ te verkrijgen, tenzij Alice deze aan hem onthult. Daarom kunnen we stellen dat het 1-bit bericht dat Alice stuurt, geauthenticeerd is.

Berichten met een grotere lengte

Wat als Alice een langer bericht wil sturen? Zelden wil iemand al zijn aandelen in één keer verkopen; vaker verkopen mensen een bepaald aantal shares. Stel dat Alice 11 aandelen wil verkopen. Om dit te doen, moet het koopcontract er anders uitzien.

Alice zou $j$ private sleutels $x$ moeten kiezen: \[\begin{matrix} x1 \\ x2 \\ x3 \\ \vdots \\ xj \end{matrix}\] en voor elk van deze $yj = F(xj)$ berekenen. Deze $j$ publieke sleutelwaarden deelt zij vervolgens met Bob als een publieke sleutelvector $Y_i$.

De waarde $j$ is een vast getal dat de bitlengte vertegenwoordigt van het bericht dat Alice kan signeren. In ons voorbeeld gebruiken we $j=100$.

Stel dat Alice later een bericht $m$ wil sturen: "Verkoop 11 aandelen". Eerst heeft ze een binaire representatie van haar bericht nodig: 01010011 01100101 01101100 01101100 00100000 00110001 00110001 00100000 01110011 01101000 01100001 01110010 01100101 01110011

De lengte van dit bericht is 112 bits, maar aangezien $j=100$, heeft ze slechts 100 vooraf berekende sleutels en kan ze dus slechts 100 bits signeren. Dit betekent niet dat ze haar bericht korter moet maken. In plaats daarvan gebruiken we een andere eenrichtingsfunctie om alle 112 bits te mappen naar 100 bits. Als het bericht te kort zou zijn, vullen we het aan met nullen tot het precies 100 bits is.

Voor elke bit van de 100 heeft ze een private sleutel $xj$ en een publieke sleutel $yj$. Om haar bericht $m$ te signeren, stuurt ze Bob alle $xj$ voor alle bits die gelijk zijn aan 1 in haar bericht. In ons voorbeeld stuurt ze voor de letter 's': \[\begin{array}{l} \texttt{01010011} \\[1ex] x2 \\ x4 \\ x7 \\ x_8 \end{array}\]

Voor de volgende letter 'e' onthult zij: \[\begin{array}{l} \texttt{01100101} \\[1ex] x2 \\ x3 \\ x6 \\ x8 \end{array}\]

Op deze manier signeert Alice elke bit van haar bericht.

Is het bericht nu beveiligd?

Niet volledig. Er is een manier voor Bob om het bericht te wijzigen. Hij kan simpelweg doen alsof hij een van de private sleutels $x_j$ niet van Alice heeft ontvangen, waardoor hij een 1 in het bericht verandert in een 0. Zo kan hij beweren dat Alice in plaats van 11 aandelen (00110001 00110001) vroeg om slechts 10 aandelen te verkopen (00110001 00110000).

Om dit te voorkomen, stellen Lamport en Diffie voor om $m'$ — een complement van $m$ — aan het einde van het bericht toe te voegen. Als Bob nu 11 aandelen wil veranderen in 10 aandelen, zou hij de $x_j$ moeten onthullen die correspondeert met de 1 in het complement $m'$, wat hij niet kan omdat Alice die private sleutel nooit heeft gestuurd.

Voorbeeld:

  • Origineel: mm' = 00110001 00110001 11001110 11001110
  • Vervalst: mm' = 00110001 00110000 11001110 11001111

De verbetering van Merkle aan de Lamport-Diffie handtekening

Hoewel het systeem nu werkt, vereist een dergelijke eenmalige handtekening te veel opslagruimte. Ralph Merkle besloot het algoritme te verbeteren.

Efficiëntere bescherming tegen vervalsing

De eerste oplossing van Merkle was om de feitelijke lengte van het beveiligde bericht te verminderen. Lamport stelde voor om het complement $m'$ van $m$ te gebruiken, maar dat maakte het bericht twee keer zo lang.

Om opslagruimte te besparen, voegt Merkle het aantal nullen toe aan het einde van het bericht $m$. Hiervoor zijn slechts $\lceil \log2 j \rceil$ extra bits nodig (in ons voorbeeld: $\lceil \log2 100 \rceil = 7$), wat aanzienlijk minder is dan in de methode van Lamport.

Waarom $\log_2$? Het aantal nullen wordt opgeslagen als een binair getal. Voor een bericht van 100 bits kan het aantal nullen maximaal 100 zijn. Omdat 100 tussen $2^6=64$ en $2^7=128$ ligt, zijn er 7 bits nodig om dit op te slaan.

Waarom niet het aantal éénen opslaan? Dat zou de handtekening namelijk niet beschermen tegen wijzigingen. Bob kan alleen éénen in nullen veranderen, niet andersom. Voor het veranderen van een 0 naar een 1 zou hij een private sleutel nodig hebben die hij nooit heeft ontvangen.

Voorbeeld (met een bericht van 8 bits en vijf nullen):

  • Origineel: 10001100 | aantal nullen: 101
  • Bob wil vervalsen door een 1 in een 0 te veranderen. Het bericht heeft nu zes nullen: 10001000 | aantal nullen: 110

Zoals je ziet, betekent het veranderen van een 1 in een 0 in het eerste deel dat er ook een 0 in een 1 moet worden veranderd in het tellerveld, wat Bob niet kan. Als we echter het aantal éénen zouden opslaan, zou Bob dit probleemloos kunnen vervalsen door in beide delen éénen in nullen te veranderen.

Boomauthenticatie (The Merkle Tree)

Zelfs met de bovenstaande verbetering blijft het probleem van de opslag van publieke sleutels bestaan. Zonder deze sleutels kan Bob niet weten of het bericht echt van Alice komt, of bijvoorbeeld van een aanvaller (Eva). Om dit op te lossen, introduceerde Merkle "boomauthenticatie".

Hoe werkt boomauthenticatie?

De constructie ziet eruit als een binaire boom. De bladeren zijn de $Y_i$ waarden (de publieke sleutels berekend via de Lamport-Diffie methode). De innerlijke knopen en de wortel (root) worden inductief berekend met behulp van een andere eenrichtingsfunctie $H$.

We beginnen bij de bladeren met: \[H(i, i, Y) = F(Y_i)\] En we gaan omhoog naar de wortel met: \[H(i, j, Y) = F\!\left( H\!\left(i,\, \frac{i+j}{2},\, Y\right),\; H\!\left(\frac{i+j}{2} + 1,\, j,\, Y\right) \right)\]

Voorbeeld van het proces

Stel dat Alice acht gesigneerde berichten naar Bob wil kunnen sturen.

  1. Ze berekent 8 vectoren $Y1, Y2, \ldots, Y_8$ via Lamport-Diffie.
  2. Ze berekent de bladknopen: $H(1, 1, Y1) = F(Y1)$ tot en met $H(8, 8, Y8) = F(Y8)$.
  3. Ze creëert innerlijke knopen door paren te combineren:
  • $H(1, 2, Y{1,2}) = F( H(1, 1, Y1), H(2, 2, Y_2) )$
  • ... enzovoort voor alle paren.
  1. Ze herhaalt dit proces tot er één uiteindelijke waarde overblijft: de wortelwaarde $R$.

Dit is de enige waarde waar Bob en Alice vooraf mee akkoord moeten gaan; het is de enige publieke sleutel die Bob hoeft op te slaan.

Hoe signeert Alice het bericht?

Wanneer Alice het eerste bericht ($m_1$) stuurt, verloopt de verificatie via een dialoog:

  • Alice stuurt: $H(5, 8, Y{5,8})$ en $H(1, 4, Y{1,4})$.
  • Bob controleert met zijn opgeslagen wortel $R$: Is $R = F( H(1, 4, Y{1,4}), H(5, 8, Y{5,8}) )$? Zo ja, ga door.
  • Alice stuurt: $H(1, 2, Y{1,2})$ en $H(3, 4, Y{3,4})$.
  • Bob controleert: Is $H(1, 4, Y{1,4}) = F( H(1, 2, Y{1,2}), H(3, 4, Y_{3,4}) )$? Zo ja, ga door.
  • Alice stuurt: $H(1, 1, Y1)$ en $H(2, 2, Y2)$.
  • Bob controleert: Is $H(1, 2, Y{1,2}) = F( H(1, 1, Y1), H(2, 2, Y_2) )$? Zo ja, ga door.
  • Alice stuurt: $Y_1$.
  • Bob controleert: Is $F(Y1) = H(1, 1, Y1)$?

Als alles klopt, is het bericht gegarandeerd van Alice. Nadat alle 8 signatures zijn gebruikt, moet de wortelwaarde $R$ worden gewijzigd en de boom opnieuw berekend.

Opslagruimte: De enorme winst

Laten we de opslag berekenen voor 1000 berichten waarbij hashfuncties een output van 100 bits hebben.

Bij Lamport-Diffie: Per bericht zijn $2 \cdot j$ sleutels nodig van $s$ bits lang: $2 \cdot 100 \cdot 100 = 20.000$ bits per bericht. Voor 1000 berichten: $20.000 \times 1000 = 20.000.000$ bits $\approx 2,5$ MB per gebruiker. Bij 1000 gebruikers is dat ongeveer 2,5 GB aan opslag voor Bob.

Bij Merkle Tree: Bob hoeft alleen de wortelwaarde $R$ op te slaan: 100 bits. Het verschil tussen 2,5 GB en 100 bits is gigantisch.

Optimalisatie voor Alice

Alice kan ook haar eigen opslag optimaliseren. In plaats van alle authenticatiepaden op te slaan, kan ze knopen verwijderen zodra ze zijn gebruikt voor verificatie.

Bovendien hoeft ze niet eens alle private sleutels $Xi$ en publieke sleutels $Yi$ op te slaan. Ze kan een enkele seedkey van 200 bits gebruiken. Met deze seedkey kan ze alle private sleutelvectoren herstellen via een encryptiefunctie $C$: \[x_{i,j} = C(\text{seedkey},\; \langle i,\, j \rangle)\] Hierbij is $i$ het berichtnummer en $j$ de positie van de bit. Omdat alleen Alice de seedkey heeft, kan zij als enige geldige private sleutels genereren. Het herberekenen van deze sleutels kost tegenwoordig minimaal aan tijd en energie, wat veel efficiënter is dan alles op te slaan.

Moderne toepassingen: Blockchain

De Merkle-boom is vandaag de dag nog steeds essentieel; het is een fundamenteel onderdeel van blockchain. In plaats van berichten bevatten de bladeren hashes van transacties.

Een bekend voorbeeld is Bitcoin. In het whitepaper "Bitcoin: A Peer-to-Peer Electronic Cash System" wordt de Merkle-boom expliciet genoemd als oplossing voor Simplified Payment Verification (SPV). Dit betekent dat je een enkele transactie kunt verifiëren zonder de gehele blockchain te downloaden. Je hebt alleen het relevante authenticatiepad nodig — precies wat Bob nodig had om één bericht te verifiëren zonder de hele boom op te slaan.

Dit bewijst dat hashfuncties niet alleen dienen voor wachtwoordbeveiliging, maar ook enorme constructies kunnen authentificeren zonder de opslagruimte te overbelasten, wat de Merkle-boom tot een van de belangrijkste stappen in de cryptografie maakt.

***

Bronnen en verdere lectuur:

  • Ralph Charles Merkle's PhD thesis "Secrecy, Authentication, and Public Key Systems"
  • "Constructing Digital Signatures from a One Way Function" door Leslie Lamport
  • "Bitcoin: A Peer-to-Peer Electronic Cash System"