3 * Poly1305 message authentication code
5 * (c) 2017 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 /*----- Header files ------------------------------------------------------*/
37 /*----- Global variables --------------------------------------------------*/
39 const octet poly1305_keysz[] = { KSZ_SET, 16, 0 };
41 /*----- Low-level implementation for 32/64-bit targets --------------------*/
43 #if !defined(POLY1305_IMPL) && defined(HAVE_UINT64)
44 # define POLY1305_IMPL 26
47 #if POLY1305_IMPL == 26
49 /* Elements x of GF(2^130 - 5) are represented by five integers x_i: x =
50 * SUM_{0<=i<5} x_i 2^{26i}.
52 * Not all elements are represented canonically. We have 0 <= r_i, s_i <
53 * 2^26 by construction. We maintain 0 <= h_i < 2^27. When we read a
54 * message block m, we have 0 <= m_i < 2^26 by construction again. When we
55 * update the hash state, we calculate h' = r (h + m). Addition is done
56 * componentwise; let t = h + m, and we will have 0 <= t_i < 3*2^26.
58 typedef uint32 felt[5];
59 #define M26 0x03ffffff
62 /* Convert 32-bit words into field-element pieces. */
63 #define P26W0(x) (((x##0) << 0)&0x03ffffff)
64 #define P26W1(x) ((((x##1) << 6)&0x03ffffc0) | (((x##0) >> 26)&0x0000003f))
65 #define P26W2(x) ((((x##2) << 12)&0x03ffffff) | (((x##1) >> 20)&0x00000fff))
66 #define P26W3(x) ((((x##3) << 18)&0x03fc0000) | (((x##2) >> 14)&0x0003ffff))
67 #define P26W4(x) (((x##3) >> 8)&0x00ffffff)
69 /* Propagate carries in parallel. If 0 <= u_i < 2^26 c_i, then we shall have
70 * 0 <= v_0 < 2^26 + 5 c_4, and 0 <= v_i < 2^26 + c_{i-1} for 1 <= i < 5.
72 #define CARRY_REDUCE(v, u) do { \
73 (v##0) = ((u##0)&M26) + 5*((u##4) >> 26); \
74 (v##1) = ((u##1)&M26) + ((u##0) >> 26); \
75 (v##2) = ((u##2)&M26) + ((u##1) >> 26); \
76 (v##3) = ((u##3)&M26) + ((u##2) >> 26); \
77 (v##4) = ((u##4)&M26) + ((u##3) >> 26); \
80 /* General multiplication, used by `concat'. */
81 static void mul(felt z, const felt x, const felt y)
83 /* Initial bounds: we assume x_i, y_i < 2^27. On exit, z_i < 2^27. */
85 uint32 x0 = x[0], x1 = x[1], x2 = x[2], x3 = x[3], x4 = x[4];
86 uint32 y0 = y[0], y1 = y[1], y2 = y[2], y3 = y[3], y4 = y[4];
87 uint64 u0, u1, u2, u3, u4;
88 uint64 v0, v1, v2, v3, v4;
89 uint32 z0, z1, z2, z3, z4;
91 /* Do the multiplication: u = h x mod 2^130 - 5. We will have u_i <
92 * 2^27 (5 (4 - i) + i + 1) 2^27 = 2^54 (21 - 4 i) = 2^52 (84 - 16 i). In
93 * all cases we have u_i < 84*2^52 < 2^59. Notably, u_4 < 5*2^54 =
96 #define M(x, y) ((uint64)(x)*(y))
97 u0 = M(x0, y0) + (M(x1, y4) + M(x2, y3) + M(x3, y2) + M(x4, y1))*5;
98 u1 = M(x0, y1) + M(x1, y0) + (M(x2, y4) + M(x3, y3) + M(x4, y2))*5;
99 u2 = M(x0, y2) + M(x1, y1) + M(x2, y0) + (M(x3, y4) + M(x4, y3))*5;
100 u3 = M(x0, y3) + M(x1, y2) + M(x2, y1) + M(x3, y0) + (M(x4, y4))*5;
101 u4 = M(x0, y4) + M(x1, y3) + M(x2, y2) + M(x3, y1) + M(x4, y0);
104 /* Now we must reduce the coefficients. We do this in an approximate
105 * manner which avoids long data-dependency chains, but requires two
108 * The reduced carry down from u_4 to u_0 in the first pass will be c_0 <
109 * 100*2^26; the remaining c_i are smaller: c_i < 2^26 (84 - 16 i). This
110 * leaves 0 <= v_i < 101*2^26. The carries in the second pass are bounded
113 CARRY_REDUCE(v, u); CARRY_REDUCE(z, v);
114 z[0] = z0; z[1] = z1; z[2] = z2; z[3] = z3; z[4] = z4;
117 /* General squaring, used by `concat'. */
118 static void sqr(felt z, const felt x)
120 /* Initial bounds: we assume x_i < 2^27. On exit, z_i < 2^27. */
122 uint32 x0 = x[0], x1 = x[1], x2 = x[2], x3 = x[3], x4 = x[4];
123 uint64 u0, u1, u2, u3, u4;
124 uint64 v0, v1, v2, v3, v4;
125 uint32 z0, z1, z2, z3, z4;
127 /* Do the squaring. See `mul' for bounds. */
128 #define M(x, y) ((uint64)(x)*(y))
129 u0 = M(x0, x0) + 10*(M(x1, x4) + M(x2, x3));
130 u1 = 2* M(x0, x1) + 5*(M(x3, x3) + 2*M(x2, x4));
131 u2 = M(x1, x1) + 2* M(x0, x2) + 10* M(x3, x4);
132 u3 = 2*(M(x0, x3) + M(x1, x2)) + 5* M(x4, x4);
133 u4 = M(x2, x2) + 2*(M(x0, x4) + M(x1, x3));
136 /* Now we must reduce the coefficients. See `mul' for bounds. */
137 CARRY_REDUCE(v, u); CARRY_REDUCE(z, v);
138 z[0] = z0; z[1] = z1; z[2] = z2; z[3] = z3; z[4] = z4;
141 /* Multiplication by r, using precomputation. */
142 static void mul_r(const poly1305_ctx *ctx, felt z, const felt x)
144 /* Initial bounds: by construction, r_i < 2^26. We assume x_i < 3*2^26.
145 * On exit, z_i < 2^27.
149 r0 = ctx->k.u.p26.r0,
150 r1 = ctx->k.u.p26.r1, rr1 = ctx->k.u.p26.rr1,
151 r2 = ctx->k.u.p26.r2, rr2 = ctx->k.u.p26.rr2,
152 r3 = ctx->k.u.p26.r3, rr3 = ctx->k.u.p26.rr3,
153 r4 = ctx->k.u.p26.r4, rr4 = ctx->k.u.p26.rr4;
154 uint32 x0 = x[0], x1 = x[1], x2 = x[2], x3 = x[3], x4 = x[4];
155 uint64 u0, u1, u2, u3, u4;
156 uint64 v0, v1, v2, v3, v4;
157 uint32 z0, z1, z2, z3, z4;
159 /* Do the multiplication: u = h x mod 2^130 - 5. We will have u_i <
160 * 2^26 (5 (4 - i) + i + 1) 3*2^26 = 2^52 (63 - 12 i). In all cases
161 * we have u_i < 63*2^52 < 2^58. Notably, u_4 < 15*2^52.
163 #define M(x, y) ((uint64)(x)*(y))
164 u0 = M(x0, r0) + M(x1, rr4) + M(x2, rr3) + M(x3, rr2) + M(x4, rr1);
165 u1 = M(x0, r1) + M(x1, r0) + M(x2, rr4) + M(x3, rr3) + M(x4, rr2);
166 u2 = M(x0, r2) + M(x1, r1) + M(x2, r0) + M(x3, rr4) + M(x4, rr3);
167 u3 = M(x0, r3) + M(x1, r2) + M(x2, r1) + M(x3, r0) + M(x4, rr4);
168 u4 = M(x0, r4) + M(x1, r3) + M(x2, r2) + M(x3, r1) + M(x4, r0);
171 /* Now we must reduce the coefficients. We do this in an approximate
172 * manner which avoids long data-dependency chains, but requires two
175 * The reduced carry down from u_4 to u_0 in the first pass will be c_0 <
176 * 75*2^26; the remaining c_i are smaller: c_i < 2^26 (63 - 12 i). This
177 * leaves 0 <= v_i < 76*2^26. The carries in the second pass are bounded
180 CARRY_REDUCE(v, u); CARRY_REDUCE(z, v);
181 z[0] = z0; z[1] = z1; z[2] = z2; z[3] = z3; z[4] = z4;
186 /*----- Low-level implementation for 16/32-bit targets --------------------*/
188 #ifndef POLY1305_IMPL
189 # define POLY1305_IMPL 11
192 #if POLY1305_IMPL == 11
194 /* Elements x of GF(2^130 - 5) are represented by 12 integers x_i: x =
195 * SUM_{0<=i<12} x_i 2^P_i, where P_i = SUM_{0<=j<i} w_j, and w_5 = w_11 =
196 * 10, and w_i = 11 for i in { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10 }.
198 * Not all elements are represented canonically. We have 0 <= r_i, s_i <
199 * 2^w_i <= 2^11 by construction. We maintain 0 <= h_i < 2^12. When we read
200 * a message block m, we have 0 <= m_i < 2^w_i by construction again. When
201 * we update the hash state, we calculate h' = r (h + m). Addition is done
202 * componentwise; let t = h + m, and we will have 0 <= t_i < 3*2^11.
204 typedef uint16 felt[12];
209 /* Load a field element from an octet string. */
210 static void load_p11(felt d, const octet *s)
216 for (i = j = n = 0, a = 0; j < 12; j++) {
217 if (j == 5 || j == 11) { w = 10; m = M10; }
218 else { w = 11; m = M11; }
219 while (n < w && i < 16) { a |= s[i++] << n; n += 8; }
220 d[j] = a&m; a >>= w; n -= w;
224 /* Reduce a field-element's pieces to manageable size. */
225 static void carry_reduce(uint32 u[12])
227 /* Initial bounds: we assume u_i < 636*2^22. On exit, u_i < 2^11. */
232 /* Do sequential carry propagation (16-bit CPUs are less likely to benefit
233 * from instruction-level parallelism). Start at u_9; truncate it to 11
234 * bits, and add the carry onto u_10. Truncate u10 to 11 bits, and add the
235 * carry onto u_11. Truncate u_11 to 10 bits, and add five times the carry
236 * onto u_0. And so on.
238 * The carry is larger than the pieces we're leaving behind. Let c_i be
239 * the high portion of u_i, to be carried onto u_{i+1}. I claim that c_i <
240 * 2557*2^10. Then the carry /into/ any u_i is at most 12785*2^10 < 2^24
241 * (allowing for the reduction as we carry from u_11 to u_0), and u_i after
242 * carry is bounded above by 636*2^22 + 12785*2^10 < 2557*2^20. Hence, the
243 * carry out is at most 2557*2^10, as claimed.
245 * Once we reach u_9 for the second time, we start with u_9 < 2^11. The
246 * carry into u_9 is at most 2557*2^10 < 1279*2^11 as calculated above; so
247 * the carry out into u_10 is at most 1280. Since u_10 < 2^11 prior to
248 * this carry in, we now have u_10 < 2^11 + 1280 < 2^12; so the carry out
249 * into u_11 is at most 1. The final reduction therefore only needs a
250 * conditional subtraction.
252 { c = u[9] >> 11; u[9] &= M11; }
253 { u[10] += c; c = u[10] >> 11; u[10] &= M11; }
254 { u[11] += c; c = u[11] >> 10; u[11] &= M10; }
255 { u[0] += 5*c; c = u[0] >> 11; u[0] &= M11; }
256 for (i = 1; i < 5; i++) { u[i] += c; c = u[i] >> 11; u[i] &= M11; }
257 { u[5] += c; c = u[5] >> 10; u[5] &= M10; }
258 for (i = 6; i < 11; i++) { u[i] += c; c = u[i] >> 11; u[i] &= M11; }
262 /* General multiplication. */
263 static void mul(felt z, const felt x, const felt y)
265 /* Initial bounds: we assume x_i < 3*2^11, and y_i < 2^12. On exit,
272 /* Do the main multiplication. After this, we shall have
274 * { 2^22 (636 - 184 i) for 0 <= i < 6
276 * { 2^22 (732 - 60 i) for 6 <= i < 12
278 * In particular, u_0 < 636*2^22 < 2^32, and u_11 < 72*2^22.
280 * The irregularly positioned pieces are annoying. Because we fold the
281 * reduction into the multiplication, it's also important to see where the
282 * reduced products fit. Finally, products don't align with the piece
283 * boundaries, and sometimes need to be doubled. The following table
284 * tracks all of this.
286 * piece width offset second
300 * The next table tracks exactly which products end up being multiplied by
301 * which constants and accumulated into which destination pieces.
303 * u_k = t_i r_j + 2 t_i r_j + 5 t_i r_j + 10 t_i r_j
304 * 0 0/0 -- 6/6 1-5/11-7 7-11/5-1
305 * 1 0-1/1-0 -- 6-7/7-6 2-5/11-8 8-11/5-2
306 * 2 0-2/2-0 -- 6-8/8-6 3-5/11-9 9-11/5-3
307 * 3 0-3/3-0 -- 6-9/9-6 4-5/11-10 10-11/5-4
308 * 4 0-4/4-0 -- 6-10/10-6 5/11 11/5
309 * 5 0-5/5-0 -- 6-11/11-6 --
310 * 6 0/6 6/0 1-5/5-1 -- 7-11/11-7
311 * 7 0-1/7-6 6-7/1-0 2-5/5-2 -- 8-11/11-8
312 * 8 0-2/8-6 6-8/2-0 3-5/5-3 -- 9-11/11-9
313 * 9 0-3/9-6 6-9/3-0 4-5/5-4 -- 10-11/11-10
314 * 10 0-4/10-6 6-10/4-0 5/5 -- 11/11
315 * 11 0-11/11-0 -- -- --
317 * And, finally, trying to bound the multiple of 6*2^22 in each destination
318 * piece is fiddly, so here's a tableau showing the calculation.
320 * k 1* + 2* + 5* +10* = 1* + 5* =
321 * 0 1 -- 1 10 1 21 106
327 * 6 2 5 -- 5 12 10 62
331 * 10 10 1 -- 1 12 2 22
332 * 11 12 -- -- -- 12 0 12
335 for (i = 0; i < 12; i++) u[i] = 0;
337 #define M(i, j) ((uint32)x[i]*y[j])
339 /* Product terms we must multiply by 10. */
340 for (k = 0; k < 5; k++) {
341 for (i = k + 1; i < 6; i++) {
343 u[k] += M(i, j) + M(j, i);
344 u[k + 6] += M(i + 6, j);
347 for (k = 0; k < 5; k++) u[k] *= 2;
348 for (k = 6; k < 11; k++) u[k] *= 5;
350 /* Product terms we must multiply by 5. */
351 for (k = 0; k < 6; k++) {
352 for (i = k + 6; i >= 6; i--) {
357 for (k = 0; k < 6; k++) u[k] *= 5;
359 /* Product terms we must multiply by 2. */
360 for (k = 6; k < 11; k++) {
361 for (i = k - 5; i < 6; i++) {
366 for (k = 6; k < 11; k++) u[k] *= 2;
368 /* Remaining product terms. */
369 for (k = 0; k < 6; k++) {
370 for (i = k; i < 6; i--) {
373 u[k + 6] += M(i + 6, j) + M(i, j + 6);
379 /* Do the reduction. Currently, `carry_reduce' does more than we need, but
384 /* Done. Write out the answer. */
385 for (i = 0; i < 12; i++) z[i] = u[i];
388 /* General squaring, used by `concat'. */
389 static void sqr(felt z, const felt x)
392 /* Multiplication by r. */
393 static void mul_r(const poly1305_ctx *ctx, felt z, const felt x)
394 { mul(z, x, ctx->k.u.p11.r); }
398 /*----- Interface functions -----------------------------------------------*/
400 /* --- @poly1305_keyinit@ --- *
402 * Arguments: @poly1305_key *key@ = key structure to fill in
403 * @const void *k@ = pointer to key material
404 * @size_t ksz@ = length of key (must be @POLY1305_KEYSZ == 16@)
408 * Use: Records a Poly1305 key and performs (minimal)
412 void poly1305_keyinit(poly1305_key *key, const void *k, size_t ksz)
415 #if POLY1305_IMPL == 11
419 KSZ_ASSERT(poly1305, ksz);
421 #if POLY1305_IMPL == 26
422 uint32 r0 = LOAD32_L(r + 0), r1 = LOAD32_L(r + 4),
423 r2 = LOAD32_L(r + 8), r3 = LOAD32_L(r + 12);
425 r0 &= 0x0fffffff; r1 &= 0x0ffffffc; r2 &= 0x0ffffffc; r3 &= 0x0ffffffc;
426 key->u.p26.r0 = P26W0(r); key->u.p26.r1 = P26W1(r);
427 key->u.p26.r2 = P26W2(r); key->u.p26.r3 = P26W3(r);
428 key->u.p26.r4 = P26W4(r);
430 key->u.p26.rr1 = 5*key->u.p26.r1; key->u.p26.rr2 = 5*key->u.p26.r2;
431 key->u.p26.rr3 = 5*key->u.p26.r3; key->u.p26.rr4 = 5*key->u.p26.r4;
435 rr[ 4] &= 0xfc; rr[ 7] &= 0x0f;
436 rr[ 8] &= 0xfc; rr[11] &= 0x0f;
437 rr[12] &= 0xfc; rr[15] &= 0x0f;
438 load_p11(key->u.p11.r, rr);
442 /* --- @poly1305_macinit@ --- *
444 * Arguments: @poly1305_ctx *ctx@ = MAC context to fill in
445 * @const poly1305_key *key@ = pointer to key structure to use
446 * @const void *iv@ = pointer to mask string
450 * Use: Initializes a MAC context for use. The key can be discarded
453 * It is permitted for @iv@ to be null, though it is not then
454 * possible to complete the MAC computation on @ctx@. The
455 * resulting context may still be useful, e.g., as an operand to
459 void poly1305_macinit(poly1305_ctx *ctx,
460 const poly1305_key *key, const void *iv)
463 #if POLY1305_IMPL == 26
464 uint32 s0, s1, s2, s3;
469 #if POLY1305_IMPL == 26
471 s0 = LOAD32_L(s + 0); s1 = LOAD32_L(s + 4);
472 s2 = LOAD32_L(s + 8); s3 = LOAD32_L(s + 12);
473 ctx->u.p26.s0 = P26W0(s); ctx->u.p26.s1 = P26W1(s);
474 ctx->u.p26.s2 = P26W2(s); ctx->u.p26.s3 = P26W3(s);
475 ctx->u.p26.s4 = P26W4(s);
477 ctx->u.p26.h[0] = ctx->u.p26.h[1] = ctx->u.p26.h[2] =
478 ctx->u.p26.h[3] = ctx->u.p26.h[4] = 0;
480 if (s) load_p11(ctx->u.p11.s, s);
481 for (i = 0; i < 12; i++) ctx->u.p11.h[i] = 0;
488 /* --- @poly1305_copy@ --- *
490 * Arguments: @poly1305_ctx *to@ = destination context
491 * @const poly1305_ctx *from@ = source context
495 * Use: Duplicates a Poly1305 MAC context. The destination need not
496 * have been initialized. Both contexts can be used
497 * independently afterwards.
500 void poly1305_copy(poly1305_ctx *ctx, const poly1305_ctx *from)
503 /* --- @poly1305_hash@ --- *
505 * Arguments: @poly1305_ctx *ctx@ = MAC context to update
506 * @const void *p@ = pointer to message data
507 * @size_t sz@ = length of message data
511 * Use: Processes a chunk of message. The message pieces may have
512 * arbitrary lengths, and may be empty.
515 static void update_full(poly1305_ctx *ctx, const octet *p)
518 #if POLY1305_IMPL == 26
520 m0 = LOAD32_L(p + 0), m1 = LOAD32_L(p + 4),
521 m2 = LOAD32_L(p + 8), m3 = LOAD32_L(p + 12);
523 t[0] = ctx->u.p26.h[0] + P26W0(m);
524 t[1] = ctx->u.p26.h[1] + P26W1(m);
525 t[2] = ctx->u.p26.h[2] + P26W2(m);
526 t[3] = ctx->u.p26.h[3] + P26W3(m);
527 t[4] = ctx->u.p26.h[4] + P26W4(m) + 0x01000000;
531 load_p11(t, p); t[11] += 0x100;
532 for (i = 0; i < 12; i++) t[i] += ctx->u.p11.h[i];
535 mul_r(ctx, ctx->u.P.h, t);
539 void poly1305_hash(poly1305_ctx *ctx, const void *p, size_t sz)
545 if (sz < 16 - ctx->nbuf) {
546 memcpy(ctx->buf + ctx->nbuf, p, sz);
551 memcpy(ctx->buf + ctx->nbuf, pp, n);
552 update_full(ctx, ctx->buf);
556 update_full(ctx, pp);
559 if (sz) memcpy(ctx->buf, pp, sz);
563 /* --- @poly1305_flush@ --- *
565 * Arguments: @poly1305_ctx *ctx@ = MAC context to flush
569 * Use: Forces any buffered message data in the context to be
570 * processed. This has no effect if the message processed so
571 * far is a whole number of blocks. Flushing is performed
572 * automatically by @poly1305_done@, but it may be necessary to
573 * force it by hand when using @poly1305_concat@.
574 * (Alternatively, you might use @poly1305_flushzero@ instead.)
576 * Flushing a partial block has an observable effect on the
577 * computation: the resulting state is (with high probability)
578 * dissimilar to any state reachable with a message which is a
579 * whole number of blocks long.
582 void poly1305_flush(poly1305_ctx *ctx)
585 #if POLY1305_IMPL == 26
586 uint32 m0, m1, m2, m3;
591 if (!ctx->nbuf) return;
592 ctx->buf[ctx->nbuf++] = 1; memset(ctx->buf + ctx->nbuf, 0, 16 - ctx->nbuf);
593 #if POLY1305_IMPL == 26
594 m0 = LOAD32_L(ctx->buf + 0); m1 = LOAD32_L(ctx->buf + 4);
595 m2 = LOAD32_L(ctx->buf + 8); m3 = LOAD32_L(ctx->buf + 12);
597 t[0] = ctx->u.p26.h[0] + P26W0(m);
598 t[1] = ctx->u.p26.h[1] + P26W1(m);
599 t[2] = ctx->u.p26.h[2] + P26W2(m);
600 t[3] = ctx->u.p26.h[3] + P26W3(m);
601 t[4] = ctx->u.p26.h[4] + P26W4(m);
603 load_p11(t, ctx->buf);
604 for (i = 0; i < 12; i++) t[i] += ctx->u.p11.h[i];
607 mul_r(ctx, ctx->u.P.h, t);
608 ctx->nbuf = 0; ctx->count++;
611 /* --- @poly1305_flushzero@ --- *
613 * Arguments: @poly1305_ctx *ctx@ = MAC context to flush
617 * Use: Forces any buffered message data in the context to be
618 * processed, by hashing between zero and fifteen additional
619 * zero bytes. Like @poly1305_flush@, this has no effect if the
620 * the message processed so far is a whole number of blocks.
621 * Unlike @poly1305_flush@, the behaviour if the message is not
622 * a whole number of blocks is equivalent to actually hashing
626 void poly1305_flushzero(poly1305_ctx *ctx)
628 if (!ctx->nbuf) return;
629 memset(ctx->buf + ctx->nbuf, 0, 16 - ctx->nbuf);
630 update_full(ctx, ctx->buf);
634 /* --- @poly1305_concat@ --- *
636 * Arguments: @poly1305_ctx *ctx@ = destination context
637 * @const poly1305_ctx *prefix, *suffix@ = two operand contexts
641 * Use: The two operand contexts @prefix@ and @suffix@ represent
642 * processing of two messages %$m$% and %$m'$%; the effect is to
643 * set @ctx@ to the state corresponding to their concatenation
646 * All three contexts must have been initialized using the same
647 * key value (though not necessarily from the same key
648 * structure). The mask values associated with the input
649 * contexts are irrelevant. The @prefix@ message %$m$% must be
650 * a whole number of blocks long: this can be arranged by
651 * flushing the context. The @suffix@ message need not be a
652 * whole number of blocks long. All of the contexts remain
653 * operational and can be used independently afterwards.
656 void poly1305_concat(poly1305_ctx *ctx,
657 const poly1305_ctx *prefix, const poly1305_ctx *suffix)
659 /* Assume that lengths are public, so it's safe to behave conditionally on
660 * the bits of ctx->count.
665 #if POLY1305_IMPL == 26
666 uint32 x0, x1, x2, x3, x4, y0, y1, y2, y3, y4;
671 /* We can only concatenate if the prefix is block-aligned. */
672 assert(!prefix->nbuf);
674 /* The hash for a message m = m_{k-1} m_{k-2} ... m_1 m_0 is h_r(m) =
675 * SUM_{0<=i<k} m_i r^{i+1}. If we have two messages, m, m', of lengths k
676 * and k' blocks respectively, then
678 * h_r(m || m') = SUM_{0<=i<k} m_i r^{k'+i+1} +
679 * SUM_{0<=i<k'} m'_i r^{i+1}
680 * = r^{k'} h_r(m) + h_r(m')
682 * This is simple left-to-right square-and-multiply exponentiation.
686 #if POLY1305_IMPL == 26
687 x[1] = x[2] = x[3] = x[4] = 0;
689 for (i = 1; i < 12; i++) x[i] = 0;
691 #define BIT (1ul << (ULONG_BITS - 1))
694 while (!(n & BIT)) { n <<= 1; i--; }
695 mul_r(prefix, x, x); n <<= 1; i--;
696 while (i--) { sqr(x, x); if (n & BIT) mul_r(prefix, x, x); n <<= 1; }
699 mul(x, prefix->u.P.h, x);
701 /* Add on the suffix hash. */
702 #if POLY1305_IMPL == 26
703 /* We're going to add the two hashes elementwise. Both h' = h_r(m') and
704 * x = r^{k'} h_r(m) are bounded above by 2^27, so the sum will be bounded
705 * by 2^28; but this is too large to leave in the accumulator. (Strictly,
706 * we could get away with it, but the caller can in theory chain an
707 * arbitrary number of concatenations and expect us to cope, and we'd
708 * definitely overflow eventually.) So we reduce. Since the excess is so
709 * small, a single round of `CARRY_REDUCE' is enough.
711 x0 = x[0] + suffix->u.p26.h[0]; x1 = x[1] + suffix->u.p26.h[1];
712 x2 = x[2] + suffix->u.p26.h[2]; x3 = x[3] + suffix->u.p26.h[3];
713 x4 = x[4] + suffix->u.p26.h[4];
715 ctx->u.p26.h[0] = y0; ctx->u.p26.h[1] = y1; ctx->u.p26.h[2] = y2;
716 ctx->u.p26.h[3] = y3; ctx->u.p26.h[4] = y4;
718 /* We'll add the two hashes elementwise and have to reduce again. The
719 * numbers are different, but the reasoning is basically the same.
721 for (i = 0; i < 12; i++) y[i] = x[i] + suffix->u.p11.h[i];
723 for (i = 0; i < 12; i++) ctx->u.p11.h[i] = y[i];
726 /* Copy the remaining pieces of the context to set up the result. */
728 memcpy(ctx->buf, suffix->buf, suffix->nbuf);
729 ctx->nbuf = suffix->nbuf;
731 ctx->count = prefix->count + suffix->count;
734 /* --- @poly1305_done@ --- *
736 * Arguments: @poly1305_ctx *ctx@ = MAC context to finish
737 * @void *h@ = buffer to write the tag to
741 * Use: Completes a Poly1305 MAC tag computation.
744 void poly1305_done(poly1305_ctx *ctx, void *h)
748 #if POLY1305_IMPL == 26
750 uint32 h0, h1, h2, h3, h4, hh0, hh1, hh2, hh3, hh4;
752 /* If there's anything left over in the buffer, pad it to form a final
753 * coefficient and update the evaluation one last time.
757 /* Collect the final hash state. */
758 h0 = ctx->u.p26.h[0];
759 h1 = ctx->u.p26.h[1];
760 h2 = ctx->u.p26.h[2];
761 h3 = ctx->u.p26.h[3];
762 h4 = ctx->u.p26.h[4];
764 /* Reduce the final value mod 2^130 - 5. First pass: set h <- h +
765 * 5 floor(h/2^130). After this, the low pieces of h will be normalized:
766 * 0 <= h_i < 2^26 for 0 <= i < 4; and 0 <= h_4 < 2^26 + 1. In the
767 * (highly unlikely) event that h_4 >= 2^26, set c and truncate to 130
770 c = h4 >> 26; h4 &= M26;
771 h0 += 5*c; c = h0 >> 26; h0 &= M26;
772 h1 += c; c = h1 >> 26; h1 &= M26;
773 h2 += c; c = h2 >> 26; h2 &= M26;
774 h3 += c; c = h3 >> 26; h3 &= M26;
775 h4 += c; c = h4 >> 26; h4 &= M26;
777 /* Calculate h' = h - (2^130 - 5). If h' >= 0 then t ends up 1; otherwise
780 t = h0 + 5; hh0 = t&M26; t >>= 26;
781 t += h1; hh1 = t&M26; t >>= 26;
782 t += h2; hh2 = t&M26; t >>= 26;
783 t += h3; hh3 = t&M26; t >>= 26;
784 t += h4; hh4 = t&M26; t >>= 26;
786 /* Keep the subtraction result above if t or c is set. */
788 h0 = (hh0&m_sub) | (h0&~m_sub);
789 h1 = (hh1&m_sub) | (h1&~m_sub);
790 h2 = (hh2&m_sub) | (h2&~m_sub);
791 h3 = (hh3&m_sub) | (h3&~m_sub);
792 h4 = (hh4&m_sub) | (h4&~m_sub);
794 /* Add the mask onto the hash result. */
795 t = h0 + ctx->u.p26.s0; h0 = t&M26; t >>= 26;
796 t += h1 + ctx->u.p26.s1; h1 = t&M26; t >>= 26;
797 t += h2 + ctx->u.p26.s2; h2 = t&M26; t >>= 26;
798 t += h3 + ctx->u.p26.s3; h3 = t&M26; t >>= 26;
799 t += h4 + ctx->u.p26.s4; h4 = t&M26; t >>= 26;
801 /* Convert this mess back into 32-bit words. We lose the top two bits,
804 h0 = (h0 >> 0) | ((h1 & 0x0000003f) << 26);
805 h1 = (h1 >> 6) | ((h2 & 0x00000fff) << 20);
806 h2 = (h2 >> 12) | ((h3 & 0x0003ffff) << 14);
807 h3 = (h3 >> 18) | ((h4 & 0x00ffffff) << 8);
810 STORE32_L(p + 0, h0); STORE32_L(p + 4, h1);
811 STORE32_L(p + 8, h2); STORE32_L(p + 12, h3);
813 uint16 hh[12], hi[12], c, t, m_sub;
817 /* If there's anything left over in the buffer, pad it to form a final
818 * coefficient and update the evaluation one last time.
822 /* Collect the final hash state. */
823 for (i = 0; i < 12; i++) hh[i] = ctx->u.p11.h[i];
825 /* Reduce the final value mod 2^130 - 5. First pass: set h <- h +
826 * 5 floor(h/2^130). After this, the low pieces of h will be normalized:
827 * 0 <= h_i < 2^{w_i} for 0 <= i < 11; and 0 <= h_{11} < 2^10 + 1. In the
828 * (highly unlikely) event that h_{11} >= 2^10, set c and truncate to 130
831 c = 5*(hh[11] >> 10); hh[11] &= M10;
832 for (i = 0; i < 12; i++) {
833 if (i == 5 || i == 11) { c += hh[i]; hh[i] = c&M10; c >>= 10; }
834 else { c += hh[i]; hh[i] = c&M11; c >>= 11; }
837 /* Calculate h' = h - (2^130 - 5). If h' >= 0 then t ends up 1; otherwise
840 for (i = 0, t = 5; i < 12; i++) {
842 if (i == 5 || i == 11) { hi[i] = t&M10; t >>= 10; }
843 else { hi[i] = t&M11; t >>= 11; }
846 /* Keep the subtraction result above if t or c is set. */
848 for (i = 0; i < 12; i++) hh[i] = (hi[i]&m_sub) | (hh[i]&~m_sub);
850 /* Add the mask onto the hash result. */
851 for (i = 0, t = 0; i < 12; i++) {
852 t += hh[i] + ctx->u.p11.s[i];
853 if (i == 5 || i == 11) { hh[i] = t&M10; t >>= 10; }
854 else { hh[i] = t&M11; t >>= 11; }
857 /* Convert this mess back into bytes. We lose the top two bits, but that's
860 for (i = j = n = 0, a = 0; i < 16; i++) {
863 n += (j == 5 || j == 11) ? 10 : 11;
866 p[i] = a&0xff; a >>= 8; n -= 8;
872 /*----- Test rig ----------------------------------------------------------*/
876 #include <mLib/testrig.h>
879 #include "rijndael-ecb.h"
881 static int vrf_hash(dstr v[])
888 if (v[0].len != 16) { fprintf(stderr, "bad key length\n"); exit(2); }
889 if (v[1].len != 16) { fprintf(stderr, "bad mask length\n"); exit(2); }
890 if (v[3].len != 16) { fprintf(stderr, "bad tag length\n"); exit(2); }
891 dstr_ensure(&t, 16); t.len = 16;
893 ct_poison(v[0].buf, v[0].len);
894 poly1305_keyinit(&k, v[0].buf, v[0].len);
895 for (i = 0; i < v[2].len; i++) {
896 for (j = i; j < v[2].len; j++) {
897 poly1305_macinit(&ctx, &k, v[1].buf);
898 poly1305_hash(&ctx, v[2].buf, i);
899 poly1305_hash(&ctx, v[2].buf + i, j - i);
900 poly1305_hash(&ctx, v[2].buf + j, v[2].len - j);
901 poly1305_done(&ctx, t.buf);
902 ct_remedy(t.buf, t.len);
903 if (memcmp(t.buf, v[3].buf, 16) != 0) {
904 fprintf(stderr, "failed...");
905 fprintf(stderr, "\n\tkey = "); type_hex.dump(&v[0], stderr);
906 fprintf(stderr, "\n\tmask = "); type_hex.dump(&v[1], stderr);
907 fprintf(stderr, "\n\tmsg = "); type_hex.dump(&v[2], stderr);
908 fprintf(stderr, "\n\texp = "); type_hex.dump(&v[3], stderr);
909 fprintf(stderr, "\n\tcalc = "); type_hex.dump(&t, stderr);
910 fprintf(stderr, "\n\tsplits = 0 .. %u .. %u .. %lu\n",
911 i, j, (unsigned long)v[1].len);
919 static int vrf_cat(dstr v[])
922 poly1305_ctx ctx, cc[3];
927 if (v[0].len != 16) { fprintf(stderr, "bad key length\n"); exit(2); }
928 if (v[1].len != 16) { fprintf(stderr, "bad mask length\n"); exit(2); }
929 if (v[5].len != 16) { fprintf(stderr, "bad tag length\n"); exit(2); }
930 dstr_ensure(&t, 16); t.len = 16;
932 poly1305_keyinit(&k, v[0].buf, v[0].len);
933 poly1305_macinit(&ctx, &k, v[1].buf);
934 for (i = 0; i < 3; i++) {
935 poly1305_macinit(&cc[i], &k, 0);
936 poly1305_hash(&cc[i], v[i + 2].buf, v[i + 2].len);
938 for (i = 0; i < 2; i++) {
940 poly1305_concat(&ctx, &cc[1], &cc[2]);
941 poly1305_concat(&ctx, &cc[0], &ctx);
943 poly1305_concat(&ctx, &cc[0], &cc[1]);
944 poly1305_concat(&ctx, &ctx, &cc[2]);
946 poly1305_done(&ctx, t.buf);
947 if (memcmp(t.buf, v[5].buf, 16) != 0) {
948 fprintf(stderr, "failed...");
949 fprintf(stderr, "\n\tkey = "); type_hex.dump(&v[0], stderr);
950 fprintf(stderr, "\n\tmask = "); type_hex.dump(&v[1], stderr);
951 fprintf(stderr, "\n\tmsg[0] = "); type_hex.dump(&v[2], stderr);
952 fprintf(stderr, "\n\tmsg[1] = "); type_hex.dump(&v[3], stderr);
953 fprintf(stderr, "\n\tmsg[2] = "); type_hex.dump(&v[4], stderr);
954 fprintf(stderr, "\n\texp = "); type_hex.dump(&v[5], stderr);
955 fprintf(stderr, "\n\tcalc = "); type_hex.dump(&t, stderr);
956 fprintf(stderr, "\n\tassoc = %s\n",
957 !i ? "msg[0] || (msg[1] || msg[2])" :
958 "(msg[0] || msg[1]) || msg[2]");
967 static int vrf_mct(dstr v[])
970 unsigned long i, niter;
975 octet k[16], r[16], n[16], s[16], *t, m[MSZMAX] = { 0 };
978 if (v[0].len != sizeof(k)) { fprintf(stderr, "AES key len\n"); exit(2); }
979 if (v[1].len != sizeof(r)) { fprintf(stderr, "poly key len\n"); exit(2); }
980 if (v[2].len != sizeof(n)) { fprintf(stderr, "nonce len\n"); exit(2); }
981 if (v[4].len != sizeof(n)) { fprintf(stderr, "result len\n"); exit(2); }
982 memcpy(k, v[0].buf, sizeof(k));
983 memcpy(r, v[1].buf, sizeof(k));
984 memcpy(n, v[2].buf, sizeof(k));
985 niter = *(unsigned long *)v[3].buf;
986 dstr_ensure(&d, 16); d.len = 16; t = (octet *)d.buf;
988 rijndael_ecbinit(&rij, k, sizeof(k), 0);
989 poly1305_keyinit(&key, r, sizeof(r));
990 for (i = 0; i < niter; i++) {
993 rijndael_ecbencrypt(&rij, n, s, 16);
994 poly1305_macinit(&mac, &key, s);
995 poly1305_hash(&mac, m, msz);
996 poly1305_done(&mac, t);
997 if (msz >= MSZMAX) break;
999 for (j = 0; j < 16; j++) n[j] ^= t[j];
1001 for (j = 0; j < 16; j++) k[j] ^= t[j];
1002 rijndael_ecbinit(&rij, k, sizeof(k), 0);
1005 for (j = 0; j < 16; j++) r[j] ^= t[j];
1006 poly1305_keyinit(&key, r, sizeof(r));
1012 if (memcmp(t, v[4].buf, 16) != 0) {
1014 fprintf(stderr, "failed...");
1015 fprintf(stderr, "\n\tinitial k = "); type_hex.dump(&v[0], stderr);
1016 fprintf(stderr, "\n\tinitial r = "); type_hex.dump(&v[1], stderr);
1017 fprintf(stderr, "\n\tinitial n = "); type_hex.dump(&v[2], stderr);
1018 fprintf(stderr, "\n\titerations = %lu", niter);
1019 fprintf(stderr, "\n\texpected = "); type_hex.dump(&v[4], stderr);
1020 fprintf(stderr, "\n\tcalculated = "); type_hex.dump(&d, stderr);
1021 fputc('\n', stderr);
1028 static const struct test_chunk tests[] = {
1029 { "poly1305-hash", vrf_hash,
1030 { &type_hex, &type_hex, &type_hex, &type_hex } },
1031 { "poly1305-cat", vrf_cat,
1032 { &type_hex, &type_hex, &type_hex, &type_hex, &type_hex, &type_hex } },
1033 { "poly1305-mct", vrf_mct,
1034 { &type_hex, &type_hex, &type_hex, &type_ulong, &type_hex } },
1038 int main(int argc, char *argv[])
1040 test_run(argc, argv, tests, SRCDIR "/t/poly1305");
1046 /*----- That's all, folks -------------------------------------------------*/