Blockciphers
Blockciphers, de naam zegt het al, zullen eerst de plaintext in blokken karakters opdelen (bv. 128 bits) en vervolgens blok per blok encrypteren.
Indien het aantal te encrypteren bytes aan data geen exact veelvoud is van de blokgrootte dient er padding te gebeuren. Hierbij zal het laatste blok opgevuld (gepad) worden met extra bytes tot het blok terug de juiste blokgrootte heeft. De manier waarop de padding gebeurt, is afhankelijk van het cipher dat gehanteerd worden.
Feistel-structuren
Ook hier zullen we dezelfde soorten operaties (XOR, substituties en transposities) zien terugkomen. Echter, ook Feistel-structuren worden hier gebruikt: in deze operatie zal de data steeds in twee helften worden gesplitst en wordt steeds een specifieke operatie (aangeduid met F van functie in de figuur), zoals een substitutie, op één helft uitgevoerd dat dan wordt ge-XOR’d met de andere helft. Dit wordt meerdere keren herhaald, waarbij de linker (L) en rechterzijde (R) steeds afwisselend door de specifieke encryptie-operatie gaan.
Net zoals bij RC4 zullen we ook vaak met een zogenaamd key scheduling algoritme werken zodat de sleutel niet constant doorheen het hele proces dezelfde is en we met subkeys of round keys werken.
DES tot op het bot
Een van de oudste blockciphers is DES oftewel Data Encryption Standard. Deze standaard werd in 1977 geboren en vereiste toen blokken van 64 bits data en gebruikte een 56bit sleutel. Ondertussen is dit cipher zeer outdated, maar we gaan hem toch bekijken omdat deze enerzijds erg belangrijk was voor de wereld - grote delen van het bankwezen beschermden er hun financiële transacties mee (en nadien met de opvolger 3DES, zie verder) - en de standaard is erg duidelijk om een goed inzicht in blockciphers te verkrijgen.
Er was wel veel controverse rond deze standaard (gebaseerd op het door IBM ontwikkelde Lucifer cipher) omdat de originele versie (genaamd Lucifer) werkte met een dubbel zo grootte sleutel (128 bit) en bijgevolg dus veiliger was op lange(re) termijn. De Amerikaanse veiligheidsdienst, NSA, was niet zo happig om een dergelijk goed beveiligd algoritme commercieel te maken en zorgde er daarom voor dat de sleutellengte gehalveerd werd.
Data met DES encrypteren (en bijgevolg ook decrypteren daar het een symmetrisch cipher is) bestaat uit twee onderdelen:
- Versleuteling: een reeks Feistel-structuren na elkaar (16 rondes) die de data blok per blok versleutelen.
- Subkeys maken: een key scheduling algoritme dat 16 subkeys genereert (één voor iedere encryptieronde), gebaseerd op de 56 bit sleutel.
Versleuteling
Volgende schema toont de encryptie bestaande uit 16 rondes:
De data wordt blok per blok doorheen dit gedeelte gestuurd. Eerst gebeurt er een Initiële Permutatie (IP in de figuur) waarbij iedere bit naar een andere plek wordt gestuurd volgens een vast patroon. Achteraan gebeurt dit nogmaals in een Finale Permutatie (FP).
Na de IP gaat de data door 16 Feistel-structuren die telkens hetzelfde doen. De data wordt in twee helften gesplitst waarbij de rechterzijde door de F-operatie gaat (die we zo meteen toelichten), het resultaat hiervan wordt ge-XOR’d met de linkerhelft van de data. Het resultaat van deze XOR, een 32 bit blok, wordt nu het rechterblok in de volgende ronde en omgekeerd.
In het F-blok wordt eerst het 32-bit blok uitgebreid (E in de figuur, van expansie) naar een 48 bit blok zodat deze even lang is als de subkey voor deze ronde. De expansie gebeurt, net als de initiële permutatie, volgens een vast patroon:
Nu worden deze 48 bits ge-XOR’d met de subkey. Het resultaat wordt in blokjes van 6 bits door een S-blok gestuurd (zogenaamde Selection blocks). In dit blokje wordt 6 bit omgezet naar 4 bit. In de figuur hieronder zien we bijvoorbeeld hoe de omzetting in blok S5 gebeurt. Ieder blokje heeft een soortgelijke tabel, maar met andere resultaten. De 6 bits bestaan uit de 2 outer bits, namelijk de eerste en de laatste bit, alsook de 4 innerbits. De outer bits vormen de rij-index in de S-box-tabel, de inner bits de kolom-index. De figuur toont bijvoorbeeld dat de output 1001 zou zijn indien er 011011 in het blok wordt geplaatst: outer bits 01 wijzen naar rij 1, inner bits 1101 naar kolom 13, en op die positie in de S5-tabel staat de waarde 1001.
Na 16 rondes krijgen we terug een 32 bit datablok dat nog een Finale permutatie ondergaat die weer de bits van plaats verandert en de output hiervan is een geëncrypteerd blok data dat kan doorgestuurd worden naar de ontvanger.
Je kan de DES standaard op web.archive.org/web/20040410171758/http://www.itl.nist.gov/fipspubs/fip46-2.htm nalezen en ontdekken dat deze niet zo lang is zoals je zou verwachten van een wereldwijd gebruikte standaard.
Subkeys maken
Iedere ronde tijdens de versleuteling vereist een sleutel. Om te voorkomen dat steeds de hoofdsleutel wordt gebruikt (en er zo potentieel dezelfde keystreams worden gemaakt), wordt deze sleutel doorheen een round-key generator algoritme gestuurd. Dit algoritme bestaat uit 16 rondes waarbij de 56 bit sleutel (8 van de 64 bits in de originele sleutel zijn zogenaamde pariteits-bits, die dienen om te controleren of de sleutel geen fouten bevat) steeds in twee helften van 28 bits wordt geknipt.
Iedere ronde wordt de helft van de sleutel 2 bits geshift (in ronde 1,2, 9 en 16 maar 1 bit). Dat wil zeggen dat alle bits twee plekjes opschuiven en de eerste (of laatste) bits komen dan achteraan (of vooraan) te staan. Deze twee geshifte helften worden dan enerzijds doorgestuurd naar de volgende ronde, anderzijds naar een compressie P-box waarvan het resultaat een 48 bits subkey zal zijn van die ronde.
De naam compressie P-box doet al vermoeden wat er gebeurt:
- Compressie: een aantal bits zullen wegvallen (er komen 56 bits in, maar we hebben maar 48 bits nodig).
- P-box: een permutatie oftewel transpositie dat alle bits van plek zal veranderen.
In de Compression P-Box wordt een aantal bits van de sleutel “tegengehouden”. Welke bits dat zijn hangt af van de P-Box. Iedere ronde wordt er een andere Compression P-Box gehanteerd.
En zo hebben we het einde van de werking van DES bereikt. Dat viel al bij al nog mee, niet?
3DES
Al van bij de start gingen er stemmen op dat de originele sleutellengte voor DES (56 bits, 48 in effectiviteit vanwege de pariteitsbits) redelijk snel zou gebruteforced worden. Om die reden werd 3DES in het leven geroepen in 1995. De oplossing, 3DES, was een mooi staaltje compromisvorming: het bood een verhoogde beveiliging doordat het een lange sleutel had (tot 168 bits lang) maar bleef tegelijkertijd compatibel met de bestaande DES hardware en software.
De werking van 3DES (triple DES) is verrassend eenvoudig: ieder blok data wordt drie keer doorheen een DES-cipher gestuurd, telkens met een andere sleutel. Om compatibel te blijven met bestaande DES hardware wordt de data hierbij eerst Encrypted, dan Decrypted, en tenslotte opnieuw Encrypted. Dit patroon wordt daarom het EDE-schema (Encrypt-Decrypt-Encrypt) genoemd. Daar we in iedere fase een andere sleutel gebruiken, heeft dit (dankzij de eigenschappen van symmetrische ciphers) als effect dat we effectief drie maal na elkaar encrypteren met steeds een andere sleutel. Aan de ontvangerzijde gebeurt het omgekeerde - decryptie, encryptie, decryptie (DED) - en ook dit met dezelfde DES hardware!
3DES laat dus ook (single) DES encryptie toe. Het enige dat je hiervoor moet doen is de subsleutels K2 en K3 gelijkstellen waardoor de tweede en derde fase tijdens de encryptie (en decryptie) eigenlijk niets doen, daar het gewoon de data encrypteert in ronde twee en dan ogenblikkelijk in ronde drie terug decrypteert.
Het bankwezen gebruikt 3DES nog steeds (of varianten die erop gebaseerd) zijn om financiële transacties van onder andere Visa en Mastercard te beveiligen.
DES in de praktijk gekraakt: EFF Deep Crack
De zorgen om de korte 56-bit sleutel van DES werden in 1998 op spectaculaire wijze bevestigd. De Electronic Frontier Foundation (EFF) bouwde voor ongeveer $250.000 een gespecialiseerde machine, bijgenaamd Deep Crack, die bestond uit 1.856 custom chips die speciaal ontworpen waren om DES-sleutels te testen.
Het resultaat? Deep Crack kon iedere willekeurige DES-sleutel in een kwestie van dagen bruteforcen. Een paar jaar later deed het project, in samenwerking met distributed.net, een DES-sleutel zelfs in minder dan 24 uur. Daarmee werd ondubbelzinnig aangetoond dat DES niet langer veilig was voor gevoelige data - exact wat critici al jaren beweerden.
Dit was eigenlijk geen verrassing voor wie had opgelet: de NSA had bij de originele Lucifer-standaard de sleutellengte van 128 bits naar 56 bits laten halveren. Een toevalligheid? Critici waren al jaren overtuigd van niet. Deep Crack bevestigde hun vermoeden op de meest publieke manier mogelijk en gaf zo ook retroactief gelijk aan de keuze voor 3DES in 1995.
Bij de publieke aankondiging werd een versleuteld bericht gekraakt in 56 uur. Het bericht? “It’s time for those 128-, 192-, and 256-bit keys.” Een niet zo subtiele boodschap aan de industrie om over te schakelen naar sterkere algoritmes. In 2001 gebeurde dat effectief, met de komst van AES (zie verder).
Block cipher modes
Tot hiertoe gingen we data steeds blok per blok in het encryptiecipher sturen en het resultaat ervan doorsturen. Klaar. Oplettende mensen hebben hier mogelijk al een hiaat in gezien: wat als twee blokken exact dezelfde data bevatten? Beiden zullen dezelfde ciphertext als resultaat genereren, daar we telkens dezelfde sleutel (en dus subkeys) gebruiken. Twee ciphertexts die identiek zijn, willen we vermijden daar het potentiële informatie over de plaintext zichtbaar maakt. Voorts laat dit soort werking ook replay attacks toe: de aanvaller kan een geëncrypteerd pakket bewaren en op een later moment terug opsturen, zonder dat hij moet weten wat de plaintext bevat.
Stel dat we een afbeelding van Tux De Pinguïn opsplitsen in ongeveer 100 bij 100 datablokken. Als we nu ieder blok individueel met een blockcipher encrypten en zouden visualiseren dan krijgen we iets dat mogelijks toch nog wat informatie van Tux doorlekt (zie de tweede afbeelding) daar blokken van de afbeelding met exact dezelfde informatie ook dezelfde ciperblock zullen genereren. Vergelijk dit met de derde afbeelding waarin we een andere modus gebruiken (die we zo meteen gaan uitleggen) waarin repetities in de plaintext geen invloed hebben op repetities in de ciphertext.
Voorgaande modus, waarin we ieder blok onafhankelijk van het vorige encrypteren, noemen we de Electronic Codebook (ECB) modus.
Alhoewel deze modus dus duidelijk een veiligheidsprobleem met zich mee draagt, heeft deze modus ook één voordeel:
- Ieder blok wordt onafhankelijk van andere blokken gedecrypteerd. Als er dus een blok niet gedecrypteerd kon worden door een fout, dan heeft dat geen invloed op de daaropvolgende blokken. Dit is dus voor streaming-situaties nuttig: beeld je in dat je decryptie faalt halverwege het binnenkrijgen van een film die je aan het bekijken bent. Je zou helemaal opnieuw moeten beginnen.
ECB is een niet zo veilige manier om een blockcipher toe te passen. Veel interessanter (veiliger) wordt het wanneer we extra informatie gebruiken om een blok te encrypteren. Enkel het huidige blok en dezelfde sleutel gebruiken is namelijk niét veilig.
Er zijn verschillende modes om veiliger te encrypteren dan ECB. We bespreken hieronder de belangrijkste.
CBC (Cipher Block Chaining)
Bij CBC wordt de output van het vorige blok (de ciphertext) mee als input voor de encryptie van het volgende blok gebruikt. Concreet wordt de ciphertext van het vorige blok ge-XOR’d met het huidige plaintext-blok, vóór de encryptie plaatsvindt. Hierdoor is de encryptie van elk blok afhankelijk van alle voorgaande blokken, wat patronen in de plaintext verbergt.
Laten we dit concreet maken met een minimalistisch voorbeeld. Stel dat ons blockcipher maar 2 bits per blok verwerkt, volgens volgende substitutietabel:
| Input | Output |
|---|---|
| 00 | 01 |
| 01 | 10 |
| 10 | 11 |
| 11 | 00 |
Onze plaintext is 00 01 10 11 (vier blokken), onze IV is 10. De CBC-encryptie verloopt dan als volgt:
| Blok | Plaintext | XOR met | Na XOR | Door cipher | Ciphertext |
|---|---|---|---|---|---|
| 1 | 00 |
IV=10 |
10 |
→ 11 |
11 |
| 2 | 01 |
11 |
10 |
→ 11 |
11 |
| 3 | 10 |
11 |
01 |
→ 10 |
10 |
| 4 | 11 |
10 |
01 |
→ 10 |
10 |
De uiteindelijke ciphertext wordt 11 11 10 10. Merk op dat onze vier plaintext-blokken allemaal verschillend waren (00, 01, 10, 11), maar dat er in de ciphertext toch herhalingen verschijnen (11 11 en 10 10). Dat is exact wat we willen: repetities in de ciphertext dragen géén informatie meer over repetities in de plaintext. De link tussen patronen in plaintext en ciphertext is doorgeknipt.
CFB (Cipher Feedback)
CFB werkt vergelijkbaar met CBC, maar de ciphertext van het vorige blok wordt iets later in het encryptieproces van het volgende blok gebruikt. Het vorige ciphertext-blok wordt eerst door het blockcipher gestuurd en daarna ge-XOR’d met de plaintext.
OFB (Output Feedback)
Bij OFB wordt het blockcipher als een streamcipher gebruikt: de output van het blockcipher wordt telkens opnieuw als input voor het blockcipher gebruikt om een keystream te genereren. Deze keystream wordt vervolgens ge-XOR’d met de plaintext.
CTR (Counter Mode)
CTR is één van de meest gebruikte modes en werkt fundamenteel anders dan CBC of CFB. In plaats van blokken aan elkaar te ketenen, wordt een teller (counter) als input voor het blockcipher gebruikt. Deze teller bevat een Initialisatie Vector (IV) die bij elk volgend blok met 1 wordt verhoogd.
De werking is als volgt: het blockcipher encrypteert niet de plaintext zelf, maar de tellerwaarde. Het resultaat hiervan wordt vervolgens ge-XOR’d met het plaintext-blok om de ciphertext te bekomen. Doordat elk blok een unieke tellerwaarde gebruikt, levert dezelfde plaintext in verschillende blokken steeds andere ciphertext op.
Een groot voordeel van CTR is dat blokken parallel verwerkt kunnen worden: de encryptie van blok 5 is volledig onafhankelijk van blok 4, aangezien enkel de tellerwaarde en de sleutel nodig zijn. Dit maakt CTR bijzonder geschikt voor toepassingen waar snelheid belangrijk is, zoals bij het streamen van video (denk aan Netflix). CTR wordt onder andere gebruikt in WPA2 en IPSEC.
Overige modes
Naast bovenstaande modes bestaan er nog andere, zoals Propagating CBC (PCBC), waarbij bij decryptie van een blok ook alle vorige blokken vereist zijn. Alle modes uit de doeken doen is hier niet aan de orde, maar het moge duidelijk zijn dat ECB de minst veilige mode is en deze best vermeden wordt.
Het concept Initialisatie Vector (IV) zal je veel zien terugkomen in ciphers. Een IV is een getal dat men als extra seed meegeeft tijdens de encryptie, naast de sleutel. Op deze manier voorkomen we dat steeds enkel de sleutel als seed wordt gebruikt en we dus effectief steeds met een andere sleutel werken. Uiteraard zal ook de andere zijde over dezelfde IV moeten beschikken en zal deze dus doorgestuurd moeten worden. Dit gebeurt meestal via de header van het bijhorende pakketje en is ongeëncrypteerd. Dit lijkt contra-intuïtief - de IV onbeveiligd doorsturen - maar is geen probleem. Uiteraard is het belangrijk dat er een goed IV selectie algoritme wordt gebruikt dat bepaalt hoe steeds het volgende IV moet worden berekend (bv. steeds met 1 verhogen, een willekeurig, etc.).
AES
Alhoewel 3DES een verbetering op DES was, was er toch nood aan een nieuwe encryptie-standaard die langere tijd kon bestaan. In 2001 werd daarom de Advanced Encryption Standard (AES) boven het doopvont gehouden als de nieuwe de facto encryptiestandaard wereldwijd. Deze Amerikaanse standaard is gebaseerd op het Rijndael-algoritme waar we als Belgen fier op mogen zijn: Rijndael is ontwikkeld door twee Belgische KUL-cryptografen Vincent Rijmen en Joan Daemen.
AES is een symmetrisch blockcipher dat data in blokken van 128 bits zal opsplitsen en sleutels tot 256 bits lang toelaat. De volledige werking van AES gaan we hier niet uit de doeken doen, het voldoet te begrijpen dat in grote lijnen hetzelfde soort stappen worden doorlopen als DES en andere symmetrische ciphers:
- KeyExpansion: uit de hoofdsleutel worden alle round keys afgeleid (één per ronde, net zoals bij DES).
- De data wordt vervolgens doorheen 10, 12 of 14 rondes gestuurd, afhankelijk van de sleutellengte (respectievelijk 128, 192 of 256 bits). Het te encrypteren blok wordt daarbij voorgesteld als een 4×4-matrix van bytes, de zogenaamde state.
- Iedere ronde bestaat uit vier vaste stappen op die state:
- SubBytes: iedere byte wordt via een vaste S-box vervangen door een andere byte (substitutie).
- ShiftRows: de rijen van de state worden cyclisch verschoven (transpositie).
- MixColumns: binnen iedere kolom worden de bytes met elkaar gemengd via een lineaire transformatie (zorgt voor diffusie). Deze stap valt weg in de allerlaatste ronde.
- AddRoundKey: de state wordt ge-XOR’d met de round key van die ronde. Dít is waar de sleutel opnieuw in de encryptie binnenkomt.
Merk op dat ook hier, in de AddRoundKey-stap, de XOR-functie nog steeds dienst zal doen als de feitelijke encryptie van de data. Zonder deze XOR-functie zou al het voorgaande enkel maar resulteren in data die van plek verandert, volgens een patroon waar de geheime sleutel niet bij van te pas komt.