git.tinc-vpn.org Git - tinc/blob - src/chacha-poly1305/poly1305.c

   1 /*
   2 poly1305 implementation using 32 bit * 32 bit = 64 bit multiplication and 64 bit addition
   3 public domain
   4 */
   5
   6 #include "poly1305.h"
   7
   8 #if (USE_UNALIGNED == 1)
   9 #define U8TO32(p) \
  10         (*((uint32_t *)(p)))
  11 #define U32TO8(p, v) \
  12         do { \
  13                 *((uint32_t *)(p)) = v; \
  14         } while (0)
  15 #else
  16 /* interpret four 8 bit unsigned integers as a 32 bit unsigned integer in little endian */
  17 static uint32_t
  18 U8TO32(const unsigned char *p) {
  19         return
  20                 (((uint32_t)(p[0] & 0xff)) |
  21                  ((uint32_t)(p[1] & 0xff) <<  8) |
  22                  ((uint32_t)(p[2] & 0xff) << 16) |
  23                  ((uint32_t)(p[3] & 0xff) << 24));
  24 }
  25
  26 /* store a 32 bit unsigned integer as four 8 bit unsigned integers in little endian */
  27 static void
  28 U32TO8(unsigned char *p, uint32_t v) {
  29         p[0] = (v) & 0xff;
  30         p[1] = (v >>  8) & 0xff;
  31         p[2] = (v >> 16) & 0xff;
  32         p[3] = (v >> 24) & 0xff;
  33 }
  34 #endif
  35
  36 void
  37 poly1305_init(struct poly1305_context *st, const unsigned char key[32]) {
  38         /* r &= 0xffffffc0ffffffc0ffffffc0fffffff */
  39         st->r[0] = (U8TO32(&key[ 0])) & 0x3ffffff;
  40         st->r[1] = (U8TO32(&key[ 3]) >> 2) & 0x3ffff03;
  41         st->r[2] = (U8TO32(&key[ 6]) >> 4) & 0x3ffc0ff;
  42         st->r[3] = (U8TO32(&key[ 9]) >> 6) & 0x3f03fff;
  43         st->r[4] = (U8TO32(&key[12]) >> 8) & 0x00fffff;
  44
  45         /* h = 0 */
  46         st->h[0] = 0;
  47         st->h[1] = 0;
  48         st->h[2] = 0;
  49         st->h[3] = 0;
  50         st->h[4] = 0;
  51
  52         /* save pad for later */
  53         st->pad[0] = U8TO32(&key[16]);
  54         st->pad[1] = U8TO32(&key[20]);
  55         st->pad[2] = U8TO32(&key[24]);
  56         st->pad[3] = U8TO32(&key[28]);
  57
  58         st->leftover = 0;
  59         st->final = 0;
  60 }
  61
  62 static void
  63 poly1305_blocks(struct poly1305_context *st, const unsigned char *m, size_t bytes) {
  64         const uint32_t hibit = (st->final) ? 0 : (1 << 24); /* 1 << 128 */
  65         uint32_t r0, r1, r2, r3, r4;
  66         uint32_t s1, s2, s3, s4;
  67         uint32_t h0, h1, h2, h3, h4;
  68         uint64_t d0, d1, d2, d3, d4;
  69         uint32_t c;
  70
  71         r0 = st->r[0];
  72         r1 = st->r[1];
  73         r2 = st->r[2];
  74         r3 = st->r[3];
  75         r4 = st->r[4];
  76
  77         s1 = r1 * 5;
  78         s2 = r2 * 5;
  79         s3 = r3 * 5;
  80         s4 = r4 * 5;
  81
  82         h0 = st->h[0];
  83         h1 = st->h[1];
  84         h2 = st->h[2];
  85         h3 = st->h[3];
  86         h4 = st->h[4];
  87
  88         while(bytes >= POLY1305_BLOCK_SIZE) {
  89                 /* h += m[i] */
  90                 h0 += (U8TO32(m + 0)) & 0x3ffffff;
  91                 h1 += (U8TO32(m + 3) >> 2) & 0x3ffffff;
  92                 h2 += (U8TO32(m + 6) >> 4) & 0x3ffffff;
  93                 h3 += (U8TO32(m + 9) >> 6) & 0x3ffffff;
  94                 h4 += (U8TO32(m + 12) >> 8) | hibit;
  95
  96                 /* h *= r */
  97                 d0 = ((uint64_t)h0 * r0) + ((uint64_t)h1 * s4) + ((uint64_t)h2 * s3) + ((uint64_t)h3 * s2) + ((uint64_t)h4 * s1);
  98                 d1 = ((uint64_t)h0 * r1) + ((uint64_t)h1 * r0) + ((uint64_t)h2 * s4) + ((uint64_t)h3 * s3) + ((uint64_t)h4 * s2);
  99                 d2 = ((uint64_t)h0 * r2) + ((uint64_t)h1 * r1) + ((uint64_t)h2 * r0) + ((uint64_t)h3 * s4) + ((uint64_t)h4 * s3);
 100                 d3 = ((uint64_t)h0 * r3) + ((uint64_t)h1 * r2) + ((uint64_t)h2 * r1) + ((uint64_t)h3 * r0) + ((uint64_t)h4 * s4);
 101                 d4 = ((uint64_t)h0 * r4) + ((uint64_t)h1 * r3) + ((uint64_t)h2 * r2) + ((uint64_t)h3 * r1) + ((uint64_t)h4 * r0);
 102
 103                 /* (partial) h %= p */
 104                 c = (uint32_t)(d0 >> 26);
 105                 h0 = (uint32_t)d0 & 0x3ffffff;
 106                 d1 += c;
 107                 c = (uint32_t)(d1 >> 26);
 108                 h1 = (uint32_t)d1 & 0x3ffffff;
 109                 d2 += c;
 110                 c = (uint32_t)(d2 >> 26);
 111                 h2 = (uint32_t)d2 & 0x3ffffff;
 112                 d3 += c;
 113                 c = (uint32_t)(d3 >> 26);
 114                 h3 = (uint32_t)d3 & 0x3ffffff;
 115                 d4 += c;
 116                 c = (uint32_t)(d4 >> 26);
 117                 h4 = (uint32_t)d4 & 0x3ffffff;
 118                 h0 += c * 5;
 119                 c = (h0 >> 26);
 120                 h0 =           h0 & 0x3ffffff;
 121                 h1 += c;
 122
 123                 m += POLY1305_BLOCK_SIZE;
 124                 bytes -= POLY1305_BLOCK_SIZE;
 125         }
 126
 127         st->h[0] = h0;
 128         st->h[1] = h1;
 129         st->h[2] = h2;
 130         st->h[3] = h3;
 131         st->h[4] = h4;
 132 }
 133
 134 void
 135 poly1305_finish(struct poly1305_context *st, unsigned char mac[16]) {
 136         uint32_t h0, h1, h2, h3, h4, c;
 137         uint32_t g0, g1, g2, g3, g4;
 138         uint64_t f;
 139         uint32_t mask;
 140
 141         /* process the remaining block */
 142         if(st->leftover) {
 143                 size_t i = st->leftover;
 144                 st->buffer[i++] = 1;
 145
 146                 for(; i < POLY1305_BLOCK_SIZE; i++) {
 147                         st->buffer[i] = 0;
 148                 }
 149
 150                 st->final = 1;
 151                 poly1305_blocks(st, st->buffer, POLY1305_BLOCK_SIZE);
 152         }
 153
 154         /* fully carry h */
 155         h0 = st->h[0];
 156         h1 = st->h[1];
 157         h2 = st->h[2];
 158         h3 = st->h[3];
 159         h4 = st->h[4];
 160
 161         c = h1 >> 26;
 162         h1 = h1 & 0x3ffffff;
 163         h2 +=     c;
 164         c = h2 >> 26;
 165         h2 = h2 & 0x3ffffff;
 166         h3 +=     c;
 167         c = h3 >> 26;
 168         h3 = h3 & 0x3ffffff;
 169         h4 +=     c;
 170         c = h4 >> 26;
 171         h4 = h4 & 0x3ffffff;
 172         h0 += c * 5;
 173         c = h0 >> 26;
 174         h0 = h0 & 0x3ffffff;
 175         h1 +=     c;
 176
 177         /* compute h + -p */
 178         g0 = h0 + 5;
 179         c = g0 >> 26;
 180         g0 &= 0x3ffffff;
 181         g1 = h1 + c;
 182         c = g1 >> 26;
 183         g1 &= 0x3ffffff;
 184         g2 = h2 + c;
 185         c = g2 >> 26;
 186         g2 &= 0x3ffffff;
 187         g3 = h3 + c;
 188         c = g3 >> 26;
 189         g3 &= 0x3ffffff;
 190         g4 = h4 + c - (1 << 26);
 191
 192         /* select h if h < p, or h + -p if h >= p */
 193         mask = (g4 >> ((sizeof(uint32_t) * 8) - 1)) - 1;
 194         g0 &= mask;
 195         g1 &= mask;
 196         g2 &= mask;
 197         g3 &= mask;
 198         g4 &= mask;
 199         mask = ~mask;
 200         h0 = (h0 & mask) | g0;
 201         h1 = (h1 & mask) | g1;
 202         h2 = (h2 & mask) | g2;
 203         h3 = (h3 & mask) | g3;
 204         h4 = (h4 & mask) | g4;
 205
 206         /* h = h % (2^128) */
 207         h0 = ((h0) | (h1 << 26)) & 0xffffffff;
 208         h1 = ((h1 >>  6) | (h2 << 20)) & 0xffffffff;
 209         h2 = ((h2 >> 12) | (h3 << 14)) & 0xffffffff;
 210         h3 = ((h3 >> 18) | (h4 <<  8)) & 0xffffffff;
 211
 212         /* mac = (h + pad) % (2^128) */
 213         f = (uint64_t)h0 + st->pad[0]            ;
 214         h0 = (uint32_t)f;
 215         f = (uint64_t)h1 + st->pad[1] + (f >> 32);
 216         h1 = (uint32_t)f;
 217         f = (uint64_t)h2 + st->pad[2] + (f >> 32);
 218         h2 = (uint32_t)f;
 219         f = (uint64_t)h3 + st->pad[3] + (f >> 32);
 220         h3 = (uint32_t)f;
 221
 222         U32TO8(mac +  0, h0);
 223         U32TO8(mac +  4, h1);
 224         U32TO8(mac +  8, h2);
 225         U32TO8(mac + 12, h3);
 226
 227         /* zero out the state */
 228         st->h[0] = 0;
 229         st->h[1] = 0;
 230         st->h[2] = 0;
 231         st->h[3] = 0;
 232         st->h[4] = 0;
 233         st->r[0] = 0;
 234         st->r[1] = 0;
 235         st->r[2] = 0;
 236         st->r[3] = 0;
 237         st->r[4] = 0;
 238         st->pad[0] = 0;
 239         st->pad[1] = 0;
 240         st->pad[2] = 0;
 241         st->pad[3] = 0;
 242 }
 243
 244
 245 void
 246 poly1305_update(struct poly1305_context *st, const unsigned char *m, size_t bytes) {
 247         size_t i;
 248
 249         /* handle leftover */
 250         if(st->leftover) {
 251                 size_t want = (POLY1305_BLOCK_SIZE - st->leftover);
 252
 253                 if(want > bytes) {
 254                         want = bytes;
 255                 }
 256
 257                 for(i = 0; i < want; i++) {
 258                         st->buffer[st->leftover + i] = m[i];
 259                 }
 260
 261                 bytes -= want;
 262                 m += want;
 263                 st->leftover += want;
 264
 265                 if(st->leftover < POLY1305_BLOCK_SIZE) {
 266                         return;
 267                 }
 268
 269                 poly1305_blocks(st, st->buffer, POLY1305_BLOCK_SIZE);
 270                 st->leftover = 0;
 271         }
 272
 273         /* process full blocks */
 274         if(bytes >= POLY1305_BLOCK_SIZE) {
 275                 size_t want = (bytes & ~(POLY1305_BLOCK_SIZE - 1));
 276                 poly1305_blocks(st, m, want);
 277                 m += want;
 278                 bytes -= want;
 279         }
 280
 281         /* store leftover */
 282         if(bytes) {
 283 #if (USE_MEMCPY == 1)
 284                 memcpy(st->buffer + st->leftover, m, bytes);
 285 #else
 286
 287                 for(i = 0; i < bytes; i++) {
 288                         st->buffer[st->leftover + i] = m[i];
 289                 }
 290
 291 #endif
 292                 st->leftover += bytes;
 293         }
 294 }
 295
 296 void
 297 poly1305_auth(unsigned char mac[16], const unsigned char *m, size_t bytes, const unsigned char key[32]) {
 298         struct poly1305_context ctx;
 299         poly1305_init(&ctx, key);
 300         poly1305_update(&ctx, m, bytes);
 301         poly1305_finish(&ctx, mac);
 302 }