_ Git - BearSSL/blob - src/hash/ghash_ctmul32.c

   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         const unsigned char *buf, *hb;
  99         unsigned char *yb;
 100         uint32_t yw[4];
 101         uint32_t hw[4], hwr[4];
 102
 103         buf = data;
 104         yb = y;
 105         hb = h;
 106         yw[3] = br_dec32be(yb);
 107         yw[2] = br_dec32be(yb + 4);
 108         yw[1] = br_dec32be(yb + 8);
 109         yw[0] = br_dec32be(yb + 12);
 110         hw[3] = br_dec32be(hb);
 111         hw[2] = br_dec32be(hb + 4);
 112         hw[1] = br_dec32be(hb + 8);
 113         hw[0] = br_dec32be(hb + 12);
 114         hwr[3] = rev32(hw[3]);
 115         hwr[2] = rev32(hw[2]);
 116         hwr[1] = rev32(hw[1]);
 117         hwr[0] = rev32(hw[0]);
 118         while (len > 0) {
 119                 const unsigned char *src;
 120                 unsigned char tmp[16];
 121                 int i;
 122                 uint32_t a[18], b[18], c[18];
 123                 uint32_t d0, d1, d2, d3, d4, d5, d6, d7;
 124                 uint32_t zw[8];
 125
 126                 if (len >= 16) {
 127                         src = buf;
 128                         buf += 16;
 129                         len -= 16;
 130                 } else {
 131                         memcpy(tmp, buf, len);
 132                         memset(tmp + len, 0, (sizeof tmp) - len);
 133                         src = tmp;
 134                         len = 0;
 135                 }
 136                 yw[3] ^= br_dec32be(src);
 137                 yw[2] ^= br_dec32be(src + 4);
 138                 yw[1] ^= br_dec32be(src + 8);
 139                 yw[0] ^= br_dec32be(src + 12);
 140
 141                 /*
 142                  * We are using Karatsuba: the 128x128 multiplication is
 143                  * reduced to three 64x64 multiplications, hence nine
 144                  * 32x32 multiplications. With the bit-reversal trick,
 145                  * we have to perform 18 32x32 multiplications.
 146                  */
 147
 148                 /*
 149                  * y[0,1]*h[0,1] -> 0,1,4
 150                  * y[2,3]*h[2,3] -> 2,3,5
 151                  * (y[0,1]+y[2,3])*(h[0,1]+h[2,3]) -> 6,7,8
 152                  */
 153
 154                 a[0] = yw[0];
 155                 a[1] = yw[1];
 156                 a[2] = yw[2];
 157                 a[3] = yw[3];
 158                 a[4] = a[0] ^ a[1];
 159                 a[5] = a[2] ^ a[3];
 160                 a[6] = a[0] ^ a[2];
 161                 a[7] = a[1] ^ a[3];
 162                 a[8] = a[6] ^ a[7];
 163
 164                 a[ 9] = rev32(yw[0]);
 165                 a[10] = rev32(yw[1]);
 166                 a[11] = rev32(yw[2]);
 167                 a[12] = rev32(yw[3]);
 168                 a[13] = a[ 9] ^ a[10];
 169                 a[14] = a[11] ^ a[12];
 170                 a[15] = a[ 9] ^ a[11];
 171                 a[16] = a[10] ^ a[12];
 172                 a[17] = a[15] ^ a[16];
 173
 174                 b[0] = hw[0];
 175                 b[1] = hw[1];
 176                 b[2] = hw[2];
 177                 b[3] = hw[3];
 178                 b[4] = b[0] ^ b[1];
 179                 b[5] = b[2] ^ b[3];
 180                 b[6] = b[0] ^ b[2];
 181                 b[7] = b[1] ^ b[3];
 182                 b[8] = b[6] ^ b[7];
 183
 184                 b[ 9] = hwr[0];
 185                 b[10] = hwr[1];
 186                 b[11] = hwr[2];
 187                 b[12] = hwr[3];
 188                 b[13] = b[ 9] ^ b[10];
 189                 b[14] = b[11] ^ b[12];
 190                 b[15] = b[ 9] ^ b[11];
 191                 b[16] = b[10] ^ b[12];
 192                 b[17] = b[15] ^ b[16];
 193
 194                 for (i = 0; i < 18; i ++) {
 195                         c[i] = bmul32(a[i], b[i]);
 196                 }
 197
 198                 c[4] ^= c[0] ^ c[1];
 199                 c[5] ^= c[2] ^ c[3];
 200                 c[8] ^= c[6] ^ c[7];
 201
 202                 c[13] ^= c[ 9] ^ c[10];
 203                 c[14] ^= c[11] ^ c[12];
 204                 c[17] ^= c[15] ^ c[16];
 205
 206                 /*
 207                  * y[0,1]*h[0,1] -> 0,9^4,1^13,10
 208                  * y[2,3]*h[2,3] -> 2,11^5,3^14,12
 209                  * (y[0,1]+y[2,3])*(h[0,1]+h[2,3]) -> 6,15^8,7^17,16
 210                  */
 211                 d0 = c[0];
 212                 d1 = c[4] ^ (rev32(c[9]) >> 1);
 213                 d2 = c[1] ^ c[0] ^ c[2] ^ c[6] ^ (rev32(c[13]) >> 1);
 214                 d3 = c[4] ^ c[5] ^ c[8]
 215                         ^ (rev32(c[10] ^ c[9] ^ c[11] ^ c[15]) >> 1);
 216                 d4 = c[2] ^ c[1] ^ c[3] ^ c[7]
 217                         ^ (rev32(c[13] ^ c[14] ^ c[17]) >> 1);
 218                 d5 = c[5] ^ (rev32(c[11] ^ c[10] ^ c[12] ^ c[16]) >> 1);
 219                 d6 = c[3] ^ (rev32(c[14]) >> 1);
 220                 d7 = rev32(c[12]) >> 1;
 221
 222                 zw[0] = d0 << 1;
 223                 zw[1] = (d1 << 1) | (d0 >> 31);
 224                 zw[2] = (d2 << 1) | (d1 >> 31);
 225                 zw[3] = (d3 << 1) | (d2 >> 31);
 226                 zw[4] = (d4 << 1) | (d3 >> 31);
 227                 zw[5] = (d5 << 1) | (d4 >> 31);
 228                 zw[6] = (d6 << 1) | (d5 >> 31);
 229                 zw[7] = (d7 << 1) | (d6 >> 31);
 230
 231                 for (i = 0; i < 4; i ++) {
 232                         uint32_t lw;
 233
 234                         lw = zw[i];
 235                         zw[i + 4] ^= lw ^ (lw >> 1) ^ (lw >> 2) ^ (lw >> 7);
 236                         zw[i + 3] ^= (lw << 31) ^ (lw << 30) ^ (lw << 25);
 237                 }
 238                 memcpy(yw, zw + 4, sizeof yw);
 239         }
 240         br_enc32be(yb, yw[3]);
 241         br_enc32be(yb + 4, yw[2]);
 242         br_enc32be(yb + 8, yw[1]);
 243         br_enc32be(yb + 12, yw[0]);
 244 }