1 /* 2 * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining 5 * a copy of this software and associated documentation files (the 6 * "Software"), to deal in the Software without restriction, including 7 * without limitation the rights to use, copy, modify, merge, publish, 8 * distribute, sublicense, and/or sell copies of the Software, and to 9 * permit persons to whom the Software is furnished to do so, subject to 10 * the following conditions: 11 * 12 * The above copyright notice and this permission notice shall be 13 * included in all copies or substantial portions of the Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 18 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 19 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 20 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 22 * SOFTWARE. 23 */ 24 25 #include "inner.h" 26 27 /* 28 * This implementation uses 32-bit multiplications, and only the low 29 * 32 bits for each multiplication result. This is meant primarily for 30 * the ARM Cortex M0 and M0+, whose multiplication opcode does not yield 31 * the upper 32 bits; but it might also be useful on architectures where 32 * access to the upper 32 bits requires use of specific registers that 33 * create contention (e.g. on i386, "mul" necessarily outputs the result 34 * in edx:eax, while "imul" can use any registers but is limited to the 35 * low 32 bits). 36 * 37 * The implementation trick that is used here is bit-reversing (bit 0 38 * is swapped with bit 31, bit 1 with bit 30, and so on). In GF(2)[X], 39 * for all values x and y, we have: 40 * rev32(x) * rev32(y) = rev64(x * y) 41 * In other words, if we bit-reverse (over 32 bits) the operands, then we 42 * bit-reverse (over 64 bits) the result. 43 */ 44 45 /* 46 * Multiplication in GF(2)[X], truncated to its low 32 bits. 47 */ 48 static inline uint32_t 49 bmul32(uint32_t x, uint32_t y) 50 { 51 uint32_t x0, x1, x2, x3; 52 uint32_t y0, y1, y2, y3; 53 uint32_t z0, z1, z2, z3; 54 55 x0 = x & (uint32_t)0x11111111; 56 x1 = x & (uint32_t)0x22222222; 57 x2 = x & (uint32_t)0x44444444; 58 x3 = x & (uint32_t)0x88888888; 59 y0 = y & (uint32_t)0x11111111; 60 y1 = y & (uint32_t)0x22222222; 61 y2 = y & (uint32_t)0x44444444; 62 y3 = y & (uint32_t)0x88888888; 63 z0 = (x0 * y0) ^ (x1 * y3) ^ (x2 * y2) ^ (x3 * y1); 64 z1 = (x0 * y1) ^ (x1 * y0) ^ (x2 * y3) ^ (x3 * y2); 65 z2 = (x0 * y2) ^ (x1 * y1) ^ (x2 * y0) ^ (x3 * y3); 66 z3 = (x0 * y3) ^ (x1 * y2) ^ (x2 * y1) ^ (x3 * y0); 67 z0 &= (uint32_t)0x11111111; 68 z1 &= (uint32_t)0x22222222; 69 z2 &= (uint32_t)0x44444444; 70 z3 &= (uint32_t)0x88888888; 71 return z0 | z1 | z2 | z3; 72 } 73 74 /* 75 * Bit-reverse a 32-bit word. 76 */ 77 static uint32_t 78 rev32(uint32_t x) 79 { 80 #define RMS(m, s) do { \ 81 x = ((x & (uint32_t)(m)) << (s)) \ 82 | ((x >> (s)) & (uint32_t)(m)); \ 83 } while (0) 84 85 RMS(0x55555555, 1); 86 RMS(0x33333333, 2); 87 RMS(0x0F0F0F0F, 4); 88 RMS(0x00FF00FF, 8); 89 return (x << 16) | (x >> 16); 90 91 #undef RMS 92 } 93 94 /* see bearssl_hash.h */ 95 void 96 br_ghash_ctmul32(void *y, const void *h, const void *data, size_t len) 97 { 98 /* 99 * This implementation is similar to br_ghash_ctmul() except 100 * that we have to do the multiplication twice, with the 101 * "normal" and "bit reversed" operands. Hence we end up with 102 * eighteen 32-bit multiplications instead of nine. 103 */ 104 105 const unsigned char *buf, *hb; 106 unsigned char *yb; 107 uint32_t yw[4]; 108 uint32_t hw[4], hwr[4]; 109 110 buf = data; 111 yb = y; 112 hb = h; 113 yw[3] = br_dec32be(yb); 114 yw[2] = br_dec32be(yb + 4); 115 yw[1] = br_dec32be(yb + 8); 116 yw[0] = br_dec32be(yb + 12); 117 hw[3] = br_dec32be(hb); 118 hw[2] = br_dec32be(hb + 4); 119 hw[1] = br_dec32be(hb + 8); 120 hw[0] = br_dec32be(hb + 12); 121 hwr[3] = rev32(hw[3]); 122 hwr[2] = rev32(hw[2]); 123 hwr[1] = rev32(hw[1]); 124 hwr[0] = rev32(hw[0]); 125 while (len > 0) { 126 const unsigned char *src; 127 unsigned char tmp[16]; 128 int i; 129 uint32_t a[18], b[18], c[18]; 130 uint32_t d0, d1, d2, d3, d4, d5, d6, d7; 131 uint32_t zw[8]; 132 133 if (len >= 16) { 134 src = buf; 135 buf += 16; 136 len -= 16; 137 } else { 138 memcpy(tmp, buf, len); 139 memset(tmp + len, 0, (sizeof tmp) - len); 140 src = tmp; 141 len = 0; 142 } 143 yw[3] ^= br_dec32be(src); 144 yw[2] ^= br_dec32be(src + 4); 145 yw[1] ^= br_dec32be(src + 8); 146 yw[0] ^= br_dec32be(src + 12); 147 148 /* 149 * We are using Karatsuba: the 128x128 multiplication is 150 * reduced to three 64x64 multiplications, hence nine 151 * 32x32 multiplications. With the bit-reversal trick, 152 * we have to perform 18 32x32 multiplications. 153 */ 154 155 /* 156 * y[0,1]*h[0,1] -> 0,1,4 157 * y[2,3]*h[2,3] -> 2,3,5 158 * (y[0,1]+y[2,3])*(h[0,1]+h[2,3]) -> 6,7,8 159 */ 160 161 a[0] = yw[0]; 162 a[1] = yw[1]; 163 a[2] = yw[2]; 164 a[3] = yw[3]; 165 a[4] = a[0] ^ a[1]; 166 a[5] = a[2] ^ a[3]; 167 a[6] = a[0] ^ a[2]; 168 a[7] = a[1] ^ a[3]; 169 a[8] = a[6] ^ a[7]; 170 171 a[ 9] = rev32(yw[0]); 172 a[10] = rev32(yw[1]); 173 a[11] = rev32(yw[2]); 174 a[12] = rev32(yw[3]); 175 a[13] = a[ 9] ^ a[10]; 176 a[14] = a[11] ^ a[12]; 177 a[15] = a[ 9] ^ a[11]; 178 a[16] = a[10] ^ a[12]; 179 a[17] = a[15] ^ a[16]; 180 181 b[0] = hw[0]; 182 b[1] = hw[1]; 183 b[2] = hw[2]; 184 b[3] = hw[3]; 185 b[4] = b[0] ^ b[1]; 186 b[5] = b[2] ^ b[3]; 187 b[6] = b[0] ^ b[2]; 188 b[7] = b[1] ^ b[3]; 189 b[8] = b[6] ^ b[7]; 190 191 b[ 9] = hwr[0]; 192 b[10] = hwr[1]; 193 b[11] = hwr[2]; 194 b[12] = hwr[3]; 195 b[13] = b[ 9] ^ b[10]; 196 b[14] = b[11] ^ b[12]; 197 b[15] = b[ 9] ^ b[11]; 198 b[16] = b[10] ^ b[12]; 199 b[17] = b[15] ^ b[16]; 200 201 for (i = 0; i < 18; i ++) { 202 c[i] = bmul32(a[i], b[i]); 203 } 204 205 c[4] ^= c[0] ^ c[1]; 206 c[5] ^= c[2] ^ c[3]; 207 c[8] ^= c[6] ^ c[7]; 208 209 c[13] ^= c[ 9] ^ c[10]; 210 c[14] ^= c[11] ^ c[12]; 211 c[17] ^= c[15] ^ c[16]; 212 213 /* 214 * y[0,1]*h[0,1] -> 0,9^4,1^13,10 215 * y[2,3]*h[2,3] -> 2,11^5,3^14,12 216 * (y[0,1]+y[2,3])*(h[0,1]+h[2,3]) -> 6,15^8,7^17,16 217 */ 218 d0 = c[0]; 219 d1 = c[4] ^ (rev32(c[9]) >> 1); 220 d2 = c[1] ^ c[0] ^ c[2] ^ c[6] ^ (rev32(c[13]) >> 1); 221 d3 = c[4] ^ c[5] ^ c[8] 222 ^ (rev32(c[10] ^ c[9] ^ c[11] ^ c[15]) >> 1); 223 d4 = c[2] ^ c[1] ^ c[3] ^ c[7] 224 ^ (rev32(c[13] ^ c[14] ^ c[17]) >> 1); 225 d5 = c[5] ^ (rev32(c[11] ^ c[10] ^ c[12] ^ c[16]) >> 1); 226 d6 = c[3] ^ (rev32(c[14]) >> 1); 227 d7 = rev32(c[12]) >> 1; 228 229 zw[0] = d0 << 1; 230 zw[1] = (d1 << 1) | (d0 >> 31); 231 zw[2] = (d2 << 1) | (d1 >> 31); 232 zw[3] = (d3 << 1) | (d2 >> 31); 233 zw[4] = (d4 << 1) | (d3 >> 31); 234 zw[5] = (d5 << 1) | (d4 >> 31); 235 zw[6] = (d6 << 1) | (d5 >> 31); 236 zw[7] = (d7 << 1) | (d6 >> 31); 237 238 for (i = 0; i < 4; i ++) { 239 uint32_t lw; 240 241 lw = zw[i]; 242 zw[i + 4] ^= lw ^ (lw >> 1) ^ (lw >> 2) ^ (lw >> 7); 243 zw[i + 3] ^= (lw << 31) ^ (lw << 30) ^ (lw << 25); 244 } 245 memcpy(yw, zw + 4, sizeof yw); 246 } 247 br_enc32be(yb, yw[3]); 248 br_enc32be(yb + 4, yw[2]); 249 br_enc32be(yb + 8, yw[1]); 250 br_enc32be(yb + 12, yw[0]); 251 } 252