Merge tag 'writeback_for_v5.9-rc3' of git://git.kernel.org/pub/scm/linux/kernel/git...
[platform/kernel/linux-rpi.git] / crypto / gf128mul.c
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 static void gf128mul_x8_bbe(be128 *x)
150 {
151         u64 a = be64_to_cpu(x->a);
152         u64 b = be64_to_cpu(x->b);
153         u64 _tt = gf128mul_table_be[a >> 56];
154
155         x->a = cpu_to_be64((a << 8) | (b >> 56));
156         x->b = cpu_to_be64((b << 8) ^ _tt);
157 }
158
159 void gf128mul_x8_ble(le128 *r, const le128 *x)
160 {
161         u64 a = le64_to_cpu(x->a);
162         u64 b = le64_to_cpu(x->b);
163         u64 _tt = gf128mul_table_be[a >> 56];
164
165         r->a = cpu_to_le64((a << 8) | (b >> 56));
166         r->b = cpu_to_le64((b << 8) ^ _tt);
167 }
168 EXPORT_SYMBOL(gf128mul_x8_ble);
169
170 void gf128mul_lle(be128 *r, const be128 *b)
171 {
172         be128 p[8];
173         int i;
174
175         p[0] = *r;
176         for (i = 0; i < 7; ++i)
177                 gf128mul_x_lle(&p[i + 1], &p[i]);
178
179         memset(r, 0, sizeof(*r));
180         for (i = 0;;) {
181                 u8 ch = ((u8 *)b)[15 - i];
182
183                 if (ch & 0x80)
184                         be128_xor(r, r, &p[0]);
185                 if (ch & 0x40)
186                         be128_xor(r, r, &p[1]);
187                 if (ch & 0x20)
188                         be128_xor(r, r, &p[2]);
189                 if (ch & 0x10)
190                         be128_xor(r, r, &p[3]);
191                 if (ch & 0x08)
192                         be128_xor(r, r, &p[4]);
193                 if (ch & 0x04)
194                         be128_xor(r, r, &p[5]);
195                 if (ch & 0x02)
196                         be128_xor(r, r, &p[6]);
197                 if (ch & 0x01)
198                         be128_xor(r, r, &p[7]);
199
200                 if (++i >= 16)
201                         break;
202
203                 gf128mul_x8_lle(r);
204         }
205 }
206 EXPORT_SYMBOL(gf128mul_lle);
207
208 void gf128mul_bbe(be128 *r, const be128 *b)
209 {
210         be128 p[8];
211         int i;
212
213         p[0] = *r;
214         for (i = 0; i < 7; ++i)
215                 gf128mul_x_bbe(&p[i + 1], &p[i]);
216
217         memset(r, 0, sizeof(*r));
218         for (i = 0;;) {
219                 u8 ch = ((u8 *)b)[i];
220
221                 if (ch & 0x80)
222                         be128_xor(r, r, &p[7]);
223                 if (ch & 0x40)
224                         be128_xor(r, r, &p[6]);
225                 if (ch & 0x20)
226                         be128_xor(r, r, &p[5]);
227                 if (ch & 0x10)
228                         be128_xor(r, r, &p[4]);
229                 if (ch & 0x08)
230                         be128_xor(r, r, &p[3]);
231                 if (ch & 0x04)
232                         be128_xor(r, r, &p[2]);
233                 if (ch & 0x02)
234                         be128_xor(r, r, &p[1]);
235                 if (ch & 0x01)
236                         be128_xor(r, r, &p[0]);
237
238                 if (++i >= 16)
239                         break;
240
241                 gf128mul_x8_bbe(r);
242         }
243 }
244 EXPORT_SYMBOL(gf128mul_bbe);
245
246 /*      This version uses 64k bytes of table space.
247     A 16 byte buffer has to be multiplied by a 16 byte key
248     value in GF(2^128).  If we consider a GF(2^128) value in
249     the buffer's lowest byte, we can construct a table of
250     the 256 16 byte values that result from the 256 values
251     of this byte.  This requires 4096 bytes. But we also
252     need tables for each of the 16 higher bytes in the
253     buffer as well, which makes 64 kbytes in total.
254 */
255 /* additional explanation
256  * t[0][BYTE] contains g*BYTE
257  * t[1][BYTE] contains g*x^8*BYTE
258  *  ..
259  * t[15][BYTE] contains g*x^120*BYTE */
260 struct gf128mul_64k *gf128mul_init_64k_bbe(const be128 *g)
261 {
262         struct gf128mul_64k *t;
263         int i, j, k;
264
265         t = kzalloc(sizeof(*t), GFP_KERNEL);
266         if (!t)
267                 goto out;
268
269         for (i = 0; i < 16; i++) {
270                 t->t[i] = kzalloc(sizeof(*t->t[i]), GFP_KERNEL);
271                 if (!t->t[i]) {
272                         gf128mul_free_64k(t);
273                         t = NULL;
274                         goto out;
275                 }
276         }
277
278         t->t[0]->t[1] = *g;
279         for (j = 1; j <= 64; j <<= 1)
280                 gf128mul_x_bbe(&t->t[0]->t[j + j], &t->t[0]->t[j]);
281
282         for (i = 0;;) {
283                 for (j = 2; j < 256; j += j)
284                         for (k = 1; k < j; ++k)
285                                 be128_xor(&t->t[i]->t[j + k],
286                                           &t->t[i]->t[j], &t->t[i]->t[k]);
287
288                 if (++i >= 16)
289                         break;
290
291                 for (j = 128; j > 0; j >>= 1) {
292                         t->t[i]->t[j] = t->t[i - 1]->t[j];
293                         gf128mul_x8_bbe(&t->t[i]->t[j]);
294                 }
295         }
296
297 out:
298         return t;
299 }
300 EXPORT_SYMBOL(gf128mul_init_64k_bbe);
301
302 void gf128mul_free_64k(struct gf128mul_64k *t)
303 {
304         int i;
305
306         for (i = 0; i < 16; i++)
307                 kfree_sensitive(t->t[i]);
308         kfree_sensitive(t);
309 }
310 EXPORT_SYMBOL(gf128mul_free_64k);
311
312 void gf128mul_64k_bbe(be128 *a, const struct gf128mul_64k *t)
313 {
314         u8 *ap = (u8 *)a;
315         be128 r[1];
316         int i;
317
318         *r = t->t[0]->t[ap[15]];
319         for (i = 1; i < 16; ++i)
320                 be128_xor(r, r, &t->t[i]->t[ap[15 - i]]);
321         *a = *r;
322 }
323 EXPORT_SYMBOL(gf128mul_64k_bbe);
324
325 /*      This version uses 4k bytes of table space.
326     A 16 byte buffer has to be multiplied by a 16 byte key
327     value in GF(2^128).  If we consider a GF(2^128) value in a
328     single byte, we can construct a table of the 256 16 byte
329     values that result from the 256 values of this byte.
330     This requires 4096 bytes. If we take the highest byte in
331     the buffer and use this table to get the result, we then
332     have to multiply by x^120 to get the final value. For the
333     next highest byte the result has to be multiplied by x^112
334     and so on. But we can do this by accumulating the result
335     in an accumulator starting with the result for the top
336     byte.  We repeatedly multiply the accumulator value by
337     x^8 and then add in (i.e. xor) the 16 bytes of the next
338     lower byte in the buffer, stopping when we reach the
339     lowest byte. This requires a 4096 byte table.
340 */
341 struct gf128mul_4k *gf128mul_init_4k_lle(const be128 *g)
342 {
343         struct gf128mul_4k *t;
344         int j, k;
345
346         t = kzalloc(sizeof(*t), GFP_KERNEL);
347         if (!t)
348                 goto out;
349
350         t->t[128] = *g;
351         for (j = 64; j > 0; j >>= 1)
352                 gf128mul_x_lle(&t->t[j], &t->t[j+j]);
353
354         for (j = 2; j < 256; j += j)
355                 for (k = 1; k < j; ++k)
356                         be128_xor(&t->t[j + k], &t->t[j], &t->t[k]);
357
358 out:
359         return t;
360 }
361 EXPORT_SYMBOL(gf128mul_init_4k_lle);
362
363 struct gf128mul_4k *gf128mul_init_4k_bbe(const be128 *g)
364 {
365         struct gf128mul_4k *t;
366         int j, k;
367
368         t = kzalloc(sizeof(*t), GFP_KERNEL);
369         if (!t)
370                 goto out;
371
372         t->t[1] = *g;
373         for (j = 1; j <= 64; j <<= 1)
374                 gf128mul_x_bbe(&t->t[j + j], &t->t[j]);
375
376         for (j = 2; j < 256; j += j)
377                 for (k = 1; k < j; ++k)
378                         be128_xor(&t->t[j + k], &t->t[j], &t->t[k]);
379
380 out:
381         return t;
382 }
383 EXPORT_SYMBOL(gf128mul_init_4k_bbe);
384
385 void gf128mul_4k_lle(be128 *a, const struct gf128mul_4k *t)
386 {
387         u8 *ap = (u8 *)a;
388         be128 r[1];
389         int i = 15;
390
391         *r = t->t[ap[15]];
392         while (i--) {
393                 gf128mul_x8_lle(r);
394                 be128_xor(r, r, &t->t[ap[i]]);
395         }
396         *a = *r;
397 }
398 EXPORT_SYMBOL(gf128mul_4k_lle);
399
400 void gf128mul_4k_bbe(be128 *a, const struct gf128mul_4k *t)
401 {
402         u8 *ap = (u8 *)a;
403         be128 r[1];
404         int i = 0;
405
406         *r = t->t[ap[0]];
407         while (++i < 16) {
408                 gf128mul_x8_bbe(r);
409                 be128_xor(r, r, &t->t[ap[i]]);
410         }
411         *a = *r;
412 }
413 EXPORT_SYMBOL(gf128mul_4k_bbe);
414
415 MODULE_LICENSE("GPL");
416 MODULE_DESCRIPTION("Functions for multiplying elements of GF(2^128)");