source: mainline/uspace/lib/crypto/aes.c@ bf22cb78

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since bf22cb78 was 8ee620c, checked in by Jiří Zárevúcky <jiri.zarevucky@…>, 7 years ago

Overlap in memcpy().
  • Property mode set to 100644
File size: 13.4 KB
Line 
1/*
2 * Copyright (c) 2015 Jan Kolarik
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @file aes.c
30 *
31 * Implementation of AES-128 symmetric cipher cryptographic algorithm.
32 *
33 * Based on FIPS 197.
34 */
35
36#include <stdbool.h>
37#include <errno.h>
38#include <mem.h>
39#include "crypto.h"
40
41/* Number of elements in rows/columns in AES arrays. */
42#define ELEMS 4
43
44/* Number of elements (words) in cipher. */
45#define CIPHER_ELEMS 4
46
47/* Length of AES block. */
48#define BLOCK_LEN 16
49
50/* Number of iterations in AES algorithm. */
51#define ROUNDS 10
52
53/** Irreducible polynomial used in AES algorithm.
54 *
55 * NOTE: x^8 + x^4 + x^3 + x + 1.
56 *
57 */
58#define AES_IP 0x1b
59
60/** Precomputed values for AES sub_byte transformation. */
61static const uint8_t sbox[BLOCK_LEN][BLOCK_LEN] = {
62 {
63 0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5,
64 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76
65 },
66 {
67 0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0,
68 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0
69 },
70 {
71 0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc,
72 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15
73 },
74 {
75 0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a,
76 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75
77 },
78 {
79 0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0,
80 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84
81 },
82 {
83 0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b,
84 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf
85 },
86 {
87 0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85,
88 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8
89 },
90 {
91 0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5,
92 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2
93 },
94 {
95 0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17,
96 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73
97 },
98 {
99 0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88,
100 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb
101 },
102 {
103 0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c,
104 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79
105 },
106 {
107 0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9,
108 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08
109 },
110 {
111 0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6,
112 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a
113 },
114 {
115 0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e,
116 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e
117 },
118 {
119 0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94,
120 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf
121 },
122 {
123 0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68,
124 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
125 }
126};
127
128/** Precomputed values for AES inv_sub_byte transformation. */
129static uint8_t inv_sbox[BLOCK_LEN][BLOCK_LEN] = {
130 {
131 0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38,
132 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb
133 },
134 {
135 0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87,
136 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb
137 },
138 {
139 0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d,
140 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e
141 },
142 {
143 0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2,
144 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25
145 },
146 {
147 0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16,
148 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92
149 },
150 {
151 0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda,
152 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84
153 },
154 {
155 0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a,
156 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06
157 },
158 {
159 0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02,
160 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b
161 },
162 {
163 0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea,
164 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73
165 },
166 {
167 0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85,
168 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e
169 },
170 {
171 0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89,
172 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b
173 },
174 {
175 0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20,
176 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4
177 },
178 {
179 0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31,
180 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f
181 },
182 {
183 0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d,
184 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef
185 },
186 {
187 0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0,
188 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61
189 },
190 {
191 0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26,
192 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d
193 }
194};
195
196/** Precomputed values of powers of 2 in GF(2^8) left shifted by 24b. */
197static const uint32_t r_con_array[] = {
198 0x01000000, 0x02000000, 0x04000000, 0x08000000,
199 0x10000000, 0x20000000, 0x40000000, 0x80000000,
200 0x1b000000, 0x36000000
201};
202
203/** Perform substitution transformation on given byte.
204 *
205 * @param byte Input byte.
206 * @param inv Flag indicating whether to use inverse table.
207 *
208 * @return Substituted value.
209 *
210 */
211static uint8_t sub_byte(uint8_t byte, bool inv)
212{
213 uint8_t i = byte >> 4;
214 uint8_t j = byte & 0xF;
215
216 if (!inv)
217 return sbox[i][j];
218
219 return inv_sbox[i][j];
220}
221
222/** Perform substitution transformation on state table.
223 *
224 * @param state State table to be modified.
225 * @param inv Flag indicating whether to use inverse table.
226 *
227 */
228static void sub_bytes(uint8_t state[ELEMS][ELEMS], bool inv)
229{
230 uint8_t val;
231
232 for (size_t i = 0; i < ELEMS; i++) {
233 for (size_t j = 0; j < ELEMS; j++) {
234 val = state[i][j];
235 state[i][j] = sub_byte(val, inv);
236 }
237 }
238}
239
240/** Perform shift rows transformation on state table.
241 *
242 * @param state State table to be modified.
243 *
244 */
245static void shift_rows(uint8_t state[ELEMS][ELEMS])
246{
247 uint8_t temp[ELEMS];
248
249 for (size_t i = 1; i < ELEMS; i++) {
250 memcpy(temp, state[i], i);
251 memmove(state[i], state[i] + i, ELEMS - i);
252 memcpy(state[i] + ELEMS - i, temp, i);
253 }
254}
255
256/** Perform inverted shift rows transformation on state table.
257 *
258 * @param state State table to be modified.
259 *
260 */
261static void inv_shift_rows(uint8_t state[ELEMS][ELEMS])
262{
263 uint8_t temp[ELEMS];
264
265 for (size_t i = 1; i < ELEMS; i++) {
266 memcpy(temp, state[i], ELEMS - i);
267 memmove(state[i], state[i] + ELEMS - i, i);
268 memcpy(state[i] + i, temp, ELEMS - i);
269 }
270}
271
272/** Multiplication in GF(2^8).
273 *
274 * @param x First factor.
275 * @param y Second factor.
276 *
277 * @return Multiplication of given factors in GF(2^8).
278 *
279 */
280static uint8_t galois_mult(uint8_t x, uint8_t y)
281{
282 uint8_t result = 0;
283 uint8_t f_bith;
284
285 for (size_t i = 0; i < 8; i++) {
286 if (y & 1)
287 result ^= x;
288
289 f_bith = (x & 0x80);
290 x <<= 1;
291
292 if (f_bith)
293 x ^= AES_IP;
294
295 y >>= 1;
296 }
297
298 return result;
299}
300
301/** Perform mix columns transformation on state table.
302 *
303 * @param state State table to be modified.
304 *
305 */
306static void mix_columns(uint8_t state[ELEMS][ELEMS])
307{
308 uint8_t orig_state[ELEMS][ELEMS];
309 memcpy(orig_state, state, BLOCK_LEN);
310
311 for (size_t j = 0; j < ELEMS; j++) {
312 state[0][j] =
313 galois_mult(0x2, orig_state[0][j]) ^
314 galois_mult(0x3, orig_state[1][j]) ^
315 orig_state[2][j] ^
316 orig_state[3][j];
317 state[1][j] =
318 orig_state[0][j] ^
319 galois_mult(0x2, orig_state[1][j]) ^
320 galois_mult(0x3, orig_state[2][j]) ^
321 orig_state[3][j];
322 state[2][j] =
323 orig_state[0][j] ^
324 orig_state[1][j] ^
325 galois_mult(0x2, orig_state[2][j]) ^
326 galois_mult(0x3, orig_state[3][j]);
327 state[3][j] =
328 galois_mult(0x3, orig_state[0][j]) ^
329 orig_state[1][j] ^
330 orig_state[2][j] ^
331 galois_mult(0x2, orig_state[3][j]);
332 }
333}
334
335/** Perform inverted mix columns transformation on state table.
336 *
337 * @param state State table to be modified.
338 *
339 */
340static void inv_mix_columns(uint8_t state[ELEMS][ELEMS])
341{
342 uint8_t orig_state[ELEMS][ELEMS];
343 memcpy(orig_state, state, BLOCK_LEN);
344
345 for (size_t j = 0; j < ELEMS; j++) {
346 state[0][j] =
347 galois_mult(0x0e, orig_state[0][j]) ^
348 galois_mult(0x0b, orig_state[1][j]) ^
349 galois_mult(0x0d, orig_state[2][j]) ^
350 galois_mult(0x09, orig_state[3][j]);
351 state[1][j] =
352 galois_mult(0x09, orig_state[0][j]) ^
353 galois_mult(0x0e, orig_state[1][j]) ^
354 galois_mult(0x0b, orig_state[2][j]) ^
355 galois_mult(0x0d, orig_state[3][j]);
356 state[2][j] =
357 galois_mult(0x0d, orig_state[0][j]) ^
358 galois_mult(0x09, orig_state[1][j]) ^
359 galois_mult(0x0e, orig_state[2][j]) ^
360 galois_mult(0x0b, orig_state[3][j]);
361 state[3][j] =
362 galois_mult(0x0b, orig_state[0][j]) ^
363 galois_mult(0x0d, orig_state[1][j]) ^
364 galois_mult(0x09, orig_state[2][j]) ^
365 galois_mult(0x0e, orig_state[3][j]);
366 }
367}
368
369/** Perform round key transformation on state table.
370 *
371 * @param state State table to be modified.
372 * @param round_key Round key to be applied on state table.
373 *
374 */
375static void add_round_key(uint8_t state[ELEMS][ELEMS], uint32_t *round_key)
376{
377 uint8_t byte_round;
378 uint8_t shift;
379 uint32_t mask = 0xff;
380
381 for (size_t j = 0; j < ELEMS; j++) {
382 for (size_t i = 0; i < ELEMS; i++) {
383 shift = 24 - 8 * i;
384 byte_round = (round_key[j] & (mask << shift)) >> shift;
385 state[i][j] = state[i][j] ^ byte_round;
386 }
387 }
388}
389
390/** Perform substitution transformation on given word.
391 *
392 * @param byte Input word.
393 *
394 * @return Substituted word.
395 *
396 */
397static uint32_t sub_word(uint32_t word)
398{
399 uint32_t temp = word;
400 uint8_t *start = (uint8_t *) &temp;
401
402 for (size_t i = 0; i < 4; i++)
403 *(start + i) = sub_byte(*(start + i), false);
404
405 return temp;
406}
407
408/** Perform left rotation by one byte on given word.
409 *
410 * @param byte Input word.
411 *
412 * @return Rotated word.
413 *
414 */
415static uint32_t rot_word(uint32_t word)
416{
417 return (word << 8 | word >> 24);
418}
419
420/** Key expansion procedure for AES algorithm.
421 *
422 * @param key Input key.
423 * @param key_exp Result key expansion.
424 *
425 */
426static void key_expansion(uint8_t *key, uint32_t *key_exp)
427{
428 uint32_t temp;
429
430 for (size_t i = 0; i < CIPHER_ELEMS; i++) {
431 key_exp[i] =
432 (key[4 * i] << 24) +
433 (key[4 * i + 1] << 16) +
434 (key[4 * i + 2] << 8) +
435 (key[4 * i + 3]);
436 }
437
438 for (size_t i = CIPHER_ELEMS; i < ELEMS * (ROUNDS + 1); i++) {
439 temp = key_exp[i - 1];
440
441 if ((i % CIPHER_ELEMS) == 0) {
442 temp = sub_word(rot_word(temp)) ^
443 r_con_array[i / CIPHER_ELEMS - 1];
444 }
445
446 key_exp[i] = key_exp[i - CIPHER_ELEMS] ^ temp;
447 }
448}
449
450/** AES-128 encryption algorithm.
451 *
452 * @param key Input key.
453 * @param input Input data sequence to be encrypted.
454 * @param output Encrypted data sequence.
455 *
456 * @return EINVAL when input or key not specified,
457 * ENOMEM when pointer for output is not allocated,
458 * otherwise EOK.
459 *
460 */
461errno_t aes_encrypt(uint8_t *key, uint8_t *input, uint8_t *output)
462{
463 if ((!key) || (!input))
464 return EINVAL;
465
466 if (!output)
467 return ENOMEM;
468
469 /* Create key expansion. */
470 uint32_t key_exp[ELEMS * (ROUNDS + 1)];
471 key_expansion(key, key_exp);
472
473 /* Copy input into state array. */
474 uint8_t state[ELEMS][ELEMS];
475 for (size_t i = 0; i < ELEMS; i++) {
476 for (size_t j = 0; j < ELEMS; j++)
477 state[i][j] = input[i + ELEMS * j];
478 }
479
480 /* Processing loop. */
481 add_round_key(state, key_exp);
482
483 for (size_t k = 1; k <= ROUNDS; k++) {
484 sub_bytes(state, false);
485 shift_rows(state);
486
487 if (k < ROUNDS)
488 mix_columns(state);
489
490 add_round_key(state, key_exp + k * ELEMS);
491 }
492
493 /* Copy state array into output. */
494 for (size_t i = 0; i < ELEMS; i++) {
495 for (size_t j = 0; j < ELEMS; j++)
496 output[i + j * ELEMS] = state[i][j];
497 }
498
499 return EOK;
500}
501
502/** AES-128 decryption algorithm.
503 *
504 * @param key Input key.
505 * @param input Input data sequence to be decrypted.
506 * @param output Decrypted data sequence.
507 *
508 * @return EINVAL when input or key not specified,
509 * ENOMEM when pointer for output is not allocated,
510 * otherwise EOK.
511 *
512 */
513errno_t aes_decrypt(uint8_t *key, uint8_t *input, uint8_t *output)
514{
515 if ((!key) || (!input))
516 return EINVAL;
517
518 if (!output)
519 return ENOMEM;
520
521 /* Create key expansion. */
522 uint32_t key_exp[ELEMS * (ROUNDS + 1)];
523 key_expansion(key, key_exp);
524
525 /* Copy input into state array. */
526 uint8_t state[ELEMS][ELEMS];
527 for (size_t i = 0; i < ELEMS; i++) {
528 for (size_t j = 0; j < ELEMS; j++)
529 state[i][j] = input[i + ELEMS * j];
530 }
531
532 /* Processing loop. */
533 add_round_key(state, key_exp + ROUNDS * ELEMS);
534
535 for (int k = ROUNDS - 1; k >= 0; k--) {
536 inv_shift_rows(state);
537 sub_bytes(state, true);
538 add_round_key(state, key_exp + k * ELEMS);
539
540 if (k > 0)
541 inv_mix_columns(state);
542 }
543
544 /* Copy state array into output. */
545 for (size_t i = 0; i < ELEMS; i++) {
546 for (size_t j = 0; j < ELEMS; j++)
547 output[i + j * ELEMS] = state[i][j];
548 }
549
550 return EOK;
551}
Note: See TracBrowser for help on using the repository browser.