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(OPENSSL_WINDOWS) || !defined(OPENSSL_X86_64) 30 31 /* We can assume little-endian. */ 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 38 static void U32TO8_LE(uint8_t *m, uint32_t v) { 39 OPENSSL_memcpy(m, &v, sizeof(v)); 40 } 41 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 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. */ 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 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_ARM) && !defined(OPENSSL_NO_ASM) 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 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_ARM) && !defined(OPENSSL_NO_ASM) 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 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_ARM) && !defined(OPENSSL_NO_ASM) 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 /* OPENSSL_WINDOWS || !OPENSSL_X86_64 */ 319
