Symmetrische encryptie

Moderne cryptosystemen

De klassieke ciphers die we tot nu toe zagen (Caesar, Vigenère en scytale) zijn fantastisch om de basisprincipes van substitutie en transpositie uit te leggen, maar in de praktijk vallen ze ondertussen om als een kaartenhuis. Caesar kraak je in maximaal 25 pogingen, Vigenère valt na Kasiski’s truc terug op een handvol parallelle Caesars, en de sleutelruimte van een scytale beperkt zich tot het aantal vlakken dat redelijkerwijs op een stok past. Tegen de rekenkracht van vandaag (denk terug aan de bruteforce-tabel hierboven) houdt geen enkel klassiek algoritme nog stand.

Moderne cryptografische systemen zijn dan ook compleet anders opgebouwd:

  • Veel grotere sleutelruimtes (128, 192, 256 bits en meer) waardoor bruteforce praktisch onhaalbaar wordt.
  • Iteratief: niet één enkele substitutie, maar tientallen rondes van substitutie én transpositie achter elkaar, waardoor statistische patronen volledig verdwijnen.
  • Publiek ontworpen en getest door duizenden experts wereldwijd (Kerckhoffs in actie) → géén security through obscurity.
  • Wisselende subkeys per ronde, afgeleid uit de hoofdsleutel. Eigenlijk het idee van Vigenère, maar dan op steroïden.

Wanneer we deze moderne systemen klasseren volgens het aantal sleutels dat ze gebruiken, vallen ze in twee grote families:

  • Symmetrische systemen: zender en ontvanger gebruiken dezelfde sleutel.
  • Asymmetrische systemen: er zijn twee sleutels - één publiek (om te encrypteren) en één privaat (om te decrypteren).

We starten met de oudste van de twee, de symmetrische cryptosystemen. Verderop in dit hoofdstuk komen de asymmetrische aan bod, en zal blijken dat beide families elkaar in de praktijk perfect aanvullen.

Symmetrische systemen zijn de oudste vorm van encryptie: zowel ontvanger als verzender gebruiken dezelfde sleutel. De term symmetrisch verwijst naar het feit dat het algoritme exact hetzelfde doet aan beide zijden. Het enige verschil is dat bij de verzender de plaintext in het systeem wordt gestoken, wat resulteert in een ciphertext. Terwijl de ontvanger de ciphertext in het systeem plaatst om een plaintext te krijgen.

Het basismodel van symmetrische encryptie.

Het basismodel van symmetrische encryptie.

  • De symmetrische encryptiesystemen zijn de oudste vorm: alle klassieke algoritmes waren van dit principe. Asymmetrische systemen zijn pas in de 20e eeuw ontwikkeld (circa 1970).

  • Voorbeelden van bestaande symmetrische encryptiesystemen zijn: AES, DES, IDEA, RC4, Blowfish, etc.

Dit type encryptie is nog steeds het meest gebruikte en wordt overal gebruikt waar data op een veilige manier (confidentiality) moet bewaard, verstuurd of verwerkt worden.

Sleuteloverdracht

De moeilijkheid bij symmetrische systemen is de sleuteloverdracht. Daar ontvanger en verzender dezelfde sleutel hanteren is het natuurlijk belangrijk dat deze de sleutel op een veilige manier kunnen uitwisselen. Dit probleem wordt niet opgelost door symmetrische cryptosystemen. Afhankelijk van de context kan deze uitwisseling op verschillende manieren gebeuren:

  • Via een asymmetrisch encryptiesysteem dat wél sleutels op een veilige manier kan uitwisselen (zie verder).
  • Via een ander beveiligd kanaal, in eender welke vorm (bijvoorbeeld fysiek de sleutel aan de andere persoon geven of zeggen, deze opsturen via een reeds opgezet symmetrisch encryptiekanaal, etc.).

Block- en streamciphers

Er zijn twee soorten symmetrische encryptieciphers als we kijken naar de manier waarop ze de te encrypteren data verwerken:

  • Streamciphers: hierbij wordt de data letterlijk als een stroom (stream) van tekens beschouwd. Waarbij teken per teken individueel geëncrypteerd wordt (het bekendste voorbeeld is RC4). Voor ieder teken dat verwerkt wordt zal er exact één geëncrypteerd teken gegenereerd worden. Dit soort algoritmes zijn over het algemeen sneller dan blockciphers.
  • Blockciphers: de data wordt in blokken (van bijvoorbeeld 128 tekens) verwerkt. Bekendste voorbeelden die we verderop behandelen zijn AES, DES, 3DES, etc.

