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/export.h>
 53#include <linux/kernel.h>
 54#include <linux/module.h>
 55#include <linux/slab.h>
 56
 57#define gf128mul_dat(q) { \
 58	q(0x00), q(0x01), q(0x02), q(0x03), q(0x04), q(0x05), q(0x06), q(0x07),\
 59	q(0x08), q(0x09), q(0x0a), q(0x0b), q(0x0c), q(0x0d), q(0x0e), q(0x0f),\
 60	q(0x10), q(0x11), q(0x12), q(0x13), q(0x14), q(0x15), q(0x16), q(0x17),\
 61	q(0x18), q(0x19), q(0x1a), q(0x1b), q(0x1c), q(0x1d), q(0x1e), q(0x1f),\
 62	q(0x20), q(0x21), q(0x22), q(0x23), q(0x24), q(0x25), q(0x26), q(0x27),\
 63	q(0x28), q(0x29), q(0x2a), q(0x2b), q(0x2c), q(0x2d), q(0x2e), q(0x2f),\
 64	q(0x30), q(0x31), q(0x32), q(0x33), q(0x34), q(0x35), q(0x36), q(0x37),\
 65	q(0x38), q(0x39), q(0x3a), q(0x3b), q(0x3c), q(0x3d), q(0x3e), q(0x3f),\
 66	q(0x40), q(0x41), q(0x42), q(0x43), q(0x44), q(0x45), q(0x46), q(0x47),\
 67	q(0x48), q(0x49), q(0x4a), q(0x4b), q(0x4c), q(0x4d), q(0x4e), q(0x4f),\
 68	q(0x50), q(0x51), q(0x52), q(0x53), q(0x54), q(0x55), q(0x56), q(0x57),\
 69	q(0x58), q(0x59), q(0x5a), q(0x5b), q(0x5c), q(0x5d), q(0x5e), q(0x5f),\
 70	q(0x60), q(0x61), q(0x62), q(0x63), q(0x64), q(0x65), q(0x66), q(0x67),\
 71	q(0x68), q(0x69), q(0x6a), q(0x6b), q(0x6c), q(0x6d), q(0x6e), q(0x6f),\
 72	q(0x70), q(0x71), q(0x72), q(0x73), q(0x74), q(0x75), q(0x76), q(0x77),\
 73	q(0x78), q(0x79), q(0x7a), q(0x7b), q(0x7c), q(0x7d), q(0x7e), q(0x7f),\
 74	q(0x80), q(0x81), q(0x82), q(0x83), q(0x84), q(0x85), q(0x86), q(0x87),\
 75	q(0x88), q(0x89), q(0x8a), q(0x8b), q(0x8c), q(0x8d), q(0x8e), q(0x8f),\
 76	q(0x90), q(0x91), q(0x92), q(0x93), q(0x94), q(0x95), q(0x96), q(0x97),\
 77	q(0x98), q(0x99), q(0x9a), q(0x9b), q(0x9c), q(0x9d), q(0x9e), q(0x9f),\
 78	q(0xa0), q(0xa1), q(0xa2), q(0xa3), q(0xa4), q(0xa5), q(0xa6), q(0xa7),\
 79	q(0xa8), q(0xa9), q(0xaa), q(0xab), q(0xac), q(0xad), q(0xae), q(0xaf),\
 80	q(0xb0), q(0xb1), q(0xb2), q(0xb3), q(0xb4), q(0xb5), q(0xb6), q(0xb7),\
 81	q(0xb8), q(0xb9), q(0xba), q(0xbb), q(0xbc), q(0xbd), q(0xbe), q(0xbf),\
 82	q(0xc0), q(0xc1), q(0xc2), q(0xc3), q(0xc4), q(0xc5), q(0xc6), q(0xc7),\
 83	q(0xc8), q(0xc9), q(0xca), q(0xcb), q(0xcc), q(0xcd), q(0xce), q(0xcf),\
 84	q(0xd0), q(0xd1), q(0xd2), q(0xd3), q(0xd4), q(0xd5), q(0xd6), q(0xd7),\
 85	q(0xd8), q(0xd9), q(0xda), q(0xdb), q(0xdc), q(0xdd), q(0xde), q(0xdf),\
 86	q(0xe0), q(0xe1), q(0xe2), q(0xe3), q(0xe4), q(0xe5), q(0xe6), q(0xe7),\
 87	q(0xe8), q(0xe9), q(0xea), q(0xeb), q(0xec), q(0xed), q(0xee), q(0xef),\
 88	q(0xf0), q(0xf1), q(0xf2), q(0xf3), q(0xf4), q(0xf5), q(0xf6), q(0xf7),\
 89	q(0xf8), q(0xf9), q(0xfa), q(0xfb), q(0xfc), q(0xfd), q(0xfe), q(0xff) \
 90}
 91
 92/*
 93 * Given a value i in 0..255 as the byte overflow when a field element
 94 * in GF(2^128) is multiplied by x^8, the following macro returns the
 95 * 16-bit value that must be XOR-ed into the low-degree end of the
 96 * product to reduce it modulo the polynomial x^128 + x^7 + x^2 + x + 1.
 97 *
 98 * There are two versions of the macro, and hence two tables: one for
 99 * the "be" convention where the highest-order bit is the coefficient of
100 * the highest-degree polynomial term, and one for the "le" convention
101 * where the highest-order bit is the coefficient of the lowest-degree
102 * polynomial term.  In both cases the values are stored in CPU byte
103 * endianness such that the coefficients are ordered consistently across
104 * bytes, i.e. in the "be" table bits 15..0 of the stored value
105 * correspond to the coefficients of x^15..x^0, and in the "le" table
106 * bits 15..0 correspond to the coefficients of x^0..x^15.
107 *
108 * Therefore, provided that the appropriate byte endianness conversions
109 * are done by the multiplication functions (and these must be in place
110 * anyway to support both little endian and big endian CPUs), the "be"
111 * table can be used for multiplications of both "bbe" and "ble"
112 * elements, and the "le" table can be used for multiplications of both
113 * "lle" and "lbe" elements.
114 */
115
116#define xda_be(i) ( \
117	(i & 0x80 ? 0x4380 : 0) ^ (i & 0x40 ? 0x21c0 : 0) ^ \
118	(i & 0x20 ? 0x10e0 : 0) ^ (i & 0x10 ? 0x0870 : 0) ^ \
119	(i & 0x08 ? 0x0438 : 0) ^ (i & 0x04 ? 0x021c : 0) ^ \
120	(i & 0x02 ? 0x010e : 0) ^ (i & 0x01 ? 0x0087 : 0) \
121)
122
123#define xda_le(i) ( \
124	(i & 0x80 ? 0xe100 : 0) ^ (i & 0x40 ? 0x7080 : 0) ^ \
125	(i & 0x20 ? 0x3840 : 0) ^ (i & 0x10 ? 0x1c20 : 0) ^ \
126	(i & 0x08 ? 0x0e10 : 0) ^ (i & 0x04 ? 0x0708 : 0) ^ \
127	(i & 0x02 ? 0x0384 : 0) ^ (i & 0x01 ? 0x01c2 : 0) \
128)
129
130static const u16 gf128mul_table_le[256] = gf128mul_dat(xda_le);
131static const u16 gf128mul_table_be[256] = gf128mul_dat(xda_be);
132
133/*
134 * The following functions multiply a field element by x^8 in
135 * the polynomial field representation.  They use 64-bit word operations
136 * to gain speed but compensate for machine endianness and hence work
137 * correctly on both styles of machine.
138 */
139
140static void gf128mul_x8_lle(be128 *x)
141{
142	u64 a = be64_to_cpu(x->a);
143	u64 b = be64_to_cpu(x->b);
144	u64 _tt = gf128mul_table_le[b & 0xff];
145
146	x->b = cpu_to_be64((b >> 8) | (a << 56));
147	x->a = cpu_to_be64((a >> 8) ^ (_tt << 48));
148}
149
150/* time invariant version of gf128mul_x8_lle */
151static void gf128mul_x8_lle_ti(be128 *x)
152{
153	u64 a = be64_to_cpu(x->a);
154	u64 b = be64_to_cpu(x->b);
155	u64 _tt = xda_le(b & 0xff); /* avoid table lookup */
156
157	x->b = cpu_to_be64((b >> 8) | (a << 56));
158	x->a = cpu_to_be64((a >> 8) ^ (_tt << 48));
159}
160
161static void gf128mul_x8_bbe(be128 *x)
162{
163	u64 a = be64_to_cpu(x->a);
164	u64 b = be64_to_cpu(x->b);
165	u64 _tt = gf128mul_table_be[a >> 56];
166
167	x->a = cpu_to_be64((a << 8) | (b >> 56));
168	x->b = cpu_to_be64((b << 8) ^ _tt);
169}
170
171void gf128mul_x8_ble(le128 *r, const le128 *x)
172{
173	u64 a = le64_to_cpu(x->a);
174	u64 b = le64_to_cpu(x->b);
175	u64 _tt = gf128mul_table_be[a >> 56];
176
177	r->a = cpu_to_le64((a << 8) | (b >> 56));
178	r->b = cpu_to_le64((b << 8) ^ _tt);
179}
180EXPORT_SYMBOL(gf128mul_x8_ble);
181
182void gf128mul_lle(be128 *r, const be128 *b)
183{
184	/*
185	 * The p array should be aligned to twice the size of its element type,
186	 * so that every even/odd pair is guaranteed to share a cacheline
187	 * (assuming a cacheline size of 32 bytes or more, which is by far the
188	 * most common). This ensures that each be128_xor() call in the loop
189	 * takes the same amount of time regardless of the value of 'ch', which
190	 * is derived from function parameter 'b', which is commonly used as a
191	 * key, e.g., for GHASH. The odd array elements are all set to zero,
192	 * making each be128_xor() a NOP if its associated bit in 'ch' is not
193	 * set, and this is equivalent to calling be128_xor() conditionally.
194	 * This approach aims to avoid leaking information about such keys
195	 * through execution time variances.
196	 *
197	 * Unfortunately, __aligned(16) or higher does not work on x86 for
198	 * variables on the stack so we need to perform the alignment by hand.
199	 */
200	be128 array[16 + 3] = {};
201	be128 *p = PTR_ALIGN(&array[0], 2 * sizeof(be128));
202	int i;
203
204	p[0] = *r;
205	for (i = 0; i < 7; ++i)
206		gf128mul_x_lle(&p[2 * i + 2], &p[2 * i]);
207
208	memset(r, 0, sizeof(*r));
209	for (i = 0;;) {
210		u8 ch = ((u8 *)b)[15 - i];
211
212		be128_xor(r, r, &p[ 0 + !(ch & 0x80)]);
213		be128_xor(r, r, &p[ 2 + !(ch & 0x40)]);
214		be128_xor(r, r, &p[ 4 + !(ch & 0x20)]);
215		be128_xor(r, r, &p[ 6 + !(ch & 0x10)]);
216		be128_xor(r, r, &p[ 8 + !(ch & 0x08)]);
217		be128_xor(r, r, &p[10 + !(ch & 0x04)]);
218		be128_xor(r, r, &p[12 + !(ch & 0x02)]);
219		be128_xor(r, r, &p[14 + !(ch & 0x01)]);
220
221		if (++i >= 16)
222			break;
223
224		gf128mul_x8_lle_ti(r); /* use the time invariant version */
225	}
226}
227EXPORT_SYMBOL(gf128mul_lle);
228
229/*      This version uses 64k bytes of table space.
230    A 16 byte buffer has to be multiplied by a 16 byte key
231    value in GF(2^128).  If we consider a GF(2^128) value in
232    the buffer's lowest byte, we can construct a table of
233    the 256 16 byte values that result from the 256 values
234    of this byte.  This requires 4096 bytes. But we also
235    need tables for each of the 16 higher bytes in the
236    buffer as well, which makes 64 kbytes in total.
237*/
238/* additional explanation
239 * t[0][BYTE] contains g*BYTE
240 * t[1][BYTE] contains g*x^8*BYTE
241 *  ..
242 * t[15][BYTE] contains g*x^120*BYTE */
243struct gf128mul_64k *gf128mul_init_64k_bbe(const be128 *g)
244{
245	struct gf128mul_64k *t;
246	int i, j, k;
247
248	t = kzalloc(sizeof(*t), GFP_KERNEL);
249	if (!t)
250		goto out;
251
252	for (i = 0; i < 16; i++) {
253		t->t[i] = kzalloc(sizeof(*t->t[i]), GFP_KERNEL);
254		if (!t->t[i]) {
255			gf128mul_free_64k(t);
256			t = NULL;
257			goto out;
258		}
259	}
260
261	t->t[0]->t[1] = *g;
262	for (j = 1; j <= 64; j <<= 1)
263		gf128mul_x_bbe(&t->t[0]->t[j + j], &t->t[0]->t[j]);
264
265	for (i = 0;;) {
266		for (j = 2; j < 256; j += j)
267			for (k = 1; k < j; ++k)
268				be128_xor(&t->t[i]->t[j + k],
269					  &t->t[i]->t[j], &t->t[i]->t[k]);
270
271		if (++i >= 16)
272			break;
273
274		for (j = 128; j > 0; j >>= 1) {
275			t->t[i]->t[j] = t->t[i - 1]->t[j];
276			gf128mul_x8_bbe(&t->t[i]->t[j]);
277		}
278	}
279
280out:
281	return t;
282}
283EXPORT_SYMBOL(gf128mul_init_64k_bbe);
284
285void gf128mul_free_64k(struct gf128mul_64k *t)
286{
287	int i;
288
289	for (i = 0; i < 16; i++)
290		kfree_sensitive(t->t[i]);
291	kfree_sensitive(t);
292}
293EXPORT_SYMBOL(gf128mul_free_64k);
294
295void gf128mul_64k_bbe(be128 *a, const struct gf128mul_64k *t)
296{
297	u8 *ap = (u8 *)a;
298	be128 r[1];
299	int i;
300
301	*r = t->t[0]->t[ap[15]];
302	for (i = 1; i < 16; ++i)
303		be128_xor(r, r, &t->t[i]->t[ap[15 - i]]);
304	*a = *r;
305}
306EXPORT_SYMBOL(gf128mul_64k_bbe);
307
308/*      This version uses 4k bytes of table space.
309    A 16 byte buffer has to be multiplied by a 16 byte key
310    value in GF(2^128).  If we consider a GF(2^128) value in a
311    single byte, we can construct a table of the 256 16 byte
312    values that result from the 256 values of this byte.
313    This requires 4096 bytes. If we take the highest byte in
314    the buffer and use this table to get the result, we then
315    have to multiply by x^120 to get the final value. For the
316    next highest byte the result has to be multiplied by x^112
317    and so on. But we can do this by accumulating the result
318    in an accumulator starting with the result for the top
319    byte.  We repeatedly multiply the accumulator value by
320    x^8 and then add in (i.e. xor) the 16 bytes of the next
321    lower byte in the buffer, stopping when we reach the
322    lowest byte. This requires a 4096 byte table.
323*/
324struct gf128mul_4k *gf128mul_init_4k_lle(const be128 *g)
325{
326	struct gf128mul_4k *t;
327	int j, k;
328
329	t = kzalloc(sizeof(*t), GFP_KERNEL);
330	if (!t)
331		goto out;
332
333	t->t[128] = *g;
334	for (j = 64; j > 0; j >>= 1)
335		gf128mul_x_lle(&t->t[j], &t->t[j+j]);
336
337	for (j = 2; j < 256; j += j)
338		for (k = 1; k < j; ++k)
339			be128_xor(&t->t[j + k], &t->t[j], &t->t[k]);
340
341out:
342	return t;
343}
344EXPORT_SYMBOL(gf128mul_init_4k_lle);
345
346void gf128mul_4k_lle(be128 *a, const struct gf128mul_4k *t)
347{
348	u8 *ap = (u8 *)a;
349	be128 r[1];
350	int i = 15;
351
352	*r = t->t[ap[15]];
353	while (i--) {
354		gf128mul_x8_lle(r);
355		be128_xor(r, r, &t->t[ap[i]]);
356	}
357	*a = *r;
358}
359EXPORT_SYMBOL(gf128mul_4k_lle);
360
361MODULE_LICENSE("GPL");
362MODULE_DESCRIPTION("Functions for multiplying elements of GF(2^128)");