Branch data Line data Source code
1 : : // Copyright (c) 2019 The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #include <crypto/common.h>
6 : : #include <crypto/poly1305.h>
7 : :
8 : : #include <string.h>
9 : :
10 : : namespace poly1305_donna {
11 : :
12 : : // Based on the public domain implementation by Andrew Moon
13 : : // poly1305-donna-32.h from https://github.com/floodyberry/poly1305-donna
14 : :
15 : 1428187 : void poly1305_init(poly1305_context *st, const unsigned char key[32]) noexcept {
16 : : /* r &= 0xffffffc0ffffffc0ffffffc0fffffff */
17 : 1428187 : st->r[0] = (ReadLE32(&key[ 0]) ) & 0x3ffffff;
18 : 1428187 : st->r[1] = (ReadLE32(&key[ 3]) >> 2) & 0x3ffff03;
19 : 1428187 : st->r[2] = (ReadLE32(&key[ 6]) >> 4) & 0x3ffc0ff;
20 : 1428187 : st->r[3] = (ReadLE32(&key[ 9]) >> 6) & 0x3f03fff;
21 : 1428187 : st->r[4] = (ReadLE32(&key[12]) >> 8) & 0x00fffff;
22 : :
23 : : /* h = 0 */
24 : 1428187 : st->h[0] = 0;
25 : 1428187 : st->h[1] = 0;
26 : 1428187 : st->h[2] = 0;
27 : 1428187 : st->h[3] = 0;
28 : 1428187 : st->h[4] = 0;
29 : :
30 : : /* save pad for later */
31 : 1428187 : st->pad[0] = ReadLE32(&key[16]);
32 : 1428187 : st->pad[1] = ReadLE32(&key[20]);
33 : 1428187 : st->pad[2] = ReadLE32(&key[24]);
34 : 1428187 : st->pad[3] = ReadLE32(&key[28]);
35 : :
36 : 1428187 : st->leftover = 0;
37 : 1428187 : st->final = 0;
38 : 1428187 : }
39 : :
40 : 1760246 : static void poly1305_blocks(poly1305_context *st, const unsigned char *m, size_t bytes) noexcept {
41 [ + + ]: 1760246 : const uint32_t hibit = (st->final) ? 0 : (1UL << 24); /* 1 << 128 */
42 : 1760246 : uint32_t r0,r1,r2,r3,r4;
43 : 1760246 : uint32_t s1,s2,s3,s4;
44 : 1760246 : uint32_t h0,h1,h2,h3,h4;
45 : 1760246 : uint64_t d0,d1,d2,d3,d4;
46 : 1760246 : uint32_t c;
47 : :
48 : 1760246 : r0 = st->r[0];
49 : 1760246 : r1 = st->r[1];
50 : 1760246 : r2 = st->r[2];
51 : 1760246 : r3 = st->r[3];
52 : 1760246 : r4 = st->r[4];
53 : :
54 : 1760246 : s1 = r1 * 5;
55 : 1760246 : s2 = r2 * 5;
56 : 1760246 : s3 = r3 * 5;
57 : 1760246 : s4 = r4 * 5;
58 : :
59 : 1760246 : h0 = st->h[0];
60 : 1760246 : h1 = st->h[1];
61 : 1760246 : h2 = st->h[2];
62 : 1760246 : h3 = st->h[3];
63 : 1760246 : h4 = st->h[4];
64 : :
65 [ + + ]: 42990416 : while (bytes >= POLY1305_BLOCK_SIZE) {
66 : : /* h += m[i] */
67 : 41230170 : h0 += (ReadLE32(m+ 0) ) & 0x3ffffff;
68 : 41230170 : h1 += (ReadLE32(m+ 3) >> 2) & 0x3ffffff;
69 : 41230170 : h2 += (ReadLE32(m+ 6) >> 4) & 0x3ffffff;
70 : 41230170 : h3 += (ReadLE32(m+ 9) >> 6) & 0x3ffffff;
71 : 41230170 : h4 += (ReadLE32(m+12) >> 8) | hibit;
72 : :
73 : : /* h *= r */
74 : 41230170 : d0 = ((uint64_t)h0 * r0) + ((uint64_t)h1 * s4) + ((uint64_t)h2 * s3) + ((uint64_t)h3 * s2) + ((uint64_t)h4 * s1);
75 : 41230170 : d1 = ((uint64_t)h0 * r1) + ((uint64_t)h1 * r0) + ((uint64_t)h2 * s4) + ((uint64_t)h3 * s3) + ((uint64_t)h4 * s2);
76 : 41230170 : d2 = ((uint64_t)h0 * r2) + ((uint64_t)h1 * r1) + ((uint64_t)h2 * r0) + ((uint64_t)h3 * s4) + ((uint64_t)h4 * s3);
77 : 41230170 : d3 = ((uint64_t)h0 * r3) + ((uint64_t)h1 * r2) + ((uint64_t)h2 * r1) + ((uint64_t)h3 * r0) + ((uint64_t)h4 * s4);
78 : 41230170 : d4 = ((uint64_t)h0 * r4) + ((uint64_t)h1 * r3) + ((uint64_t)h2 * r2) + ((uint64_t)h3 * r1) + ((uint64_t)h4 * r0);
79 : :
80 : : /* (partial) h %= p */
81 : 41230170 : c = (uint32_t)(d0 >> 26); h0 = (uint32_t)d0 & 0x3ffffff;
82 : 41230170 : d1 += c; c = (uint32_t)(d1 >> 26); h1 = (uint32_t)d1 & 0x3ffffff;
83 : 41230170 : d2 += c; c = (uint32_t)(d2 >> 26); h2 = (uint32_t)d2 & 0x3ffffff;
84 : 41230170 : d3 += c; c = (uint32_t)(d3 >> 26); h3 = (uint32_t)d3 & 0x3ffffff;
85 : 41230170 : d4 += c; c = (uint32_t)(d4 >> 26); h4 = (uint32_t)d4 & 0x3ffffff;
86 : 41230170 : h0 += c * 5; c = (h0 >> 26); h0 = h0 & 0x3ffffff;
87 : 41230170 : h1 += c;
88 : :
89 : 41230170 : m += POLY1305_BLOCK_SIZE;
90 : 41230170 : bytes -= POLY1305_BLOCK_SIZE;
91 : : }
92 : :
93 : 1760246 : st->h[0] = h0;
94 : 1760246 : st->h[1] = h1;
95 : 1760246 : st->h[2] = h2;
96 : 1760246 : st->h[3] = h3;
97 : 1760246 : st->h[4] = h4;
98 : 1760246 : }
99 : :
100 : 1428187 : void poly1305_finish(poly1305_context *st, unsigned char mac[16]) noexcept {
101 : 1428187 : uint32_t h0,h1,h2,h3,h4,c;
102 : 1428187 : uint32_t g0,g1,g2,g3,g4;
103 : 1428187 : uint64_t f;
104 : 1428187 : uint32_t mask;
105 : :
106 : : /* process the remaining block */
107 [ + + ]: 1428187 : if (st->leftover) {
108 : 947 : size_t i = st->leftover;
109 : 947 : st->buffer[i++] = 1;
110 [ + + ]: 7374 : for (; i < POLY1305_BLOCK_SIZE; i++) {
111 : 6427 : st->buffer[i] = 0;
112 : : }
113 : 947 : st->final = 1;
114 : 947 : poly1305_blocks(st, st->buffer, POLY1305_BLOCK_SIZE);
115 : : }
116 : :
117 : : /* fully carry h */
118 : 1428187 : h0 = st->h[0];
119 : 1428187 : h1 = st->h[1];
120 : 1428187 : h2 = st->h[2];
121 : 1428187 : h3 = st->h[3];
122 : 1428187 : h4 = st->h[4];
123 : :
124 : 1428187 : c = h1 >> 26; h1 = h1 & 0x3ffffff;
125 : 1428187 : h2 += c; c = h2 >> 26; h2 = h2 & 0x3ffffff;
126 : 1428187 : h3 += c; c = h3 >> 26; h3 = h3 & 0x3ffffff;
127 : 1428187 : h4 += c; c = h4 >> 26; h4 = h4 & 0x3ffffff;
128 : 1428187 : h0 += c * 5; c = h0 >> 26; h0 = h0 & 0x3ffffff;
129 : 1428187 : h1 += c;
130 : :
131 : : /* compute h + -p */
132 : 1428187 : g0 = h0 + 5; c = g0 >> 26; g0 &= 0x3ffffff;
133 : 1428187 : g1 = h1 + c; c = g1 >> 26; g1 &= 0x3ffffff;
134 : 1428187 : g2 = h2 + c; c = g2 >> 26; g2 &= 0x3ffffff;
135 : 1428187 : g3 = h3 + c; c = g3 >> 26; g3 &= 0x3ffffff;
136 : 1428187 : g4 = h4 + c - (1UL << 26);
137 : :
138 : : /* select h if h < p, or h + -p if h >= p */
139 : 1428187 : mask = (g4 >> ((sizeof(uint32_t) * 8) - 1)) - 1;
140 : 1428187 : g0 &= mask;
141 : 1428187 : g1 &= mask;
142 : 1428187 : g2 &= mask;
143 : 1428187 : g3 &= mask;
144 : 1428187 : g4 &= mask;
145 : 1428187 : mask = ~mask;
146 : 1428187 : h0 = (h0 & mask) | g0;
147 : 1428187 : h1 = (h1 & mask) | g1;
148 : 1428187 : h2 = (h2 & mask) | g2;
149 : 1428187 : h3 = (h3 & mask) | g3;
150 : 1428187 : h4 = (h4 & mask) | g4;
151 : :
152 : : /* h = h % (2^128) */
153 : 1428187 : h0 = ((h0 ) | (h1 << 26)) & 0xffffffff;
154 : 1428187 : h1 = ((h1 >> 6) | (h2 << 20)) & 0xffffffff;
155 : 1428187 : h2 = ((h2 >> 12) | (h3 << 14)) & 0xffffffff;
156 : 1428187 : h3 = ((h3 >> 18) | (h4 << 8)) & 0xffffffff;
157 : :
158 : : /* mac = (h + pad) % (2^128) */
159 : 1428187 : f = (uint64_t)h0 + st->pad[0] ; h0 = (uint32_t)f;
160 : 1428187 : f = (uint64_t)h1 + st->pad[1] + (f >> 32); h1 = (uint32_t)f;
161 : 1428187 : f = (uint64_t)h2 + st->pad[2] + (f >> 32); h2 = (uint32_t)f;
162 : 1428187 : f = (uint64_t)h3 + st->pad[3] + (f >> 32); h3 = (uint32_t)f;
163 : :
164 : 1428187 : WriteLE32(mac + 0, h0);
165 : 1428187 : WriteLE32(mac + 4, h1);
166 : 1428187 : WriteLE32(mac + 8, h2);
167 : 1428187 : WriteLE32(mac + 12, h3);
168 : :
169 : : /* zero out the state */
170 : 1428187 : st->h[0] = 0;
171 : 1428187 : st->h[1] = 0;
172 : 1428187 : st->h[2] = 0;
173 : 1428187 : st->h[3] = 0;
174 : 1428187 : st->h[4] = 0;
175 : 1428187 : st->r[0] = 0;
176 : 1428187 : st->r[1] = 0;
177 : 1428187 : st->r[2] = 0;
178 : 1428187 : st->r[3] = 0;
179 : 1428187 : st->r[4] = 0;
180 : 1428187 : st->pad[0] = 0;
181 : 1428187 : st->pad[1] = 0;
182 : 1428187 : st->pad[2] = 0;
183 : 1428187 : st->pad[3] = 0;
184 : 1428187 : }
185 : :
186 : 7140852 : void poly1305_update(poly1305_context *st, const unsigned char *m, size_t bytes) noexcept {
187 : 7140852 : size_t i;
188 : :
189 : : /* handle leftover */
190 [ + + ]: 7140852 : if (st->leftover) {
191 : 215392 : size_t want = (POLY1305_BLOCK_SIZE - st->leftover);
192 [ + + ]: 215392 : if (want > bytes) {
193 : 2872 : want = bytes;
194 : : }
195 [ + + ]: 2572969 : for (i = 0; i < want; i++) {
196 : 2357577 : st->buffer[st->leftover + i] = m[i];
197 : : }
198 : 215392 : bytes -= want;
199 : 215392 : m += want;
200 : 215392 : st->leftover += want;
201 [ + + ]: 215392 : if (st->leftover < POLY1305_BLOCK_SIZE) return;
202 : 212520 : poly1305_blocks(st, st->buffer, POLY1305_BLOCK_SIZE);
203 : 212520 : st->leftover = 0;
204 : : }
205 : :
206 : : /* process full blocks */
207 [ + + ]: 7137980 : if (bytes >= POLY1305_BLOCK_SIZE) {
208 : 1546779 : size_t want = (bytes & ~(POLY1305_BLOCK_SIZE - 1));
209 : 1546779 : poly1305_blocks(st, m, want);
210 : 1546779 : m += want;
211 : 1546779 : bytes -= want;
212 : : }
213 : :
214 : : /* store leftover */
215 [ + + ]: 7137980 : if (bytes) {
216 [ + + ]: 1263988 : for (i = 0; i < bytes; i++) {
217 : 1050521 : st->buffer[st->leftover + i] = m[i];
218 : : }
219 : 213467 : st->leftover += bytes;
220 : : }
221 : : }
222 : :
223 : : } // namespace poly1305_donna
|