Streamciphers

De werking van een symmetrisch streamcipher is verrassend eenvoudig en bestaat uit twee delen:

  • Een pseudorandom keystream generator: deze zal de sleutel als het ware expanderen naar een sleutel met de zelfde lengte als de stream, genaamd een keystream. Als je 400 bytes aan data wenst te encrypteren, zal je een keystream van 400 bytes moeten genereren. Daar we met een stream werken zal deze generator teken per teken genereren. Hoe dit gebeurt, leggen we verderop uit.
  • De XOR of “exclusieve of” functie: deze zal de plaintext naar een ciphertext omzetten door de plaintext met de keystream samen te voegen. Deze stap is de feitelijke encryptie!

Het streamcipher proces.

Het streamcipher proces.

Aan de ontvangerzijde gebeurt exact hetzelfde. Enkel indien de ontvanger dezelfde sleutel gebruikt, zal deze dezelfde keystream kunnen genereren, en bijgevolg enkel dan de originele plaintext verkrijgen.

Het hart van een symmetrisch streamcipher is dus enerzijds de XOR-functie én, belangrijker, de manier waarop de keystream wordt gemaakt.

De XOR functie

De waarheidstabel van de XOR-functie is de volgende:

Plaintext input Keystream input Ciphertext output
1 0 1
0 1 1
0 0 0
1 1 0

De XOR-functie wordt in schema’s aangeduid door een cirkel met een plusje in: \(\oplus\)

Beeld je in dat we het bericht 1010 willen versleutelen, en we hebben een gegenereerde keystream 1101. Als we deze XOR’n dan geeft dit 0111. Dit is dus de ciphertext. Als de ontvanger dezelfde keystream kan genereren en deze XOR’d met de verkregen ciphertext, dan krijgt deze terug de originele plaintext.

De keystream generator

De keystream generator heeft dus als doel om voor ieder karakter dat moet geëncrypteerd worden een bijhorend keystream karakter te maken. Deze karaktergeneratie moet onvoorspelbaar zijn (random) tegenover de sleutel die wordt gebruikt en het voorgaande karakter dat werd gemaakt. Echter, dit moet wel PSEUDO (schijn)-willekeurig zijn: dezelfde sleutel als beginpunt (seed) moet steeds dezelfde reeks genereren.

De kracht (en zwakte) van een symmetrisch streamcipher ligt in de implementatie van de manier waarom deze keystream generator werkt. Mogelijke zwakheden kunnen bijvoorbeeld zijn dat de gegenereerde stroom informatie van de sleutel “lekt” naar de keystream (wat desastreuze gevolgen bleek te hebben bij de originele wifi-security (WEP), waarover later meer) of een voorspelbare “randomiteit” van de keystream.

Om aan encryptie te kunnen doen, hebben we systemen nodig die onvoorspelbaar zijn. Als de aanvaller kan voorspellen wat de uitvoer van een onderdeel van de encryptie zal zijn, dan kunnen we geen confidentiality en integrity voorzien. Kortom, we hebben algoritmes nodig die willekeurige getallen kunnen generen die 100% onvoorspelbaar zijn. Net zoals het werpen van een dobbelsteen niet voorspeld kan worden, zo ook moeten onze algoritmes een (digitale) dobbelsteen hebben.

Digitale systemen die perfect willekeurige getallen genereren noemt men random number generators (RNG). Uiteraard moet een RNG geprogrammeerd kunnen worden: dat behelst dus een algoritme. Een algoritme is per definitie “voorspelbaar”. Alles hangt daarom af van de invoer die het algoritme gebruikt om random getallen te beginnen genereren. We spreken dan van een pseudorandom number generator (PRNG), pseudo (schijnbaar) omdat de uitvoer afhankelijk is van het startgetal, de zogenaamde seed. Die seed kan bijvoorbeeld de encryptiesleutel zijn: enkel met dié sleutel zal het algoritme dezelfde reeks getallen generen. Er zijn echter ook systemen die bijvoorbeeld de huidige tijd of de staat van een flipflop als startpunt gebruiken (wanneer je een flipflop aanzet kan je niet voorspellen of deze op 1 of 0 zal staan, daar deze staat beïnvloed wordt door de elektromagnetische straling). Uiteraard is een dergelijke seed voor een keystream generator nutteloos, daar zowel verzender én ontvanger dezelfde reeks getallen moeten kunnen genereren.

Een eenvoudig PRNG: middle-square

