Rijndael (cryptografie)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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 opzicht 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 welke opereert op 32-bit words simpelweg een word 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:

128 bits 192 bits 256 bits
128 bits 10 12 14
192 bits 12 12 14
256 bits 14 14 14

Welke richting (horizontaal of verticaal) de block- of sleutelgrootte is mag u zelf weten.

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

Addkey[bewerken]

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 Ecole 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 sneller 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]