4 Cryptografie
Whitfield Diffie had altijd al een voorliefde voor codes. Al sinds zijn docent in het vijfde leerjaar hem substitutieversleuteling leerde (een basistechniek in de wiskundige tak van de cryptografie), was hij gefascineerd door deze methode van geheimhouding. Het feit dat tekstversleutelingsalgoritmen in die tijd – de jaren vijftig – de specialiteit van het leger, geheime agenten en spionnen waren, droeg alleen maar bij tot de mysterieuze aantrekkingskracht.1
De jonge Whitfield was al snel in de ban van elk cryptografieboek dat zijn vader, een universiteitsprofessor, in de bibliotheek van het City College in New York kon vinden. Hij stortte zich op werken zoals het boek Cryptoanalysis uit 1939 van Helen Forché Gaines, dat diverse methoden beschreef om berichten om te zetten in onleesbare versleutelde tekst, bij voorkeur zo dat alleen de beoogde ontvanger ze kon ontcijferen.
Met de zeer simpele Caesar-cipher (vermoedelijk gebruikt door Julius Caesar), kunnen berichten bijvoorbeeld in ciphertext worden omgezet door elke letter te vervangen door een andere letter. De coderingssleutel ‘+1’ vervangt bijvoorbeeld elke letter door de volgende letter in het alfabet - ‘a’ wordt ‘b’, ‘b’ wordt ‘c’, enzovoort. Het woord ‘Secret’ verandert in ‘Tfdsfu’. Om de versleutelde tekst te ontcijferen, wordt dezelfde coderingssleutel gebruikt, maar in omgekeerde volgorde: elke letter wordt vervangen door de vorige letter in het alfabet ( ‘Tfdsfu’ wordt weer ‘Secret’).
Deze +1 coderingssleutel is natuurlijk niet erg sterk. Een tegenstander die vastbesloten is om de resulterende ciphertext te ontcijferen – een cryptanalist – zou het waarschijnlijk bij hun eerste poging raden. En zelfs al doen ze dat niet, zijn er toch een aantal patronen in een versleutelde tekst die gespecialiseerde codekrakers kunnen helpen te bepalen welke vervangende letters waarschijnlijk overeenkomen met welke originele letters. Vooral in langere teksten kunnen aanwijzingen worden gevonden in de frequentie van specifieke letters en de lengte van woorden, om maar een paar voorbeelden te noemen.
Moderne coderingssleutels gebruikten daarom veel geavanceerdere technieken, en gebruikten bijvoorbeeld enkele delen van een tekst om andere delen te versleutelen. Tegen het midden van de twintigste eeuw was encryptie, en het breken ervan, essentieel voor militaire operaties. Het werk werd uitgevoerd door toegewijde specialisten die het vakgebied verder hadden ontwikkeld tot het punt waarop ciphertext volledig willekeurig kon lijken. Zonder patronen om te analyseren, waren zelfs de beste cryptografen ter wereld niet in staat om de codes te breken.
Desalniettemin bleef het basisidee grotendeels onveranderd. Net als bij de Caesar-cipher waren de geheime sleutels altijd symmetrisch: de decoderingssleutel was dezelfde als de coderingssleutel, alleen in omgekeerde volgorde gebruikt. Om veilig te communiceren, moesten mensen eerst een sleutel met elkaar uitwisselen.
Een sleutel via een onbeveiligd communicatiekanaal delen, was echter geen optie. Als iemand meeluisterde en de sleutel kon onderscheppen, zouden ze alle daaropvolgende berichten die met die sleutel gecodeerd waren, kunnen ontcijferen. Hiermee zou dus het hele doel van het versleutelen van berichten teniet gedaan worden. De sleutels werden daarom meestal in persoon gedeeld. Beide partijen moesten eerst fysiek samenkomen voordat ze versleutelde berichten konden uitwisselen.
Dit was natuurlijk niet altijd gemakkelijk, of zelfs mogelijk. Grote afstanden of extreme situaties zoals oorlog konden het proces aanzienlijk bemoeilijken. Toch geloofden cryptografen, zoals Diffie in zijn beginjaren leerde, dat er geen andere manier was: men moest eerst sleutels persoonlijk uitwisselen.
MIT
Ongeveer tien jaar nadat hij voor het eerst met de methode van de substitutiecipher kennismaakte, begon Whitfield Diffie wiskunde te studeren aan de Massachusetts Institute of Technology. Dit viel ook samen met de komst van de allereerste computers op de universiteitscampus. Hoewel hij zichzelf toen, als jonge twintiger en als een naar eigen zeggen vredelievend persoon, meer als een pure wiskundige dan als een informaticus zag, besloot Diffie toch om te leren programmeren. Zo wilde hij zijn vaardigheden uitbreiden met meer praktische kennis.
Het zou goed uitpakken voor hem. In 1965 studeerde hij af aan de technische universtiteit, en accepteerde hij een baan bij Mitre, een defensiecontractant die slechts een paar jaren daarvoor van MIT’s Lincoln Laboratory afgesplitst was. Zo kon hij tijdens de Vietnamoorlog aan de dienstplicht ontsnappen, terwijl het werk zelf ook niets met de oorlog te maken had. Diffie zou helpen bij de ontwikkeling van het computeralgebrasysteem Macsyma.
Diffie hoefde zelfs niet naar het kantoor van Mitre te komen. Hij kon werken vanuit het AI Lab van MIT, waar hij zich volledig verdiepte in de nieuwe hackercultuur en haar vrije en collaboratieve filosofie.
Toch week Diffie op sommige punten van de typische hackerethiek af. Hij was niet van mening dat onbeperkte vrijheid in alle computeromgevingen gewenst was en vond dat software in bepaalde contexten ook privacy moest bieden. Naarmate mensen, bedrijven en regeringen hun activiteiten naar het digitale domein gingen verplaatsen, zag hij in dat het belangrijk zou worden om gevoelige data, zoals persoonlijke gezondheidsgegevens, bedrijfsfinanciën of militaire geheimen, te beschermen.
Diffie nam het initiatief om een virtuele kluis te bouwen. Net zoals een fysieke kluis, moest de digitale variant eenvoudig te openen zijn door de legitieme eigenaar van de gegevens, maar de toegang voor alle anderen beperken. Hij geloofde dat sterke versleuteling dit type probleem kon oplossen.
Hoewel de hacker zijn jeugdpassie eigenlijk niet echt had behouden (hij geloofde dat alle relevante paden in het domein van cryptografie al waren verkend) hielp zijn baas bij het AI Lab, de wiskundige Roland Silver, hem weer op de been. En toen Diffie ontdekte dat er, sinds hij het als kind bestudeerde, significante vooruitgang in het veld van cryptografie geboekt was, werd zijn interesse opnieuw aangewakkerd.
Maar Diffie leerde nu ook dat de werkelijke voorhoede van cryptografie waarschijnlijk achter gesloten deuren verborgen bleef. De National Security Agency (NSA), de Amerikaanse inlichtingendienst die destijds in het geheim werkte en officieel niet bestond, had al jaren de beste cryptografen van het land binnengehaald. Waarschijnlijk bleef elk echt baanbrekend onderzoek, en de superieure cryptografische technieken die daaruit voortkwamen, geclassificeerd.
Het idee dat de NSA belangrijke informatie voor het publiek kon achterhouden, zat helemaal niet lekker bij Diffie.
Stanford
Toen de hackercultuur zich voor het eerst buiten de campus van MIT begon te verspreiden, vond het al snel een thuis in de San Francisco Bay Area, op de Stanford University. En zo zou ook Diffie zijn weg daarheen vinden. Toen hij in 1969 vierentwintig werd en de leeftijdsgrens voor zijn dienstplicht naderde, ruilde de afgestudeerde van MIT Mitre in om voor het AI Lab van Stanford te werken. Hier vond hij nieuwe uitdagingen die bij zijn hernieuwde interesse in cryptografie pasten.
De eerste van deze uitdagingen werd geïnspireerd door John McCarthy. De mede-oprichter van het AI Lab van MIT en de originele ontwerper van de LISP-programmeertaal was verder gegaan met het oprichten van Stanfords AI Lab, en hij leidde het onderzoeksinstituut toen Diffie daar voor het eerst aankwam. Tegen die tijd had McCarthy een interesse ontwikkeld in de toekomst van digitale handel, wat op zijn beurt Diffie ertoe aanzette om te dromen van het geautomatiseerde kantoor, waar software wordt gebruikt om werkgerelateerde documenten digitaal te creëren, verzamelen, opslaan, bewerken en te verspreiden. Dit motiveerde hem om zich te richten op het vraagstuk rondom authenticatie.
In de fysieke wereld worden documenten doorgaans geverifieerd door middel van persoonlijke, geschreven handtekeningen. Mensen ondertekenen een brief om te bewijzen dat ze echt degenen zijn die hem geschreven hebben, of ze voegen hun handtekening toe aan een contract om het juridisch bindend te maken. Maar, zo bedacht Diffie, naarmate documenten meer digitaal worden, zouden mensen een digitaal equivalent van een handtekening nodig hebben om te bewijzen dat zij echt degenen zijn die de inhoud van deze documenten goedkeurden.
Het creëren van een dergelijke vorm van digitale authenticatie was echter niet zo eenvoudig: Diffie en McCarthy brachten talloze uren door in het onderzoeksinstituut, peinzend over mogelijke oplossingen. Het hoofdprobleem was dat zelfs specifieke individuele gegevens, bijvoorbeeld een lang, persoonlijk nummer, makkelijk waren om te kopiëren. Iedereen kon zo’n digitale handtekening overnemen van één contract en toevoegen aan een ander contract. Dat zou ze nutteloos maken.
Een andere uitdaging ontstond in de schoot van het Advanced Research Projects Agency (ARPA) van het ministerie van Defensie, dat in 1972 was begonnen met het verbinden van grote onderzoeksinstellingen in het land door middel van een computernetwerk: ARPAnet. Als onderdeel van dit project, zocht Larry Roberts, de directeur van Information Processing Techniques bij ARPA, naar manieren om berichten over het netwerk privé te houden. Nadat de NSA hem elke hulp had geweigerd - het geheime overheidsagentschap weigerde aan een dergelijk openbaar project te werken - hoopte hij dat een van zijn belangrijkste onderzoekers misschien een idee had.
Toen McCarthy, een van de belangrijkste onderzoekers, het probleem besprak met de hackers in Stanfords AI Lab, erkende Diffie het belang van dit vraagstuk. Als in de toekomst de communicatie steeds meer elektronisch zou plaatsvinden (en dit was al meer en meer het geval) zou het persoonlijk delen van coderingssleutels waarschijnlijk onhaalbaar worden, waardoor privégesprekken onmogelijk zouden zijn. Tenzij mensen toegang zouden hebben tot hulpmiddelen om hun communicatie te beveiligen, vreesde Diffie dat iedereen op elk moment potentieel in de gaten kon worden gehouden. Een verontrustend toekomstbeeld.
Terwijl hij oplossingen probeerde te vinden voor deze uitdagingen, groeide Diffies hernieuwde interesse in cryptografie langzaam uit tot een obsessie. Zijn enthousiasme werd verder aangewakkerd door het lezen van The Codebreakers, een boek uit 1967 van David Kahn dat de gehele geschiedenis van cryptografie gedetailleerd beschrijft en deels gebaseerd is op informatie van twee NSA-overlopers die naar de Sovjet-Unie waren gevlucht. Hij was steeds meer vastberaden om de cryptografische technieken en inzichten te achterhalen die nog steeds door inlichtingendiensten werden onderdrukt.
Dit was echter niet de enige reden waarom de hacker van het AI Lab uiteindelijk besloot om alles op alles te zetten.
Rondreis door Amerika
Toen Diffie in de zomer van 1973 een oude vriendin, de dierentrainster Marie Fischer uit Brooklyn, bezocht, had hij niet verwacht verliefd te worden. Maar toen dat gebeurde, veranderden zijn plannen drastisch. In plaats van terug te keren naar de Westkust, besloot hij om zijn baan in het AI Lab van Stanford op te zeggen en tijd met zijn nieuwe vriendin op de weg door te brengen. De twee begonnen aan een rondreis door het land in een oude Datsun 510.
Dit gaf Diffie toevallig ook de tijd en gelegenheid om zich echt te wijden aan het ontdekken van superieure cryptografische technieken. Levend van zijn spaargeld, nam hij Fischer mee op zijn zoektocht naar aanwijzingen. Ze bezochten David Kahn, de auteur van The Codebreakers, in Great Neck op Long Island, snuffelden in bibliotheken op zoek naar referentiewerken, en maakten afspraken met experts in de cryptografie uit zowel de academische wereld als het bedrijfsleven over heel de VS.
Diffie hoopte uiteindelijk een formele logicatheorie te ontwikkelen, een wiskundig systeem dat als basis zou dienen voor de cryptografie. Om dit te bereiken, geloofde hij dat hij bij de basis moest beginnen.
Het eenvoudigste cryptografische fenomeen dat hij kon vinden was de eenrichtingsfunctie: een vergelijking waarvan het eenvoudig is om de oplossing in één richting uit te rekenen, maar aanzienlijk moeilijker om in de omgekeerde richting te berekenen.
Een zeer simpele eenrichtingsfunctie — aangeduid als een polynoom — zou herkenbaar moeten zijn voor iedereen die algebra heeft gestudeerd op de middelbare school. Het zou er bijvoorbeeld uit kunnen zien als \(x^{2} - 5x + 8\). Als de invoer (x) in dit voorbeeld 16 is, is het vrij makkelijk te berekenen dat de vergelijking het resultaat 184 als uitkomst geeft. Echter, wanneer alleen de uitkomst van 184 bekend is, kan de vergelijking niet eenvoudig worden omgekeerd om te berekenen dat de oorspronkelijke invoer (x) 16 was. Een eenrichtingsfunctie is het wiskundige equivalent van een eenrichtingsstraat.
Bovendien leerde Diffie het concept van een valdeur kennen, waarvan men aannam dat het een onderdeel kon zijn van sommige soorten eenrichtingsfuncties. Een valdeur was in feite een geheim stuk informatie, meestal een andere vergelijking, dat de omgekeerde berekening ook gemakkelijk zou maken. Als de vergelijking in het voorbeeld hierboven een valdeur bevatte, kon de uitkomst 184 worden gebruikt om de invoer 16 net zo gemakkelijk te berekenen als dat het oorspronkelijk was om 184 uit 16 te produceren. Als een eenrichtingsfunctie een eenrichtingsstraat is, dan is de valdeurfunctie een geheime tunnel in de tegenovergestelde richting.
Deze concepten fascineerden Diffie. Eenrichtingsfuncties en valdeuren leken intuïtief iets van grote waarde te zijn in het veld van de cryptografie, hoewel hij niet precies wist hoe ze gebruikt konden worden.
Via een gemeenschappelijke kennis leidde Diffies vermoeden hem uiteindelijk naar Martin Hellman, een dertigjarige assistent-professor aan Stanford. Hellman deelde zowel Diffies interesse in cryptografie als zijn ideologische overtuiging dat deze technologie veel breder beschikbaar moest zijn: hij had net een baan van de NSA afgewezen omdat hij wilde dat zijn werk de bevolking ten goede zou komen. En ook Hellman had nagedacht over hoe eenrichtingsfuncties breder toegepast konden worden in de cryptografie.
Toen Diffie en Hellman elkaar voor het eerst ontmoetten in 1974 en het idee bespraken in Hellmans kantoor aan Stanford, vonden ze niet meteen de oplossing waar ze naar op zoek waren. Maar in elkaar vonden ze iemand die geïnteresseerd was in hetzelfde probleem. Vanaf dat moment zouden ze hun denkvermogen bundelen door ideeën aan elkaar te toetsen en nieuwe inzichten te delen.
Toen Diffie na meer dan een jaar reizen besloot om zich te vestigen in de Bay Area, werden hij en Hellman goede vrienden en al snel collega’s: Hellman nam Diffie aan als deeltijdse onderzoeker aan de universiteit.
Publieke-sleutelcryptografie
Op een doodgewone middag, toen Diffie op het huis van zijn voormalige werkgever John McCarthy pastte, viel het kwartje eindelijk.
Twee sleutels.
De oplossing was om twee sleutels te gebruiken.
Cryptografen hadden altijd als vanzelfsprekend beschouwd dat coderingssleutels geheim moesten blijven, omdat ze ook dienden als decoderingssleutels. Maar Diffie negeerde deze vanzelfsprekende waarheid en kwam met het idee van sleutelparen. In plaats van slechts één geheime sleutel, zou iedereen twee sleutels hebben, namelijk een geheime sleutel die daadwerkelijk geheim moest blijven, en een publieke sleutel die vrijuit gedeeld kon worden.
Diffie was van mening dat de sleutels wiskundig met elkaar verbonden moesten zijn, waarbij de publieke sleutel in essentie van de geheime sleutel afgeleid werd door middel van een soort eenrichtingsfunctie. Zijn visie was erop gericht dat een verzender – laten we haar ‘Alice’ noemen, zoals cryptografen graag doen – een bericht versleutelde met haar geheime sleutel, waarna de beoogde ontvanger, ‘Bob’, het zou kunnen ontcijferen met behulp van haar publieke sleutel.
Als Bob het bericht inderdaad kan ontcijferen met de publieke sleutel van Alice, bewijst dit dat het bericht specifiek met Alice’s geheime sleutel werd versleuteld. Dit maakt in feite een vorm van authenticatie mogelijk, aangezien de versleutelde versie van een bericht als Alice’s digitale handtekening zou dienen.
Deze digitale handtekeningen zouden zelfs krachtiger zijn dan geschreven handtekeningen, aangezien een cryptografische handtekening alleen geldig zou zijn in combinatie met het precieze stuk data dat werd ondertekend. Als een digitaal contract na ondertekening zou worden gewijzigd, zou de cryptografische handtekening niet meer overeenkomen. Op een bepaalde manier zouden zowel de handtekening als de data zelf onmogelijk na te maken zijn.
Bovendien zag Diffie in dat het omgekeerde ook kon werken. Alice zou een bericht naar Bob kunnen versleutelen met Bobs publieke sleutel, waarna Bob, en alleen Bob, het zou kunnen ontcijferen met zijn geheime sleutel. Publieke-sleutelcryptografie beloofde zowel digitale authenticatie als veilige communicatie te bieden!
Toen het concept die avond aan Hellman werd uitgelegd, was hij het ermee eens dat Diffie potentieel iets belangrijks had bedacht, ook al was het idee nog maar in de ontwerpfase en moest de exacte wiskunde nog worden uitgewerkt. In de weken die volgden, legde het duo de vroege wiskundige basis om het idee tastbaarder te maken.
Dit resulteerde in het eerste gezamenlijk geschreven artikel van Diffie en Hellman. Multiuser Cryptographic Techniques, dat in het voorjaar van 1976 werd gepubliceerd en kort daarna werd gepresenteerd op de National Computer Conference in New York. In het artikel gaven de twee onderzoekers toe dat er nog grote vragen onbeantwoord waren. Ze wisten nog niet precies hoe encryptie of decryptie zou werken, noch hoe een publieke sleutel zou worden afgeleid van een geheime sleutel.
‘Op dit moment hebben we noch een bewijs dat er publieke sleutelsystemen bestaan, noch een demonstratiesysteem.’, gaven Diffie en Hellman toe in hun paper2
Ze kondigden echter aan dat ze bezig waren met iets groots: ze presenteerden het idee van cryptografie met publieke sleutels.
Ralph Merkle
Het artikel was nauwelijks gepubliceerd toen Hellman een brief van een afgestudeerde student aan de Universiteit van Californië, Berkeley ontving.
De student had zelf ook een werkstuk geschreven, zo legde hij uit in zijn brief. ‘De mensen met wie ik probeer te praten, begrijpen totaal niet wat er aan de hand is, of zien elke poging tot het vinden van een oplossing als onmogelijk’, schreef hij. Zijn frustratie druipte van de pagina. Hij concludeerde: ‘Ik zie een kans voor samenwerking en ben geïnteresseerd om die verder te verkennen.’3
Ondertekend: Ralph C. Merkle.
Hoewel Merkle zo’n zeven of acht jaar jonger was dan Diffie en Hellman, leek zijn verhaal niet zo verschillend van dat van hen. Hij was altijd goed geweest met cijfers, stond consequent aan de top van elke wiskunde klas, en had sinds de aanvang van zijn universiteitsloopbaan een bijzondere interesse ontwikkeld voor computers.
In zijn laatste semester als student maakte hij tijdens een cursus over computerbeveiliging kennis met het veld cryptografie. Maar toen de docent de cipher van Caeser en andere vormen van symmetrische versleuteling besprak, realiseerde hij zich meteen dat de noodzakelijke sleuteluitwisseling in persoon de toepasbaarheid ervan ernstig beperkte. Merkle geloofde dat in een wereld waarin steeds meer communicatie digitaal zou gaan verlopen, er dringend behoefte was aan een betere oplossing.
In plaats van het hele land door te reizen op zoek naar antwoorden, beperkte Merkle zijn zoektocht naar een oplossing tot zijn eigen creatieve geest. En uiteindelijk bedacht hij een plan dat, althans tot op zekere hoogte, het probleem zou kunnen oplossen.
Zo zou het werken:
Eerst maakt Alice een groot aantal cryptografische puzzels, misschien wel miljoenen of zelfs meer. De oplossing voor elke puzzel bestaat uit een uniek getal en een even unieke geheime sleutel. Alice zelf kent de oplossing voor elke puzzel al: ze weet welke getallen bij welke geheime sleutels horen. Maar elke individuele puzzel kan ook door iemand anders worden opgelost, mits een beetje rekenkracht.
Alice stuurt vervolgens alle puzzels naar Bob. Bob kiest op zijn beurt willekeurig een puzzel, en lost deze met een beetje rekenkracht op om het unieke nummer en de bijbehorende geheime sleutel te vinden. Daarna stuurt hij het nummer (maar niet de bijbehorende geheime sleutel) naar Alice terug.
Op basis van het unieke nummer dat Bob terugstuurt, weet Alice onmiddellijk welke geheime sleutel Bob daarbij heeft gevonden. Deze geheime sleutel is dan de coderingssleutel die ze met elkaar delen. Net als elke andere symmetrische coderingssleutel, wordt deze gebruikt om berichten tussen hen te coderen en te decoderen.
Een afluisteraar die alle puzzels van Alice naar Bob heeft gezien, en ook welk uniek nummer Bob naar Alice heeft teruggestuurd, zal nog steeds de bijbehorende geheime sleutel niet weten.
Om erachter te komen welke sleutel Alice en Bob hebben gekozen, moet een afluisteraar alle puzzels willekeurig oplossen (via brute kracht) om dat ene unieke nummer te vinden dat Bob terugstuurde, wat tevens de geheime sleutel zal onthullen. Dit is echter een intensief rekenkundig proces. Afhankelijk van de hoeveelheid puzzels die aanvankelijk gemaakt werden (en de moeilijkheidsgraad om elke puzzel op te lossen), zal het veel rekenkracht en tijd in beslag kunnen nemen.
Alice en Bob hebben daarom een asymmetrisch voordeel ten opzichte van de afluisteraar. Ze hoefden nauwelijks berekeningen uit te voeren om het over een geheime sleutel eens te worden, terwijl de afluisteraar heel veel berekeningen moet uitvoeren om hun gesprek te decoderen.
Deze oplossing vereiste echter wel dat Alice en Bob veel data met elkaar deelden in de vorm van puzzels, en de veiligheid van de oplossing nam lineair toe met het totale aantal puzzels. Om het kraken van het systeem tien keer moeilijker te maken, moeten ze tien keer zoveel puzzels delen; om het systeem honderd keer moeilijker te kraken te maken, moeten ze honderd keer zoveel puzzels delen, enzovoort. In de praktijk impliceren de limieten in data en rekenkracht van normale gebruikers dat een goed gefinancierde aanvaller met een supercomputer berichten in veel gevallen binnen enkele dagen zou kunnen ontcijferen.
Desondanks had Merkle een oplossing bedacht die twee mensen de mogelijkheid bood om tamelijk privé te communiceren zonder dat ze elkaar vooraf persoonlijk hoefden te ontmoeten. Hoewel het niet perfect was, was hij van mening dat deze techniek voor sleuteluitwisseling zeker innovatief en potentieel nuttig was.
Merkle was echter niet in staat om iemand anders te overtuigen. Zijn idee ontving weinig lof aan de Universiteit van Berkeley, en zijn artikel werd afgewezen door Communications of the ACM, het prestigieuze blad van de Association for Computing Machinery (ACM). Het verzenden van geheime sleutels via een onveilig netwerk werd door de recensenten als onacceptabel beschouwd. Bovendien merkten zij op dat er geen eerdere literatuur bestond die sleuteluitwisseling had vastgesteld als een belangrijk probleem.
Omdat hij het potentieel ervan aan niemand om hem heen kon uitleggen, stond de teleurgestelde student op het punt om zijn idee helemaal los te laten, totdat hij een proefdruk van Diffie en Hellmans paper in handen kreeg. Merkle zag meteen dat het duo een soortgelijk probleem probeerde op te lossen. Het bood een vorm van bevestiging die hij wanhopig nodig had en hij besloot om contact op te nemen.
In tegenstelling tot Merkle’s professor in Berkeley en de recensenten van het tijdschrift, bewonderden Diffie en Hellman de vindingrijkheid van het voorstel. Waar het idee van Diffie draaide om sleutelparen, zorgde Merkle’s aanpak er op een slimme manier voor dat Alice en Bob overeen konden komen over een gedeelde sleutel op zo’n manier dat alleen zij (gemakkelijk) konden berekenen wat deze sleutel is. Hoewel Diffie en Hellman uiteindelijk concludeerden dat het protocol niet robuust genoeg was voor wat ze probeerden te bereiken, daagde het puzzelprotocol hen uit om het probleem vanuit een nieuw oogpunt te bekijken.
Hellman besloot om Merkle een zomerstage aan te bieden, waarbij hij de student uit Berkeley bijstond in het herschrijven van zijn paper tot een versie die uiteindelijk geaccepteerd werd door het ACM-blad. En door te bewijzen dat hij een creatieve en scherpzinnige denker was, werd Merkle bovendien ook betrokken bij verdere discussies rondom publieke-sleutelcryptografie.
Toen waren er drie indviduen bezig met het probleem.
De doorbraak
Uiteindelijk was het Hellman die de puzzelstukjes op hun plek liet vallen.
Hoewel zijn oplossing niet aan alle vereisten voldeed waar hij en Diffie op mikten (want er was geen digitale authenticatie), bedacht Hellman wel een protocol dat twee partijen privé liet communiceren, zonder de noodzaak om persoonlijk op voorhand een coderingssleutel te delen. Vergelijkbaar met het puzzelprotocol van Merkle is het idee achter de Diffie-Hellman-sleuteluitwisseling (zoals deze oplossing bekend zou worden) dat Alice en Bob een gezamenlijk geheim kunnen afspreken: in essentie, een symmetrische coderingssleutel die alleen zij kennen.
Om dit gedeelde geheim te genereren, gebruiken Alice en Bob sleutelparen, zoals oorspronkelijk door Diffie werd geopperd. Hun geheime sleutels zijn in wezen gewoon zeer grote willekeurige getallen, die zelfs de snelste supercomputers binnen een miljoen jaar niet kunnen raden. Elke publieke sleutel kan vervolgens van een geheime sleutel afgeleid worden door middel van een eenrichtingsfunctie. Het berekenen van de publieke sleutel uit de geheime sleutel is gemakkelijk, terwijl het berekenen van de geheime sleutel uit de publieke sleutel in principe onmogelijk is.
Om het gedeelde geheim te produceren, vermenigvuldigen Alice en Bob elk hun eigen geheime sleutel met de publieke sleutel van de ander. Dit moet hen beiden hetzelfde resultaat geven: het gedeelde geheim.
Dit werkt omdat in beide gevallen het gedeelde geheim in essentie een combinatie is van beide geheime sleutels die telkens eenmaal door een eenrichtingsfunctie zijn gehaald. Wanneer Alice haar geheime sleutel vermenigvuldigt met de publieke sleutel van Bob, is de eenrichtingsfunctie al ingebed in de publieke sleutel van Bob, en hetzelfde is waar als Bob zijn geheime sleutel vermenigvuldigt met de publieke sleutel van Alice. Hoewel Alice en Bob de wiskunde in een andere volgorde uitvoeren, moet de uitkomst hetzelfde zijn.
(Dit is, weliswaar enigzins vereenvoudigd, vergelijkbaar met hoe de uitkomst van 2 x (3 x 5) en 3 x (2 x 5) beide 30 zijn. In deze analogie is de 2 de geheime sleutel van Alice, de 3 is de geheime sleutel van Bob, x 5 is de eenrichtingsfunctie, en 30 is het gedeelde geheim.)
Tegelijk kan niemand anders het gedeelde geheim van Alice en Bob vinden. Immers, als de twee publieke sleutels worden vermenigvuldigd, is het resultaat in wezen een combinatie van beide geheime sleutels, maar dan twee keer door een eenrichtingsfunctie heen gegaan, en dus een keer te veel (als we de analogie voortzetten, is dit te vergelijken met (2 x 5) x (3 x 5), wat 150 is in plaats van 30).
Het genereren van het gedeelde geheim vereist dus toegang tot ofwel de geheime sleutel van Alice of van Bob. Zolang zij deze geheim houden, kunnen ze gebruik maken van door de wiskunde gegarandeerde privécommunicatie.
Het Diffie-Hellman-sleuteluitwisselingsprotocol doorbrak de status-quo in het veld van de cryptografie en was in staat om iets te realiseren dat lang onmogelijk werd geacht. Hun techniek had de potentie om het volledige onderzoeksgebied van de cryptografie dramatisch te transformeren. De twee onconventionele cryptografen waren zich hier maar al te goed van bewust toen ze hun tweede publicatie, New Directions in Cryptography, indienden bij IEEE Transactions on Information Theory, een prestigieus wetenschappelijk tijdschrift, uitgegeven door een professionele vereniging voor elektronische techniek.
‘Vandaag staan we aan de vooravond van een revolutie in de cryptografie’, kondigden Diffie en Hellmann aan in hun paper, gepubliceerd in de editie van november 1976 van het tijdschrift. In de overtuiging dat hun doorbraak het begin van een grote omwenteling zou markeren, vervolgden ze: ‘theoretische ontwikkelingen in informatietheorie en informatica beloven aantoonbaar veilige cryptosystemen mogelijk te maken, waardoor deze eeuwenoude kunst verandert in een wetenschap.’4
Het werd al snel duidelijk dat Diffie en Hellman een stroomversnelling hadden veroorzaakt. Een nieuwe generatie cryptografen stond op het punt om een waterval aan innovatie in de wereld van de cryptografie te introduceren.
RSA
Onder de eersten die geïnspireerd raakten door het paper van Diffie en Hellman waren drie jonge wiskundigen van het MIT. Niet alleen hielden ze allen van getallen, ze waren ook gedreven om lastige problemen op te lossen. Ron Rivest, een assistent-professor aan de universiteit, Adi Shamir, een gastprofessor, en Leonard Adleman, een computerspecialist aan hetzelfde instituut, begonnen samen aan het ontwerp van een eenrichtingsfunctie die specifiek voor publieke-sleutelcryptografie moest dienen.
Enkele maanden later, in 1977, was het ze gelukt.
RSA, zoals hun algoritme werd genoemd (elke letter vertegenwoordigt een van de uitvinders), benutte eeuwenoude wiskundige inzichten in priemfactoren (de vermenigvuldiging van priemgetallen) om een eenrichtingsfunctie met een ingebouwde valdeur te creëren. Door berekeningen te doen met een maximaal getal, zouden twee opeenvolgende, maar verschillende vermenigvuldigingen altijd het originele invoergetal teruggeven. In feite zou de eerste vermenigvuldiging de data versleutelen, terwijl de tweede het zou ontsleutelen.
Als een vereenvoudigde analogie, het is alsof je wiskunde toepast op een klok. Aangezien een klok maar tot twaalf telt, is het resultaat van tien plus vijf drie. Drie plus zeven, brengt ons vervolgens weer terug naar tien. In deze analogie is tien de oorspronkelijke data, het optellen van vijf staat voor het versleutelen, het aanvankelijke resultaat van drie is de versleutelde data, en wanneer er weer zeven wordt opgeteld vertegenwoordigt dit de functie van de valdeur, wat neerkomt op het ontcijferen (decrypten).
RSA maakte het versleutelen en ontsleutelen van berichten compatibel met het oorspronkelijke idee van Diffie. Als Alice naar Bob een versleuteld bericht wilde sturen, kon ze simpelweg het bericht versleutelen met Bobs publieke sleutel. Bob kon het bericht vervolgens ontcijferen met alleen zijn geheime sleutel. Bob had de publieke sleutel van Alice niet meer nodig, en beiden hadden geen gedeeld geheim meer nodig.
Misschien nog belangrijker: het algoritme werkte net zo goed in omgekeerde volgorde. Twee opeenvolgende vermenigvuldigingen leverden altijd het oorspronkelijke getal terug, ongeacht welke van de twee vermenigvuldigingen eerst werd uitgevoerd. Voortbordurend op de klok-analogie, waarbij tien plus vijf plus zeven ons terugbracht naar tien, brengt de omgekeerde volgorde (tien plus zeven plus vijf) ons ook terug naar tien.
In de praktijk betekende dit dat een geheime sleutel kon worden gebruikt om data te versleutelen, die vervolgens kon worden ontcijferd met de bijpassende publieke sleutel. Hierdoor maakte RSA een cryptografisch handtekeningenprotocol mogelijk: Alice kan een bericht versleutelen, dat Bob (of iemand anders) kan ontcijferen met haar publieke sleutel, wat bewijst dat het bericht daadwerkelijk is versleuteld met Alice’s geheime sleutel.
Terwijl de Diffie-Hellman-sleuteluitwisseling privécommunicatie mogelijk maakte, faciliteerde RSA voor het eerst ook een vorm van digitale authenticatie.
En tot slot, RSA-encryptie schaalde (ongeveer) exponentieel. Gewoon een paar cijfers toevoegen aan de originele priemgetallen die in dit protocol werden gebruikt, zou het veel moeilijker maken om later te ontdekken welke priemgetallen werden gebruikt, en daarmee ook veel moeilijker om de encryptie te breken. Met publieke sleutels die zo klein zijn dat zelfs informele computergebruikers ze gemakkelijk konden delen, was beveiliging voor miljoenen jaren wiskundig gegarandeerd.
Met RSA was Diffies visie voor publieke-sleutelcryptografie echt werkelijkheid geworden.
David Chaum
Een andere jonge cryptograaf die geïnspireerd werd door de doorbraak van Diffie en Hellman was David Chaum.
Chaum groeide op in de buitenwijken van Los Angeles in de jaren 60 en begin jaren 70, waar hij al op jonge leeftijd een natuurlijke interesse voor beveiligingstechnologie ontwikkelde. Aanvankelijk ging zijn belangstelling uit naar hardware, zoals deursloten, inbraakalarmen en fysieke kluizen. Aan het einde van zijn jeugdjaren resulteerde dit in het ontwerpen van een nieuw type slot. Chaum stond zelfs op het punt zijn ontwerp aan een grote fabrikant te verkopen.
Maar tegen die tijd begon tevens zijn interesse in het relatief nieuwe gebied van de informatietechnologie te groeien. Hij wisselde regelmatig van universiteit. Zijn studie begon aan de University of California, Los Angeles nog voordat hij de middelbare school had afgerond. Hij schakelde daarna over naar de University of Sonora in Mexico om dicht bij zijn vriendin van dat moment te zijn, en studeerde uiteindelijk af aan de University of California, San Diego. Chaum studeerde informatica en wiskunde, en tegen de late jaren ’70 leerde hij over cryptografie en de recente doorbraken in dat onderzoeksgebied.
Chaum zag natuurlijk ook de potentie van de publieke-sleutelcryptografie omdat hij eveneens glimpsen van de toekomst had opgevangen. Hij voorzag dat computers steeds gebruikelijker zouden worden, totdat uiteindelijk elk huishouden er een in huis zou hebben. En terwijl ARPAnet langzaam begon te transformeren naar het (meer algemeen toegankelijke) vroege internet, verwachtte hij dat elektronische communicatie de wereld zou transformeren.
Net zoals Diffie dat voor hem deed, herkende Chaum ook dat deze transformatie naar een tamelijk dystopische toekomst kon leiden. Hij begreep dat als berichten, documenten of bestanden over het internet zouden worden verzonden, al deze data het risico liep om op een nooit eerder geziene schaal door tirannen te worden gemonitord, onderschept en geëxploiteerd. Chaum maakte zich zorgen dat mensen zich anders zouden gaan gedragen als ze geloven dat ze mogelijk bekeken zouden worden. Massasurveillance zou een gevangenis voor de geest creëren, conformiteit bevorderen, en uiteindelijk fundamentele vrijheden vernietigen, aldus Chaum.
‘De cyberruimte kent niet dezelfde fysieke beperkingen’, legde Chaum later uit aan een journalist van het technologiemagazine Wired. ‘Er zijn geen muren… het is een andere, angstaanjagende, vreemde plek en met identificatie wordt het een nachtmerrie van panoptisch toezicht. Juist? Alles wat je doet kan door iedereen gekend zijn, kan voor altijd worden opgenomen. Het druist volledig in tegen het basisprincipe waarop de mechanismen van de democratie zijn gebaseerd’5
Maar hij zag dat er nu een alternatief was: een andere mogelijke toekomst. Chaum besefte dat de gloednieuwe ontwikkelingen in de cryptografie konden worden ingezet ter verdediging. De maatschappij stond op een kruispunt, en innovaties zoals publieke-sleutelcryptografie boden hoop op een wereld waarin mensen de macht hebben over hun eigen data.
Gedeeltelijk omdat hij wist dat Ralph Merkle naar Berkeley was gegaan (maar niet op de hoogte was dat Merkle’s initiële puzzelprotocol daar niet bepaald goed was ontvangen), koos Chaum voor de universiteit in de Bay Area om zijn doctoraat te behalen. Hier was hij van dichtbij getuige van hoe cryptografie tegen het einde van dat decennium evolueerde van een niche interesse, uitsluitend voor kleine universiteitsafdelingen en academische tijdschriften, naar een kleine revolutie in de informatica, aangedreven door een toegewijde en groeiende gemeenschap van gelijkgestemde wiskundigen.
Het resulteerde in de allereerste Crypto-conferentie in 1981, georganiseerd aan de Universiteit van Californië, Santa Barbara. De grootste vernieuwers in het gebied – Diffie, Hellman, Merkle, Rivest, Shamir, Adelman – en ongeveer vijftig andere cryptografen waren aanwezig, met velen die elkaar voor het eerst in persoon ontmoetten. Ze presenteerden hun nieuwste documenten, bespraken mogelijke verbeteringen aan bestaande protocollen, of leerden elkaar gewoon wat beter kennen terwijl ze een avond doorbrachten met een barbecue op het strand.
Echter, dit gebeurde allemaal tot grote ontsteltenis van de NSA. Net als de nieuwe lichting cryptografen die samengekomen waren bij Crypto 1981, herkende ook de overheidsorganisatie de potentie van publieke-sleutelcryptografie. Maar in tegenstelling tot het optimisme en de vreugde van op de conferentie, waren mensen binnen de inlichtingengemeenschap bezorgd dat sterke encryptie hun hele werkwijze in gevaar zou kunnen brengen. Ze wilden deze cryptografische revolutie stoppen voordat het te ver zou gaan, en in de nasleep van de conferentie begon de NSA waarschuwingen te geven aan wetenschappelijke organisaties om geen presentaties te faciliteren, zoals die tijdens Crypto 1981 zo openlijk tentoongesteld werden.
Toen hij hiervan hoorde, besloot Chaum terug te vechten. Hij ondernam actie om ervoor te zorgen dat de conferentie geen eenmalig evenement zou blijven. Uitgerust met een lijst van namen en contactinformatie die door Adleman was verstrekt, begon de promovendus contact op te nemen met alle grote namen in de cryptografie. Om geen aandacht te trekken van de NSA, stuurde hij fysieke brieven of ontmoette hij de mensen persoonlijk, maar vermeed telefoongesprekken over het onderwerp. Uiteindelijk wist Chaum iedereen terug samen te brengen in Santa Barbara op Crypto 1982, terwijl hij ook een Europese conventie (Eurocrypt) in Duitsland organiseerde in datzelfde jaar.
Daarnaast richtte Chaum de International Association for Cryptologic Research op, een non-profit organisatie die belast werd met het bevorderen van onderzoek in de cryptografie. Hij kondigde de oprichting van deze organisatie aan tijdens de Crypto conferentie van 1982, wat opnieuw voor veel irritatie zorgde bij de NSA.
De grootste bijdragen van Chaum aan de cryptografie waren echter niet de evenementen die hij organiseerde of de organisatie die hij oprichtte, maar de technieken die hij ontwikkelde.
Remailers
Publieke-sleutelcryptografie maakte het mogelijk voor twee mensen die elkaar nog nooit hadden ontmoet om berichten uit te wisselen die alleen zij konden lezen. Dit bood privacy in communicatie — een baanbrekende ontwikkeling.
Maar het was geen wondermiddel, besefte Chaum. Zelfs met de publieke-sleutelcryptografie, bleef een aanzienlijk privacy-risico bestaan: verkeersanalyse kon onthullen wie met wie praatte, en wanneer.
Dergelijke metadata kan meer over iemand onthullen dan men zou willen. Een onderzoeksjournalist wil misschien niet dat zijn bronnen bekend worden, bijvoorbeeld. Of burgers uit landen met autoritaire regimes willen misschien niet dat iemand weet dat ze communiceren met een politieke dissident. Ook zal een werknemer die naar vacatures bij een concurrerend bedrijf informeert er waarschijnlijk de voorkeur aan geven dat zijn baas niet ontdekt dat hij contact heeft gehad met dat bedrijf.
In zijn paper uit 1981 getiteld Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms, stelde Chaum een oplossing voor dit probleem voor, eveneens gebaseerd op publieke-sleutelcryptografie.6
Dit is hoe het werkt.
Als Alice een bericht aan Bob wil sturen, moet ze eerst zijn publieke sleutel nemen en het bericht daarmee versleutelen. Op deze manier kan alleen Bob het bericht ontcijferen.
Maar ze stuurt het bericht niet rechtstreeks naar Bob: een afluisteraar die hun verbindingen monitort, zou dan kunnen zien dat de twee communiceren, wat Alice juist probeert te vermijden.
In plaats daarvan neemt Alice het versleutelde bericht en voegt daar het e-mailadres van Bob aan toe. Vervolgens versleutelt ze dit hele pakket (het versleutelde bericht voor Bob en zijn e-mailadres) nog een keer, maar nu met de publieke sleutel van een speciale mixserver. Het bericht heeft nu twee lagen van codering: één laag voor het originele bericht en een andere laag voor het hele pakket. Alice stuurt dit dubbel versleutelde pakket dan naar de mixer.
Om het originele gecodeerde bericht en Bobs e-mailadres te vinden, ontcijfert de mixserver op zijn beurt het pakket met zijn geheime sleutel. De mixer gebruikt dit om het gecodeerde bericht naar Bob te sturen, die het vervolgens ontcijfert om Alice’s originele bericht te lezen. Als tussenpersoon brak de mixer de directe link tussen Alice en Bob, waardoor het voor de afluisteraar moeilijker werd om te achterhalen dat ze communiceerden. Tenzij het duidelijk is uit de inhoud van het bericht, weet Bob zelf ook niet dat het van Alice afkomstig was.
Deze basisopzet functioneert zolang je op de mixer kan rekenen en zolang deze niet aan de gluurder (of aan Bob) onthult dat hij het versleutelde pakket eerst van Alice heeft ontvangen. Maar Chaum maakte duidelijk dat het zelfs niet nodig is om de mixer te vertrouwen.
Om het risico van een onbetrouwbare mixer te verminderen, kan Alice meerdere mixers gebruiken. In dat geval zou Alice een gecodeerd pakket naar mixer 1 sturen, dat mixer 1 kan ontcijferen om het e-mailadres van mixer 2 en een ander gecodeerd bericht te vinden. Dit bericht kan mixer 2 vervolgens ontcijferen om het e-mailadres van mixer 3 te vinden en nog een ander gecodeerd bericht. Dit bericht kan mixer 3 dan ontcijferen om inderdaad het e-mailadres van Bob en nog een gecodeerd bericht te vinden. Dit laatste bericht kan Bob ten slotte ontcijferen om het originele bericht te lezen. Door elk één laag van de encryptie te verwijderen en het pakket naar de volgende ontvanger door te sturen, zouden de mixers weten van wie ze het pakket hebben ontvangen en naar wie ze het hebben doorgestuurd, maar geen van hen zou weten waar het pakket oorspronkelijk vandaan kwam en wie de eindontvanger is.
Een afluisteraar die Bobs communicatie probeert te monitoren, zou mogelijk kunnen weten dat mixer 3 uiteindelijk het bericht naar Bob stuurde, maar zelfs als mixer 3 deze informatie met de indringer deelt op verzoek (of gerechtelijk bevel), helpt dit de indringer slechts één stap vooruit. Als er ook maar één van de mixers weigert mee te werken, stopt het spoor (en als de mixers in verschillende rechtsgebieden verblijven, kunnen zelfs handhavingsautoriteiten uit een bepaald land het moeilijk hebben om de oorsprong van een bericht na te gaan).
Zo had Chaum het cruciale conceptuele fundament gelegd voor wat later bekend zou worden als remailers.
En zijn bijdragen aan de cryptografie zouden daar niet ophouden…
Een groot deel van dit hoofdstuk is gebaseerd op Steven Levy’s Crypto: How the Code Rebels Beat the Government – Saving Privacy in the Digital Age.↩︎
Whitfield Diffie and Martin E. Hellman, Multiuser Cryptographic Techniques, AFIPS…: Proceedings of the June 7-10, 1976, national computer conference and exposition: 109–112.↩︎
Levy, Crypto, 76.↩︎
Whitfield Diffie and Martin E. Hellman, New Directions in Cryptography, IEEE Transactions On Information Theory, vol. IT-22, no. 6: 644.↩︎
David Chaum, Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms, Communications of the ACM 24, 2: 84–90.↩︎