437 lines · c
1/* gf128mul.c - GF(2^128) multiplication functions2 *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 at7 * http://gladman.plushost.co.uk/oldsite/cryptography_technology/index.php8 * See the original copyright notice below.9 *10 * This program is free software; you can redistribute it and/or modify it11 * under the terms of the GNU General Public License as published by the Free12 * 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 TERMS21 22 The free distribution and use of this software in both source and binary23 form is allowed (with or without changes) provided that:24 25 1. distributions of this source code include the above copyright26 notice, this list of conditions and the following disclaimer;27 28 2. distributions in binary form include the above copyright29 notice, this list of conditions and the following disclaimer30 in the documentation and/or other associated materials;31 32 3. the copyright holder's name is not used to endorse products33 built using this software without specific written permission.34 35 ALTERNATIVELY, provided that this notice is retained in full, this product36 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 DISCLAIMER40 41 This software is provided 'as is' with no explicit or implied warranties42 in respect of its properties, including, but not limited to, correctness43 and/or fitness for purpose.44 ---------------------------------------------------------------------------45 Issue 31/01/200646 47 This file provides fast multiplication in GF(2^128) as required by several48 cryptographic authentication modes49*/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 element93 * in GF(2^128) is multiplied by x^8, the following macro returns the94 * 16-bit value that must be XOR-ed into the low-degree end of the95 * 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 for98 * the "be" convention where the highest-order bit is the coefficient of99 * the highest-degree polynomial term, and one for the "le" convention100 * where the highest-order bit is the coefficient of the lowest-degree101 * polynomial term. In both cases the values are stored in CPU byte102 * endianness such that the coefficients are ordered consistently across103 * bytes, i.e. in the "be" table bits 15..0 of the stored value104 * correspond to the coefficients of x^15..x^0, and in the "le" table105 * bits 15..0 correspond to the coefficients of x^0..x^15.106 *107 * Therefore, provided that the appropriate byte endianness conversions108 * are done by the multiplication functions (and these must be in place109 * 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 both112 * "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 129static const u16 gf128mul_table_le[256] = gf128mul_dat(xda_le);130static const u16 gf128mul_table_be[256] = gf128mul_dat(xda_be);131 132/*133 * The following functions multiply a field element by x^8 in134 * the polynomial field representation. They use 64-bit word operations135 * to gain speed but compensate for machine endianness and hence work136 * correctly on both styles of machine.137 */138 139static 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 */150static 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 160static 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 170void 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}179EXPORT_SYMBOL(gf128mul_x8_ble);180 181void 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 cacheline186 * (assuming a cacheline size of 32 bytes or more, which is by far the187 * most common). This ensures that each be128_xor() call in the loop188 * takes the same amount of time regardless of the value of 'ch', which189 * is derived from function parameter 'b', which is commonly used as a190 * 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 not192 * set, and this is equivalent to calling be128_xor() conditionally.193 * This approach aims to avoid leaking information about such keys194 * through execution time variances.195 *196 * Unfortunately, __aligned(16) or higher does not work on x86 for197 * 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}226EXPORT_SYMBOL(gf128mul_lle);227 228void 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}264EXPORT_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 key268 value in GF(2^128). If we consider a GF(2^128) value in269 the buffer's lowest byte, we can construct a table of270 the 256 16 byte values that result from the 256 values271 of this byte. This requires 4096 bytes. But we also272 need tables for each of the 16 higher bytes in the273 buffer as well, which makes 64 kbytes in total.274*/275/* additional explanation276 * t[0][BYTE] contains g*BYTE277 * t[1][BYTE] contains g*x^8*BYTE278 * ..279 * t[15][BYTE] contains g*x^120*BYTE */280struct 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 317out:318 return t;319}320EXPORT_SYMBOL(gf128mul_init_64k_bbe);321 322void 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}330EXPORT_SYMBOL(gf128mul_free_64k);331 332void 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}343EXPORT_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 key347 value in GF(2^128). If we consider a GF(2^128) value in a348 single byte, we can construct a table of the 256 16 byte349 values that result from the 256 values of this byte.350 This requires 4096 bytes. If we take the highest byte in351 the buffer and use this table to get the result, we then352 have to multiply by x^120 to get the final value. For the353 next highest byte the result has to be multiplied by x^112354 and so on. But we can do this by accumulating the result355 in an accumulator starting with the result for the top356 byte. We repeatedly multiply the accumulator value by357 x^8 and then add in (i.e. xor) the 16 bytes of the next358 lower byte in the buffer, stopping when we reach the359 lowest byte. This requires a 4096 byte table.360*/361struct 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 378out:379 return t;380}381EXPORT_SYMBOL(gf128mul_init_4k_lle);382 383struct 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 400out:401 return t;402}403EXPORT_SYMBOL(gf128mul_init_4k_bbe);404 405void 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}418EXPORT_SYMBOL(gf128mul_4k_lle);419 420void 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}433EXPORT_SYMBOL(gf128mul_4k_bbe);434 435MODULE_LICENSE("GPL");436MODULE_DESCRIPTION("Functions for multiplying elements of GF(2^128)");437