src/third_party/openssl/openssl/crypto/poly1305/poly1305.c

   1 /* ====================================================================
   2  * Copyright (c) 2011-2013 The OpenSSL Project.  All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  *
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in
  13  *    the documentation and/or other materials provided with the
  14  *    distribution.
  15  *
  16  * 3. All advertising materials mentioning features or use of this
  17  *    software must display the following acknowledgment:
  18  *    "This product includes software developed by the OpenSSL Project
  19  *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
  20  *
  21  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  22  *    endorse or promote products derived from this software without
  23  *    prior written permission. For written permission, please contact
  24  *    licensing@OpenSSL.org.
  25  *
  26  * 5. Products derived from this software may not be called "OpenSSL"
  27  *    nor may "OpenSSL" appear in their names without prior written
  28  *    permission of the OpenSSL Project.
  29  *
  30  * 6. Redistributions of any form whatsoever must retain the following
  31  *    acknowledgment:
  32  *    "This product includes software developed by the OpenSSL Project
  33  *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
  34  *
  35  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  36  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  37  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  38  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  39  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  40  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  41  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  42  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  43  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  44  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  45  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  46  * OF THE POSSIBILITY OF SUCH DAMAGE.
  47  * ====================================================================
  48  */
  49
  50 /* This implementation of poly1305 is by Andrew Moon
  51  * (https://github.com/floodyberry/poly1305-donna) and released as public
  52  * domain. */
  53
  54 #include <string.h>
  55 #include <stdint.h>
  56 #include <openssl/opensslconf.h>
  57
  58 #if !defined(OPENSSL_NO_POLY1305)
  59
  60 #include <openssl/poly1305.h>
  61 #include <openssl/crypto.h>
  62
  63 #if defined(__i386) || defined(__i386__) || defined(__x86_64) || defined(__x86_64__)
  64 /* We can assume little-endian. */
  65 static uint32_t U8TO32_LE(const unsigned char *m)
  66         {
  67         uint32_t r;
  68         memcpy(&r, m, sizeof(r));
  69         return r;
  70         }
  71
  72 static void U32TO8_LE(unsigned char *m, uint32_t v)
  73         {
  74         memcpy(m, &v, sizeof(v));
  75         }
  76 #else
  77 static uint32_t U8TO32_LE(const unsigned char *m)
  78         {
  79         return (uint32_t)m[0] |
  80                (uint32_t)m[1] << 8 |
  81                (uint32_t)m[2] << 16 |
  82                (uint32_t)m[3] << 24;
  83         }
  84
  85 static void U32TO8_LE(unsigned char *m, uint32_t v)
  86         {
  87         m[0] = v;
  88         m[1] = v >> 8;
  89         m[2] = v >> 16;
  90         m[3] = v >> 24;
  91         }
  92 #endif
  93
  94 #if __arm__
  95 void CRYPTO_poly1305_init_neon(poly1305_state* state,
  96                                const unsigned char key[32]);
  97
  98 void CRYPTO_poly1305_update_neon(poly1305_state* state,
  99                                  const unsigned char *in,
 100                                  size_t in_len);
 101
 102 void CRYPTO_poly1305_finish_neon(poly1305_state* state, unsigned char mac[16]);
 103 #endif
 104
 105 static uint64_t
 106 mul32x32_64(uint32_t a, uint32_t b)
 107         {
 108         return (uint64_t)a * b;
 109         }
 110
 111
 112 struct poly1305_state_st
 113         {
 114         uint32_t r0,r1,r2,r3,r4;
 115         uint32_t s1,s2,s3,s4;
 116         uint32_t h0,h1,h2,h3,h4;
 117         unsigned char buf[16];
 118         unsigned int buf_used;
 119         unsigned char key[16];
 120         };
 121
 122 /* poly1305_blocks updates |state| given some amount of input data. This
 123  * function may only be called with a |len| that is not a multiple of 16 at the
 124  * end of the data. Otherwise the input must be buffered into 16 byte blocks.
 125  * */
 126 static void poly1305_update(struct poly1305_state_st *state,
 127                             const unsigned char *in, size_t len)
 128         {
 129         uint32_t t0,t1,t2,t3;
 130         uint64_t t[5];
 131         uint32_t b;
 132         uint64_t c;
 133         size_t j;
 134         unsigned char mp[16];
 135
 136         if (len < 16)
 137                 goto poly1305_donna_atmost15bytes;
 138
 139 poly1305_donna_16bytes:
 140         t0 = U8TO32_LE(in);
 141         t1 = U8TO32_LE(in+4);
 142         t2 = U8TO32_LE(in+8);
 143         t3 = U8TO32_LE(in+12);
 144
 145         in += 16;
 146         len -= 16;
 147
 148         state->h0 += t0 & 0x3ffffff;
 149         state->h1 += ((((uint64_t)t1 << 32) | t0) >> 26) & 0x3ffffff;
 150         state->h2 += ((((uint64_t)t2 << 32) | t1) >> 20) & 0x3ffffff;
 151         state->h3 += ((((uint64_t)t3 << 32) | t2) >> 14) & 0x3ffffff;
 152         state->h4 += (t3 >> 8) | (1 << 24);
 153
 154 poly1305_donna_mul:
 155         t[0] = mul32x32_64(state->h0,state->r0) +
 156                mul32x32_64(state->h1,state->s4) +
 157                mul32x32_64(state->h2,state->s3) +
 158                mul32x32_64(state->h3,state->s2) +
 159                mul32x32_64(state->h4,state->s1);
 160         t[1] = mul32x32_64(state->h0,state->r1) +
 161                mul32x32_64(state->h1,state->r0) +
 162                mul32x32_64(state->h2,state->s4) +
 163                mul32x32_64(state->h3,state->s3) +
 164                mul32x32_64(state->h4,state->s2);
 165         t[2] = mul32x32_64(state->h0,state->r2) +
 166                mul32x32_64(state->h1,state->r1) +
 167                mul32x32_64(state->h2,state->r0) +
 168                mul32x32_64(state->h3,state->s4) +
 169                mul32x32_64(state->h4,state->s3);
 170         t[3] = mul32x32_64(state->h0,state->r3) +
 171                mul32x32_64(state->h1,state->r2) +
 172                mul32x32_64(state->h2,state->r1) +
 173                mul32x32_64(state->h3,state->r0) +
 174                mul32x32_64(state->h4,state->s4);
 175         t[4] = mul32x32_64(state->h0,state->r4) +
 176                mul32x32_64(state->h1,state->r3) +
 177                mul32x32_64(state->h2,state->r2) +
 178                mul32x32_64(state->h3,state->r1) +
 179                mul32x32_64(state->h4,state->r0);
 180
 181                    state->h0 = (uint32_t)t[0] & 0x3ffffff; c =           (t[0] >> 26);
 182         t[1] += c; state->h1 = (uint32_t)t[1] & 0x3ffffff; b = (uint32_t)(t[1] >> 26);
 183         t[2] += b; state->h2 = (uint32_t)t[2] & 0x3ffffff; b = (uint32_t)(t[2] >> 26);
 184         t[3] += b; state->h3 = (uint32_t)t[3] & 0x3ffffff; b = (uint32_t)(t[3] >> 26);
 185         t[4] += b; state->h4 = (uint32_t)t[4] & 0x3ffffff; b = (uint32_t)(t[4] >> 26);
 186         state->h0 += b * 5;
 187
 188         if (len >= 16)
 189                 goto poly1305_donna_16bytes;
 190
 191         /* final bytes */
 192 poly1305_donna_atmost15bytes:
 193         if (!len)
 194                 return;
 195
 196         for (j = 0; j < len; j++)
 197                 mp[j] = in[j];
 198         mp[j++] = 1;
 199         for (; j < 16; j++)
 200                 mp[j] = 0;
 201         len = 0;
 202
 203         t0 = U8TO32_LE(mp+0);
 204         t1 = U8TO32_LE(mp+4);
 205         t2 = U8TO32_LE(mp+8);
 206         t3 = U8TO32_LE(mp+12);
 207
 208         state->h0 += t0 & 0x3ffffff;
 209         state->h1 += ((((uint64_t)t1 << 32) | t0) >> 26) & 0x3ffffff;
 210         state->h2 += ((((uint64_t)t2 << 32) | t1) >> 20) & 0x3ffffff;
 211         state->h3 += ((((uint64_t)t3 << 32) | t2) >> 14) & 0x3ffffff;
 212         state->h4 += (t3 >> 8);
 213
 214         goto poly1305_donna_mul;
 215         }
 216
 217 void CRYPTO_poly1305_init(poly1305_state *statep, const unsigned char key[32])
 218         {
 219         struct poly1305_state_st *state = (struct poly1305_state_st*) statep;
 220         uint32_t t0,t1,t2,t3;
 221
 222 #if 0 /* Disabled because of crbug.com/341598 */
 223 #if __arm__
 224         if (CRYPTO_is_NEON_capable())
 225                 {
 226                 CRYPTO_poly1305_init_neon(statep, key);
 227                 return;
 228                 }
 229 #endif
 230 #endif
 231
 232         t0 = U8TO32_LE(key+0);
 233         t1 = U8TO32_LE(key+4);
 234         t2 = U8TO32_LE(key+8);
 235         t3 = U8TO32_LE(key+12);
 236
 237         /* precompute multipliers */
 238         state->r0 = t0 & 0x3ffffff; t0 >>= 26; t0 |= t1 << 6;
 239         state->r1 = t0 & 0x3ffff03; t1 >>= 20; t1 |= t2 << 12;
 240         state->r2 = t1 & 0x3ffc0ff; t2 >>= 14; t2 |= t3 << 18;
 241         state->r3 = t2 & 0x3f03fff; t3 >>= 8;
 242         state->r4 = t3 & 0x00fffff;
 243
 244         state->s1 = state->r1 * 5;
 245         state->s2 = state->r2 * 5;
 246         state->s3 = state->r3 * 5;
 247         state->s4 = state->r4 * 5;
 248
 249         /* init state */
 250         state->h0 = 0;
 251         state->h1 = 0;
 252         state->h2 = 0;
 253         state->h3 = 0;
 254         state->h4 = 0;
 255
 256         state->buf_used = 0;
 257         memcpy(state->key, key + 16, sizeof(state->key));
 258         }
 259
 260 void CRYPTO_poly1305_update(poly1305_state *statep, const unsigned char *in,
 261                      size_t in_len)
 262         {
 263         unsigned int i;
 264         struct poly1305_state_st *state = (struct poly1305_state_st*) statep;
 265
 266 #if 0 /* Disabled because of crbug.com/341598 */
 267 #if __arm__
 268         if (CRYPTO_is_NEON_capable())
 269                 {
 270                 CRYPTO_poly1305_update_neon(statep, in, in_len);
 271                 return;
 272                 }
 273 #endif
 274 #endif
 275
 276         if (state->buf_used)
 277                 {
 278                 unsigned int todo = 16 - state->buf_used;
 279                 if (todo > in_len)
 280                         todo = in_len;
 281                 for (i = 0; i < todo; i++)
 282                         state->buf[state->buf_used + i] = in[i];
 283                 state->buf_used += todo;
 284                 in_len -= todo;
 285                 in += todo;
 286
 287                 if (state->buf_used == 16)
 288                         {
 289                         poly1305_update(state, state->buf, 16);
 290                         state->buf_used = 0;
 291                         }
 292                 }
 293
 294         if (in_len >= 16)
 295                 {
 296                 size_t todo = in_len & ~0xf;
 297                 poly1305_update(state, in, todo);
 298                 in += todo;
 299                 in_len &= 0xf;
 300                 }
 301
 302         if (in_len)
 303                 {
 304                 for (i = 0; i < in_len; i++)
 305                         state->buf[i] = in[i];
 306                 state->buf_used = in_len;
 307                 }
 308         }
 309
 310 void CRYPTO_poly1305_finish(poly1305_state *statep, unsigned char mac[16])
 311         {
 312         struct poly1305_state_st *state = (struct poly1305_state_st*) statep;
 313         uint64_t f0,f1,f2,f3;
 314         uint32_t g0,g1,g2,g3,g4;
 315         uint32_t b, nb;
 316
 317 #if 0 /* Disabled because of crbug.com/341598 */
 318 #if __arm__
 319         if (CRYPTO_is_NEON_capable())
 320                 {
 321                 CRYPTO_poly1305_finish_neon(statep, mac);
 322                 return;
 323                 }
 324 #endif
 325 #endif
 326
 327         if (state->buf_used)
 328                 poly1305_update(state, state->buf, state->buf_used);
 329
 330                             b = state->h0 >> 26; state->h0 = state->h0 & 0x3ffffff;
 331         state->h1 +=     b; b = state->h1 >> 26; state->h1 = state->h1 & 0x3ffffff;
 332         state->h2 +=     b; b = state->h2 >> 26; state->h2 = state->h2 & 0x3ffffff;
 333         state->h3 +=     b; b = state->h3 >> 26; state->h3 = state->h3 & 0x3ffffff;
 334         state->h4 +=     b; b = state->h4 >> 26; state->h4 = state->h4 & 0x3ffffff;
 335         state->h0 += b * 5;
 336
 337         g0 = state->h0 + 5; b = g0 >> 26; g0 &= 0x3ffffff;
 338         g1 = state->h1 + b; b = g1 >> 26; g1 &= 0x3ffffff;
 339         g2 = state->h2 + b; b = g2 >> 26; g2 &= 0x3ffffff;
 340         g3 = state->h3 + b; b = g3 >> 26; g3 &= 0x3ffffff;
 341         g4 = state->h4 + b - (1 << 26);
 342
 343         b = (g4 >> 31) - 1;
 344         nb = ~b;
 345         state->h0 = (state->h0 & nb) | (g0 & b);
 346         state->h1 = (state->h1 & nb) | (g1 & b);
 347         state->h2 = (state->h2 & nb) | (g2 & b);
 348         state->h3 = (state->h3 & nb) | (g3 & b);
 349         state->h4 = (state->h4 & nb) | (g4 & b);
 350
 351         f0 = ((state->h0      ) | (state->h1 << 26)) + (uint64_t)U8TO32_LE(&state->key[0]);
 352         f1 = ((state->h1 >>  6) | (state->h2 << 20)) + (uint64_t)U8TO32_LE(&state->key[4]);
 353         f2 = ((state->h2 >> 12) | (state->h3 << 14)) + (uint64_t)U8TO32_LE(&state->key[8]);
 354         f3 = ((state->h3 >> 18) | (state->h4 <<  8)) + (uint64_t)U8TO32_LE(&state->key[12]);
 355
 356         U32TO8_LE(&mac[ 0], f0); f1 += (f0 >> 32);
 357         U32TO8_LE(&mac[ 4], f1); f2 += (f1 >> 32);
 358         U32TO8_LE(&mac[ 8], f2); f3 += (f2 >> 32);
 359         U32TO8_LE(&mac[12], f3);
 360         }
 361
 362 #endif  /* !OPENSSL_NO_POLY1305 */