10ac341f1SConrad Meyer /*
20ac341f1SConrad Meyer poly1305 implementation using 32 bit * 32 bit = 64 bit multiplication
30ac341f1SConrad Meyer and 64 bit addition
40ac341f1SConrad Meyer */
50ac341f1SConrad Meyer
60ac341f1SConrad Meyer #if defined(_MSC_VER)
70ac341f1SConrad Meyer # define POLY1305_NOINLINE __declspec(noinline)
80ac341f1SConrad Meyer #elif defined(__clang__) || defined(__GNUC__)
90ac341f1SConrad Meyer # define POLY1305_NOINLINE __attribute__((noinline))
100ac341f1SConrad Meyer #else
110ac341f1SConrad Meyer # define POLY1305_NOINLINE
120ac341f1SConrad Meyer #endif
130ac341f1SConrad Meyer
140ac341f1SConrad Meyer #include "private/common.h"
150ac341f1SConrad Meyer
160ac341f1SConrad Meyer #define poly1305_block_size 16
170ac341f1SConrad Meyer
180ac341f1SConrad Meyer /* 17 + sizeof(unsigned long long) + 14*sizeof(unsigned long) */
190ac341f1SConrad Meyer typedef struct poly1305_state_internal_t {
200ac341f1SConrad Meyer unsigned long r[5];
210ac341f1SConrad Meyer unsigned long h[5];
220ac341f1SConrad Meyer unsigned long pad[4];
230ac341f1SConrad Meyer unsigned long long leftover;
240ac341f1SConrad Meyer unsigned char buffer[poly1305_block_size];
250ac341f1SConrad Meyer unsigned char final;
260ac341f1SConrad Meyer } poly1305_state_internal_t;
270ac341f1SConrad Meyer
280ac341f1SConrad Meyer static void
poly1305_init(poly1305_state_internal_t * st,const unsigned char key[32])290ac341f1SConrad Meyer poly1305_init(poly1305_state_internal_t *st, const unsigned char key[32])
300ac341f1SConrad Meyer {
310ac341f1SConrad Meyer /* r &= 0xffffffc0ffffffc0ffffffc0fffffff - wiped after finalization */
320ac341f1SConrad Meyer st->r[0] = (LOAD32_LE(&key[0])) & 0x3ffffff;
330ac341f1SConrad Meyer st->r[1] = (LOAD32_LE(&key[3]) >> 2) & 0x3ffff03;
340ac341f1SConrad Meyer st->r[2] = (LOAD32_LE(&key[6]) >> 4) & 0x3ffc0ff;
350ac341f1SConrad Meyer st->r[3] = (LOAD32_LE(&key[9]) >> 6) & 0x3f03fff;
360ac341f1SConrad Meyer st->r[4] = (LOAD32_LE(&key[12]) >> 8) & 0x00fffff;
370ac341f1SConrad Meyer
380ac341f1SConrad Meyer /* h = 0 */
390ac341f1SConrad Meyer st->h[0] = 0;
400ac341f1SConrad Meyer st->h[1] = 0;
410ac341f1SConrad Meyer st->h[2] = 0;
420ac341f1SConrad Meyer st->h[3] = 0;
430ac341f1SConrad Meyer st->h[4] = 0;
440ac341f1SConrad Meyer
450ac341f1SConrad Meyer /* save pad for later */
460ac341f1SConrad Meyer st->pad[0] = LOAD32_LE(&key[16]);
470ac341f1SConrad Meyer st->pad[1] = LOAD32_LE(&key[20]);
480ac341f1SConrad Meyer st->pad[2] = LOAD32_LE(&key[24]);
490ac341f1SConrad Meyer st->pad[3] = LOAD32_LE(&key[28]);
500ac341f1SConrad Meyer
510ac341f1SConrad Meyer st->leftover = 0;
520ac341f1SConrad Meyer st->final = 0;
530ac341f1SConrad Meyer }
540ac341f1SConrad Meyer
550ac341f1SConrad Meyer static void
poly1305_blocks(poly1305_state_internal_t * st,const unsigned char * m,unsigned long long bytes)560ac341f1SConrad Meyer poly1305_blocks(poly1305_state_internal_t *st, const unsigned char *m,
570ac341f1SConrad Meyer unsigned long long bytes)
580ac341f1SConrad Meyer {
590ac341f1SConrad Meyer const unsigned long hibit = (st->final) ? 0UL : (1UL << 24); /* 1 << 128 */
600ac341f1SConrad Meyer unsigned long r0, r1, r2, r3, r4;
610ac341f1SConrad Meyer unsigned long s1, s2, s3, s4;
620ac341f1SConrad Meyer unsigned long h0, h1, h2, h3, h4;
630ac341f1SConrad Meyer unsigned long long d0, d1, d2, d3, d4;
640ac341f1SConrad Meyer unsigned long c;
650ac341f1SConrad Meyer
660ac341f1SConrad Meyer r0 = st->r[0];
670ac341f1SConrad Meyer r1 = st->r[1];
680ac341f1SConrad Meyer r2 = st->r[2];
690ac341f1SConrad Meyer r3 = st->r[3];
700ac341f1SConrad Meyer r4 = st->r[4];
710ac341f1SConrad Meyer
720ac341f1SConrad Meyer s1 = r1 * 5;
730ac341f1SConrad Meyer s2 = r2 * 5;
740ac341f1SConrad Meyer s3 = r3 * 5;
750ac341f1SConrad Meyer s4 = r4 * 5;
760ac341f1SConrad Meyer
770ac341f1SConrad Meyer h0 = st->h[0];
780ac341f1SConrad Meyer h1 = st->h[1];
790ac341f1SConrad Meyer h2 = st->h[2];
800ac341f1SConrad Meyer h3 = st->h[3];
810ac341f1SConrad Meyer h4 = st->h[4];
820ac341f1SConrad Meyer
830ac341f1SConrad Meyer while (bytes >= poly1305_block_size) {
840ac341f1SConrad Meyer /* h += m[i] */
850ac341f1SConrad Meyer h0 += (LOAD32_LE(m + 0)) & 0x3ffffff;
860ac341f1SConrad Meyer h1 += (LOAD32_LE(m + 3) >> 2) & 0x3ffffff;
870ac341f1SConrad Meyer h2 += (LOAD32_LE(m + 6) >> 4) & 0x3ffffff;
880ac341f1SConrad Meyer h3 += (LOAD32_LE(m + 9) >> 6) & 0x3ffffff;
890ac341f1SConrad Meyer h4 += (LOAD32_LE(m + 12) >> 8) | hibit;
900ac341f1SConrad Meyer
910ac341f1SConrad Meyer /* h *= r */
920ac341f1SConrad Meyer d0 = ((unsigned long long) h0 * r0) + ((unsigned long long) h1 * s4) +
930ac341f1SConrad Meyer ((unsigned long long) h2 * s3) + ((unsigned long long) h3 * s2) +
940ac341f1SConrad Meyer ((unsigned long long) h4 * s1);
950ac341f1SConrad Meyer d1 = ((unsigned long long) h0 * r1) + ((unsigned long long) h1 * r0) +
960ac341f1SConrad Meyer ((unsigned long long) h2 * s4) + ((unsigned long long) h3 * s3) +
970ac341f1SConrad Meyer ((unsigned long long) h4 * s2);
980ac341f1SConrad Meyer d2 = ((unsigned long long) h0 * r2) + ((unsigned long long) h1 * r1) +
990ac341f1SConrad Meyer ((unsigned long long) h2 * r0) + ((unsigned long long) h3 * s4) +
1000ac341f1SConrad Meyer ((unsigned long long) h4 * s3);
1010ac341f1SConrad Meyer d3 = ((unsigned long long) h0 * r3) + ((unsigned long long) h1 * r2) +
1020ac341f1SConrad Meyer ((unsigned long long) h2 * r1) + ((unsigned long long) h3 * r0) +
1030ac341f1SConrad Meyer ((unsigned long long) h4 * s4);
1040ac341f1SConrad Meyer d4 = ((unsigned long long) h0 * r4) + ((unsigned long long) h1 * r3) +
1050ac341f1SConrad Meyer ((unsigned long long) h2 * r2) + ((unsigned long long) h3 * r1) +
1060ac341f1SConrad Meyer ((unsigned long long) h4 * r0);
1070ac341f1SConrad Meyer
1080ac341f1SConrad Meyer /* (partial) h %= p */
1090ac341f1SConrad Meyer c = (unsigned long) (d0 >> 26);
1100ac341f1SConrad Meyer h0 = (unsigned long) d0 & 0x3ffffff;
1110ac341f1SConrad Meyer d1 += c;
1120ac341f1SConrad Meyer c = (unsigned long) (d1 >> 26);
1130ac341f1SConrad Meyer h1 = (unsigned long) d1 & 0x3ffffff;
1140ac341f1SConrad Meyer d2 += c;
1150ac341f1SConrad Meyer c = (unsigned long) (d2 >> 26);
1160ac341f1SConrad Meyer h2 = (unsigned long) d2 & 0x3ffffff;
1170ac341f1SConrad Meyer d3 += c;
1180ac341f1SConrad Meyer c = (unsigned long) (d3 >> 26);
1190ac341f1SConrad Meyer h3 = (unsigned long) d3 & 0x3ffffff;
1200ac341f1SConrad Meyer d4 += c;
1210ac341f1SConrad Meyer c = (unsigned long) (d4 >> 26);
1220ac341f1SConrad Meyer h4 = (unsigned long) d4 & 0x3ffffff;
1230ac341f1SConrad Meyer h0 += c * 5;
1240ac341f1SConrad Meyer c = (h0 >> 26);
1250ac341f1SConrad Meyer h0 = h0 & 0x3ffffff;
1260ac341f1SConrad Meyer h1 += c;
1270ac341f1SConrad Meyer
1280ac341f1SConrad Meyer m += poly1305_block_size;
1290ac341f1SConrad Meyer bytes -= poly1305_block_size;
1300ac341f1SConrad Meyer }
1310ac341f1SConrad Meyer
1320ac341f1SConrad Meyer st->h[0] = h0;
1330ac341f1SConrad Meyer st->h[1] = h1;
1340ac341f1SConrad Meyer st->h[2] = h2;
1350ac341f1SConrad Meyer st->h[3] = h3;
1360ac341f1SConrad Meyer st->h[4] = h4;
1370ac341f1SConrad Meyer }
1380ac341f1SConrad Meyer
1390ac341f1SConrad Meyer static POLY1305_NOINLINE void
poly1305_finish(poly1305_state_internal_t * st,unsigned char mac[16])1400ac341f1SConrad Meyer poly1305_finish(poly1305_state_internal_t *st, unsigned char mac[16])
1410ac341f1SConrad Meyer {
1420ac341f1SConrad Meyer unsigned long h0, h1, h2, h3, h4, c;
1430ac341f1SConrad Meyer unsigned long g0, g1, g2, g3, g4;
1440ac341f1SConrad Meyer unsigned long long f;
1450ac341f1SConrad Meyer unsigned long mask;
1460ac341f1SConrad Meyer
1470ac341f1SConrad Meyer /* process the remaining block */
1480ac341f1SConrad Meyer if (st->leftover) {
1490ac341f1SConrad Meyer unsigned long long i = st->leftover;
1500ac341f1SConrad Meyer
1510ac341f1SConrad Meyer st->buffer[i++] = 1;
1520ac341f1SConrad Meyer for (; i < poly1305_block_size; i++) {
1530ac341f1SConrad Meyer st->buffer[i] = 0;
1540ac341f1SConrad Meyer }
1550ac341f1SConrad Meyer st->final = 1;
1560ac341f1SConrad Meyer poly1305_blocks(st, st->buffer, poly1305_block_size);
1570ac341f1SConrad Meyer }
1580ac341f1SConrad Meyer
1590ac341f1SConrad Meyer /* fully carry h */
1600ac341f1SConrad Meyer h0 = st->h[0];
1610ac341f1SConrad Meyer h1 = st->h[1];
1620ac341f1SConrad Meyer h2 = st->h[2];
1630ac341f1SConrad Meyer h3 = st->h[3];
1640ac341f1SConrad Meyer h4 = st->h[4];
1650ac341f1SConrad Meyer
1660ac341f1SConrad Meyer c = h1 >> 26;
1670ac341f1SConrad Meyer h1 = h1 & 0x3ffffff;
1680ac341f1SConrad Meyer h2 += c;
1690ac341f1SConrad Meyer c = h2 >> 26;
1700ac341f1SConrad Meyer h2 = h2 & 0x3ffffff;
1710ac341f1SConrad Meyer h3 += c;
1720ac341f1SConrad Meyer c = h3 >> 26;
1730ac341f1SConrad Meyer h3 = h3 & 0x3ffffff;
1740ac341f1SConrad Meyer h4 += c;
1750ac341f1SConrad Meyer c = h4 >> 26;
1760ac341f1SConrad Meyer h4 = h4 & 0x3ffffff;
1770ac341f1SConrad Meyer h0 += c * 5;
1780ac341f1SConrad Meyer c = h0 >> 26;
1790ac341f1SConrad Meyer h0 = h0 & 0x3ffffff;
1800ac341f1SConrad Meyer h1 += c;
1810ac341f1SConrad Meyer
1820ac341f1SConrad Meyer /* compute h + -p */
1830ac341f1SConrad Meyer g0 = h0 + 5;
1840ac341f1SConrad Meyer c = g0 >> 26;
1850ac341f1SConrad Meyer g0 &= 0x3ffffff;
1860ac341f1SConrad Meyer g1 = h1 + c;
1870ac341f1SConrad Meyer c = g1 >> 26;
1880ac341f1SConrad Meyer g1 &= 0x3ffffff;
1890ac341f1SConrad Meyer g2 = h2 + c;
1900ac341f1SConrad Meyer c = g2 >> 26;
1910ac341f1SConrad Meyer g2 &= 0x3ffffff;
1920ac341f1SConrad Meyer g3 = h3 + c;
1930ac341f1SConrad Meyer c = g3 >> 26;
1940ac341f1SConrad Meyer g3 &= 0x3ffffff;
1950ac341f1SConrad Meyer g4 = h4 + c - (1UL << 26);
1960ac341f1SConrad Meyer
1970ac341f1SConrad Meyer /* select h if h < p, or h + -p if h >= p */
1980ac341f1SConrad Meyer mask = (g4 >> ((sizeof(unsigned long) * 8) - 1)) - 1;
1990ac341f1SConrad Meyer g0 &= mask;
2000ac341f1SConrad Meyer g1 &= mask;
2010ac341f1SConrad Meyer g2 &= mask;
2020ac341f1SConrad Meyer g3 &= mask;
2030ac341f1SConrad Meyer g4 &= mask;
2040ac341f1SConrad Meyer mask = ~mask;
2050ac341f1SConrad Meyer
2060ac341f1SConrad Meyer h0 = (h0 & mask) | g0;
2070ac341f1SConrad Meyer h1 = (h1 & mask) | g1;
2080ac341f1SConrad Meyer h2 = (h2 & mask) | g2;
2090ac341f1SConrad Meyer h3 = (h3 & mask) | g3;
2100ac341f1SConrad Meyer h4 = (h4 & mask) | g4;
2110ac341f1SConrad Meyer
2120ac341f1SConrad Meyer /* h = h % (2^128) */
2130ac341f1SConrad Meyer h0 = ((h0) | (h1 << 26)) & 0xffffffff;
2140ac341f1SConrad Meyer h1 = ((h1 >> 6) | (h2 << 20)) & 0xffffffff;
2150ac341f1SConrad Meyer h2 = ((h2 >> 12) | (h3 << 14)) & 0xffffffff;
2160ac341f1SConrad Meyer h3 = ((h3 >> 18) | (h4 << 8)) & 0xffffffff;
2170ac341f1SConrad Meyer
2180ac341f1SConrad Meyer /* mac = (h + pad) % (2^128) */
2190ac341f1SConrad Meyer f = (unsigned long long) h0 + st->pad[0];
2200ac341f1SConrad Meyer h0 = (unsigned long) f;
2210ac341f1SConrad Meyer f = (unsigned long long) h1 + st->pad[1] + (f >> 32);
2220ac341f1SConrad Meyer h1 = (unsigned long) f;
2230ac341f1SConrad Meyer f = (unsigned long long) h2 + st->pad[2] + (f >> 32);
2240ac341f1SConrad Meyer h2 = (unsigned long) f;
2250ac341f1SConrad Meyer f = (unsigned long long) h3 + st->pad[3] + (f >> 32);
2260ac341f1SConrad Meyer h3 = (unsigned long) f;
2270ac341f1SConrad Meyer
2280ac341f1SConrad Meyer STORE32_LE(mac + 0, (uint32_t) h0);
2290ac341f1SConrad Meyer STORE32_LE(mac + 4, (uint32_t) h1);
2300ac341f1SConrad Meyer STORE32_LE(mac + 8, (uint32_t) h2);
2310ac341f1SConrad Meyer STORE32_LE(mac + 12, (uint32_t) h3);
2320ac341f1SConrad Meyer
2330ac341f1SConrad Meyer /* zero out the state */
2340ac341f1SConrad Meyer sodium_memzero((void *) st, sizeof *st);
2350ac341f1SConrad Meyer }
236