Een van de eerste PRNG-algoritmes werd in 1946 bedacht door de legendarische wiskundige John von Neumann: de middle-square methode. De werking is verbluffend eenvoudig:

  1. Neem een startgetal (de seed).
  2. Kwadrateer het.
  3. Neem de middelste cijfers als volgende pseudo-willekeurig getal.
  4. Gebruik dat getal opnieuw als invoer voor stap 2, enzovoort.

Laten we dit uitvoeren met seed 1111 (pad tot 8 cijfers zodat we altijd 4 middelste cijfers hebben):

  • \(1111^2 = 01234321\) → middelste 4 cijfers: 2343
  • \(2343^2 = 05489649\) → middelste 4 cijfers: 4896
  • \(4896^2 = 23970816\) → middelste 4 cijfers: 9708
  • …

Onze pseudo-willekeurige reeks wordt dus 2343, 4896, 9708, .... Wie met dezelfde seed start, krijgt gegarandeerd dezelfde reeks. En dát is precies wat we willen voor encryptie: zender én ontvanger moeten dezelfde keystream kunnen genereren.

In de praktijk is middle-square ondertussen niet meer bruikbaar: de gegenereerde reeksen vallen snel in korte cycli of landen op 0000 waarna het algoritme vast komt te zitten. Maar het idee - deterministisch uit een seed een schijnbaar willekeurige reeks maken - blijft de basis van alle moderne PRNGs zoals die in RC4.

PRNG in de praktijk: Random() in C#

Zo goed als iedere moderne programmeertaal heeft een ingebouwde PRNG. In C# gebruik je new Random(seed), in Python random.seed(), in JavaScript… tja, daar is het een beetje complexer. Een eenvoudig voorbeeld in C# maakt het principe meteen concreet:

int key = 666;

// Zender genereert 10 getallen
Random s = new Random(key);
for (int i = 0; i < 10; i++) Console.Write(s.Next(1, 10));
// Output: 6337963648

// Ontvanger gebruikt dezelfde seed → identieke reeks
Random r = new Random(key);
for (int i = 0; i < 10; i++) Console.Write(r.Next(1, 10));
// Output: 6337963648

// Eve probeert met een andere seed
Random e = new Random(123);
for (int i = 0; i < 10; i++) Console.Write(e.Next(1, 10));
// Output: 9978711226

Zender en ontvanger die dezelfde sleutel (seed) gebruiken, krijgen identiek dezelfde reeks - perfect als keystream voor een streamcipher. Zonder de juiste seed krijg je een totaal andere reeks en is de keystream nutteloos voor cryptanalyse.

Waarschuwing

De ingebouwde Random-klasse in C# is niet cryptografisch veilig. Hij is prima voor games, simulaties of dobbelstenen, maar niet geschikt om data mee te beschermen. Voor écht cryptografisch gebruik neem je de klasse RandomNumberGenerator uit System.Security.Cryptography. Het basisprincipe (seed + deterministisch algoritme = reproduceerbare reeks) blijft wel identiek.

RC4 tot op het bot

Laten we eens één van de meest gebruikte streamciphers bekijken, het RC4 cipher. Dit algoritme, ontwikkeld door Ron Rivest (de afkorting staat trouwens voor Rons Cipher 4), wordt gebruikt onder andere om een beveiligde SSL-tunnel (zie later) op te zetten en zit in het hart van veel geëncrypteerde communicatiekanalen.

RC4 werkt zoals we eerder verklaarden hoe een streamcipher werkt: het heeft een keystream generator en zal de keystream vervolgens XOR’n met de plaintext. Eerst zal de ingevoerde sleutel (die 40 tot 2048 bits lang mag zijn) omgezet worden naar een compatibele werksleutel met behulp van een Key scheduling algorithm (KSA). Deze werksleutel zal dan als seed gebruikt worden om een keystream in het Pseudo-random generator algorithm (PRGA) te maken.

RC4 tot op het bot.

RC4 tot op het bot.

KSA

De KSA heeft als doel om de ingevoerde 40 tot 2k-bit sleutel om te zetten naar een compatibele sleutel voor de PRGA. Het doet dit volgens een eenvoudig algoritme:

Stap 1: plaats de ingevoerde sleutel in een array (T) van 256 karakters. Herhaal de sleutel indien nodig.

Stap 2: maak een sleutelarray (S) aan, ook van 256 karakters, en plaats er de waarden 0 tot en met 255 in.

Stap 3: permuteer (transpositie) de elementen in de array S met behulp van de array T als volgt:

