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 <openssl/poly1305.h>
20 
21 #include <string.h>
22 
23 #include <openssl/cpu.h>
24 
25 #include "internal.h"
26 #include "../internal.h"
27 
28 
29 #if !defined(BORINGSSL_HAS_UINT128) || !defined(OPENSSL_X86_64)
30 
31 // We can assume little-endian.
U8TO32_LE(const uint8_t * m)32 static uint32_t U8TO32_LE(const uint8_t *m) {
33   uint32_t r;
34   OPENSSL_memcpy(&r, m, sizeof(r));
35   return r;
36 }
37 
U32TO8_LE(uint8_t * m,uint32_t v)38 static void U32TO8_LE(uint8_t *m, uint32_t v) {
39   OPENSSL_memcpy(m, &v, sizeof(v));
40 }
41 
mul32x32_64(uint32_t a,uint32_t b)42 static uint64_t mul32x32_64(uint32_t a, uint32_t b) { return (uint64_t)a * b; }
43 
44 struct poly1305_state_st {
45   uint32_t r0, r1, r2, r3, r4;
46   uint32_t s1, s2, s3, s4;
47   uint32_t h0, h1, h2, h3, h4;
48   uint8_t buf[16];
49   unsigned int buf_used;
50   uint8_t key[16];
51 };
52 
poly1305_aligned_state(poly1305_state * state)53 static inline struct poly1305_state_st *poly1305_aligned_state(
54     poly1305_state *state) {
55   return (struct poly1305_state_st *)(((uintptr_t)state + 63) & ~63);
56 }
57 
58 // poly1305_blocks updates |state| given some amount of input data. This
59 // function may only be called with a |len| that is not a multiple of 16 at the
60 // 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)61 static void poly1305_update(struct poly1305_state_st *state, const uint8_t *in,
62                             size_t len) {
63   uint32_t t0, t1, t2, t3;
64   uint64_t t[5];
65   uint32_t b;
66   uint64_t c;
67   size_t j;
68   uint8_t mp[16];
69 
70   if (len < 16) {
71     goto poly1305_donna_atmost15bytes;
72   }
73 
74 poly1305_donna_16bytes:
75   t0 = U8TO32_LE(in);
76   t1 = U8TO32_LE(in + 4);
77   t2 = U8TO32_LE(in + 8);
78   t3 = U8TO32_LE(in + 12);
79 
80   in += 16;
81   len -= 16;
82 
83   state->h0 += t0 & 0x3ffffff;
84   state->h1 += ((((uint64_t)t1 << 32) | t0) >> 26) & 0x3ffffff;
85   state->h2 += ((((uint64_t)t2 << 32) | t1) >> 20) & 0x3ffffff;
86   state->h3 += ((((uint64_t)t3 << 32) | t2) >> 14) & 0x3ffffff;
87   state->h4 += (t3 >> 8) | (1 << 24);
88 
89 poly1305_donna_mul:
90   t[0] = mul32x32_64(state->h0, state->r0) + mul32x32_64(state->h1, state->s4) +
91          mul32x32_64(state->h2, state->s3) + mul32x32_64(state->h3, state->s2) +
92          mul32x32_64(state->h4, state->s1);
93   t[1] = mul32x32_64(state->h0, state->r1) + mul32x32_64(state->h1, state->r0) +
94          mul32x32_64(state->h2, state->s4) + mul32x32_64(state->h3, state->s3) +
95          mul32x32_64(state->h4, state->s2);
96   t[2] = mul32x32_64(state->h0, state->r2) + mul32x32_64(state->h1, state->r1) +
97          mul32x32_64(state->h2, state->r0) + mul32x32_64(state->h3, state->s4) +
98          mul32x32_64(state->h4, state->s3);
99   t[3] = mul32x32_64(state->h0, state->r3) + mul32x32_64(state->h1, state->r2) +
100          mul32x32_64(state->h2, state->r1) + mul32x32_64(state->h3, state->r0) +
101          mul32x32_64(state->h4, state->s4);
102   t[4] = mul32x32_64(state->h0, state->r4) + mul32x32_64(state->h1, state->r3) +
103          mul32x32_64(state->h2, state->r2) + mul32x32_64(state->h3, state->r1) +
104          mul32x32_64(state->h4, state->r0);
105 
106   state->h0 = (uint32_t)t[0] & 0x3ffffff;
107   c = (t[0] >> 26);
108   t[1] += c;
109   state->h1 = (uint32_t)t[1] & 0x3ffffff;
110   b = (uint32_t)(t[1] >> 26);
111   t[2] += b;
112   state->h2 = (uint32_t)t[2] & 0x3ffffff;
113   b = (uint32_t)(t[2] >> 26);
114   t[3] += b;
115   state->h3 = (uint32_t)t[3] & 0x3ffffff;
116   b = (uint32_t)(t[3] >> 26);
117   t[4] += b;
118   state->h4 = (uint32_t)t[4] & 0x3ffffff;
119   b = (uint32_t)(t[4] >> 26);
120   state->h0 += b * 5;
121 
122   if (len >= 16) {
123     goto poly1305_donna_16bytes;
124   }
125 
126 // final bytes
127 poly1305_donna_atmost15bytes:
128   if (!len) {
129     return;
130   }
131 
132   for (j = 0; j < len; j++) {
133     mp[j] = in[j];
134   }
135   mp[j++] = 1;
136   for (; j < 16; j++) {
137     mp[j] = 0;
138   }
139   len = 0;
140 
141   t0 = U8TO32_LE(mp + 0);
142   t1 = U8TO32_LE(mp + 4);
143   t2 = U8TO32_LE(mp + 8);
144   t3 = U8TO32_LE(mp + 12);
145 
146   state->h0 += t0 & 0x3ffffff;
147   state->h1 += ((((uint64_t)t1 << 32) | t0) >> 26) & 0x3ffffff;
148   state->h2 += ((((uint64_t)t2 << 32) | t1) >> 20) & 0x3ffffff;
149   state->h3 += ((((uint64_t)t3 << 32) | t2) >> 14) & 0x3ffffff;
150   state->h4 += (t3 >> 8);
151 
152   goto poly1305_donna_mul;
153 }
154 
CRYPTO_poly1305_init(poly1305_state * statep,const uint8_t key[32])155 void CRYPTO_poly1305_init(poly1305_state *statep, const uint8_t key[32]) {
156   struct poly1305_state_st *state = poly1305_aligned_state(statep);
157   uint32_t t0, t1, t2, t3;
158 
159 #if defined(OPENSSL_POLY1305_NEON)
160   if (CRYPTO_is_NEON_capable()) {
161     CRYPTO_poly1305_init_neon(statep, key);
162     return;
163   }
164 #endif
165 
166   t0 = U8TO32_LE(key + 0);
167   t1 = U8TO32_LE(key + 4);
168   t2 = U8TO32_LE(key + 8);
169   t3 = U8TO32_LE(key + 12);
170 
171   // precompute multipliers
172   state->r0 = t0 & 0x3ffffff;
173   t0 >>= 26;
174   t0 |= t1 << 6;
175   state->r1 = t0 & 0x3ffff03;
176   t1 >>= 20;
177   t1 |= t2 << 12;
178   state->r2 = t1 & 0x3ffc0ff;
179   t2 >>= 14;
180   t2 |= t3 << 18;
181   state->r3 = t2 & 0x3f03fff;
182   t3 >>= 8;
183   state->r4 = t3 & 0x00fffff;
184 
185   state->s1 = state->r1 * 5;
186   state->s2 = state->r2 * 5;
187   state->s3 = state->r3 * 5;
188   state->s4 = state->r4 * 5;
189 
190   // init state
191   state->h0 = 0;
192   state->h1 = 0;
193   state->h2 = 0;
194   state->h3 = 0;
195   state->h4 = 0;
196 
197   state->buf_used = 0;
198   OPENSSL_memcpy(state->key, key + 16, sizeof(state->key));
199 }
200 
CRYPTO_poly1305_update(poly1305_state * statep,const uint8_t * in,size_t in_len)201 void CRYPTO_poly1305_update(poly1305_state *statep, const uint8_t *in,
202                             size_t in_len) {
203   unsigned int i;
204   struct poly1305_state_st *state = poly1305_aligned_state(statep);
205 
206 #if defined(OPENSSL_POLY1305_NEON)
207   if (CRYPTO_is_NEON_capable()) {
208     CRYPTO_poly1305_update_neon(statep, in, in_len);
209     return;
210   }
211 #endif
212 
213   if (state->buf_used) {
214     unsigned todo = 16 - state->buf_used;
215     if (todo > in_len) {
216       todo = (unsigned)in_len;
217     }
218     for (i = 0; i < todo; i++) {
219       state->buf[state->buf_used + i] = in[i];
220     }
221     state->buf_used += todo;
222     in_len -= todo;
223     in += todo;
224 
225     if (state->buf_used == 16) {
226       poly1305_update(state, state->buf, 16);
227       state->buf_used = 0;
228     }
229   }
230 
231   if (in_len >= 16) {
232     size_t todo = in_len & ~0xf;
233     poly1305_update(state, in, todo);
234     in += todo;
235     in_len &= 0xf;
236   }
237 
238   if (in_len) {
239     for (i = 0; i < in_len; i++) {
240       state->buf[i] = in[i];
241     }
242     state->buf_used = (unsigned)in_len;
243   }
244 }
245 
CRYPTO_poly1305_finish(poly1305_state * statep,uint8_t mac[16])246 void CRYPTO_poly1305_finish(poly1305_state *statep, uint8_t mac[16]) {
247   struct poly1305_state_st *state = poly1305_aligned_state(statep);
248   uint64_t f0, f1, f2, f3;
249   uint32_t g0, g1, g2, g3, g4;
250   uint32_t b, nb;
251 
252 #if defined(OPENSSL_POLY1305_NEON)
253   if (CRYPTO_is_NEON_capable()) {
254     CRYPTO_poly1305_finish_neon(statep, mac);
255     return;
256   }
257 #endif
258 
259   if (state->buf_used) {
260     poly1305_update(state, state->buf, state->buf_used);
261   }
262 
263   b = state->h0 >> 26;
264   state->h0 = state->h0 & 0x3ffffff;
265   state->h1 += b;
266   b = state->h1 >> 26;
267   state->h1 = state->h1 & 0x3ffffff;
268   state->h2 += b;
269   b = state->h2 >> 26;
270   state->h2 = state->h2 & 0x3ffffff;
271   state->h3 += b;
272   b = state->h3 >> 26;
273   state->h3 = state->h3 & 0x3ffffff;
274   state->h4 += b;
275   b = state->h4 >> 26;
276   state->h4 = state->h4 & 0x3ffffff;
277   state->h0 += b * 5;
278 
279   g0 = state->h0 + 5;
280   b = g0 >> 26;
281   g0 &= 0x3ffffff;
282   g1 = state->h1 + b;
283   b = g1 >> 26;
284   g1 &= 0x3ffffff;
285   g2 = state->h2 + b;
286   b = g2 >> 26;
287   g2 &= 0x3ffffff;
288   g3 = state->h3 + b;
289   b = g3 >> 26;
290   g3 &= 0x3ffffff;
291   g4 = state->h4 + b - (1 << 26);
292 
293   b = (g4 >> 31) - 1;
294   nb = ~b;
295   state->h0 = (state->h0 & nb) | (g0 & b);
296   state->h1 = (state->h1 & nb) | (g1 & b);
297   state->h2 = (state->h2 & nb) | (g2 & b);
298   state->h3 = (state->h3 & nb) | (g3 & b);
299   state->h4 = (state->h4 & nb) | (g4 & b);
300 
301   f0 = ((state->h0) | (state->h1 << 26)) + (uint64_t)U8TO32_LE(&state->key[0]);
302   f1 = ((state->h1 >> 6) | (state->h2 << 20)) +
303        (uint64_t)U8TO32_LE(&state->key[4]);
304   f2 = ((state->h2 >> 12) | (state->h3 << 14)) +
305        (uint64_t)U8TO32_LE(&state->key[8]);
306   f3 = ((state->h3 >> 18) | (state->h4 << 8)) +
307        (uint64_t)U8TO32_LE(&state->key[12]);
308 
309   U32TO8_LE(&mac[0], f0);
310   f1 += (f0 >> 32);
311   U32TO8_LE(&mac[4], f1);
312   f2 += (f1 >> 32);
313   U32TO8_LE(&mac[8], f2);
314   f3 += (f2 >> 32);
315   U32TO8_LE(&mac[12], f3);
316 }
317 
318 #endif  // !BORINGSSL_HAS_UINT128 || !OPENSSL_X86_64
319