Rijndael (cryptografie)
Rijndael is een cryptografisch algoritme bedacht door Joan Daemen en Vincent Rijmen. In november 2001 werd het algoritme door het Amerikaanse NIST uitgekozen tot de nieuwe Advanced Encryption Standard, de opvolger van de Data Encryption Standard. De naam Rijndael is enigszins afgeleid van "Rijmen" en "Daemen".
Rijndael is een doorontwikkeling van het cryptografisch algoritme Square, terwijl Square een doorontwikkeling is van Shark. Het grote voordeel van Rijndael ten opzichte van DES is dat het in software efficiënt te implementeren is. In het DES-algoritme is het namelijk het geval dat in veel stappen bits verwisseld worden. Processoren werken echter op woord-niveau en moeten met losse instructies iedere keer een losse bit uit een encryptieblok halen en op de juiste plaats op de bestemming gezet worden. In hardware is dit beter op te lossen met de juiste configuratie: hardware is niet gebonden aan hele word-bewerkingen.
Rijndael werkt daarentegen met 32 bit-words zodat een processor die opereert op 32 bit-words simpelweg een woord kan lezen en op de juiste plaats wegschrijven. Vrijwel iedere moderne processor is in staat tot 32 bit-word-operaties. Daardoor kan een processor dit algoritme efficiënter uitvoeren dan het oude DES algoritme. Voor hardware maakt het voor de implementatie geen verschil welk van de twee algoritmes er wordt gebruikt.
Werking
bewerkenOm Rijndael toe te passen wordt eerst de te vercijferen tekst in blokken opgedeeld. Deze blokken worden vervolgens in matrixvorm geplaatst. De grootte van deze blokken kan variëren van 128 bits tot 256 bits met een stapgrootte van 32 bits. Dit houdt in dat men de volgende blokgroottes kan krijgen:
- 128 bits (16 bytes)
- 160 bits (20 bytes)
- 192 bits (24 bytes)
- 224 bits (28 bytes)
- 256 bits (32 bytes)
De sleutel wordt ook in blokken opgedeeld en in een matrixvorm geplaatst. De sleutelgrootte kan theoretisch alle sleutelgroottes aannemen van minstens 128 bits en ook een stapgrootte van 32 bits. Vervolgens wordt een aantal ronden toegepast. Het aantal ronden is afhankelijk van de lengte van de sleutel en van het blok. Het aantal rondes zou men kunnen berekenen met deze formule: waar x de blokgrootte of sleutelgrootte is, in bits. Van de blokgrootte en sleutelgrootte wordt de grootste gekozen om x te 'vullen'. Dus bij een blokgrootte van 128 bits en een sleutelgrootte van 256 bits wordt x = 256 ingevuld en dan kan men dus het aantal rondes uitrekenen door: Men kan nagaan dat dan dit het aantal rondes is voor een paar andere groottes:
Blockgrootte | ||||
---|---|---|---|---|
128 bits | 192 bits | 256 bits | ||
Sleutelgrootte | 128 bits | 10 | 12 | 14 |
192 bits | 12 | 12 | 14 | |
256 bits | 14 | 14 | 14 |
AES is hetzelfde als Rijndael, maar dan alleen met de blokgrootte 128 bits en de sleutelgroottes 128 bits, 192 bits en 256 bits. Hier wordt heel vaak[bron?] een fout in gemaakt.
Om een blok te vercijferen wordt eerst het blok met een XOR-operatie op de sleutel verwerkt, vervolgens wordt het bovenstaand aantal ronden uitgevoerd, de laatste ronde wordt alleen de mix-columns-stap overgeslagen.
Uitvoeren van een ronde
bewerkenEen ronde bestaat uit een aantal stappen.
Subbytes
bewerkenIn de subbytes-stap wordt ieder byte door een ander byte vervangen. De byte-waarde wordt in een tabel opgezocht, de S-box, en de waarde in de S-Box-tabel is de vervangwaarde. De S-box ziet er in 16 bij 16 formaat zo uit:
99 | 124 | 119 | 123 | 242 | 107 | 111 | 197 | 48 | 1 | 103 | 43 | 254 | 215 | 171 | 118 |
202 | 130 | 201 | 125 | 250 | 89 | 71 | 240 | 173 | 212 | 162 | 175 | 156 | 164 | 114 | 192 |
183 | 253 | 147 | 38 | 54 | 63 | 247 | 204 | 52 | 165 | 229 | 241 | 113 | 216 | 49 | 21 |
4 | 199 | 35 | 195 | 24 | 150 | 5 | 154 | 7 | 18 | 128 | 226 | 235 | 39 | 178 | 117 |
9 | 131 | 44 | 26 | 27 | 110 | 90 | 160 | 82 | 59 | 214 | 179 | 41 | 227 | 47 | 132 |
83 | 209 | 0 | 237 | 32 | 252 | 177 | 91 | 106 | 203 | 190 | 57 | 74 | 76 | 88 | 207 |
208 | 239 | 170 | 251 | 67 | 77 | 51 | 133 | 69 | 249 | 2 | 127 | 80 | 60 | 159 | 168 |
81 | 163 | 64 | 143 | 146 | 157 | 56 | 245 | 188 | 182 | 218 | 33 | 16 | 255 | 243 | 210 |
205 | 12 | 19 | 236 | 95 | 151 | 68 | 23 | 196 | 167 | 126 | 61 | 100 | 93 | 25 | 115 |
96 | 129 | 79 | 220 | 34 | 42 | 144 | 136 | 70 | 238 | 184 | 20 | 222 | 94 | 11 | 219 |
224 | 50 | 58 | 10 | 73 | 6 | 36 | 92 | 194 | 211 | 172 | 98 | 145 | 149 | 228 | 121 |
231 | 200 | 55 | 109 | 141 | 213 | 78 | 169 | 108 | 86 | 244 | 234 | 101 | 122 | 174 | 8 |
186 | 120 | 37 | 46 | 28 | 166 | 180 | 198 | 232 | 221 | 116 | 31 | 75 | 189 | 139 | 138 |
112 | 62 | 181 | 102 | 72 | 3 | 246 | 14 | 97 | 53 | 87 | 185 | 134 | 193 | 29 | 158 |
225 | 248 | 152 | 17 | 105 | 217 | 142 | 148 | 155 | 30 | 135 | 233 | 206 | 85 | 40 | 223 |
140 | 161 | 137 | 13 | 191 | 230 | 66 | 104 | 65 | 153 | 45 | 15 | 176 | 84 | 187 | 22 |
Shiftrow
bewerkenZoals gezegd waren de 128 bits = 16 bytes in matrix-vorm gezet. In deze matrix worden de rijen op de volgende manier verschoven:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
wordt |
1 2 3 4 6 7 8 5 11 12 9 10 16 13 14 15 |
Elke rij wordt n keer naar links geroteerd waarbij n het rijnummer is. Rij 0 wordt 0 keer geroteerd, rij 1 wordt 1 keer geroteerd, ...
Mix Column
bewerkenMix columns moet niet gebruikt worden bij de laatste ronde.
In de mix-column stap wordt het blok vermenigvuldigd met de volgende matrix:
2 | 3 | 1 | 1 |
1 | 2 | 3 | 1 |
1 | 1 | 2 | 3 |
3 | 1 | 1 | 2 |
Deze vermenigvuldiging wordt echter uitgevoerd over GF(2^8). Dat betekent dat de bytes als polynomen in plaats van getallen worden behandeld. Een vermenigvuldiging kan uitgevoerd worden met behulp van de volgende tabellen:
E-tabel
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | |
0 | 01 | 03 | 05 | 0F | 11 | 33 | 55 | FF | 1A | 2E | 72 | 96 | A1 | F8 | 13 | 35 |
1 | 5F | E1 | 38 | 48 | D8 | 73 | 95 | A4 | F7 | 02 | 06 | 0A | 1E | 22 | 66 | AA |
2 | E5 | 34 | 5C | E4 | 37 | 59 | EB | 26 | 6A | BE | D9 | 70 | 90 | AB | E6 | 31 |
3 | 53 | F5 | 04 | 0C | 14 | 3C | 44 | CC | 4F | D1 | 68 | B8 | D3 | 6E | B2 | CD |
4 | 4C | D4 | 67 | A9 | E0 | 3B | 4D | D7 | 62 | A6 | F1 | 08 | 18 | 28 | 78 | 88 |
5 | 83 | 9E | B9 | D0 | 6B | BD | DC | 7F | 81 | 98 | B3 | CE | 49 | DB | 76 | 9A |
6 | B5 | C4 | 57 | F9 | 10 | 30 | 50 | F0 | 0B | 1D | 27 | 69 | BB | D6 | 61 | A3 |
7 | FE | 19 | 2B | 7D | 87 | 92 | AD | EC | 2F | 71 | 93 | AE | E9 | 20 | 60 | A0 |
8 | FB | 16 | 3A | 4E | D2 | 6D | B7 | C2 | 5D | E7 | 32 | 56 | FA | 15 | 3F | 41 |
9 | C3 | 5E | E2 | 3D | 47 | C9 | 40 | C0 | 5B | ED | 2C | 74 | 9C | BF | DA | 75 |
A | 9F | BA | D5 | 64 | AC | EF | 2A | 7E | 82 | 9D | BC | DF | 7A | 8E | 89 | 80 |
B | 9B | B6 | C1 | 58 | E8 | 23 | 65 | AF | EA | 25 | 6F | B1 | C8 | 43 | C5 | 54 |
C | FC | 1F | 21 | 63 | A5 | F4 | 07 | 09 | 1B | 2D | 77 | 99 | B0 | CB | 46 | CA |
D | 45 | CF | 4A | DE | 79 | 8B | 86 | 91 | A8 | E3 | 3E | 42 | C6 | 51 | F3 | 0E |
E | 12 | 36 | 5A | EE | 29 | 7B | 8D | 8C | 8F | 8A | 85 | 94 | A7 | F2 | 0D | 17 |
F | 39 | 4B | DD | 7C | 84 | 97 | A2 | FD | 1C | 24 | 6C | B4 | C7 | 52 | F6 | 01 |
L-tabel
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | |
0 | 00 | 19 | 01 | 32 | 02 | 1A | C6 | 4B | C7 | 1B | 68 | 33 | EE | DF | 03 | |
1 | 64 | 04 | E0 | 0E | 34 | 8D | 81 | EF | 4C | 71 | 08 | C8 | F8 | 69 | 1C | C1 |
2 | 7D | C2 | 1D | B5 | F9 | B9 | 27 | 6A | 4D | E4 | A6 | 72 | 9A | C9 | 09 | 78 |
3 | 65 | 2F | 8A | 05 | 21 | 0F | E1 | 24 | 12 | F0 | 82 | 45 | 35 | 93 | DA | 8E |
4 | 96 | 8F | DB | BD | 36 | D0 | CE | 94 | 13 | 5C | D2 | F1 | 40 | 46 | 83 | 38 |
5 | 66 | DD | FD | 30 | BF | 06 | 8B | 62 | B3 | 25 | E2 | 98 | 22 | 88 | 91 | 10 |
6 | 7E | 6E | 48 | C3 | A3 | B6 | 1E | 42 | 3A | 6B | 28 | 54 | FA | 85 | 3D | BA |
7 | 2B | 79 | 0A | 15 | 9B | 9F | 5E | CA | 4E | D4 | AC | E5 | F3 | 73 | A7 | 57 |
8 | AF | 58 | A8 | 50 | F4 | EA | D6 | 74 | 4F | AE | E9 | D5 | E7 | E6 | AD | E8 |
9 | 2C | D7 | 75 | 7A | EB | 16 | 0B | F5 | 59 | CB | 5F | B0 | 9C | A9 | 51 | A0 |
A | 7F | 0C | F6 | 6F | 17 | C4 | 49 | EC | D8 | 43 | 1F | 2D | A4 | 76 | 7B | B7 |
B | CC | BB | 3E | 5A | FB | 60 | B1 | 86 | 3B | 52 | A1 | 6C | AA | 55 | 29 | 9D |
C | 97 | B2 | 87 | 90 | 61 | BE | DC | FC | BC | 95 | CF | CD | 37 | 3F | 5B | D1 |
D | 53 | 39 | 84 | 3C | 41 | A2 | 6D | 47 | 14 | 2A | 9E | 5D | 56 | F2 | D3 | AB |
E | 44 | 11 | 92 | D9 | 23 | 20 | 2E | 89 | B4 | 7C | B8 | 26 | 77 | 99 | E3 | A5 |
F | 67 | 4A | ED | DE | C5 | 31 | FE | 18 | 0D | 63 | 8C | 80 | C0 | F7 | 70 | 07 |
Om een vermenigvuldiging van twee getallen uit te voeren zoeken we beide getallen op in de L-tabel. Vervolgens worden beide getallen bij elkaar opgeteld. Komt het getal boven de 255 uit dan trekken we er 256 van af. Het resulterende getal wordt in de E-tabel opgezocht.
Bijvoorbeeld we willen het hexadecimale getal B6 met 4 vermenigvuldigen. We zoeken B6 op in de L-tabel, daar staat B1. We zoeken 4 op, daar staat 32. We tellen ze getallen bij elkaar op: B1+32=E3. We zoeken E3 op in de E-tabel en vinden EE.
Addkey
bewerkenIn deze stap wordt op tussenresultaat een XOR-bewerking met de ronde-sleutel uitgevoerd.
Veiligheid
bewerkenIn augustus 2004 waren er nog geen succesvolle aanvallen tegen het Rijndael-algoritme uitgevoerd. De meest gebruikte aanval tegen blokvercijferingsalgoritmen als Rijndael is het uitvoeren van een aanval op een enigszins aangepaste versie met minder ronden. In 2000 zijn er met succes aanvallen uitgevoerd op versies met 7 ronden voor 128 bits-sleutels, 8 voor 192 bits-sleutels en 9 voor 256 bits-sleutels (Ferguson et al, 2000).
Sommige cryptoanalisten maken zich zorgen om de veiligheid van het Rijndael algoritme. Tussen het aantal ronden dat gebruikt wordt en het aantal ronden waar men aanvallen op heeft kunnen uitvoeren zit volgens hen een te klein gat. Indien deze aanvallen verbeterd kunnen worden, zou dat betekenen dat het algoritme gebroken kan worden; dat wil zeggen, men kan sneller ontcijferen dan alle mogelijke sleutelcombinaties afzoeken, een brute force attack. Het algoritme is technisch gezien gebroken als men 2128-1 of minder berekeningen nodig zou hebben om een 128 bits-sleutel te bepalen.
Verder maakt men zich zorgen over de wiskundige structuur van het Rijndael-algoritme. In tegenstelling tot andere algoritmen kan het algoritme wiskundig netjes beschreven worden. Er wordt gevreesd dat het mogelijk zal zijn hierdoor wiskundige vereenvoudigingen door te voeren.
In 2002 beschreven Nicolas Courtois en Josef Pieprzyk een theoretische aanval genaamd XSL-aanval. Ook deze aanval vergt vooralsnog veel te veel berekeningen om praktisch uitvoerbaar te zijn. Alhoewel er inmiddels claims zijn dat de berekeningen drastisch verlaagd kunnen worden zijn er inmiddels zwakheden in de wiskunde achter de aanval gevonden, en kan het het geval zijn dat de aanval in het geheel niet werkt. Voorlopig blijft de vraag of de XSL-aanval tegen Rijndael gebruikt kan worden dan ook speculatie.
Op 17 augustus 2011 raakte bekend dat onderzoekers aan de Katholieke Universiteit Leuven in samenwerking met Microsoft en de École Normale Supérieure in Parijs een zwak puntje in het algoritme gevonden hadden. Door dit te benutten kan het kraken van het algoritme vier keer zo snel gebeuren, al duurt het nog altijd twee miljard jaar met duizend miljard computers die duizend keer sneller zijn dan de huidige generatie computers.[1][2]
Externe links
bewerken- Informatie over AES op de website van het National Institute of Standards and Technology
- Het document dat Joan Daemen en Vincent Rijmen indienden bij het NIST
- Tien jaar Vlaamse veiligheid op internet - Algoritme Rijndael is wereldwijd standaard geworden (Standaard.be)