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