Rijndael (cryptografie)
Van Wikipedia
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 zowel in hardware als 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 byte-niveau en moeten met losse instructies iedere keer een los bit uit een encryptieblok halen en op de juiste plaats op de bestemming gezet worden. In hardware is dit daarentegen op te lossen met de juiste bedrading.
Rijndael werkt daarentegen met hele bytes zodat een processor simpelweg een byte kan lezen en op de juiste plaats wegschrijven. Niet alleen wordt zo een byte per keer verwerkt (8 keer zoveel dus), er zijn ook geen assemblerinstructies nodig om er losse bits uit te halen. In hardware is het nog steeds een kwestie van bedrading aanleggen.
Inhoud |
[bewerk] Werking
Om Rijndael toe te passen wordt eerst de te vercijferen tekst in blokken opgedeeld. Deze blokken worden vervolgens in matrixvorm geplaatst. Vervolgens wordt een aantal ronden toegepast. Dat aantal ronden is afhankelijk van de lengte van de sleutel en van het blok:
- 9 ronden als zowel sleutel en blok 128-bits zijn
- 11 ronden als sleutel of blok 192-bits is en geen van hen groter.
- 13 ronden in de overige gevallen
Om een blok te vercijferen wordt eerst het blok met een XOR-operatie op de sleutel verwerkt, vervolgens wordt het bovenstaand aantal ronden uitgevoerd, en vervolgens wordt nog 1 ronde uitgevoerd waarbij de laatste stap (de mix-column stap) overgeslagen wordt.
[bewerk] Uitvoeren van een ronde
Een ronde bestaat uit een aantal stappen. We bespreken ze afzonderlijk.
[bewerk] Subbytes
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 indien we hem in 16 bij 16 neerschrijven 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
[bewerk] Shiftrow
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, ...
[bewerk] Mix Column
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 i.p.v. 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 en wordt het 9de bit dat door de optelling kan ontstaan weggegooid. 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.
[bewerk] Addkey
In deze stap wordt op tussenresultaat een XOR-bewerking met de sleutel uitgevoerd.
[bewerk] Veiligheid
Heden ten dage, augustus 2004, zijn 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. Vandaag de dag 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 (Fergusonet 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 om je op je gemak te voelen. Indien deze aanvallen verbeterd kunnen worden zou dat betekenen dat het algoritme gebroken kan worden, dat wil zeggen, je kunt sneller ontcijferen dan alle mogelijke sleutelcombinaties afzoeken. Echter, als je "slechts" 2120 berekeningen nodig zou hebben om een 128-bits sleutel te bepalen, dan zou het algoritme technisch gebroken zijn, maar gezien er in de praktijk geen computers zijn om zoveel berekeningen uit te voeren zou zo'n lek praktisch weinig te betekenen hebben.
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.
