Klassieke algoritmes en cryptanalyse
De eerste algoritmes
Het doel van ieder encryptie-algoritme is om data zodanig te versleutelen zodat enkel eigenaars van de gebruikte sleutel de originele tekst kunnen terugvinden. We vertelden net dat encryptie-algoritmes kunnen onderverdeeld worden volgens de actie die ze uitvoeren: substitutie, transpositie of een combinatie. We tonen van iedere variant nu een historisch voorbeeld.
Volgende tool, speciaal gemaakt om crypto te leren, is een erg handig iets om de verschillende cryptografische systemen te visualiseren én testen: link
Substitutie: Caesar encryptie
De Caesar encryptie (naar Julius Caesar) bestaat uit een eenvoudig substitutie algoritme. De sleutel is een getal tussen 1 en 25 en geeft aan door welk element uit het alfabet een teken wordt aangepast, als volgt:
- Ieder element wordt voorgesteld als een cijfer. A krijgt de waarde 0, B wordt 1,… Z wordt 25. (We tellen vanaf 0, zodat we straks netjes met de modulo-operator kunnen werken.)
- Als de sleutel het getal 3 is, dan zal nu iedere letter A in de tekst vervangen worden door het teken 0+3, dus D. Iedere B wordt een E, enzovoort.
- Indien er een “overflow” is achteraan komen we uiteraard terug naar voor in het alfabet. Iedere Z wordt dus een C, iedere Y een B, enzovoort.
Het Caesarcipher wordt ook wel kortweg Rot genoemd, naar het woord rotatie. Een cijfer erachter geeft dan aan welk de te gebruiken sleutel is. Rot4 wil dus zeggen dat alle elementen vier plaatsen opgeschoven moeten worden. Merk op dat Rot13 (ook wel Caesaralfabet genoemd) een speciale sleutel is. Als je namelijk twee maal na elkaar Rot13 toepast op een tekst (eerst op de plaintext, dan op de resulterende ciphertext) dan verkrijgt men terug de originele tekst.
Een mooie fysieke manier om Caesar te visualiseren is met een cipher wheel (of Caesar-wiel): twee concentrische schijven die allebei het alfabet langs de rand hebben staan. Door de binnenste schijf een aantal plaatsen te draaien (afhankelijk van je sleutel), kan je voor iedere letter op de buitenste schijf meteen aflezen welke letter eronder staat. Geen pen en papier nodig - gewoon draaien en aflezen. Historisch werden dergelijke wielen letterlijk gebruikt door legers en spionnen om snel in en uit geheimschrift te gaan.
Uiteraard kan iedere weldenkende mens in de 21e eeuw een Caesar encryptie bruteforcen. Het aantal mogelijke sleutels beperkt zich tot 25 mogelijkheden (sleutels 0, 26, etc. zullen resulteren in géén encryptie: je plaintext en ciphertext zullen identiek zijn) en je kan dit dus snel testen.
Door frequentieanalyse op de ciphertext toe te passen kan men ook de plaintext terugvinden zonder te moeten bruteforcen. Indien de plaintext een tekst in, bijvoorbeeld, het Nederlands is, dan kunnen we gebruik maken van de statistische eigenschappen van een taal. Zo weten we dat bepaalde letters in een standaard Nederlandstalige tekst meer of minder vaak voorkomen. De letter e komt bijvoorbeeld veel vaker voor dan de v. Daar iedere letter in de encryptie door een andere wordt vervangen, is het dus voldoende om te ontdekken (a.d.h.v. frequentieanalyse) welke letter(s) het meest of minst voorkomen om je zo een vermoeden te geven van de originele letter.
Dit verklaart ook waarom je best je te encrypteren berichten zo kort mogelijk houdt. Hoe minder tekens, hoe minder frequentieanalyse zal werken. Een andere veelvoorkomende fout (in klassiekere encryptie) was dat de verzender bijvoorbeeld voorspelbare tekst ging encrypteren. Als je weet dat de verzender altijd begint met “Geachte” in z’n berichten, dan is de kans groot dat de eerste 7 tekens in de ciphertext deze plaintext voorstellen.
Het principe van Caesar encryptie, de substitutie, blijft echter overeind staan en zal je nog zien terugkomen in de komende algoritmes.
Over de modulo operator
De modulo operator (%) is nuttig bij substitutie-algoritmes zoals bij Caesar encryptie. De modulo operator geeft de rest weer wanneer we de linkse door de rechtse operator zouden delen. 19%5 geeft dus 4 als resultaat.
Je kan de operator gebruiken om snel te weten wat de waarde van een teken wordt bij Caesar-encryptie als volgt:
(teken + sleutel) % alfabetLengte => nieuw teken
De alfabetLengte is 26 bij Caesar-encryptie, namelijk alle letters van A tot en met Z.
Als je dus een sleutel hebt met waarde 7 en je wilt weten wat de waarde van Y (element 24, daar we vanaf 0 tellen) wordt dan schrijf je:
(24 + 7) % 26 => 5
Dit zal dus 5 worden, oftewel een F.
Vigenère: een slimmere substitutie
De grote zwakte van Caesar is dat iedere letter altijd op dezelfde manier wordt vervangen: in een tekst vercijferd met sleutel 3 wordt iedere e een h. Net daarom werkt frequentieanalyse zo goed.
Het Vigenère-cipher, vernoemd naar de 16e-eeuwse Fransman Blaise de Vigenère, pakt dit aan met een verrassend eenvoudige truc: in plaats van één vaste shift gebruik je een sleutelwoord dat je herhaalt over de plaintext. Iedere letter van het sleutelwoord bepaalt hoeveel de bijhorende plaintext-letter moet opschuiven. Je kan Vigenère dus zien als een rij Caesar-ciphers na elkaar, elk met een eigen shift.
Stel dat onze sleutel COUNTON is en de plaintext vigenerecipher. We herhalen het sleutelwoord tot het even lang is als de plaintext:
Sleutel: C O U N T O N C O U N T O N
Plaintext: v i g e n e r e c i p h e r
Ciphertext: X W A R G S E G Q C C A S EDe eerste v gecombineerd met sleutel-letter C levert X op (shift 2). De volgende i met O geeft W. En zo verder. Merk op dat de vier e’s in de plaintext telkens door een andere letter worden vervangen (respectievelijk R, S, G en S), afhankelijk van welke sleutelletter er op dat moment boven staat.
In de praktijk gebruikte men een tabula recta - een tabel met alle 26 Caesar-alfabetten onder elkaar - om snel de juiste substitutie af te lezen. De rij kies je op basis van de sleutelletter, de kolom op basis van de plaintext-letter.
En dát is de kracht van Vigenère: eenvoudige frequentieanalyse werkt niet meer. Letters die in de plaintext veel voorkomen, zijn niet langer letters die in de ciphertext veel voorkomen.
Vigenère heette eeuwenlang le chiffre indéchiffrable - “het onontcijferbare cipher”. Pas in de 19e eeuw werd het systematisch gekraakt door Friedrich Kasiski: eens je de sleutellengte kan achterhalen (via het tellen van herhalingen in de ciphertext), herleidt Vigenère zich tot meerdere parallelle Caesar-ciphers die je elk afzonderlijk met frequentieanalyse kan aanvallen.
Het principe van Vigenère - variatie inbrengen door een sleutel die zelf varieert - zie je nog steeds terug in moderne algoritmes. De round keys in DES en AES die we verderop behandelen, zijn directe nazaten van dit idee.
Transpositie: scytale encryptie
Bij transpositie-algoritmen gaan we de positie van de karakters veranderen. De sleutel kan hierbij bepalen op welke manier dit moet gebeuren. De Oude Grieken gebruikten een zogenaamde scytale om aan transpositie-encryptie te doen. Een scytale was een lange stok bestaande uit drie of meerdere lange zijden. De boodschap werd op een lang lint geschreven en dit lint werd dan over de scytale gedraaid. De sleutel gaf aan uit hoeveel vlakken de te gebruiken scytale moest bestaan. Ieder volgend karakter van de plaintext (op het lint) kwam op een andere zijde te liggen. Vervolgens werden alle letters op één zijde achter elkaar gezet, en dit werd herhaald voor iedere zijde: dit werd de ciphertext die werd doorgestuurd.
Om nu de ciphertext te decrypteren werd een onbeschreven lint over de juiste scytale gelegd. Vervolgens werd de verkregen ciphertext op dit lint, zijde per zijde, overgeschreven. Als de ontvanger dan het lint ontrolde kreeg hij terug de originele tekst te zien.
Stel dat we de tekst “De perzen komen er nu aan” (bron: wikipedia) over een scytale met vier zijden wikkelen, dan krijgen we:
De ciphertext die we vervolgens versturen (wanneer we het lint afwikkelen) wordt:
Uiteraard zijn er tal van varianten mogelijk om transpositie te doen. Eerst kan je beslissen om je plaintext in een bepaalde vorm te plaatsen: bijvoorbeeld in tien kolommen. Vervolgens kan je dan, gebaseerd op de sleutel, beslissen in welke volgorde je de kolommen achter elkaar plaatst om zo de ciphertext te bekomen. Dit is een zogenaamd route cipher wat onder andere werd gebruikt tijdens de Amerikaanse Burgeroorlog.
Combinatie
Het spreekt voor zich dat een combinatie van een transpositiecipher en een substitutiecipher je encryptie nog versterkt. Veel moderne algoritmen kunnen nog steeds herleid worden tot een sequentie van meerdere basisvormen na elkaar.
De Advanced Encryption Standard (AES) is in de 21e eeuw zo’n beetje de de facto standaard als het aankomt op symmetrische encryptie (d.w.z. encryptie waar maar één sleutel voor nodig is, verder meer hierover). Als we echter eens het algoritme opengooien en een enkele encryption round bekijken (AES bestaat uit een sequentie van deze rondes) dan zien we dat de bits die bovenaan binnenkomen (state) vervolgens een combinatie van substituties (sub) en transposities (mixcolumns en shiftrows) ondergaan.
We gaan AES nog terug zien opduiken wanneer we gaan bekijken hoe draadloze netwerken worden beveiligd. Als Belg mogen we trouwens erg fier zijn op deze wereldwijd gebruikte Amerikaanse standaard. Je zal later ontdekken waarom dat zo is!
Doel van dit hoofdstuk is ook aantonen dat je geen wiskundig wondertalent moet zijn om de basisconcepten van cryptografie te begrijpen. Hier en daar neem ik wat vrijheden om bepaalde stappen te vereenvoudigen, maar de essentie van de algoritmen blijft wel bewaard en daarmee, hopelijk, ook de eenvoud (en dus elegantie) ervan.
Cryptanalyse
De term cryptanalyse is nu al enkele keren gevallen: de wereld van de cryptologie bestaat uit twee delen, die elkaars tegengestelden zijn:
- Cryptografie: de wetenschap van het versleutelen van informatie.
- Cryptanalyse: de wetenschap van het ontcijferen van versleutelde informatie, zonder kennis van de gebruikte sleutel.
We gaan in dit boek niet te veel tijd aan de wondere wereld van cryptanalyse spenderen, daar dit ons te ver zou brengen. We vatten echter even de belangrijkste concepten hier samen.
Sleutellengtes en bruteforcen
De term bruteforce dekt de lading goed. Letterlijk vertaald wordt het: met brute kracht forceren. Kortom, je gebruikt het wanneer je niet weet wat doen tijdens de cryptanalyse en gewoonweg de minst efficiënte manier mogelijk zal toepassen, maar waarvan wel geweten is dat ze altijd zal werken. Namelijk iedere mogelijke sleutel testen die het cipher toelaat.
Zoals je je kan inbeelden is de sleutellengte evenredig met de tijd die cryptanalysten nodig hebben om je sleutel te bruteforcen. De maximale tijd die nodig is alle sleutels van een bepaalde lengte te berekenen kan je als volgt vinden:
\(MaximaleTijd = \frac{AantalMogelijkeTekens^{SleutelLengte}}{pogingen/seconde}\)
Een bruteforce getalvoorbeeld
Een sleutel (of wachtwoord) bestaat uit 8 tekens, enkel kleine letters van a tot en met z zijn toegestaan. De berekeningen worden op een GeForce GTX 1080 gedaan die ongeveer 30 miljoen pogingen per seconde kan doen. We krijgen dan:
\(MaximaleTijd = \frac{26^{8}}{30000000}\)
Oftewel ongeveer 6960 seconden, wat neerkomt op ongeveer 1,9 uur tijd benodigd om alle mogelijke sleutels te testen (herinner je eraan dat deze tijd gehalveerd moet worden om te weten hoe lang het gemiddeld zal duren om de juiste sleutel terug te vinden.
Volgende tabel (bron) toont nog voorbeelden waarbij telkens dezelfde GeForce 1080 GTX kaart werd gebruikt. Het getal tussen haakjes geeft aan hoeveel mogelijke tekens er in dit type mogelijk zijn:
| # tekens | enkel nummers (10) | kleine letters (26) | grote & kleine letters & nummers (62) | eender welk teken (95) |
|---|---|---|---|---|
| 4 | 0,3 ms | 15 ms | 490 ms | 2,7 s |
| 5 | 3 ms | 400 ms | 31 s | 4,3 min |
| 6 | 33 ms | 10 s | 32 min | 6,8 uur |
| 7 | 330 ms | 4,5 min | 33 uur | 27 dagen |
| 8 | 3,3 s | 1,9 uur | 84 dagen | 7 jaren |
| 9 | 33 s | 2,1 dagen | 14 jaren | 670 jaren |
| 10 | 5,6 min | 54 dagen | 890 jaren | \(6,3*10^{4}\) jaren |
| 11 | 56 min | 3,9 jaren | \(5,5*10^{4}\) jaren | \(6*10^{6}\) jaren |
| 12 | 9,3 u | 100 jaren | \(3,4*10^{6}\) jaren | \(5,7*10^{8}\) jaren |
| 13 | 3,9 dagen | \(2,6*10^{3}\) jaren | \(2,1*10^{8}\) jaren | \(5,4*10^{10}\) jaren |
| 14 | 39 dagen | \(6,8*10^{4}\) jaren | \(1,3*10^{10}\) jaren | \(5,1*10^{12}\) jaren |
| 15 | 1,1 jaar | \(1,8*10^{6}\) jaren | \(8,1*10^{11}\) jaren | \(4,9*10^{14}\) jaren |
| 16 | 11 jaar | \(4,6*10^{7}\) jaren | \(5*10^{13}\) jaren | \(4,7*10^{16}\) jaren |
Per verdubbeling van het aantal GeForce-kaarten halveert de tijd.
Om bovenstaande gigantische getallen wat te duiden: de leeftijd van ons universum wordt op 13,8 miljard jaar geschat, oftewel \(1,38*10^{10}\) jaren. Onze mooie blauwe planeet is ongeveer 4,5 miljard jaar oud. De Tyrannosaurus Rex liep ongeveer 70 miljoen jaar geleden rond, oftewel \(7*10^{7}\) jaren geleden.
Dictionary attack
Wanneer de cryptanalist vermoedt dat de te zoeken sleutel iets anders is dan volledig willekeurige tekens dan kan hij de bruteforce aanval verbeteren (denk aan “administrator2022”). In plaats van alle mogelijke combinaties (permutaties) van de sleutel te testen, zal hij een woordenboek (dictionary) gebruiken met daarin alle mogelijke sleutels en woorden die mogelijk de originele sleutel bevatten.
Tools zoals John The Ripper kan je voeden met een dergelijk woordenboek en dan vragen om sleutels te testen die gebaseerd zijn op zaken uit dat woordenboek, inclusief bijvoorbeeld door er tekens voor en na te zetten. Als in het woordenboek het woord god staat, dan kan John The Ripper bijvoorbeeld ook alle sleutels testen zoals god1, god2, etc.
Er zijn tal van woordenboeken online te downloaden die gevuld zijn met de meest gebruikte wachtwoorden die cryptanalisten (en dus ook de digitale stropers) kunnen gebruiken om de sleutel sneller te vinden. Het is aangeraden om zeker geen wachtwoorden (of permutaties ervan) te gebruiken die in volgende lijsten voorkomen: https://github.com/danielmiessler/SecLists/tree/master/Passwords/Common-Credentials
Dit waren in 2020 de 10 meest gebruikte wachtwoorden:
123456, password, 12345678, qwerty, 123456789, 12345, 1234, 111111, 1234567, dragon
Dit soort lijsten worden opgesteld door gekende datalekken te analyseren op welke wachtwoorden er in voorkomen.
Soorten cryptanalytische aanvallen
Geregeld zullen we in dit boek bepaalde zwakheden beschrijven die in algoritmes misbruikt kunnen worden door een bepaald type cryptanalytische aanval. Deze aanvallen zijn afhankelijk van de informatie die de cryptanalist bezit:
- Enkel de ciphertext: vanuit het standpunt van de cyberboswachters is dit het beste soort informatie dat de aanvaller bezit. Hij heeft enkel een hoop geëncrypteerde informatie en moet proberen daar de originele plaintext uit te krijgen. Vanuit het standpunt van de cryptanalist is dit dus de minst goede situatie om vanuit te starten.
- Gekende plaintext: de cryptanalist heeft één of meerdere stukken informatie waarvan zowel de ciphertext als de bijhorende plaintext gekend is.
- Gekozen plaintext: de cryptanalist kan zelf plaintext kiezen waarvan de bijhorende ciphertext moet gemaakt worden. Dit zorgt ervoor dat de cryptanalist als het ware kan experimenteren.
- Gekozen ciphertext: het zelfde concept als gekozen plaintext maar deze keer kiest de cryptanalist de ciphertext waarvan hij de bijhorende plaintext wil genereren.
Er zijn nog enkele meer gespecialiseerde types, maar voor deze cursus zullen we het bij deze vier basistypes houden.
Er wordt in deze sectie soms over aanvaller gesproken, alsof de cryptanalist automatisch van kwade wil is. De wetenschap van de cryptanalyse is dat uiteraard verre van: enerzijds zorgt het ervoor dat bestaande en nieuwe cryptografische algoritmes op hun sterkte kunnen getest worden. Anderzijds helpen ze in tijden van oorlog om boodschappen van vijanden te onderscheppen en proberen lezen.
De menselijke factor: de échte beste “cryptanalyse”
Tijd voor een ongemakkelijke waarheid: de meest effectieve aanval op een cryptografisch systeem is in de praktijk géén cryptanalyse. Het is véél goedkoper, sneller en betrouwbaarder om de sleutel gewoon te vragen aan de gebruiker. Een welgemikte phishingmail, een vervalste helpdeskoproep, een post-it onder het toetsenbord, of een collega die “even snel” z’n scherm ontgrendelt - dát zijn de aanvallen waar cyberboswachters écht wakker van liggen.
There is no patch for human stupidity, is een vaak gehoord cliché in de security-wereld. Hoe sterk je algoritme ook is, hoe lang je sleutel ook, als de gebruiker z’n wachtwoord opschrijft op een briefje of doorgeeft aan wie er “vriendelijk om vraagt”, dan valt heel je cryptografische kaartenhuis in elkaar.
Deze categorie aanvallen noemen we social engineering en we behandelen ze uitgebreid in een later hoofdstuk. Onthoud voor nu: cryptografie is een noodzakelijke voorwaarde voor veiligheid, maar zelden voldoende.
En wat met quantum-computers?
Al jaren houdt de crypto-wereld angstvallig de ontwikkelingen in de quantum-computer wereld in het oog. Alhoewel we nog maar in de babyfase van quantum-computers zijn, is het toch best mogelijk dat binnen afzienbare tijd (20, 30 jaar?) we effectief zodanig sterke quantum-computers zullen hebben die alle bestaande cryptografische systemen in een handomdraai kunnen “kraken”.
Daarom hanteren veiligheidsdiensten al vele decennia ook het store now, decrypt later principe. Ze gaan ervan uit dat computers steeds krachtiger worden: berichten die in de jaren 60 werden versleuteld, kunnen nu in een handomdraai ontcijferd worden. Quantum-computers zullen dit proces nog veel sneller maken.
Hoe dit zal gebeuren snapt de auteur ook (nog) niet en zal dus niet verder uitgewerkt worden in dit handboek. Besef gewoon dat quantum-computers van de toekomst potentiële bruteforce aanvallen drastisch zullen kunnen versnellen.
Het is om deze reden dat er nu reeds onderzoek wordt gedaan naar cryptografische ciphers die bestand zullen zijn tegen de computers van de toekomst. Dit soort ciphers worden post-quantum cryptografische ciphers genoemd en zullen niet in dit boek besproken worden.
Trouwens, ook andere systemen die gebruik maken van cryptografische concepten zullen in één klap hun nut verliezen. Of zoals dit artikel zegt “And [as ]encryption is everywhere in modern day life, from e-commerce, to online payments, to passwords, everything will be vulnerable!”
Denk daarbij bijvoorbeeld aan cryptocurrencies zoals Ethereum en Bitcoin:
Cybersecurity specialist Itan Barmes led the vulnerability study of the Bitcoin blockchain. He found the level of exposure that a large enough quantum computer would have on the Bitcoin blockchain presents a systemic risk. “If [4 million] coins are eventually stolen in this way, then trust in the system will be lost and the value of Bitcoin will probably go to zero,” he says. Bron