1 /* gf128mul.c - GF(2^128) multiplication functions
2 *
3 * Copyright (c) 2003, Dr Brian Gladman, Worcester, UK.
4 * Copyright (c) 2006, Rik Snel <rsnel@cube.dyndns.org>
5 *
6 * Based on Dr Brian Gladman's (GPL'd) work published at
7 * http://gladman.plushost.co.uk/oldsite/cryptography_technology/index.php
8 * See the original copyright notice below.
9 *
10 * This program is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License as published by the Free
12 * Software Foundation; either version 2 of the License, or (at your option)
13 * any later version.
14 */
15
16 /*
17 ---------------------------------------------------------------------------
18 Copyright (c) 2003, Dr Brian Gladman, Worcester, UK. All rights reserved.
19
20 LICENSE TERMS
21
22 The free distribution and use of this software in both source and binary
23 form is allowed (with or without changes) provided that:
24
25 1. distributions of this source code include the above copyright
26 notice, this list of conditions and the following disclaimer;
27
28 2. distributions in binary form include the above copyright
29 notice, this list of conditions and the following disclaimer
30 in the documentation and/or other associated materials;
31
32 3. the copyright holder's name is not used to endorse products
33 built using this software without specific written permission.
34
35 ALTERNATIVELY, provided that this notice is retained in full, this product
36 may be distributed under the terms of the GNU General Public License (GPL),
37 in which case the provisions of the GPL apply INSTEAD OF those given above.
38
39 DISCLAIMER
40
41 This software is provided 'as is' with no explicit or implied warranties
42 in respect of its properties, including, but not limited to, correctness
43 and/or fitness for purpose.
44 ---------------------------------------------------------------------------
45 Issue 31/01/2006
46
47 This file provides fast multiplication in GF(2^128) as required by several
48 cryptographic authentication modes
49 */
50
51 #include <crypto/gf128mul.h>
52 #include <linux/kernel.h>
53 #include <linux/module.h>
54 #include <linux/slab.h>
55
56 #define gf128mul_dat(q) { \
57 q(0x00), q(0x01), q(0x02), q(0x03), q(0x04), q(0x05), q(0x06), q(0x07),\
58 q(0x08), q(0x09), q(0x0a), q(0x0b), q(0x0c), q(0x0d), q(0x0e), q(0x0f),\
59 q(0x10), q(0x11), q(0x12), q(0x13), q(0x14), q(0x15), q(0x16), q(0x17),\
60 q(0x18), q(0x19), q(0x1a), q(0x1b), q(0x1c), q(0x1d), q(0x1e), q(0x1f),\
61 q(0x20), q(0x21), q(0x22), q(0x23), q(0x24), q(0x25), q(0x26), q(0x27),\
62 q(0x28), q(0x29), q(0x2a), q(0x2b), q(0x2c), q(0x2d), q(0x2e), q(0x2f),\
63 q(0x30), q(0x31), q(0x32), q(0x33), q(0x34), q(0x35), q(0x36), q(0x37),\
64 q(0x38), q(0x39), q(0x3a), q(0x3b), q(0x3c), q(0x3d), q(0x3e), q(0x3f),\
65 q(0x40), q(0x41), q(0x42), q(0x43), q(0x44), q(0x45), q(0x46), q(0x47),\
66 q(0x48), q(0x49), q(0x4a), q(0x4b), q(0x4c), q(0x4d), q(0x4e), q(0x4f),\
67 q(0x50), q(0x51), q(0x52), q(0x53), q(0x54), q(0x55), q(0x56), q(0x57),\
68 q(0x58), q(0x59), q(0x5a), q(0x5b), q(0x5c), q(0x5d), q(0x5e), q(0x5f),\
69 q(0x60), q(0x61), q(0x62), q(0x63), q(0x64), q(0x65), q(0x66), q(0x67),\
70 q(0x68), q(0x69), q(0x6a), q(0x6b), q(0x6c), q(0x6d), q(0x6e), q(0x6f),\
71 q(0x70), q(0x71), q(0x72), q(0x73), q(0x74), q(0x75), q(0x76), q(0x77),\
72 q(0x78), q(0x79), q(0x7a), q(0x7b), q(0x7c), q(0x7d), q(0x7e), q(0x7f),\
73 q(0x80), q(0x81), q(0x82), q(0x83), q(0x84), q(0x85), q(0x86), q(0x87),\
74 q(0x88), q(0x89), q(0x8a), q(0x8b), q(0x8c), q(0x8d), q(0x8e), q(0x8f),\
75 q(0x90), q(0x91), q(0x92), q(0x93), q(0x94), q(0x95), q(0x96), q(0x97),\
76 q(0x98), q(0x99), q(0x9a), q(0x9b), q(0x9c), q(0x9d), q(0x9e), q(0x9f),\
77 q(0xa0), q(0xa1), q(0xa2), q(0xa3), q(0xa4), q(0xa5), q(0xa6), q(0xa7),\
78 q(0xa8), q(0xa9), q(0xaa), q(0xab), q(0xac), q(0xad), q(0xae), q(0xaf),\
79 q(0xb0), q(0xb1), q(0xb2), q(0xb3), q(0xb4), q(0xb5), q(0xb6), q(0xb7),\
80 q(0xb8), q(0xb9), q(0xba), q(0xbb), q(0xbc), q(0xbd), q(0xbe), q(0xbf),\
81 q(0xc0), q(0xc1), q(0xc2), q(0xc3), q(0xc4), q(0xc5), q(0xc6), q(0xc7),\
82 q(0xc8), q(0xc9), q(0xca), q(0xcb), q(0xcc), q(0xcd), q(0xce), q(0xcf),\
83 q(0xd0), q(0xd1), q(0xd2), q(0xd3), q(0xd4), q(0xd5), q(0xd6), q(0xd7),\
84 q(0xd8), q(0xd9), q(0xda), q(0xdb), q(0xdc), q(0xdd), q(0xde), q(0xdf),\
85 q(0xe0), q(0xe1), q(0xe2), q(0xe3), q(0xe4), q(0xe5), q(0xe6), q(0xe7),\
86 q(0xe8), q(0xe9), q(0xea), q(0xeb), q(0xec), q(0xed), q(0xee), q(0xef),\
87 q(0xf0), q(0xf1), q(0xf2), q(0xf3), q(0xf4), q(0xf5), q(0xf6), q(0xf7),\
88 q(0xf8), q(0xf9), q(0xfa), q(0xfb), q(0xfc), q(0xfd), q(0xfe), q(0xff) \
89 }
90
91 /*
92 * Given a value i in 0..255 as the byte overflow when a field element
93 * in GF(2^128) is multiplied by x^8, the following macro returns the
94 * 16-bit value that must be XOR-ed into the low-degree end of the
95 * product to reduce it modulo the polynomial x^128 + x^7 + x^2 + x + 1.
96 *
97 * There are two versions of the macro, and hence two tables: one for
98 * the "be" convention where the highest-order bit is the coefficient of
99 * the highest-degree polynomial term, and one for the "le" convention
100 * where the highest-order bit is the coefficient of the lowest-degree
101 * polynomial term. In both cases the values are stored in CPU byte
102 * endianness such that the coefficients are ordered consistently across
103 * bytes, i.e. in the "be" table bits 15..0 of the stored value
104 * correspond to the coefficients of x^15..x^0, and in the "le" table
105 * bits 15..0 correspond to the coefficients of x^0..x^15.
106 *
107 * Therefore, provided that the appropriate byte endianness conversions
108 * are done by the multiplication functions (and these must be in place
109 * anyway to support both little endian and big endian CPUs), the "be"
110 * table can be used for multiplications of both "bbe" and "ble"
111 * elements, and the "le" table can be used for multiplications of both
112 * "lle" and "lbe" elements.
113 */
114
115 #define xda_be(i) ( \
116 (i & 0x80 ? 0x4380 : 0) ^ (i & 0x40 ? 0x21c0 : 0) ^ \
117 (i & 0x20 ? 0x10e0 : 0) ^ (i & 0x10 ? 0x0870 : 0) ^ \
118 (i & 0x08 ? 0x0438 : 0) ^ (i & 0x04 ? 0x021c : 0) ^ \
119 (i & 0x02 ? 0x010e : 0) ^ (i & 0x01 ? 0x0087 : 0) \
120 )
121
122 #define xda_le(i) ( \
123 (i & 0x80 ? 0xe100 : 0) ^ (i & 0x40 ? 0x7080 : 0) ^ \
124 (i & 0x20 ? 0x3840 : 0) ^ (i & 0x10 ? 0x1c20 : 0) ^ \
125 (i & 0x08 ? 0x0e10 : 0) ^ (i & 0x04 ? 0x0708 : 0) ^ \
126 (i & 0x02 ? 0x0384 : 0) ^ (i & 0x01 ? 0x01c2 : 0) \
127 )
128
129 static const u16 gf128mul_table_le[256] = gf128mul_dat(xda_le);
130 static const u16 gf128mul_table_be[256] = gf128mul_dat(xda_be);
131
132 /*
133 * The following functions multiply a field element by x^8 in
134 * the polynomial field representation. They use 64-bit word operations
135 * to gain speed but compensate for machine endianness and hence work
136 * correctly on both styles of machine.
137 */
138
139 static void gf128mul_x8_lle(be128 *x)
140 {
141 u64 a = be64_to_cpu(x->a);
142 u64 b = be64_to_cpu(x->b);
143 u64 _tt = gf128mul_table_le[b & 0xff];
144
145 x->b = cpu_to_be64((b >> 8) | (a << 56));
146 x->a = cpu_to_be64((a >> 8) ^ (_tt << 48));
147 }
148
149 /* time invariant version of gf128mul_x8_lle */
150 static void gf128mul_x8_lle_ti(be128 *x)
151 {
152 u64 a = be64_to_cpu(x->a);
153 u64 b = be64_to_cpu(x->b);
154 u64 _tt = xda_le(b & 0xff); /* avoid table lookup */
155
156 x->b = cpu_to_be64((b >> 8) | (a << 56));
157 x->a = cpu_to_be64((a >> 8) ^ (_tt << 48));
158 }
159
160 static void gf128mul_x8_bbe(be128 *x)
161 {
162 u64 a = be64_to_cpu(x->a);
163 u64 b = be64_to_cpu(x->b);
164 u64 _tt = gf128mul_table_be[a >> 56];
165
166 x->a = cpu_to_be64((a << 8) | (b >> 56));
167 x->b = cpu_to_be64((b << 8) ^ _tt);
168 }
169
170 void gf128mul_x8_ble(le128 *r, const le128 *x)
171 {
172 u64 a = le64_to_cpu(x->a);
173 u64 b = le64_to_cpu(x->b);
174 u64 _tt = gf128mul_table_be[a >> 56];
175
176 r->a = cpu_to_le64((a << 8) | (b >> 56));
177 r->b = cpu_to_le64((b << 8) ^ _tt);
178 }
179 EXPORT_SYMBOL(gf128mul_x8_ble);
180
181 void gf128mul_lle(be128 *r, const be128 *b)
182 {
183 /*
184 * The p array should be aligned to twice the size of its element type,
185 * so that every even/odd pair is guaranteed to share a cacheline
186 * (assuming a cacheline size of 32 bytes or more, which is by far the
187 * most common). This ensures that each be128_xor() call in the loop
188 * takes the same amount of time regardless of the value of 'ch', which
189 * is derived from function parameter 'b', which is commonly used as a
190 * key, e.g., for GHASH. The odd array elements are all set to zero,
191 * making each be128_xor() a NOP if its associated bit in 'ch' is not
192 * set, and this is equivalent to calling be128_xor() conditionally.
193 * This approach aims to avoid leaking information about such keys
194 * through execution time variances.
195 *
196 * Unfortunately, __aligned(16) or higher does not work on x86 for
197 * variables on the stack so we need to perform the alignment by hand.
198 */
199 be128 array[16 + 3] = {};
200 be128 *p = PTR_ALIGN(&array[0], 2 * sizeof(be128));
201 int i;
202
203 p[0] = *r;
204 for (i = 0; i < 7; ++i)
205 gf128mul_x_lle(&p[2 * i + 2], &p[2 * i]);
206
207 memset(r, 0, sizeof(*r));
208 for (i = 0;;) {
209 u8 ch = ((u8 *)b)[15 - i];
210
211 be128_xor(r, r, &p[ 0 + !(ch & 0x80)]);
212 be128_xor(r, r, &p[ 2 + !(ch & 0x40)]);
213 be128_xor(r, r, &p[ 4 + !(ch & 0x20)]);
214 be128_xor(r, r, &p[ 6 + !(ch & 0x10)]);
215 be128_xor(r, r, &p[ 8 + !(ch & 0x08)]);
216 be128_xor(r, r, &p[10 + !(ch & 0x04)]);
217 be128_xor(r, r, &p[12 + !(ch & 0x02)]);
218 be128_xor(r, r, &p[14 + !(ch & 0x01)]);
219
220 if (++i >= 16)
221 break;
222
223 gf128mul_x8_lle_ti(r); /* use the time invariant version */
224 }
225 }
226 EXPORT_SYMBOL(gf128mul_lle);
227
228 void gf128mul_bbe(be128 *r, const be128 *b)
229 {
230 be128 p[8];
231 int i;
232
233 p[0] = *r;
234 for (i = 0; i < 7; ++i)
235 gf128mul_x_bbe(&p[i + 1], &p[i]);
236
237 memset(r, 0, sizeof(*r));
238 for (i = 0;;) {
239 u8 ch = ((u8 *)b)[i];
240
241 if (ch & 0x80)
242 be128_xor(r, r, &p[7]);
243 if (ch & 0x40)
244 be128_xor(r, r, &p[6]);
245 if (ch & 0x20)
246 be128_xor(r, r, &p[5]);
247 if (ch & 0x10)
248 be128_xor(r, r, &p[4]);
249 if (ch & 0x08)
250 be128_xor(r, r, &p[3]);
251 if (ch & 0x04)
252 be128_xor(r, r, &p[2]);
253 if (ch & 0x02)
254 be128_xor(r, r, &p[1]);
255 if (ch & 0x01)
256 be128_xor(r, r, &p[0]);
257
258 if (++i >= 16)
259 break;
260
261 gf128mul_x8_bbe(r);
262 }
263 }
264 EXPORT_SYMBOL(gf128mul_bbe);
265
266 /* This version uses 64k bytes of table space.
267 A 16 byte buffer has to be multiplied by a 16 byte key
268 value in GF(2^128). If we consider a GF(2^128) value in
269 the buffer's lowest byte, we can construct a table of
270 the 256 16 byte values that result from the 256 values
271 of this byte. This requires 4096 bytes. But we also
272 need tables for each of the 16 higher bytes in the
273 buffer as well, which makes 64 kbytes in total.
274 */
275 /* additional explanation
276 * t[0][BYTE] contains g*BYTE
277 * t[1][BYTE] contains g*x^8*BYTE
278 * ..
279 * t[15][BYTE] contains g*x^120*BYTE */
280 struct gf128mul_64k *gf128mul_init_64k_bbe(const be128 *g)
281 {
282 struct gf128mul_64k *t;
283 int i, j, k;
284
285 t = kzalloc(sizeof(*t), GFP_KERNEL);
286 if (!t)
287 goto out;
288
289 for (i = 0; i < 16; i++) {
290 t->t[i] = kzalloc(sizeof(*t->t[i]), GFP_KERNEL);
291 if (!t->t[i]) {
292 gf128mul_free_64k(t);
293 t = NULL;
294 goto out;
295 }
296 }
297
298 t->t[0]->t[1] = *g;
299 for (j = 1; j <= 64; j <<= 1)
300 gf128mul_x_bbe(&t->t[0]->t[j + j], &t->t[0]->t[j]);
301
302 for (i = 0;;) {
303 for (j = 2; j < 256; j += j)
304 for (k = 1; k < j; ++k)
305 be128_xor(&t->t[i]->t[j + k],
306 &t->t[i]->t[j], &t->t[i]->t[k]);
307
308 if (++i >= 16)
309 break;
310
311 for (j = 128; j > 0; j >>= 1) {
312 t->t[i]->t[j] = t->t[i - 1]->t[j];
313 gf128mul_x8_bbe(&t->t[i]->t[j]);
314 }
315 }
316
317 out:
318 return t;
319 }
320 EXPORT_SYMBOL(gf128mul_init_64k_bbe);
321
322 void gf128mul_free_64k(struct gf128mul_64k *t)
323 {
324 int i;
325
326 for (i = 0; i < 16; i++)
327 kfree_sensitive(t->t[i]);
328 kfree_sensitive(t);
329 }
330 EXPORT_SYMBOL(gf128mul_free_64k);
331
332 void gf128mul_64k_bbe(be128 *a, const struct gf128mul_64k *t)
333 {
334 u8 *ap = (u8 *)a;
335 be128 r[1];
336 int i;
337
338 *r = t->t[0]->t[ap[15]];
339 for (i = 1; i < 16; ++i)
340 be128_xor(r, r, &t->t[i]->t[ap[15 - i]]);
341 *a = *r;
342 }
343 EXPORT_SYMBOL(gf128mul_64k_bbe);
344
345 /* This version uses 4k bytes of table space.
346 A 16 byte buffer has to be multiplied by a 16 byte key
347 value in GF(2^128). If we consider a GF(2^128) value in a
348 single byte, we can construct a table of the 256 16 byte
349 values that result from the 256 values of this byte.
350 This requires 4096 bytes. If we take the highest byte in
351 the buffer and use this table to get the result, we then
352 have to multiply by x^120 to get the final value. For the
353 next highest byte the result has to be multiplied by x^112
354 and so on. But we can do this by accumulating the result
355 in an accumulator starting with the result for the top
356 byte. We repeatedly multiply the accumulator value by
357 x^8 and then add in (i.e. xor) the 16 bytes of the next
358 lower byte in the buffer, stopping when we reach the
359 lowest byte. This requires a 4096 byte table.
360 */
361 struct gf128mul_4k *gf128mul_init_4k_lle(const be128 *g)
362 {
363 struct gf128mul_4k *t;
364 int j, k;
365
366 t = kzalloc(sizeof(*t), GFP_KERNEL);
367 if (!t)
368 goto out;
369
370 t->t[128] = *g;
371 for (j = 64; j > 0; j >>= 1)
372 gf128mul_x_lle(&t->t[j], &t->t[j+j]);
373
374 for (j = 2; j < 256; j += j)
375 for (k = 1; k < j; ++k)
376 be128_xor(&t->t[j + k], &t->t[j], &t->t[k]);
377
378 out:
379 return t;
380 }
381 EXPORT_SYMBOL(gf128mul_init_4k_lle);
382
383 struct gf128mul_4k *gf128mul_init_4k_bbe(const be128 *g)
384 {
385 struct gf128mul_4k *t;
386 int j, k;
387
388 t = kzalloc(sizeof(*t), GFP_KERNEL);
389 if (!t)
390 goto out;
391
392 t->t[1] = *g;
393 for (j = 1; j <= 64; j <<= 1)
394 gf128mul_x_bbe(&t->t[j + j], &t->t[j]);
395
396 for (j = 2; j < 256; j += j)
397 for (k = 1; k < j; ++k)
398 be128_xor(&t->t[j + k], &t->t[j], &t->t[k]);
399
400 out:
401 return t;
402 }
403 EXPORT_SYMBOL(gf128mul_init_4k_bbe);
404
405 void gf128mul_4k_lle(be128 *a, const struct gf128mul_4k *t)
406 {
407 u8 *ap = (u8 *)a;
408 be128 r[1];
409 int i = 15;
410
411 *r = t->t[ap[15]];
412 while (i--) {
413 gf128mul_x8_lle(r);
414 be128_xor(r, r, &t->t[ap[i]]);
415 }
416 *a = *r;
417 }
418 EXPORT_SYMBOL(gf128mul_4k_lle);
419
420 void gf128mul_4k_bbe(be128 *a, const struct gf128mul_4k *t)
421 {
422 u8 *ap = (u8 *)a;
423 be128 r[1];
424 int i = 0;
425
426 *r = t->t[ap[0]];
427 while (++i < 16) {
428 gf128mul_x8_bbe(r);
429 be128_xor(r, r, &t->t[ap[i]]);
430 }
431 *a = *r;
432 }
433 EXPORT_SYMBOL(gf128mul_4k_bbe);
434
435 MODULE_LICENSE("GPL");
436 MODULE_DESCRIPTION("Functions for multiplying elements of GF(2^128)");
437
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.