Rijndael (cryptografie)

cryptografisch algoritme

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

bewerken

Om 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

bewerken

Een ronde bestaat uit een aantal stappen.

Subbytes

bewerken

In 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

bewerken

Zoals 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

bewerken

Mix 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.

In deze stap wordt op tussenresultaat een XOR-bewerking met de ronde-sleutel uitgevoerd.

Veiligheid

bewerken

In 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]

bewerken