j = 0
for i = 0 tot 255
{ 
  j = (j + S[i] + T[i]) % 256
  Verwissel(S[i],S[j])
}

Deze stap zal dus de elementen in de sleutelarray S naar nieuwe posities in diezelfde array plaatsen en deze ook de hele tijd van plek wisselen. De index j is afhankelijk van de originele sleutel uit stap 1 en zorgt er dus voor dat iedere finale sleutel een unieke array S zal opleveren.

Uitgewerkt voorbeeld van KSA

Stel dat onze sleutel “ab” is. De decimale ASCII-waarden van a en b zijn 97 en 98 respectievelijk. Onze array T zal dus bestaan uit 128 keer de waarden 97 en 98 na elkaar aan de start:

Index Waarde
T[0] 97
T[1] 98
T[2] 97
etc.

Stap twee genereert de tabel S die gewoon de waarden 0 tot en met 255 heeft in de 255 plekjes van de array (de waarde is dus in deze fase gewoon ook de index van het element)

Als we dan stap drie toepassen dan krijgen we na de eerste iteratie van de loop (i=0):

j = (0 + S[0] + T[0]) % 256

oftewel

j= (0 + 0 + 97) % 256 => j wordt 97

De eerste wissel die in S zal plaatsvinden is dan Verwissel(S[0],S[97])

S ziet er dan als volgt uit na de eerste iteratie:

Index Waarde
S[0] 97
S[1] 1
S[2] 2
…
S[97] 0
etc.

En dit herhalen we nog 255 keer. Finaal hebben we nu in tabel S een sleutel die bestaat uit de getallen 0 tot en met 255 verdeeld over willekeurige plekken in de array. Indien we een andere initiële sleutel zouden hebben gebruikt dan zou deze tabel er totaal anders uitzien.

PRGA

Nu we een compatibele sleutel S hebben kan de keystream generatie van start gaan. Deze bestaat uit een loop die blijft doorgaan telkens een nieuw plaintext karakter binnenkomt, als volgt:

i = 0
j = 0
Herhaal telkens keystream karakter nodig is
{
  i = (i+1) % 256
  j = (j +S[i]) % 256
  Verwissel(S[i],S[j])
  k = S[(S[i]+S[j]) % 256]
  output k naar keystream
}

Telkens zal het algoritme één specifieke waarde (tussen 0 en 255) uit de array teruggeven als keystream karakter k. Zoals je ziet zal de array S voorts de hele tijd van “gedaante” blijven veranderen. Telkens we een element k uitsturen zal ook de tabel S weer wat zijn veranderd daar we de waarden van S[i] en S[j] onderling verwisselen.

Uitgewerkt voorbeeld van PRGA

Als we verder werken met de tabel S van het vorige uitgewerkte KSA voorbeeld en de waarden ervan gebruiken na één iteratie dan krijgen we onderstaande berekeningen (We veronderstellen even dat we de KSA niet verder hebben uitgevoerd en de tabel S dus dezelfde is gebleven als op het einde van het voorbeeld, wat in het echt niet zal zijn.):

i = (0+1) % 256 => 1
j = (0 + S[1]) % 256 => (0+1) % 256 => 1
  (S[1] is nog steeds 1: in de KSA-iteratie hebben we enkel S[0] en S[97] gewisseld)
Verwissel(S[1], S[1]) => geen werkelijke wissel, want i en j vallen samen
k = S[ (S[1] + S[1]) % 256 ] => k = S[2] => 2
we outputten de waarde 2 als eerste keystream-karakter
Opmerking

In dit specifieke voorbeeld vallen i en j toevallig samen, waardoor er geen wissel gebeurt. In een realistische PRGA-run (na een volledige KSA van 256 iteraties) is de tabel S echter grondig dooreengeschud en zal vrijwel iedere PRGA-iteratie wél een wissel opleveren.

Finaal zal de output, de waarde k, ge-XOR’d worden met het huidige karakter van de plaintext stream.

Opmerking

Zo, dat viel nog mee he? Zoals al gezegd, een belangrijke motivatie van dit boek is aantonen dat je niet bang hoeft te zijn van wat er achter de schermen van de cyberwereld gebeurt. De hoeveelheid wiskunde die we bijvoorbeeld nodig hadden, is beperkt gebleven tot onze trouwe modulo (%)-operator en meer niet. Wanneer we zo meteen een blockcipher gaan uitkleden, zal je ook daar ontdekken dat je best in staat bent schijnbaar complexe technologieën te begrijpen. Hop naar de blockciphers dus!