1 /* gf128mul.c - GF(2^128) multiplication functions
2 *
3 * Copyright (c) 2003, Dr Brian Gladman, Worcester, UK.
4 * Copyright (c) 2006, Rik Snel <[email protected]>
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
gf128mul_x8_lle(be128 * x)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 */
gf128mul_x8_lle_ti(be128 * x)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
gf128mul_x8_bbe(be128 * x)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
gf128mul_x8_ble(le128 * r,const le128 * x)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
gf128mul_lle(be128 * r,const be128 * b)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 /* This version uses 64k bytes of table space.
229 A 16 byte buffer has to be multiplied by a 16 byte key
230 value in GF(2^128). If we consider a GF(2^128) value in
231 the buffer's lowest byte, we can construct a table of
232 the 256 16 byte values that result from the 256 values
233 of this byte. This requires 4096 bytes. But we also
234 need tables for each of the 16 higher bytes in the
235 buffer as well, which makes 64 kbytes in total.
236 */
237 /* additional explanation
238 * t[0][BYTE] contains g*BYTE
239 * t[1][BYTE] contains g*x^8*BYTE
240 * ..
241 * t[15][BYTE] contains g*x^120*BYTE */
gf128mul_init_64k_bbe(const be128 * g)242 struct gf128mul_64k *gf128mul_init_64k_bbe(const be128 *g)
243 {
244 struct gf128mul_64k *t;
245 int i, j, k;
246
247 t = kzalloc(sizeof(*t), GFP_KERNEL);
248 if (!t)
249 goto out;
250
251 for (i = 0; i < 16; i++) {
252 t->t[i] = kzalloc(sizeof(*t->t[i]), GFP_KERNEL);
253 if (!t->t[i]) {
254 gf128mul_free_64k(t);
255 t = NULL;
256 goto out;
257 }
258 }
259
260 t->t[0]->t[1] = *g;
261 for (j = 1; j <= 64; j <<= 1)
262 gf128mul_x_bbe(&t->t[0]->t[j + j], &t->t[0]->t[j]);
263
264 for (i = 0;;) {
265 for (j = 2; j < 256; j += j)
266 for (k = 1; k < j; ++k)
267 be128_xor(&t->t[i]->t[j + k],
268 &t->t[i]->t[j], &t->t[i]->t[k]);
269
270 if (++i >= 16)
271 break;
272
273 for (j = 128; j > 0; j >>= 1) {
274 t->t[i]->t[j] = t->t[i - 1]->t[j];
275 gf128mul_x8_bbe(&t->t[i]->t[j]);
276 }
277 }
278
279 out:
280 return t;
281 }
282 EXPORT_SYMBOL(gf128mul_init_64k_bbe);
283
gf128mul_free_64k(struct gf128mul_64k * t)284 void gf128mul_free_64k(struct gf128mul_64k *t)
285 {
286 int i;
287
288 for (i = 0; i < 16; i++)
289 kfree_sensitive(t->t[i]);
290 kfree_sensitive(t);
291 }
292 EXPORT_SYMBOL(gf128mul_free_64k);
293
gf128mul_64k_bbe(be128 * a,const struct gf128mul_64k * t)294 void gf128mul_64k_bbe(be128 *a, const struct gf128mul_64k *t)
295 {
296 u8 *ap = (u8 *)a;
297 be128 r[1];
298 int i;
299
300 *r = t->t[0]->t[ap[15]];
301 for (i = 1; i < 16; ++i)
302 be128_xor(r, r, &t->t[i]->t[ap[15 - i]]);
303 *a = *r;
304 }
305 EXPORT_SYMBOL(gf128mul_64k_bbe);
306
307 /* This version uses 4k bytes of table space.
308 A 16 byte buffer has to be multiplied by a 16 byte key
309 value in GF(2^128). If we consider a GF(2^128) value in a
310 single byte, we can construct a table of the 256 16 byte
311 values that result from the 256 values of this byte.
312 This requires 4096 bytes. If we take the highest byte in
313 the buffer and use this table to get the result, we then
314 have to multiply by x^120 to get the final value. For the
315 next highest byte the result has to be multiplied by x^112
316 and so on. But we can do this by accumulating the result
317 in an accumulator starting with the result for the top
318 byte. We repeatedly multiply the accumulator value by
319 x^8 and then add in (i.e. xor) the 16 bytes of the next
320 lower byte in the buffer, stopping when we reach the
321 lowest byte. This requires a 4096 byte table.
322 */
gf128mul_init_4k_lle(const be128 * g)323 struct gf128mul_4k *gf128mul_init_4k_lle(const be128 *g)
324 {
325 struct gf128mul_4k *t;
326 int j, k;
327
328 t = kzalloc(sizeof(*t), GFP_KERNEL);
329 if (!t)
330 goto out;
331
332 t->t[128] = *g;
333 for (j = 64; j > 0; j >>= 1)
334 gf128mul_x_lle(&t->t[j], &t->t[j+j]);
335
336 for (j = 2; j < 256; j += j)
337 for (k = 1; k < j; ++k)
338 be128_xor(&t->t[j + k], &t->t[j], &t->t[k]);
339
340 out:
341 return t;
342 }
343 EXPORT_SYMBOL(gf128mul_init_4k_lle);
344
gf128mul_4k_lle(be128 * a,const struct gf128mul_4k * t)345 void gf128mul_4k_lle(be128 *a, const struct gf128mul_4k *t)
346 {
347 u8 *ap = (u8 *)a;
348 be128 r[1];
349 int i = 15;
350
351 *r = t->t[ap[15]];
352 while (i--) {
353 gf128mul_x8_lle(r);
354 be128_xor(r, r, &t->t[ap[i]]);
355 }
356 *a = *r;
357 }
358 EXPORT_SYMBOL(gf128mul_4k_lle);
359
360 MODULE_LICENSE("GPL");
361 MODULE_DESCRIPTION("Functions for multiplying elements of GF(2^128)");
362