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@.
575 * Flushing a partial block has an observable effect on the
576 * computation: the resulting state is (with high probability)
577 * dissimilar to any state reachable with a message which is a
578 * whole number of blocks long.
581 void poly1305_flush(poly1305_ctx
*ctx
)
584 #if POLY1305_IMPL == 26
585 uint32 m0
, m1
, m2
, m3
;
590 if (!ctx
->nbuf
) return;
591 ctx
->buf
[ctx
->nbuf
++] = 1; memset(ctx
->buf
+ ctx
->nbuf
, 0, 16 - ctx
->nbuf
);
592 #if POLY1305_IMPL == 26
593 m0
= LOAD32_L(ctx
->buf
+ 0); m1
= LOAD32_L(ctx
->buf
+ 4);
594 m2
= LOAD32_L(ctx
->buf
+ 8); m3
= LOAD32_L(ctx
->buf
+ 12);
596 t
[0] = ctx
->u
.p26
.h
[0] + P26W0(m
);
597 t
[1] = ctx
->u
.p26
.h
[1] + P26W1(m
);
598 t
[2] = ctx
->u
.p26
.h
[2] + P26W2(m
);
599 t
[3] = ctx
->u
.p26
.h
[3] + P26W3(m
);
600 t
[4] = ctx
->u
.p26
.h
[4] + P26W4(m
);
602 load_p11(t
, ctx
->buf
);
603 for (i
= 0; i
< 12; i
++) t
[i
] += ctx
->u
.p11
.h
[i
];
606 mul_r(ctx
, ctx
->u
.P
.h
, t
);
611 /* --- @poly1305_concat@ --- *
613 * Arguments: @poly1305_ctx *ctx@ = destination context
614 * @const poly1305_ctx *prefix, *suffix@ = two operand contexts
618 * Use: The two operand contexts @prefix@ and @suffix@ represent
619 * processing of two messages %$m$% and %$m'$%; the effect is to
620 * set @ctx@ to the state corresponding to their concatenation
623 * All three contexts must have been initialized using the same
624 * key value (though not necessarily from the same key
625 * structure). The mask values associated with the input
626 * contexts are irrelevant. The @prefix@ message %$m$% must be
627 * a whole number of blocks long: this can be arranged by
628 * flushing the context. The @suffix@ message need not be a
629 * whole number of blocks long. All of the contexts remain
630 * operational and can be used independently afterwards.
633 void poly1305_concat(poly1305_ctx
*ctx
,
634 const poly1305_ctx
*prefix
, const poly1305_ctx
*suffix
)
636 /* Assume that lengths are public, so it's safe to behave conditionally on
637 * the bits of ctx->count.
642 #if POLY1305_IMPL == 26
643 uint32 x0
, x1
, x2
, x3
, x4
, y0
, y1
, y2
, y3
, y4
;
648 /* We can only concatenate if the prefix is block-aligned. */
649 assert(!prefix
->nbuf
);
651 /* The hash for a message m = m_{k-1} m_{k-2} ... m_1 m_0 is h_r(m) =
652 * SUM_{0<=i<k} m_i r^{i+1}. If we have two messages, m, m', of lengths k
653 * and k' blocks respectively, then
655 * h_r(m || m') = SUM_{0<=i<k} m_i r^{k'+i+1} +
656 * SUM_{0<=i<k'} m'_i r^{i+1}
657 * = r^{k'} h_r(m) + h_r(m')
659 * This is simple left-to-right square-and-multiply exponentiation.
663 #if POLY1305_IMPL == 26
664 x
[1] = x
[2] = x
[3] = x
[4] = 0;
666 for (i
= 1; i
< 12; i
++) x
[i
] = 0;
668 #define BIT (1ul << (ULONG_BITS - 1))
671 while (!(n
& BIT
)) { n
<<= 1; i
--; }
672 mul_r(prefix
, x
, x
); n
<<= 1; i
--;
673 while (i
--) { sqr(x
, x
); if (n
& BIT
) mul_r(prefix
, x
, x
); n
<<= 1; }
676 mul(x
, prefix
->u
.P
.h
, x
);
678 /* Add on the suffix hash. */
679 #if POLY1305_IMPL == 26
680 /* We're going to add the two hashes elementwise. Both h' = h_r(m') and
681 * x = r^{k'} h_r(m) are bounded above by 2^27, so the sum will be bounded
682 * by 2^28; but this is too large to leave in the accumulator. (Strictly,
683 * we could get away with it, but the caller can in theory chain an
684 * arbitrary number of concatenations and expect us to cope, and we'd
685 * definitely overflow eventually.) So we reduce. Since the excess is so
686 * small, a single round of `CARRY_REDUCE' is enough.
688 x0
= x
[0] + suffix
->u
.p26
.h
[0]; x1
= x
[1] + suffix
->u
.p26
.h
[1];
689 x2
= x
[2] + suffix
->u
.p26
.h
[2]; x3
= x
[3] + suffix
->u
.p26
.h
[3];
690 x4
= x
[4] + suffix
->u
.p26
.h
[4];
692 ctx
->u
.p26
.h
[0] = y0
; ctx
->u
.p26
.h
[1] = y1
; ctx
->u
.p26
.h
[2] = y2
;
693 ctx
->u
.p26
.h
[3] = y3
; ctx
->u
.p26
.h
[4] = y4
;
695 /* We'll add the two hashes elementwise and have to reduce again. The
696 * numbers are different, but the reasoning is basically the same.
698 for (i
= 0; i
< 12; i
++) y
[i
] = x
[i
] + suffix
->u
.p11
.h
[i
];
700 for (i
= 0; i
< 12; i
++) ctx
->u
.p11
.h
[i
] = y
[i
];
703 /* Copy the remaining pieces of the context to set up the result. */
705 memcpy(ctx
->buf
, suffix
->buf
, suffix
->nbuf
);
706 ctx
->nbuf
= suffix
->nbuf
;
708 ctx
->count
= prefix
->count
+ suffix
->count
;
711 /* --- @poly1305_done@ --- *
713 * Arguments: @poly1305_ctx *ctx@ = MAC context to finish
714 * @void *h@ = buffer to write the tag to
718 * Use: Completes a Poly1305 MAC tag computation.
721 void poly1305_done(poly1305_ctx
*ctx
, void *h
)
725 #if POLY1305_IMPL == 26
727 uint32 h0
, h1
, h2
, h3
, h4
, hh0
, hh1
, hh2
, hh3
, hh4
;
729 /* If there's anything left over in the buffer, pad it to form a final
730 * coefficient and update the evaluation one last time.
734 /* Collect the final hash state. */
735 h0
= ctx
->u
.p26
.h
[0];
736 h1
= ctx
->u
.p26
.h
[1];
737 h2
= ctx
->u
.p26
.h
[2];
738 h3
= ctx
->u
.p26
.h
[3];
739 h4
= ctx
->u
.p26
.h
[4];
741 /* Reduce the final value mod 2^130 - 5. First pass: set h <- h +
742 * 5 floor(h/2^130). After this, the low pieces of h will be normalized:
743 * 0 <= h_i < 2^26 for 0 <= i < 4; and 0 <= h_4 < 2^26 + 1. In the
744 * (highly unlikely) event that h_4 >= 2^26, set c and truncate to 130
747 c
= h4
>> 26; h4
&= M26
;
748 h0
+= 5*c
; c
= h0
>> 26; h0
&= M26
;
749 h1
+= c
; c
= h1
>> 26; h1
&= M26
;
750 h2
+= c
; c
= h2
>> 26; h2
&= M26
;
751 h3
+= c
; c
= h3
>> 26; h3
&= M26
;
752 h4
+= c
; c
= h4
>> 26; h4
&= M26
;
754 /* Calculate h' = h - (2^130 - 5). If h' >= 0 then t ends up 1; otherwise
757 t
= h0
+ 5; hh0
= t
&M26
; t
>>= 26;
758 t
+= h1
; hh1
= t
&M26
; t
>>= 26;
759 t
+= h2
; hh2
= t
&M26
; t
>>= 26;
760 t
+= h3
; hh3
= t
&M26
; t
>>= 26;
761 t
+= h4
; hh4
= t
&M26
; t
>>= 26;
763 /* Keep the subtraction result above if t or c is set. */
765 h0
= (hh0
&m_sub
) | (h0
&~m_sub
);
766 h1
= (hh1
&m_sub
) | (h1
&~m_sub
);
767 h2
= (hh2
&m_sub
) | (h2
&~m_sub
);
768 h3
= (hh3
&m_sub
) | (h3
&~m_sub
);
769 h4
= (hh4
&m_sub
) | (h4
&~m_sub
);
771 /* Add the mask onto the hash result. */
772 t
= h0
+ ctx
->u
.p26
.s0
; h0
= t
&M26
; t
>>= 26;
773 t
+= h1
+ ctx
->u
.p26
.s1
; h1
= t
&M26
; t
>>= 26;
774 t
+= h2
+ ctx
->u
.p26
.s2
; h2
= t
&M26
; t
>>= 26;
775 t
+= h3
+ ctx
->u
.p26
.s3
; h3
= t
&M26
; t
>>= 26;
776 t
+= h4
+ ctx
->u
.p26
.s4
; h4
= t
&M26
; t
>>= 26;
778 /* Convert this mess back into 32-bit words. We lose the top two bits,
781 h0
= (h0
>> 0) | ((h1
& 0x0000003f) << 26);
782 h1
= (h1
>> 6) | ((h2
& 0x00000fff) << 20);
783 h2
= (h2
>> 12) | ((h3
& 0x0003ffff) << 14);
784 h3
= (h3
>> 18) | ((h4
& 0x00ffffff) << 8);
787 STORE32_L(p
+ 0, h0
); STORE32_L(p
+ 4, h1
);
788 STORE32_L(p
+ 8, h2
); STORE32_L(p
+ 12, h3
);
790 uint16 hh
[12], hi
[12], c
, t
, m_sub
;
794 /* If there's anything left over in the buffer, pad it to form a final
795 * coefficient and update the evaluation one last time.
799 /* Collect the final hash state. */
800 for (i
= 0; i
< 12; i
++) hh
[i
] = ctx
->u
.p11
.h
[i
];
802 /* Reduce the final value mod 2^130 - 5. First pass: set h <- h +
803 * 5 floor(h/2^130). After this, the low pieces of h will be normalized:
804 * 0 <= h_i < 2^{w_i} for 0 <= i < 11; and 0 <= h_{11} < 2^10 + 1. In the
805 * (highly unlikely) event that h_{11} >= 2^10, set c and truncate to 130
808 c
= 5*(hh
[11] >> 10); hh
[11] &= M10
;
809 for (i
= 0; i
< 12; i
++) {
810 if (i
== 5 || i
== 11) { c
+= hh
[i
]; hh
[i
] = c
&M10
; c
>>= 10; }
811 else { c
+= hh
[i
]; hh
[i
] = c
&M11
; c
>>= 11; }
814 /* Calculate h' = h - (2^130 - 5). If h' >= 0 then t ends up 1; otherwise
817 for (i
= 0, t
= 5; i
< 12; i
++) {
819 if (i
== 5 || i
== 11) { hi
[i
] = t
&M10
; t
>>= 10; }
820 else { hi
[i
] = t
&M11
; t
>>= 11; }
823 /* Keep the subtraction result above if t or c is set. */
825 for (i
= 0; i
< 12; i
++) hh
[i
] = (hi
[i
]&m_sub
) | (hh
[i
]&~m_sub
);
827 /* Add the mask onto the hash result. */
828 for (i
= 0, t
= 0; i
< 12; i
++) {
829 t
+= hh
[i
] + ctx
->u
.p11
.s
[i
];
830 if (i
== 5 || i
== 11) { hh
[i
] = t
&M10
; t
>>= 10; }
831 else { hh
[i
] = t
&M11
; t
>>= 11; }
834 /* Convert this mess back into bytes. We lose the top two bits, but that's
837 for (i
= j
= n
= 0, a
= 0; i
< 16; i
++) {
840 n
+= (j
== 5 || j
== 11) ?
10 : 11;
843 p
[i
] = a
&0xff; a
>>= 8; n
-= 8;
849 /*----- Test rig ----------------------------------------------------------*/
853 #include <mLib/testrig.h>
855 static int vrf_hash(dstr v
[])
862 if (v
[0].len
!= 16) { fprintf(stderr
, "bad key length\n"); exit(2); }
863 if (v
[1].len
!= 16) { fprintf(stderr
, "bad mask length\n"); exit(2); }
864 if (v
[3].len
!= 16) { fprintf(stderr
, "bad tag length\n"); exit(2); }
865 dstr_ensure(&t
, 16); t
.len
= 16;
867 poly1305_keyinit(&k
, v
[0].buf
, v
[0].len
);
868 for (i
= 0; i
< v
[2].len
; i
++) {
869 for (j
= i
; j
< v
[2].len
; j
++) {
870 poly1305_macinit(&ctx
, &k
, v
[1].buf
);
871 poly1305_hash(&ctx
, v
[2].buf
, i
);
872 poly1305_hash(&ctx
, v
[2].buf
+ i
, j
- i
);
873 poly1305_hash(&ctx
, v
[2].buf
+ j
, v
[2].len
- j
);
874 poly1305_done(&ctx
, t
.buf
);
875 if (memcmp(t
.buf
, v
[3].buf
, 16) != 0) {
876 fprintf(stderr
, "failed...");
877 fprintf(stderr
, "\n\tkey = "); type_hex
.dump(&v
[0], stderr
);
878 fprintf(stderr
, "\n\tmask = "); type_hex
.dump(&v
[1], stderr
);
879 fprintf(stderr
, "\n\tmsg = "); type_hex
.dump(&v
[2], stderr
);
880 fprintf(stderr
, "\n\texp = "); type_hex
.dump(&v
[3], stderr
);
881 fprintf(stderr
, "\n\tcalc = "); type_hex
.dump(&t
, stderr
);
882 fprintf(stderr
, "\n\tsplits = 0 .. %u .. %u .. %lu\n",
883 i
, j
, (unsigned long)v
[1].len
);
891 static int vrf_cat(dstr v
[])
894 poly1305_ctx ctx
, cc
[3];
899 if (v
[0].len
!= 16) { fprintf(stderr
, "bad key length\n"); exit(2); }
900 if (v
[1].len
!= 16) { fprintf(stderr
, "bad mask length\n"); exit(2); }
901 if (v
[5].len
!= 16) { fprintf(stderr
, "bad tag length\n"); exit(2); }
902 dstr_ensure(&t
, 16); t
.len
= 16;
904 poly1305_keyinit(&k
, v
[0].buf
, v
[0].len
);
905 poly1305_macinit(&ctx
, &k
, v
[1].buf
);
906 for (i
= 0; i
< 3; i
++) {
907 poly1305_macinit(&cc
[i
], &k
, 0);
908 poly1305_hash(&cc
[i
], v
[i
+ 2].buf
, v
[i
+ 2].len
);
910 for (i
= 0; i
< 2; i
++) {
912 poly1305_concat(&ctx
, &cc
[1], &cc
[2]);
913 poly1305_concat(&ctx
, &cc
[0], &ctx
);
915 poly1305_concat(&ctx
, &cc
[0], &cc
[1]);
916 poly1305_concat(&ctx
, &ctx
, &cc
[2]);
918 poly1305_done(&ctx
, t
.buf
);
919 if (memcmp(t
.buf
, v
[5].buf
, 16) != 0) {
920 fprintf(stderr
, "failed...");
921 fprintf(stderr
, "\n\tkey = "); type_hex
.dump(&v
[0], stderr
);
922 fprintf(stderr
, "\n\tmask = "); type_hex
.dump(&v
[1], stderr
);
923 fprintf(stderr
, "\n\tmsg[0] = "); type_hex
.dump(&v
[2], stderr
);
924 fprintf(stderr
, "\n\tmsg[1] = "); type_hex
.dump(&v
[3], stderr
);
925 fprintf(stderr
, "\n\tmsg[2] = "); type_hex
.dump(&v
[4], stderr
);
926 fprintf(stderr
, "\n\texp = "); type_hex
.dump(&v
[5], stderr
);
927 fprintf(stderr
, "\n\tcalc = "); type_hex
.dump(&t
, stderr
);
928 fprintf(stderr
, "\n\tassoc = %s\n",
929 !i ?
"msg[0] || (msg[1] || msg[2])" :
930 "(msg[0] || msg[1]) || msg[2]");
937 static const struct test_chunk tests
[] = {
938 { "poly1305-hash", vrf_hash
,
939 { &type_hex
, &type_hex
, &type_hex
, &type_hex
} },
940 { "poly1305-cat", vrf_cat
,
941 { &type_hex
, &type_hex
, &type_hex
, &type_hex
, &type_hex
, &type_hex
} },
945 int main(int argc
, char *argv
[])
947 test_run(argc
, argv
, tests
, SRCDIR
"/t/poly1305");
953 /*----- That's all, folks -------------------------------------------------*/