1 /* Copyright (c) 2014, Google Inc.
2 *
3 * Permission to use, copy, modify, and/or distribute this software for any
4 * purpose with or without fee is hereby granted, provided that the above
5 * copyright notice and this permission notice appear in all copies.
6 *
7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
10 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
12 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
13 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
14
15 // This implementation of poly1305 is by Andrew Moon
16 // (https://github.com/floodyberry/poly1305-donna) and released as public
17 // domain.
18
19 #include <ring-core/poly1305.h>
20
21 #include "internal.h"
22 #include "../internal.h"
23
24
25 #if !defined(BORINGSSL_HAS_UINT128) || !defined(OPENSSL_X86_64)
26
27 #if defined(__GNUC__) || defined(__clang__)
28 #pragma GCC diagnostic ignored "-Wsign-conversion"
29 #pragma GCC diagnostic ignored "-Wconversion"
30 #endif
31
mul32x32_64(uint32_t a,uint32_t b)32 static uint64_t mul32x32_64(uint32_t a, uint32_t b) { return (uint64_t)a * b; }
33
34 struct poly1305_state_st {
35 uint32_t r0, r1, r2, r3, r4;
36 uint32_t s1, s2, s3, s4;
37 uint32_t h0, h1, h2, h3, h4;
38 uint8_t buf[16];
39 size_t buf_used;
40 uint8_t key[16];
41 };
42
43 OPENSSL_STATIC_ASSERT(
44 sizeof(struct poly1305_state_st) + 63 <= sizeof(poly1305_state),
45 "poly1305_state isn't large enough to hold aligned poly1305_state_st");
46
poly1305_aligned_state(poly1305_state * state)47 static inline struct poly1305_state_st *poly1305_aligned_state(
48 poly1305_state *state) {
49 dev_assert_secret(((uintptr_t)state & 63) == 0);
50 return (struct poly1305_state_st *)(((uintptr_t)state + 63) & ~63);
51 }
52
53 // poly1305_blocks updates |state| given some amount of input data. This
54 // function may only be called with a |len| that is not a multiple of 16 at the
55 // end of the data. Otherwise the input must be buffered into 16 byte blocks.
poly1305_update(struct poly1305_state_st * state,const uint8_t * in,size_t len)56 static void poly1305_update(struct poly1305_state_st *state, const uint8_t *in,
57 size_t len) {
58 uint32_t t0, t1, t2, t3;
59 uint64_t t[5];
60 uint32_t b;
61 uint64_t c;
62 size_t j;
63 uint8_t mp[16];
64
65 if (len < 16) {
66 goto poly1305_donna_atmost15bytes;
67 }
68
69 poly1305_donna_16bytes:
70 t0 = CRYPTO_load_u32_le(in);
71 t1 = CRYPTO_load_u32_le(in + 4);
72 t2 = CRYPTO_load_u32_le(in + 8);
73 t3 = CRYPTO_load_u32_le(in + 12);
74
75 in += 16;
76 len -= 16;
77
78 state->h0 += t0 & 0x3ffffff;
79 state->h1 += ((((uint64_t)t1 << 32) | t0) >> 26) & 0x3ffffff;
80 state->h2 += ((((uint64_t)t2 << 32) | t1) >> 20) & 0x3ffffff;
81 state->h3 += ((((uint64_t)t3 << 32) | t2) >> 14) & 0x3ffffff;
82 state->h4 += (t3 >> 8) | (1 << 24);
83
84 poly1305_donna_mul:
85 t[0] = mul32x32_64(state->h0, state->r0) + mul32x32_64(state->h1, state->s4) +
86 mul32x32_64(state->h2, state->s3) + mul32x32_64(state->h3, state->s2) +
87 mul32x32_64(state->h4, state->s1);
88 t[1] = mul32x32_64(state->h0, state->r1) + mul32x32_64(state->h1, state->r0) +
89 mul32x32_64(state->h2, state->s4) + mul32x32_64(state->h3, state->s3) +
90 mul32x32_64(state->h4, state->s2);
91 t[2] = mul32x32_64(state->h0, state->r2) + mul32x32_64(state->h1, state->r1) +
92 mul32x32_64(state->h2, state->r0) + mul32x32_64(state->h3, state->s4) +
93 mul32x32_64(state->h4, state->s3);
94 t[3] = mul32x32_64(state->h0, state->r3) + mul32x32_64(state->h1, state->r2) +
95 mul32x32_64(state->h2, state->r1) + mul32x32_64(state->h3, state->r0) +
96 mul32x32_64(state->h4, state->s4);
97 t[4] = mul32x32_64(state->h0, state->r4) + mul32x32_64(state->h1, state->r3) +
98 mul32x32_64(state->h2, state->r2) + mul32x32_64(state->h3, state->r1) +
99 mul32x32_64(state->h4, state->r0);
100
101 state->h0 = (uint32_t)t[0] & 0x3ffffff;
102 c = (t[0] >> 26);
103 t[1] += c;
104 state->h1 = (uint32_t)t[1] & 0x3ffffff;
105 b = (uint32_t)(t[1] >> 26);
106 t[2] += b;
107 state->h2 = (uint32_t)t[2] & 0x3ffffff;
108 b = (uint32_t)(t[2] >> 26);
109 t[3] += b;
110 state->h3 = (uint32_t)t[3] & 0x3ffffff;
111 b = (uint32_t)(t[3] >> 26);
112 t[4] += b;
113 state->h4 = (uint32_t)t[4] & 0x3ffffff;
114 b = (uint32_t)(t[4] >> 26);
115 state->h0 += b * 5;
116
117 if (len >= 16) {
118 goto poly1305_donna_16bytes;
119 }
120
121 // final bytes
122 poly1305_donna_atmost15bytes:
123 if (!len) {
124 return;
125 }
126
127 for (j = 0; j < len; j++) {
128 mp[j] = in[j];
129 }
130 mp[j++] = 1;
131 for (; j < 16; j++) {
132 mp[j] = 0;
133 }
134 len = 0;
135
136 t0 = CRYPTO_load_u32_le(mp + 0);
137 t1 = CRYPTO_load_u32_le(mp + 4);
138 t2 = CRYPTO_load_u32_le(mp + 8);
139 t3 = CRYPTO_load_u32_le(mp + 12);
140
141 state->h0 += t0 & 0x3ffffff;
142 state->h1 += ((((uint64_t)t1 << 32) | t0) >> 26) & 0x3ffffff;
143 state->h2 += ((((uint64_t)t2 << 32) | t1) >> 20) & 0x3ffffff;
144 state->h3 += ((((uint64_t)t3 << 32) | t2) >> 14) & 0x3ffffff;
145 state->h4 += (t3 >> 8);
146
147 goto poly1305_donna_mul;
148 }
149
CRYPTO_poly1305_init(poly1305_state * statep,const uint8_t key[32])150 void CRYPTO_poly1305_init(poly1305_state *statep, const uint8_t key[32]) {
151 struct poly1305_state_st *state = poly1305_aligned_state(statep);
152 uint32_t t0, t1, t2, t3;
153
154 t0 = CRYPTO_load_u32_le(key + 0);
155 t1 = CRYPTO_load_u32_le(key + 4);
156 t2 = CRYPTO_load_u32_le(key + 8);
157 t3 = CRYPTO_load_u32_le(key + 12);
158
159 // precompute multipliers
160 state->r0 = t0 & 0x3ffffff;
161 t0 >>= 26;
162 t0 |= t1 << 6;
163 state->r1 = t0 & 0x3ffff03;
164 t1 >>= 20;
165 t1 |= t2 << 12;
166 state->r2 = t1 & 0x3ffc0ff;
167 t2 >>= 14;
168 t2 |= t3 << 18;
169 state->r3 = t2 & 0x3f03fff;
170 t3 >>= 8;
171 state->r4 = t3 & 0x00fffff;
172
173 state->s1 = state->r1 * 5;
174 state->s2 = state->r2 * 5;
175 state->s3 = state->r3 * 5;
176 state->s4 = state->r4 * 5;
177
178 // init state
179 state->h0 = 0;
180 state->h1 = 0;
181 state->h2 = 0;
182 state->h3 = 0;
183 state->h4 = 0;
184
185 state->buf_used = 0;
186 OPENSSL_memcpy(state->key, key + 16, sizeof(state->key));
187 }
188
CRYPTO_poly1305_update(poly1305_state * statep,const uint8_t * in,size_t in_len)189 void CRYPTO_poly1305_update(poly1305_state *statep, const uint8_t *in,
190 size_t in_len) {
191 struct poly1305_state_st *state = poly1305_aligned_state(statep);
192
193 // Work around a C language bug. See https://crbug.com/1019588.
194 if (in_len == 0) {
195 return;
196 }
197
198 if (state->buf_used) {
199 size_t todo = 16 - state->buf_used;
200 if (todo > in_len) {
201 todo = in_len;
202 }
203 for (size_t i = 0; i < todo; i++) {
204 state->buf[state->buf_used + i] = in[i];
205 }
206 state->buf_used += todo;
207 in_len -= todo;
208 in += todo;
209
210 if (state->buf_used == 16) {
211 poly1305_update(state, state->buf, 16);
212 state->buf_used = 0;
213 }
214 }
215
216 if (in_len >= 16) {
217 size_t todo = in_len & ~0xf;
218 poly1305_update(state, in, todo);
219 in += todo;
220 in_len &= 0xf;
221 }
222
223 if (in_len) {
224 for (size_t i = 0; i < in_len; i++) {
225 state->buf[i] = in[i];
226 }
227 state->buf_used = in_len;
228 }
229 }
230
CRYPTO_poly1305_finish(poly1305_state * statep,uint8_t mac[16])231 void CRYPTO_poly1305_finish(poly1305_state *statep, uint8_t mac[16]) {
232 struct poly1305_state_st *state = poly1305_aligned_state(statep);
233 uint32_t g0, g1, g2, g3, g4;
234 uint32_t b, nb;
235
236 if (state->buf_used) {
237 poly1305_update(state, state->buf, state->buf_used);
238 }
239
240 b = state->h0 >> 26;
241 state->h0 = state->h0 & 0x3ffffff;
242 state->h1 += b;
243 b = state->h1 >> 26;
244 state->h1 = state->h1 & 0x3ffffff;
245 state->h2 += b;
246 b = state->h2 >> 26;
247 state->h2 = state->h2 & 0x3ffffff;
248 state->h3 += b;
249 b = state->h3 >> 26;
250 state->h3 = state->h3 & 0x3ffffff;
251 state->h4 += b;
252 b = state->h4 >> 26;
253 state->h4 = state->h4 & 0x3ffffff;
254 state->h0 += b * 5;
255
256 g0 = state->h0 + 5;
257 b = g0 >> 26;
258 g0 &= 0x3ffffff;
259 g1 = state->h1 + b;
260 b = g1 >> 26;
261 g1 &= 0x3ffffff;
262 g2 = state->h2 + b;
263 b = g2 >> 26;
264 g2 &= 0x3ffffff;
265 g3 = state->h3 + b;
266 b = g3 >> 26;
267 g3 &= 0x3ffffff;
268 g4 = state->h4 + b - (1 << 26);
269
270 b = (g4 >> 31) - 1;
271 nb = ~b;
272 state->h0 = (state->h0 & nb) | (g0 & b);
273 state->h1 = (state->h1 & nb) | (g1 & b);
274 state->h2 = (state->h2 & nb) | (g2 & b);
275 state->h3 = (state->h3 & nb) | (g3 & b);
276 state->h4 = (state->h4 & nb) | (g4 & b);
277
278 uint64_t f0 = ((state->h0) | (state->h1 << 26)) +
279 (uint64_t)CRYPTO_load_u32_le(&state->key[0]);
280 uint64_t f1 = ((state->h1 >> 6) | (state->h2 << 20)) +
281 (uint64_t)CRYPTO_load_u32_le(&state->key[4]);
282 uint64_t f2 = ((state->h2 >> 12) | (state->h3 << 14)) +
283 (uint64_t)CRYPTO_load_u32_le(&state->key[8]);
284 uint64_t f3 = ((state->h3 >> 18) | (state->h4 << 8)) +
285 (uint64_t)CRYPTO_load_u32_le(&state->key[12]);
286
287 CRYPTO_store_u32_le(&mac[0], (uint32_t)f0);
288 f1 += (f0 >> 32);
289 CRYPTO_store_u32_le(&mac[4], (uint32_t)f1);
290 f2 += (f1 >> 32);
291 CRYPTO_store_u32_le(&mac[8], (uint32_t)f2);
292 f3 += (f2 >> 32);
293 CRYPTO_store_u32_le(&mac[12], (uint32_t)f3);
294 }
295
296 #endif // !BORINGSSL_HAS_UINT128 || !OPENSSL_X86_64
297