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 32/64-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>
878 #include "rijndael-ecb.h"
880 static int vrf_hash(dstr v
[])
887 if (v
[0].len
!= 16) { fprintf(stderr
, "bad key length\n"); exit(2); }
888 if (v
[1].len
!= 16) { fprintf(stderr
, "bad mask length\n"); exit(2); }
889 if (v
[3].len
!= 16) { fprintf(stderr
, "bad tag length\n"); exit(2); }
890 dstr_ensure(&t
, 16); t
.len
= 16;
892 poly1305_keyinit(&k
, v
[0].buf
, v
[0].len
);
893 for (i
= 0; i
< v
[2].len
; i
++) {
894 for (j
= i
; j
< v
[2].len
; j
++) {
895 poly1305_macinit(&ctx
, &k
, v
[1].buf
);
896 poly1305_hash(&ctx
, v
[2].buf
, i
);
897 poly1305_hash(&ctx
, v
[2].buf
+ i
, j
- i
);
898 poly1305_hash(&ctx
, v
[2].buf
+ j
, v
[2].len
- j
);
899 poly1305_done(&ctx
, t
.buf
);
900 if (memcmp(t
.buf
, v
[3].buf
, 16) != 0) {
901 fprintf(stderr
, "failed...");
902 fprintf(stderr
, "\n\tkey = "); type_hex
.dump(&v
[0], stderr
);
903 fprintf(stderr
, "\n\tmask = "); type_hex
.dump(&v
[1], stderr
);
904 fprintf(stderr
, "\n\tmsg = "); type_hex
.dump(&v
[2], stderr
);
905 fprintf(stderr
, "\n\texp = "); type_hex
.dump(&v
[3], stderr
);
906 fprintf(stderr
, "\n\tcalc = "); type_hex
.dump(&t
, stderr
);
907 fprintf(stderr
, "\n\tsplits = 0 .. %u .. %u .. %lu\n",
908 i
, j
, (unsigned long)v
[1].len
);
916 static int vrf_cat(dstr v
[])
919 poly1305_ctx ctx
, cc
[3];
924 if (v
[0].len
!= 16) { fprintf(stderr
, "bad key length\n"); exit(2); }
925 if (v
[1].len
!= 16) { fprintf(stderr
, "bad mask length\n"); exit(2); }
926 if (v
[5].len
!= 16) { fprintf(stderr
, "bad tag length\n"); exit(2); }
927 dstr_ensure(&t
, 16); t
.len
= 16;
929 poly1305_keyinit(&k
, v
[0].buf
, v
[0].len
);
930 poly1305_macinit(&ctx
, &k
, v
[1].buf
);
931 for (i
= 0; i
< 3; i
++) {
932 poly1305_macinit(&cc
[i
], &k
, 0);
933 poly1305_hash(&cc
[i
], v
[i
+ 2].buf
, v
[i
+ 2].len
);
935 for (i
= 0; i
< 2; i
++) {
937 poly1305_concat(&ctx
, &cc
[1], &cc
[2]);
938 poly1305_concat(&ctx
, &cc
[0], &ctx
);
940 poly1305_concat(&ctx
, &cc
[0], &cc
[1]);
941 poly1305_concat(&ctx
, &ctx
, &cc
[2]);
943 poly1305_done(&ctx
, t
.buf
);
944 if (memcmp(t
.buf
, v
[5].buf
, 16) != 0) {
945 fprintf(stderr
, "failed...");
946 fprintf(stderr
, "\n\tkey = "); type_hex
.dump(&v
[0], stderr
);
947 fprintf(stderr
, "\n\tmask = "); type_hex
.dump(&v
[1], stderr
);
948 fprintf(stderr
, "\n\tmsg[0] = "); type_hex
.dump(&v
[2], stderr
);
949 fprintf(stderr
, "\n\tmsg[1] = "); type_hex
.dump(&v
[3], stderr
);
950 fprintf(stderr
, "\n\tmsg[2] = "); type_hex
.dump(&v
[4], stderr
);
951 fprintf(stderr
, "\n\texp = "); type_hex
.dump(&v
[5], stderr
);
952 fprintf(stderr
, "\n\tcalc = "); type_hex
.dump(&t
, stderr
);
953 fprintf(stderr
, "\n\tassoc = %s\n",
954 !i ?
"msg[0] || (msg[1] || msg[2])" :
955 "(msg[0] || msg[1]) || msg[2]");
964 static int vrf_mct(dstr v
[])
967 unsigned long i
, niter
;
972 octet k
[16], r
[16], n
[16], s
[16], *t
, m
[MSZMAX
] = { 0 };
975 if (v
[0].len
!= sizeof(k
)) { fprintf(stderr
, "AES key len\n"); exit(2); }
976 if (v
[1].len
!= sizeof(r
)) { fprintf(stderr
, "poly key len\n"); exit(2); }
977 if (v
[2].len
!= sizeof(n
)) { fprintf(stderr
, "nonce len\n"); exit(2); }
978 if (v
[4].len
!= sizeof(n
)) { fprintf(stderr
, "result len\n"); exit(2); }
979 memcpy(k
, v
[0].buf
, sizeof(k
));
980 memcpy(r
, v
[1].buf
, sizeof(k
));
981 memcpy(n
, v
[2].buf
, sizeof(k
));
982 niter
= *(unsigned long *)v
[3].buf
;
983 dstr_ensure(&d
, 16); d
.len
= 16; t
= (octet
*)d
.buf
;
985 rijndael_ecbinit(&rij
, k
, sizeof(k
), 0);
986 poly1305_keyinit(&key
, r
, sizeof(r
));
987 for (i
= 0; i
< niter
; i
++) {
990 rijndael_ecbencrypt(&rij
, n
, s
, 16);
991 poly1305_macinit(&mac
, &key
, s
);
992 poly1305_hash(&mac
, m
, msz
);
993 poly1305_done(&mac
, t
);
994 if (msz
>= MSZMAX
) break;
996 for (j
= 0; j
< 16; j
++) n
[j
] ^= t
[j
];
998 for (j
= 0; j
< 16; j
++) k
[j
] ^= t
[j
];
999 rijndael_ecbinit(&rij
, k
, sizeof(k
), 0);
1002 for (j
= 0; j
< 16; j
++) r
[j
] ^= t
[j
];
1003 poly1305_keyinit(&key
, r
, sizeof(r
));
1009 if (memcmp(t
, v
[4].buf
, 16) != 0) {
1011 fprintf(stderr
, "failed...");
1012 fprintf(stderr
, "\n\tinitial k = "); type_hex
.dump(&v
[0], stderr
);
1013 fprintf(stderr
, "\n\tinitial r = "); type_hex
.dump(&v
[1], stderr
);
1014 fprintf(stderr
, "\n\tinitial n = "); type_hex
.dump(&v
[2], stderr
);
1015 fprintf(stderr
, "\n\titerations = %lu", niter
);
1016 fprintf(stderr
, "\n\texpected = "); type_hex
.dump(&v
[4], stderr
);
1017 fprintf(stderr
, "\n\tcalculated = "); type_hex
.dump(&d
, stderr
);
1018 fputc('\n', stderr
);
1025 static const struct test_chunk tests
[] = {
1026 { "poly1305-hash", vrf_hash
,
1027 { &type_hex
, &type_hex
, &type_hex
, &type_hex
} },
1028 { "poly1305-cat", vrf_cat
,
1029 { &type_hex
, &type_hex
, &type_hex
, &type_hex
, &type_hex
, &type_hex
} },
1030 { "poly1305-mct", vrf_mct
,
1031 { &type_hex
, &type_hex
, &type_hex
, &type_ulong
, &type_hex
} },
1035 int main(int argc
, char *argv
[])
1037 test_run(argc
, argv
, tests
, SRCDIR
"/t/poly1305");
1043 /*----- That's all, folks -------------------------------------------------*/