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_10; truncate it to 11
234 * bits, and add the carry onto u_11. Truncate u_11 to 10 bits, and add
235 * five times the carry onto u_0. And so on.
237 * The carry is larger than the pieces we're leaving behind. Let c_i be
238 * the high portion of u_i, to be carried onto u_{i+1}. I claim that c_i <
239 * 2557*2^10. Then the carry /into/ any u_i is at most 12785*2^10 < 2^24
240 * (allowing for the reduction as we carry from u_11 to u_0), and u_i after
241 * carry is bounded above by 636*2^22 + 12785*2^10 < 2557*2^20. Hence, the
242 * carry out is at most 2557*2^10, as claimed.
244 * Once we reach u_10 for the second time, we start with u_10 < 2^11. The
245 * carry into u_10 is at most 2557*2^10 < 1279*2^11 as calculated above; so
246 * the carry out into u_11 is at most 1280. Since u_11 < 2^10 prior to
247 * this carry in, all of the u_i are now bounded above by 2^11. The final
248 * reduction therefore only needs a conditional subtraction.
250 { c
= u
[10] >> 11; u
[10] &= M11
; }
251 { u
[11] += c
; c
= u
[11] >> 10; u
[11] &= M10
; }
252 { u
[0] += 5*c
; c
= u
[0] >> 11; u
[0] &= M11
; }
253 for (i
= 1; i
< 5; i
++) { u
[i
] += c
; c
= u
[i
] >> 11; u
[i
] &= M11
; }
254 { u
[5] += c
; c
= u
[5] >> 10; u
[5] &= M10
; }
255 for (i
= 6; i
< 11; i
++) { u
[i
] += c
; c
= u
[i
] >> 11; u
[i
] &= M11
; }
259 /* General multiplication. */
260 static void mul(felt z
, const felt x
, const felt y
)
262 /* Initial bounds: we assume x_i < 3*2^11, and y_i < 2^12. On exit,
269 /* Do the main multiplication. After this, we shall have
271 * { 2^22 (636 - 184 i) for 0 <= i < 6
273 * { 2^22 (732 - 60 i) for 6 <= i < 12
275 * In particular, u_0 < 636*2^22 < 2^32, and u_11 < 72*2^22.
277 * The irregularly positioned pieces are annoying. Because we fold the
278 * reduction into the multiplication, it's also important to see where the
279 * reduced products fit. Finally, products don't align with the piece
280 * boundaries, and sometimes need to be doubled. The following table
281 * tracks all of this.
283 * piece width offset second
297 * The next table tracks exactly which products end up being multiplied by
298 * which constants and accumulated into which destination pieces.
300 * u_k = t_i r_j + 2 t_i r_j + 5 t_i r_j + 10 t_i r_j
301 * 0 0/0 -- 6/6 1-5/11-7 7-11/5-1
302 * 1 0-1/1-0 -- 6-7/7-6 2-5/11-8 8-11/5-2
303 * 2 0-2/2-0 -- 6-8/8-6 3-5/11-9 9-11/5-3
304 * 3 0-3/3-0 -- 6-9/9-6 4-5/11-10 10-11/5-4
305 * 4 0-4/4-0 -- 6-10/10-6 5/11 11/5
306 * 5 0-5/5-0 -- 6-11/11-6 --
307 * 6 0/6 6/0 1-5/5-1 -- 7-11/11-7
308 * 7 0-1/7-6 6-7/1-0 2-5/5-2 -- 8-11/11-8
309 * 8 0-2/8-6 6-8/2-0 3-5/5-3 -- 9-11/11-9
310 * 9 0-3/9-6 6-9/3-0 4-5/5-4 -- 10-11/11-10
311 * 10 0-4/10-6 6-10/4-0 5/5 -- 11/11
312 * 11 0-11/11-0 -- -- --
314 * And, finally, trying to bound the multiple of 6*2^22 in each destination
315 * piece is fiddly, so here's a tableau showing the calculation.
317 * k 1* + 2* + 5* +10* = 1* + 5* =
318 * 0 1 -- 1 10 1 21 106
324 * 6 2 5 -- 5 12 10 62
328 * 10 10 1 -- 1 12 2 22
329 * 11 12 -- -- -- 12 0 12
332 for (i
= 0; i
< 12; i
++) u
[i
] = 0;
334 #define M(i, j) ((uint32)x[i]*y[j])
336 /* Product terms we must multiply by 10. */
337 for (k
= 0; k
< 5; k
++) {
338 for (i
= k
+ 1; i
< 6; i
++) {
340 u
[k
] += M(i
, j
) + M(j
, i
);
341 u
[k
+ 6] += M(i
+ 6, j
);
344 for (k
= 0; k
< 5; k
++) u
[k
] *= 2;
345 for (k
= 6; k
< 11; k
++) u
[k
] *= 5;
347 /* Product terms we must multiply by 5. */
348 for (k
= 0; k
< 6; k
++) {
349 for (i
= k
+ 6; i
>= 6; i
--) {
354 for (k
= 0; k
< 6; k
++) u
[k
] *= 5;
356 /* Product terms we must multiply by 2. */
357 for (k
= 6; k
< 11; k
++) {
358 for (i
= k
- 5; i
< 6; i
++) {
363 for (k
= 6; k
< 11; k
++) u
[k
] *= 2;
365 /* Remaining product terms. */
366 for (k
= 0; k
< 6; k
++) {
367 for (i
= k
; i
< 6; i
--) {
370 u
[k
+ 6] += M(i
+ 6, j
) + M(i
, j
+ 6);
376 /* Do the reduction. Currently, `carry_reduce' does more than we need, but
381 /* Done. Write out the answer. */
382 for (i
= 0; i
< 12; i
++) z
[i
] = u
[i
];
385 /* General squaring, used by `concat'. */
386 static void sqr(felt z
, const felt x
)
389 /* Multiplication by r. */
390 static void mul_r(const poly1305_ctx
*ctx
, felt z
, const felt x
)
391 { mul(z
, x
, ctx
->k
.u
.p11
.r
); }
395 /*----- Interface functions -----------------------------------------------*/
397 /* --- @poly1305_keyinit@ --- *
399 * Arguments: @poly1305_key *key@ = key structure to fill in
400 * @const void *k@ = pointer to key material
401 * @size_t ksz@ = length of key (must be @POLY1305_KEYSZ == 16@)
405 * Use: Records a Poly1305 key and performs (minimal)
409 void poly1305_keyinit(poly1305_key
*key
, const void *k
, size_t ksz
)
412 #if POLY1305_IMPL == 11
416 KSZ_ASSERT(poly1305
, ksz
);
418 #if POLY1305_IMPL == 26
419 uint32 r0
= LOAD32_L(r
+ 0), r1
= LOAD32_L(r
+ 4),
420 r2
= LOAD32_L(r
+ 8), r3
= LOAD32_L(r
+ 12);
422 r0
&= 0x0fffffff; r1
&= 0x0ffffffc; r2
&= 0x0ffffffc; r3
&= 0x0ffffffc;
423 key
->u
.p26
.r0
= P26W0(r
); key
->u
.p26
.r1
= P26W1(r
);
424 key
->u
.p26
.r2
= P26W2(r
); key
->u
.p26
.r3
= P26W3(r
);
425 key
->u
.p26
.r4
= P26W4(r
);
427 key
->u
.p26
.rr1
= 5*key
->u
.p26
.r1
; key
->u
.p26
.rr2
= 5*key
->u
.p26
.r2
;
428 key
->u
.p26
.rr3
= 5*key
->u
.p26
.r3
; key
->u
.p26
.rr4
= 5*key
->u
.p26
.r4
;
432 rr
[ 4] &= 0xfc; rr
[ 7] &= 0x0f;
433 rr
[ 8] &= 0xfc; rr
[11] &= 0x0f;
434 rr
[12] &= 0xfc; rr
[15] &= 0x0f;
435 load_p11(key
->u
.p11
.r
, rr
);
439 /* --- @poly1305_macinit@ --- *
441 * Arguments: @poly1305_ctx *ctx@ = MAC context to fill in
442 * @const poly1305_key *key@ = pointer to key structure to use
443 * @const void *iv@ = pointer to mask string
447 * Use: Initializes a MAC context for use. The key can be discarded
450 * It is permitted for @iv@ to be null, though it is not then
451 * possible to complete the MAC computation on @ctx@. The
452 * resulting context may still be useful, e.g., as an operand to
456 void poly1305_macinit(poly1305_ctx
*ctx
,
457 const poly1305_key
*key
, const void *iv
)
460 #if POLY1305_IMPL == 26
461 uint32 s0
, s1
, s2
, s3
;
466 #if POLY1305_IMPL == 26
468 s0
= LOAD32_L(s
+ 0); s1
= LOAD32_L(s
+ 4);
469 s2
= LOAD32_L(s
+ 8); s3
= LOAD32_L(s
+ 12);
470 ctx
->u
.p26
.s0
= P26W0(s
); ctx
->u
.p26
.s1
= P26W1(s
);
471 ctx
->u
.p26
.s2
= P26W2(s
); ctx
->u
.p26
.s3
= P26W3(s
);
472 ctx
->u
.p26
.s4
= P26W4(s
);
474 ctx
->u
.p26
.h
[0] = ctx
->u
.p26
.h
[1] = ctx
->u
.p26
.h
[2] =
475 ctx
->u
.p26
.h
[3] = ctx
->u
.p26
.h
[4] = 0;
477 if (s
) load_p11(ctx
->u
.p11
.s
, s
);
478 for (i
= 0; i
< 12; i
++) ctx
->u
.p11
.h
[i
] = 0;
485 /* --- @poly1305_copy@ --- *
487 * Arguments: @poly1305_ctx *to@ = destination context
488 * @const poly1305_ctx *from@ = source context
492 * Use: Duplicates a Poly1305 MAC context. The destination need not
493 * have been initialized. Both contexts can be used
494 * independently afterwards.
497 void poly1305_copy(poly1305_ctx
*ctx
, const poly1305_ctx
*from
)
500 /* --- @poly1305_hash@ --- *
502 * Arguments: @poly1305_ctx *ctx@ = MAC context to update
503 * @const void *p@ = pointer to message data
504 * @size_t sz@ = length of message data
508 * Use: Processes a chunk of message. The message pieces may have
509 * arbitrary lengths, and may be empty.
512 static void update_full(poly1305_ctx
*ctx
, const octet
*p
)
515 #if POLY1305_IMPL == 26
517 m0
= LOAD32_L(p
+ 0), m1
= LOAD32_L(p
+ 4),
518 m2
= LOAD32_L(p
+ 8), m3
= LOAD32_L(p
+ 12);
520 t
[0] = ctx
->u
.p26
.h
[0] + P26W0(m
);
521 t
[1] = ctx
->u
.p26
.h
[1] + P26W1(m
);
522 t
[2] = ctx
->u
.p26
.h
[2] + P26W2(m
);
523 t
[3] = ctx
->u
.p26
.h
[3] + P26W3(m
);
524 t
[4] = ctx
->u
.p26
.h
[4] + P26W4(m
) + 0x01000000;
528 load_p11(t
, p
); t
[11] += 0x100;
529 for (i
= 0; i
< 12; i
++) t
[i
] += ctx
->u
.p11
.h
[i
];
532 mul_r(ctx
, ctx
->u
.P
.h
, t
);
536 void poly1305_hash(poly1305_ctx
*ctx
, const void *p
, size_t sz
)
542 if (sz
< 16 - ctx
->nbuf
) {
543 memcpy(ctx
->buf
+ ctx
->nbuf
, p
, sz
);
548 memcpy(ctx
->buf
+ ctx
->nbuf
, pp
, n
);
549 update_full(ctx
, ctx
->buf
);
553 update_full(ctx
, pp
);
556 if (sz
) memcpy(ctx
->buf
, pp
, sz
);
560 /* --- @poly1305_flush@ --- *
562 * Arguments: @poly1305_ctx *ctx@ = MAC context to flush
566 * Use: Forces any buffered message data in the context to be
567 * processed. This has no effect if the message processed so
568 * far is a whole number of blocks. Flushing is performed
569 * automatically by @poly1305_done@, but it may be necessary to
570 * force it by hand when using @poly1305_concat@.
572 * Flushing a partial block has an observable effect on the
573 * computation: the resulting state is (with high probability)
574 * dissimilar to any state reachable with a message which is a
575 * whole number of blocks long.
578 void poly1305_flush(poly1305_ctx
*ctx
)
581 #if POLY1305_IMPL == 26
582 uint32 m0
, m1
, m2
, m3
;
587 if (!ctx
->nbuf
) return;
588 ctx
->buf
[ctx
->nbuf
++] = 1; memset(ctx
->buf
+ ctx
->nbuf
, 0, 16 - ctx
->nbuf
);
589 #if POLY1305_IMPL == 26
590 m0
= LOAD32_L(ctx
->buf
+ 0); m1
= LOAD32_L(ctx
->buf
+ 4);
591 m2
= LOAD32_L(ctx
->buf
+ 8); m3
= LOAD32_L(ctx
->buf
+ 12);
593 t
[0] = ctx
->u
.p26
.h
[0] + P26W0(m
);
594 t
[1] = ctx
->u
.p26
.h
[1] + P26W1(m
);
595 t
[2] = ctx
->u
.p26
.h
[2] + P26W2(m
);
596 t
[3] = ctx
->u
.p26
.h
[3] + P26W3(m
);
597 t
[4] = ctx
->u
.p26
.h
[4] + P26W4(m
);
599 load_p11(t
, ctx
->buf
);
600 for (i
= 0; i
< 12; i
++) t
[i
] += ctx
->u
.p11
.h
[i
];
603 mul_r(ctx
, ctx
->u
.P
.h
, t
);
608 /* --- @poly1305_concat@ --- *
610 * Arguments: @poly1305_ctx *ctx@ = destination context
611 * @const poly1305_ctx *prefix, *suffix@ = two operand contexts
615 * Use: The two operand contexts @prefix@ and @suffix@ represent
616 * processing of two messages %$m$% and %$m'$%; the effect is to
617 * set @ctx@ to the state corresponding to their concatenation
620 * All three contexts must have been initialized using the same
621 * key value (though not necessarily from the same key
622 * structure). The mask values associated with the input
623 * contexts are irrelevant. The @prefix@ message %$m$% must be
624 * a whole number of blocks long: this can be arranged by
625 * flushing the context. The @suffix@ message need not be a
626 * whole number of blocks long. All of the contexts remain
627 * operational and can be used independently afterwards.
630 void poly1305_concat(poly1305_ctx
*ctx
,
631 const poly1305_ctx
*prefix
, const poly1305_ctx
*suffix
)
633 /* Assume that lengths are public, so it's safe to behave conditionally on
634 * the bits of ctx->count.
639 #if POLY1305_IMPL == 26
640 uint32 x0
, x1
, x2
, x3
, x4
, y0
, y1
, y2
, y3
, y4
;
645 /* We can only concatenate if the prefix is block-aligned. */
646 assert(!prefix
->nbuf
);
648 /* The hash for a message m = m_{k-1} m_{k-2} ... m_1 m_0 is h_r(m) =
649 * SUM_{0<=i<k} m_i r^{i+1}. If we have two messages, m, m', of lengths k
650 * and k' blocks respectively, then
652 * h_r(m || m') = SUM_{0<=i<k} m_i r^{k'+i+1} +
653 * SUM_{0<=i<k'} m'_i r^{i+1}
654 * = r^{k'} h_r(m) + h_r(m')
656 * This is simple left-to-right square-and-multiply exponentiation.
660 #if POLY1305_IMPL == 26
661 x
[1] = x
[2] = x
[3] = x
[4] = 0;
663 for (i
= 1; i
< 12; i
++) x
[i
] = 0;
665 #define BIT (1ul << (ULONG_BITS - 1))
668 while (!(n
& BIT
)) { n
<<= 1; i
--; }
669 mul_r(prefix
, x
, x
); n
<<= 1; i
--;
670 while (i
--) { sqr(x
, x
); if (n
& BIT
) mul_r(prefix
, x
, x
); n
<<= 1; }
673 mul(x
, prefix
->u
.P
.h
, x
);
675 /* Add on the suffix hash. */
676 #if POLY1305_IMPL == 26
677 /* We're going to add the two hashes elementwise. Both h' = h_r(m') and
678 * x = r^{k'} h_r(m) are bounded above by 2^27, so the sum will be bounded
679 * by 2^28; but this is too large to leave in the accumulator. (Strictly,
680 * we could get away with it, but the caller can in theory chain an
681 * arbitrary number of concatenations and expect us to cope, and we'd
682 * definitely overflow eventually.) So we reduce. Since the excess is so
683 * small, a single round of `CARRY_REDUCE' is enough.
685 x0
= x
[0] + suffix
->u
.p26
.h
[0]; x1
= x
[1] + suffix
->u
.p26
.h
[1];
686 x2
= x
[2] + suffix
->u
.p26
.h
[2]; x3
= x
[3] + suffix
->u
.p26
.h
[3];
687 x4
= x
[4] + suffix
->u
.p26
.h
[4];
689 ctx
->u
.p26
.h
[0] = y0
; ctx
->u
.p26
.h
[1] = y1
; ctx
->u
.p26
.h
[2] = y2
;
690 ctx
->u
.p26
.h
[3] = y3
; ctx
->u
.p26
.h
[4] = y4
;
692 /* We'll add the two hashes elementwise and have to reduce again. The
693 * numbers are different, but the reasoning is basically the same.
695 for (i
= 0; i
< 12; i
++) y
[i
] = x
[i
] + suffix
->u
.p11
.h
[i
];
697 for (i
= 0; i
< 12; i
++) ctx
->u
.p11
.h
[i
] = y
[i
];
700 /* Copy the remaining pieces of the context to set up the result. */
702 memcpy(ctx
->buf
, suffix
->buf
, suffix
->nbuf
);
703 ctx
->nbuf
= suffix
->nbuf
;
705 ctx
->count
= prefix
->count
+ suffix
->count
;
708 /* --- @poly1305_done@ --- *
710 * Arguments: @poly1305_ctx *ctx@ = MAC context to finish
711 * @void *h@ = buffer to write the tag to
715 * Use: Completes a Poly1305 MAC tag computation.
718 void poly1305_done(poly1305_ctx
*ctx
, void *h
)
722 #if POLY1305_IMPL == 26
724 uint32 h0
, h1
, h2
, h3
, h4
, hh0
, hh1
, hh2
, hh3
, hh4
;
726 /* If there's anything left over in the buffer, pad it to form a final
727 * coefficient and update the evaluation one last time.
731 /* Collect the final hash state. */
732 h0
= ctx
->u
.p26
.h
[0];
733 h1
= ctx
->u
.p26
.h
[1];
734 h2
= ctx
->u
.p26
.h
[2];
735 h3
= ctx
->u
.p26
.h
[3];
736 h4
= ctx
->u
.p26
.h
[4];
738 /* Reduce the final value mod 2^130 - 5. First pass: set h <- h +
739 * 5 floor(h/2^130). After this, the low pieces of h will be normalized:
740 * 0 <= h_i < 2^26 for 0 <= i < 4; and 0 <= h_4 < 2^26 + 1. In the
741 * (highly unlikely) event that h_4 >= 2^26, set c and truncate to 130
744 c
= h4
>> 26; h4
&= M26
;
745 h0
+= 5*c
; c
= h0
>> 26; h0
&= M26
;
746 h1
+= c
; c
= h1
>> 26; h1
&= M26
;
747 h2
+= c
; c
= h2
>> 26; h2
&= M26
;
748 h3
+= c
; c
= h3
>> 26; h3
&= M26
;
749 h4
+= c
; c
= h4
>> 26; h4
&= M26
;
751 /* Calculate h' = h - (2^130 - 5). If h' >= 0 then t ends up 1; otherwise
754 t
= h0
+ 5; hh0
= t
&M26
; t
>>= 26;
755 t
+= h1
; hh1
= t
&M26
; t
>>= 26;
756 t
+= h2
; hh2
= t
&M26
; t
>>= 26;
757 t
+= h3
; hh3
= t
&M26
; t
>>= 26;
758 t
+= h4
; hh4
= t
&M26
; t
>>= 26;
760 /* Keep the subtraction result above if t or c is set. */
762 h0
= (hh0
&m_sub
) | (h0
&~m_sub
);
763 h1
= (hh1
&m_sub
) | (h1
&~m_sub
);
764 h2
= (hh2
&m_sub
) | (h2
&~m_sub
);
765 h3
= (hh3
&m_sub
) | (h3
&~m_sub
);
766 h4
= (hh4
&m_sub
) | (h4
&~m_sub
);
768 /* Add the mask onto the hash result. */
769 t
= h0
+ ctx
->u
.p26
.s0
; h0
= t
&M26
; t
>>= 26;
770 t
+= h1
+ ctx
->u
.p26
.s1
; h1
= t
&M26
; t
>>= 26;
771 t
+= h2
+ ctx
->u
.p26
.s2
; h2
= t
&M26
; t
>>= 26;
772 t
+= h3
+ ctx
->u
.p26
.s3
; h3
= t
&M26
; t
>>= 26;
773 t
+= h4
+ ctx
->u
.p26
.s4
; h4
= t
&M26
; t
>>= 26;
775 /* Convert this mess back into 32-bit words. We lose the top two bits,
778 h0
= (h0
>> 0) | ((h1
& 0x0000003f) << 26);
779 h1
= (h1
>> 6) | ((h2
& 0x00000fff) << 20);
780 h2
= (h2
>> 12) | ((h3
& 0x0003ffff) << 14);
781 h3
= (h3
>> 18) | ((h4
& 0x00ffffff) << 8);
784 STORE32_L(p
+ 0, h0
); STORE32_L(p
+ 4, h1
);
785 STORE32_L(p
+ 8, h2
); STORE32_L(p
+ 12, h3
);
787 uint16 hh
[12], hi
[12], c
, t
, m_sub
;
791 /* If there's anything left over in the buffer, pad it to form a final
792 * coefficient and update the evaluation one last time.
796 /* Collect the final hash state. */
797 for (i
= 0; i
< 12; i
++) hh
[i
] = ctx
->u
.p11
.h
[i
];
799 /* Reduce the final value mod 2^130 - 5. First pass: set h <- h +
800 * 5 floor(h/2^130). After this, the low pieces of h will be normalized:
801 * 0 <= h_i < 2^{w_i} for 0 <= i < 11; and 0 <= h_{11} < 2^10 + 1. In the
802 * (highly unlikely) event that h_{11} >= 2^10, set c and truncate to 130
805 c
= 5*(hh
[11] >> 10); hh
[11] &= M10
;
806 for (i
= 0; i
< 12; i
++) {
807 if (i
== 5 || i
== 11) { c
+= hh
[i
]; hh
[i
] = c
&M10
; c
>>= 10; }
808 else { c
+= hh
[i
]; hh
[i
] = c
&M11
; c
>>= 11; }
811 /* Calculate h' = h - (2^130 - 5). If h' >= 0 then t ends up 1; otherwise
814 for (i
= 0, t
= 5; i
< 12; i
++) {
816 if (i
== 5 || i
== 11) { hi
[i
] = t
&M10
; t
>>= 10; }
817 else { hi
[i
] = t
&M11
; t
>>= 11; }
820 /* Keep the subtraction result above if t or c is set. */
822 for (i
= 0; i
< 12; i
++) hh
[i
] = (hi
[i
]&m_sub
) | (hh
[i
]&~m_sub
);
824 /* Add the mask onto the hash result. */
825 for (i
= 0, t
= 0; i
< 12; i
++) {
826 t
+= hh
[i
] + ctx
->u
.p11
.s
[i
];
827 if (i
== 5 || i
== 11) { hh
[i
] = t
&M10
; t
>>= 10; }
828 else { hh
[i
] = t
&M11
; t
>>= 11; }
831 /* Convert this mess back into bytes. We lose the top two bits, but that's
834 for (i
= j
= n
= 0, a
= 0; i
< 16; i
++) {
837 n
+= (j
== 5 || j
== 11) ?
10 : 11;
840 p
[i
] = a
&0xff; a
>>= 8; n
-= 8;
846 /*----- Test rig ----------------------------------------------------------*/
850 #include <mLib/testrig.h>
852 static int vrf_hash(dstr v
[])
859 if (v
[0].len
!= 16) { fprintf(stderr
, "bad key length\n"); exit(2); }
860 if (v
[1].len
!= 16) { fprintf(stderr
, "bad mask length\n"); exit(2); }
861 if (v
[3].len
!= 16) { fprintf(stderr
, "bad tag length\n"); exit(2); }
862 dstr_ensure(&t
, 16); t
.len
= 16;
864 poly1305_keyinit(&k
, v
[0].buf
, v
[0].len
);
865 for (i
= 0; i
< v
[2].len
; i
++) {
866 for (j
= i
; j
< v
[2].len
; j
++) {
867 poly1305_macinit(&ctx
, &k
, v
[1].buf
);
868 poly1305_hash(&ctx
, v
[2].buf
, i
);
869 poly1305_hash(&ctx
, v
[2].buf
+ i
, j
- i
);
870 poly1305_hash(&ctx
, v
[2].buf
+ j
, v
[2].len
- j
);
871 poly1305_done(&ctx
, t
.buf
);
872 if (memcmp(t
.buf
, v
[3].buf
, 16) != 0) {
873 fprintf(stderr
, "failed...");
874 fprintf(stderr
, "\n\tkey = "); type_hex
.dump(&v
[0], stderr
);
875 fprintf(stderr
, "\n\tmask = "); type_hex
.dump(&v
[1], stderr
);
876 fprintf(stderr
, "\n\tmsg = "); type_hex
.dump(&v
[2], stderr
);
877 fprintf(stderr
, "\n\texp = "); type_hex
.dump(&v
[3], stderr
);
878 fprintf(stderr
, "\n\tcalc = "); type_hex
.dump(&t
, stderr
);
879 fprintf(stderr
, "\n\tsplits = 0 .. %u .. %u .. %lu\n",
880 i
, j
, (unsigned long)v
[1].len
);
888 static int vrf_cat(dstr v
[])
891 poly1305_ctx ctx
, cc
[3];
896 if (v
[0].len
!= 16) { fprintf(stderr
, "bad key length\n"); exit(2); }
897 if (v
[1].len
!= 16) { fprintf(stderr
, "bad mask length\n"); exit(2); }
898 if (v
[5].len
!= 16) { fprintf(stderr
, "bad tag length\n"); exit(2); }
899 dstr_ensure(&t
, 16); t
.len
= 16;
901 poly1305_keyinit(&k
, v
[0].buf
, v
[0].len
);
902 poly1305_macinit(&ctx
, &k
, v
[1].buf
);
903 for (i
= 0; i
< 3; i
++) {
904 poly1305_macinit(&cc
[i
], &k
, 0);
905 poly1305_hash(&cc
[i
], v
[i
+ 2].buf
, v
[i
+ 2].len
);
907 for (i
= 0; i
< 2; i
++) {
909 poly1305_concat(&ctx
, &cc
[1], &cc
[2]);
910 poly1305_concat(&ctx
, &cc
[0], &ctx
);
912 poly1305_concat(&ctx
, &cc
[0], &cc
[1]);
913 poly1305_concat(&ctx
, &ctx
, &cc
[2]);
915 poly1305_done(&ctx
, t
.buf
);
916 if (memcmp(t
.buf
, v
[5].buf
, 16) != 0) {
917 fprintf(stderr
, "failed...");
918 fprintf(stderr
, "\n\tkey = "); type_hex
.dump(&v
[0], stderr
);
919 fprintf(stderr
, "\n\tmask = "); type_hex
.dump(&v
[1], stderr
);
920 fprintf(stderr
, "\n\tmsg[0] = "); type_hex
.dump(&v
[2], stderr
);
921 fprintf(stderr
, "\n\tmsg[1] = "); type_hex
.dump(&v
[3], stderr
);
922 fprintf(stderr
, "\n\tmsg[2] = "); type_hex
.dump(&v
[4], stderr
);
923 fprintf(stderr
, "\n\texp = "); type_hex
.dump(&v
[5], stderr
);
924 fprintf(stderr
, "\n\tcalc = "); type_hex
.dump(&t
, stderr
);
925 fprintf(stderr
, "\n\tassoc = %s\n",
926 !i ?
"msg[0] || (msg[1] || msg[2])" :
927 "(msg[0] || msg[1]) || msg[2]");
934 static const struct test_chunk tests
[] = {
935 { "poly1305-hash", vrf_hash
,
936 { &type_hex
, &type_hex
, &type_hex
, &type_hex
} },
937 { "poly1305-cat", vrf_cat
,
938 { &type_hex
, &type_hex
, &type_hex
, &type_hex
, &type_hex
, &type_hex
} },
942 int main(int argc
, char *argv
[])
944 test_run(argc
, argv
, tests
, SRCDIR
"/t/poly1305");
950 /*----- That's all, folks -------------------------------------------------*/