Initial commit.
[BoarSSL] / Crypto / AES.cs
1 /*
2  * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining 
5  * a copy of this software and associated documentation files (the
6  * "Software"), to deal in the Software without restriction, including
7  * without limitation the rights to use, copy, modify, merge, publish,
8  * distribute, sublicense, and/or sell copies of the Software, and to
9  * permit persons to whom the Software is furnished to do so, subject to
10  * the following conditions:
11  *
12  * The above copyright notice and this permission notice shall be 
13  * included in all copies or substantial portions of the Software.
14  *
15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22  * SOFTWARE.
23  */
24
25 using System;
26
27 namespace Crypto {
28
29 /*
30  * Classic AES implementation, with tables (8->32 lookup tables, four
31  * tables for encryption, four other tables for decryption). This is
32  * relatively efficient, but not constant-time.
33  */
34
35 public sealed class AES : BlockCipherCore {
36
37         uint[] skey;
38         uint[] iskey;
39         int rounds;
40
41         /*
42          * Initialize a new instance.
43          */
44         public AES()
45         {
46                 skey = new uint[4 * 15];
47                 iskey = new uint[skey.Length];
48         }
49
50         /* see IBlockCipher */
51         public override IBlockCipher Dup()
52         {
53                 AES a = new AES();
54                 Array.Copy(skey, 0, a.skey, 0, skey.Length);
55                 Array.Copy(iskey, 0, a.iskey, 0, iskey.Length);
56                 a.rounds = rounds;
57                 return a;
58         }
59
60         /*
61          * Get the block size in bytes (always 16).
62          */
63         public override int BlockSize {
64                 get {
65                         return 16;
66                 }
67         }
68
69         /*
70          * Set the key (16, 24 or 32 bytes).
71          */
72         public override void SetKey(byte[] key, int off, int len)
73         {
74                 switch (len) {
75                 case 16:
76                         rounds = 10;
77                         break;
78                 case 24:
79                         rounds = 12;
80                         break;
81                 case 32:
82                         rounds = 14;
83                         break;
84                 default:
85                         throw new ArgumentException(
86                                 "bad AES key length: " + len);
87                 }
88                 int nk = len >> 2;
89                 int nkf = (rounds + 1) << 2;
90                 for (int i = 0; i < nk; i ++) {
91                         skey[i] = Dec32be(key, off + (i << 2));
92                 }
93                 for (int i = nk, j = 0, k = 0; i < nkf; i ++) {
94                         uint tmp = skey[i - 1];
95                         if (j == 0) {
96                                 tmp = (tmp << 8) | (tmp >> 24);
97                                 tmp = SubWord(tmp) ^ Rcon[k];
98                         } else if (nk > 6 && j == 4) {
99                                 tmp = SubWord(tmp);
100                         }
101                         skey[i] = skey[i - nk] ^ tmp;
102                         if (++ j == nk) {
103                                 j = 0;
104                                 k ++;
105                         }
106                 }
107
108                 /*
109                  * Subkeys for decryption (with InvMixColumns() already
110                  * applied for the inner rounds).
111                  */
112                 Array.Copy(skey, 0, iskey, 0, 4);
113                 for (int i = 4; i < (rounds << 2); i ++) {
114                         uint p = skey[i];
115                         uint p0 = p >> 24;
116                         uint p1 = (p >> 16) & 0xFF;
117                         uint p2 = (p >> 8) & 0xFF;
118                         uint p3 = p & 0xFF;
119                         uint q0 = mule(p0) ^ mulb(p1) ^ muld(p2) ^ mul9(p3);
120                         uint q1 = mul9(p0) ^ mule(p1) ^ mulb(p2) ^ muld(p3);
121                         uint q2 = muld(p0) ^ mul9(p1) ^ mule(p2) ^ mulb(p3);
122                         uint q3 = mulb(p0) ^ muld(p1) ^ mul9(p2) ^ mule(p3);
123                         iskey[i] = (q0 << 24) | (q1 << 16) | (q2 << 8) | q3;
124                 }
125                 Array.Copy(skey, rounds << 2, iskey, rounds << 2, 4);
126         }
127
128         /* see IBlockCipher */
129         public override void BlockEncrypt(byte[] buf, int off)
130         {
131                 uint s0 = Dec32be(buf, off);
132                 uint s1 = Dec32be(buf, off + 4);
133                 uint s2 = Dec32be(buf, off + 8);
134                 uint s3 = Dec32be(buf, off + 12);
135                 s0 ^= skey[0];
136                 s1 ^= skey[1];
137                 s2 ^= skey[2];
138                 s3 ^= skey[3];
139                 for (int i = 1; i < rounds; i ++) {
140                         uint v0 = Ssm0[s0 >> 24]
141                                 ^ Ssm1[(s1 >> 16) & 0xFF]
142                                 ^ Ssm2[(s2 >> 8) & 0xFF]
143                                 ^ Ssm3[s3 & 0xFF];
144                         uint v1 = Ssm0[s1 >> 24]
145                                 ^ Ssm1[(s2 >> 16) & 0xFF]
146                                 ^ Ssm2[(s3 >> 8) & 0xFF]
147                                 ^ Ssm3[s0 & 0xFF];
148                         uint v2 = Ssm0[s2 >> 24]
149                                 ^ Ssm1[(s3 >> 16) & 0xFF]
150                                 ^ Ssm2[(s0 >> 8) & 0xFF]
151                                 ^ Ssm3[s1 & 0xFF];
152                         uint v3 = Ssm0[s3 >> 24]
153                                 ^ Ssm1[(s0 >> 16) & 0xFF]
154                                 ^ Ssm2[(s1 >> 8) & 0xFF]
155                                 ^ Ssm3[s2 & 0xFF];
156                         s0 = v0;
157                         s1 = v1;
158                         s2 = v2;
159                         s3 = v3;
160                         s0 ^= skey[i << 2];
161                         s1 ^= skey[(i << 2) + 1];
162                         s2 ^= skey[(i << 2) + 2];
163                         s3 ^= skey[(i << 2) + 3];
164                 }
165                 uint t0 = (S[s0 >> 24] << 24)
166                         | (S[(s1 >> 16) & 0xFF] << 16)
167                         | (S[(s2 >> 8) & 0xFF] << 8)
168                         | S[s3 & 0xFF];
169                 uint t1 = (S[s1 >> 24] << 24)
170                         | (S[(s2 >> 16) & 0xFF] << 16)
171                         | (S[(s3 >> 8) & 0xFF] << 8)
172                         | S[s0 & 0xFF];
173                 uint t2 = (S[s2 >> 24] << 24)
174                         | (S[(s3 >> 16) & 0xFF] << 16)
175                         | (S[(s0 >> 8) & 0xFF] << 8)
176                         | S[s1 & 0xFF];
177                 uint t3 = (S[s3 >> 24] << 24)
178                         | (S[(s0 >> 16) & 0xFF] << 16)
179                         | (S[(s1 >> 8) & 0xFF] << 8)
180                         | S[s2 & 0xFF];
181                 s0 = t0 ^ skey[rounds << 2];
182                 s1 = t1 ^ skey[(rounds << 2) + 1];
183                 s2 = t2 ^ skey[(rounds << 2) + 2];
184                 s3 = t3 ^ skey[(rounds << 2) + 3];
185                 Enc32be(s0, buf, off);
186                 Enc32be(s1, buf, off + 4);
187                 Enc32be(s2, buf, off + 8);
188                 Enc32be(s3, buf, off + 12);
189         }
190
191         /* see IBlockCipher */
192         public override void BlockDecrypt(byte[] buf, int off)
193         {
194                 uint s0 = Dec32be(buf, off);
195                 uint s1 = Dec32be(buf, off + 4);
196                 uint s2 = Dec32be(buf, off + 8);
197                 uint s3 = Dec32be(buf, off + 12);
198                 s0 ^= iskey[rounds << 2];
199                 s1 ^= iskey[(rounds << 2) + 1];
200                 s2 ^= iskey[(rounds << 2) + 2];
201                 s3 ^= iskey[(rounds << 2) + 3];
202                 for (int i = rounds - 1; i > 0; i --) {
203                         uint v0 = iSsm0[s0 >> 24]
204                                 ^ iSsm1[(s3 >> 16) & 0xFF]
205                                 ^ iSsm2[(s2 >> 8) & 0xFF]
206                                 ^ iSsm3[s1 & 0xFF];
207                         uint v1 = iSsm0[s1 >> 24]
208                                 ^ iSsm1[(s0 >> 16) & 0xFF]
209                                 ^ iSsm2[(s3 >> 8) & 0xFF]
210                                 ^ iSsm3[s2 & 0xFF];
211                         uint v2 = iSsm0[s2 >> 24]
212                                 ^ iSsm1[(s1 >> 16) & 0xFF]
213                                 ^ iSsm2[(s0 >> 8) & 0xFF]
214                                 ^ iSsm3[s3 & 0xFF];
215                         uint v3 = iSsm0[s3 >> 24]
216                                 ^ iSsm1[(s2 >> 16) & 0xFF]
217                                 ^ iSsm2[(s1 >> 8) & 0xFF]
218                                 ^ iSsm3[s0 & 0xFF];
219                         s0 = v0;
220                         s1 = v1;
221                         s2 = v2;
222                         s3 = v3;
223                         s0 ^= iskey[i << 2];
224                         s1 ^= iskey[(i << 2) + 1];
225                         s2 ^= iskey[(i << 2) + 2];
226                         s3 ^= iskey[(i << 2) + 3];
227                 }
228                 uint t0 = (iS[s0 >> 24] << 24)
229                         | (iS[(s3 >> 16) & 0xFF] << 16)
230                         | (iS[(s2 >> 8) & 0xFF] << 8)
231                         | iS[s1 & 0xFF];
232                 uint t1 = (iS[s1 >> 24] << 24)
233                         | (iS[(s0 >> 16) & 0xFF] << 16)
234                         | (iS[(s3 >> 8) & 0xFF] << 8)
235                         | iS[s2 & 0xFF];
236                 uint t2 = (iS[s2 >> 24] << 24)
237                         | (iS[(s1 >> 16) & 0xFF] << 16)
238                         | (iS[(s0 >> 8) & 0xFF] << 8)
239                         | iS[s3 & 0xFF];
240                 uint t3 = (iS[s3 >> 24] << 24)
241                         | (iS[(s2 >> 16) & 0xFF] << 16)
242                         | (iS[(s1 >> 8) & 0xFF] << 8)
243                         | iS[s0 & 0xFF];
244                 s0 = t0 ^ iskey[0];
245                 s1 = t1 ^ iskey[1];
246                 s2 = t2 ^ iskey[2];
247                 s3 = t3 ^ iskey[3];
248                 Enc32be(s0, buf, off);
249                 Enc32be(s1, buf, off + 4);
250                 Enc32be(s2, buf, off + 8);
251                 Enc32be(s3, buf, off + 12);
252         }
253
254         static uint Dec32be(byte[] buf, int off)
255         {
256                 return ((uint)buf[off] << 24)
257                         | ((uint)buf[off + 1] << 16)
258                         | ((uint)buf[off + 2] << 8)
259                         | (uint)buf[off + 3];
260         }
261
262         static void Enc32be(uint x, byte[] buf, int off)
263         {
264                 buf[off] = (byte)(x >> 24);
265                 buf[off + 1] = (byte)(x >> 16);
266                 buf[off + 2] = (byte)(x >> 8);
267                 buf[off + 3] = (byte)x;
268         }
269
270         static uint mul2(uint x)
271         {
272                 x <<= 1;
273                 return x ^ ((uint)(-(int)(x >> 8)) & 0x11B);
274         }
275
276         static uint mul3(uint x)
277         {
278                 return x ^ mul2(x);
279         }
280
281         static uint mul9(uint x)
282         {
283                 return x ^ mul2(mul2(mul2(x)));
284         }
285
286         static uint mulb(uint x)
287         {
288                 uint x2 = mul2(x);
289                 return x ^ x2 ^ mul2(mul2(x2));
290         }
291
292         static uint muld(uint x)
293         {
294                 uint x4 = mul2(mul2(x));
295                 return x ^ x4 ^ mul2(x4);
296         }
297
298         static uint mule(uint x)
299         {
300                 uint x2 = mul2(x);
301                 uint x4 = mul2(x2);
302                 return x2 ^ x4 ^ mul2(x4);
303         }
304
305         static uint aff(uint x)
306         {
307                 x |= x << 8;
308                 x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7) ^ 0x63;
309                 return x & 0xFF;
310         }
311
312         static uint[] Rcon;
313         static uint[] S;
314         static uint[] Ssm0, Ssm1, Ssm2, Ssm3;
315         static uint[] iS;
316         static uint[] iSsm0, iSsm1, iSsm2, iSsm3;
317
318         static uint SubWord(uint x)
319         {
320                 return (S[x >> 24] << 24)
321                         | (S[(x >> 16) & 0xFF] << 16)
322                         | (S[(x >> 8) & 0xFF] << 8)
323                         | S[x & 0xFF];
324         }
325
326         static AES()
327         {
328                 /*
329                  * The Rcon[] constants are used in the key schedule.
330                  */
331                 Rcon = new uint[10];
332                 uint x = 1;
333                 for (int i = 0; i < Rcon.Length; i ++) {
334                         Rcon[i] = x << 24;
335                         x = mul2(x);
336                 }
337
338                 /*
339                  * Generate the map x -> 3^x in GF(2^8). "3" happens to
340                  * be a generator for GF(2^8)*, so we get all 255 non-zero
341                  * elements.
342                  */
343                 uint[] pow3 = new uint[255];
344                 x = 1;
345                 for (int i = 0; i < 255; i ++) {
346                         pow3[i] = x;
347                         x ^= mul2(x);
348                 }
349
350                 /*
351                  * Compute the log3 map 3^x -> x that maps any non-zero
352                  * element in GF(2^8) to its logarithm in base 3 (in the
353                  * 0..254 range).
354                  */
355                 int[] log3 = new int[256];
356                 for (int i = 0; i < 255; i ++) {
357                         log3[pow3[i]] = i;
358                 }
359
360                 /*
361                  * Compute the S-box.
362                  */
363                 S = new uint[256];
364                 S[0] = aff(0);
365                 S[1] = aff(1);
366                 for (uint y = 2; y < 0x100; y ++) {
367                         S[y] = aff(pow3[255 - log3[y]]);
368                 }
369
370                 /*
371                  * Compute the inverse S-box (for decryption).
372                  */
373                 iS = new uint[256];
374                 for (uint y = 0; y < 0x100; y ++) {
375                         iS[S[y]] = y;
376                 }
377
378                 /*
379                  * The Ssm*[] arrays combine SubBytes() and MixColumns():
380                  * SsmX[v] is the effect of byte of value v when appearing
381                  * on row X.
382                  *
383                  * The iSsm*[] arrays similarly combine InvSubBytes() and
384                  * InvMixColumns(), for decryption.
385                  */
386                 Ssm0 = new uint[256];
387                 Ssm1 = new uint[256];
388                 Ssm2 = new uint[256];
389                 Ssm3 = new uint[256];
390                 iSsm0 = new uint[256];
391                 iSsm1 = new uint[256];
392                 iSsm2 = new uint[256];
393                 iSsm3 = new uint[256];
394                 for (uint p = 0; p < 0x100; p ++) {
395                         uint q = S[p];
396                         Ssm0[p] = (mul2(q) << 24)
397                                 | (q << 16)
398                                 | (q << 8)
399                                 | mul3(q);
400                         Ssm1[p] = (mul3(q) << 24)
401                                 | (mul2(q) << 16)
402                                 | (q << 8)
403                                 | q;
404                         Ssm2[p] = (q << 24)
405                                 | (mul3(q) << 16)
406                                 | (mul2(q) << 8)
407                                 | q;
408                         Ssm3[p] = (q << 24)
409                                 | (q << 16)
410                                 | (mul3(q) << 8)
411                                 | mul2(q);
412                         q = iS[p];
413                         iSsm0[p] = (mule(q) << 24)
414                                 | (mul9(q) << 16)
415                                 | (muld(q) << 8)
416                                 | mulb(q);
417                         iSsm1[p] = (mulb(q) << 24)
418                                 | (mule(q) << 16)
419                                 | (mul9(q) << 8)
420                                 | muld(q);
421                         iSsm2[p] = (muld(q) << 24)
422                                 | (mulb(q) << 16)
423                                 | (mule(q) << 8)
424                                 | mul9(q);
425                         iSsm3[p] = (mul9(q) << 24)
426                                 | (muld(q) << 16)
427                                 | (mulb(q) << 8)
428                                 | mule(q);
429                 }
430         }
431 }
432
433 }