2 * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
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:
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
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
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
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.
46 * Multiplication in GF(2)[X], truncated to its low 32 bits.
48 static inline uint32_t
49 bmul32(uint32_t x
, uint32_t y
)
51 uint32_t x0
, x1
, x2
, x3
;
52 uint32_t y0
, y1
, y2
, y3
;
53 uint32_t z0
, z1
, z2
, z3
;
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
;
75 * Bit-reverse a 32-bit word.
80 #define RMS(m, s) do { \
81 x = ((x & (uint32_t)(m)) << (s)) \
82 | ((x >> (s)) & (uint32_t)(m)); \
89 return (x
<< 16) | (x
>> 16);
94 /* see bearssl_hash.h */
96 br_ghash_ctmul32(void *y
, const void *h
, const void *data
, size_t len
)
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.
105 const unsigned char *buf
, *hb
;
108 uint32_t hw
[4], hwr
[4];
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]);
126 const unsigned char *src
;
127 unsigned char tmp
[16];
129 uint32_t a
[18], b
[18], c
[18];
130 uint32_t d0
, d1
, d2
, d3
, d4
, d5
, d6
, d7
;
138 memcpy(tmp
, buf
, len
);
139 memset(tmp
+ len
, 0, (sizeof tmp
) - len
);
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);
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.
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
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];
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];
201 for (i
= 0; i
< 18; i
++) {
202 c
[i
] = bmul32(a
[i
], b
[i
]);
209 c
[13] ^= c
[ 9] ^ c
[10];
210 c
[14] ^= c
[11] ^ c
[12];
211 c
[17] ^= c
[15] ^ c
[16];
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
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;
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);
238 for (i
= 0; i
< 4; i
++) {
242 zw
[i
+ 4] ^= lw
^ (lw
>> 1) ^ (lw
>> 2) ^ (lw
>> 7);
243 zw
[i
+ 3] ^= (lw
<< 31) ^ (lw
<< 30) ^ (lw
<< 25);
245 memcpy(yw
, zw
+ 4, sizeof yw
);
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]);