gerrit.fd Code Review - trex.git/blob

   1 /*
   2         poly1305 implementation using 64 bit * 64 bit = 128 bit multiplication and 128 bit addition
   3 */
   4
   5 #define POLY1305_IMPLEMENTATION_NAME "donna64"
   6
   7 #if defined(__SIZEOF_INT128__)
   8 typedef unsigned __int128 uint128_t;
   9 #else
  10 typedef unsigned uint128_t __attribute__((mode(TI)));
  11 #endif
  12
  13 #define MUL(out, x, y) out = ((uint128_t)x * y)
  14 #define ADD(out, in) out += in
  15 #define ADDLO(out, in) out += in
  16 #define SHR(in, shift) (unsigned long long)(in >> (shift))
  17 #define LO(in) (unsigned long long)(in)
  18
  19 #define POLY1305_NOINLINE __attribute__((noinline))
  20
  21 #define poly1305_block_size 16
  22
  23 /* 17 + sizeof(unsigned long long) + 8*sizeof(unsigned long long) */
  24 typedef struct poly1305_state_internal_t {
  25         unsigned long long r[3];
  26         unsigned long long h[3];
  27         unsigned long long pad[2];
  28         unsigned long long leftover;
  29         unsigned char buffer[poly1305_block_size];
  30         unsigned char final;
  31 } poly1305_state_internal_t;
  32
  33 /* interpret eight 8 bit unsigned integers as a 64 bit unsigned integer in little endian */
  34 static unsigned long long
  35 U8TO64(const unsigned char *p) {
  36         return
  37            (((unsigned long long)(p[0] & 0xff)      ) |
  38             ((unsigned long long)(p[1] & 0xff) <<  8) |
  39             ((unsigned long long)(p[2] & 0xff) << 16) |
  40             ((unsigned long long)(p[3] & 0xff) << 24) |
  41             ((unsigned long long)(p[4] & 0xff) << 32) |
  42             ((unsigned long long)(p[5] & 0xff) << 40) |
  43             ((unsigned long long)(p[6] & 0xff) << 48) |
  44             ((unsigned long long)(p[7] & 0xff) << 56));
  45 }
  46
  47 /* store a 64 bit unsigned integer as eight 8 bit unsigned integers in little endian */
  48 static void
  49 U64TO8(unsigned char *p, unsigned long long v) {
  50         p[0] = (v      ) & 0xff;
  51         p[1] = (v >>  8) & 0xff;
  52         p[2] = (v >> 16) & 0xff;
  53         p[3] = (v >> 24) & 0xff;
  54         p[4] = (v >> 32) & 0xff;
  55         p[5] = (v >> 40) & 0xff;
  56         p[6] = (v >> 48) & 0xff;
  57         p[7] = (v >> 56) & 0xff;
  58 }
  59
  60 static void
  61 poly1305_init(poly1305_context *ctx, const unsigned char key[32]) {
  62         poly1305_state_internal_t *st = (poly1305_state_internal_t *)(void *)ctx;
  63         unsigned long long t0,t1;
  64
  65         /* r &= 0xffffffc0ffffffc0ffffffc0fffffff */
  66         t0 = U8TO64(&key[0]);
  67         t1 = U8TO64(&key[8]);
  68
  69         st->r[0] = ( t0                    ) & 0xffc0fffffff;
  70         st->r[1] = ((t0 >> 44) | (t1 << 20)) & 0xfffffc0ffff;
  71         st->r[2] = ((t1 >> 24)             ) & 0x00ffffffc0f;
  72
  73         /* h = 0 */
  74         st->h[0] = 0;
  75         st->h[1] = 0;
  76         st->h[2] = 0;
  77
  78         /* save pad for later */
  79         st->pad[0] = U8TO64(&key[16]);
  80         st->pad[1] = U8TO64(&key[24]);
  81
  82         st->leftover = 0;
  83         st->final = 0;
  84 }
  85
  86 static void
  87 poly1305_blocks(poly1305_state_internal_t *st, const unsigned char *m, unsigned long long bytes) {
  88         const unsigned long long hibit = (st->final) ? 0 : ((unsigned long long)1 << 40); /* 1 << 128 */
  89         unsigned long long r0,r1,r2;
  90         unsigned long long s1,s2;
  91         unsigned long long h0,h1,h2;
  92         unsigned long long c;
  93         uint128_t d0,d1,d2,d;
  94
  95         r0 = st->r[0];
  96         r1 = st->r[1];
  97         r2 = st->r[2];
  98
  99         h0 = st->h[0];
 100         h1 = st->h[1];
 101         h2 = st->h[2];
 102
 103         s1 = r1 * (5 << 2);
 104         s2 = r2 * (5 << 2);
 105
 106         while (bytes >= poly1305_block_size) {
 107                 unsigned long long t0,t1;
 108
 109                 /* h += m[i] */
 110                 t0 = U8TO64(&m[0]);
 111                 t1 = U8TO64(&m[8]);
 112
 113                 h0 += (( t0                    ) & 0xfffffffffff);
 114                 h1 += (((t0 >> 44) | (t1 << 20)) & 0xfffffffffff);
 115                 h2 += (((t1 >> 24)             ) & 0x3ffffffffff) | hibit;
 116
 117                 /* h *= r */
 118                 MUL(d0, h0, r0); MUL(d, h1, s2); ADD(d0, d); MUL(d, h2, s1); ADD(d0, d);
 119                 MUL(d1, h0, r1); MUL(d, h1, r0); ADD(d1, d); MUL(d, h2, s2); ADD(d1, d);
 120                 MUL(d2, h0, r2); MUL(d, h1, r1); ADD(d2, d); MUL(d, h2, r0); ADD(d2, d);
 121
 122                 /* (partial) h %= p */
 123                               c = SHR(d0, 44); h0 = LO(d0) & 0xfffffffffff;
 124                 ADDLO(d1, c); c = SHR(d1, 44); h1 = LO(d1) & 0xfffffffffff;
 125                 ADDLO(d2, c); c = SHR(d2, 42); h2 = LO(d2) & 0x3ffffffffff;
 126                 h0  += c * 5; c = (h0 >> 44);  h0 =    h0  & 0xfffffffffff;
 127                 h1  += c;
 128
 129                 m += poly1305_block_size;
 130                 bytes -= poly1305_block_size;
 131         }
 132
 133         st->h[0] = h0;
 134         st->h[1] = h1;
 135         st->h[2] = h2;
 136 }
 137
 138
 139 static POLY1305_NOINLINE void
 140 poly1305_finish(poly1305_context *ctx, unsigned char mac[16]) {
 141         poly1305_state_internal_t *st = (poly1305_state_internal_t *)(void *)ctx;
 142         unsigned long long h0,h1,h2,c;
 143         unsigned long long g0,g1,g2;
 144         unsigned long long t0,t1;
 145
 146         /* process the remaining block */
 147         if (st->leftover) {
 148                 unsigned long long i = st->leftover;
 149                 st->buffer[i] = 1;
 150                 for (i = i + 1; i < poly1305_block_size; i++)
 151                         st->buffer[i] = 0;
 152                 st->final = 1;
 153                 poly1305_blocks(st, st->buffer, poly1305_block_size);
 154         }
 155
 156         /* fully carry h */
 157         h0 = st->h[0];
 158         h1 = st->h[1];
 159         h2 = st->h[2];
 160
 161                      c = (h1 >> 44); h1 &= 0xfffffffffff;
 162         h2 += c;     c = (h2 >> 42); h2 &= 0x3ffffffffff;
 163         h0 += c * 5; c = (h0 >> 44); h0 &= 0xfffffffffff;
 164         h1 += c;         c = (h1 >> 44); h1 &= 0xfffffffffff;
 165         h2 += c;     c = (h2 >> 42); h2 &= 0x3ffffffffff;
 166         h0 += c * 5; c = (h0 >> 44); h0 &= 0xfffffffffff;
 167         h1 += c;
 168
 169         /* compute h + -p */
 170         g0 = h0 + 5; c = (g0 >> 44); g0 &= 0xfffffffffff;
 171         g1 = h1 + c; c = (g1 >> 44); g1 &= 0xfffffffffff;
 172         g2 = h2 + c - ((unsigned long long)1 << 42);
 173
 174         /* select h if h < p, or h + -p if h >= p */
 175         c = (g2 >> ((sizeof(unsigned long long) * 8) - 1)) - 1;
 176         g0 &= c;
 177         g1 &= c;
 178         g2 &= c;
 179         c = ~c;
 180         h0 = (h0 & c) | g0;
 181         h1 = (h1 & c) | g1;
 182         h2 = (h2 & c) | g2;
 183
 184         /* h = (h + pad) */
 185         t0 = st->pad[0];
 186         t1 = st->pad[1];
 187
 188         h0 += (( t0                    ) & 0xfffffffffff)    ; c = (h0 >> 44); h0 &= 0xfffffffffff;
 189         h1 += (((t0 >> 44) | (t1 << 20)) & 0xfffffffffff) + c; c = (h1 >> 44); h1 &= 0xfffffffffff;
 190         h2 += (((t1 >> 24)             ) & 0x3ffffffffff) + c;                 h2 &= 0x3ffffffffff;
 191
 192         /* mac = h % (2^128) */
 193         h0 = ((h0      ) | (h1 << 44));
 194         h1 = ((h1 >> 20) | (h2 << 24));
 195
 196         U64TO8(&mac[0], h0);
 197         U64TO8(&mac[8], h1);
 198
 199         /* zero out the state */
 200         sodium_memzero((void *)st, sizeof *st);
 201 }
 202