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