[PATCH v3 2/2] lib/crypto: tests: Add Poly1305 split-update carry regression test
Jason A. Donenfeld
Jason at zx2c4.com
Fri Oct 9 09:19:27 PDT 2026
On Fri, Oct 9, 2026 at 2:54 PM Eric Biggers <ebiggers at kernel.org> wrote:
>
> Add a test case which reproduces the bug fixed by commit f5602ce803dc
> ("lib/crypto: arm64: Fix lost Poly1305 carry when resuming NEON state").
> It is written in a fairly general way, such that it should also be able
> to reproduce similar bugs in other implementations.
>
> Update the comment on test_poly1305_allones_keys_and_message() to more
> accurately describe what it does and differentiate it from the new test.
>
> Signed-off-by: Eric Biggers <ebiggers at kernel.org>
> ---
> lib/crypto/tests/poly1305_kunit.c | 97 ++++++++++++++++++++++++++++---
> 1 file changed, 88 insertions(+), 9 deletions(-)
>
> diff --git a/lib/crypto/tests/poly1305_kunit.c b/lib/crypto/tests/poly1305_kunit.c
> index f3cb6245bc29..d065d8b6442f 100644
> --- a/lib/crypto/tests/poly1305_kunit.c
> +++ b/lib/crypto/tests/poly1305_kunit.c
> @@ -55,16 +55,17 @@ static int poly1305_suite_init(struct kunit_suite *suite)
> * - Using an all-one-bits r_key tests the key clamping.
> * - Using an all-one-bits s_key tests carries in implementations of the
> * addition mod 2**128 during finalization.
> - * - Using all-one-bits message, and to a lesser extent r_key, tends to maximize
> - * any intermediate accumulator values. This increases the chance of
> - * detecting bugs that occur only in rare cases where the accumulator values
> - * get very large, for example the bug fixed by commit 678cce4019d746da
> - * ("crypto: x86/poly1305 - fix overflow during partial reduction").
> + * - Using all-one-bits message and r_key results in large values for the
> + * internal products of r_key by (accumulator + message block). This
> + * increases the chance of detecting bugs that occur only in rare cases where
> + * the sum of these internal products is very large, for example the bug fixed
> + * by commit 678cce4019d746da ("crypto: x86/poly1305 - fix overflow during
> + * partial reduction").
> *
> - * Accumulator overflow bugs may be specific to particular update lengths (in
> - * blocks) and/or particular values of the previous acculumator. Note that the
> - * accumulator starts at 0 which gives the lowest chance of an overflow. Thus,
> - * a single all-one-bits test vector may be insufficient.
> + * Bugs with the handling of large internal product sums may be specific to
> + * particular update lengths (in blocks) and/or require that the accumulator
> + * also have a large value. Note that the accumulator starts at 0. Thus, a
> + * single all-one-bits test vector may be insufficient.
> *
> * Considering that, do the following test: continuously update a single
> * Poly1305 context with all-one-bits data of varying lengths (0, 16, 32, ...,
> @@ -141,10 +142,88 @@ static void test_poly1305_reduction_edge_cases(struct kunit *test)
> }
> }
>
> +/*
> + * Test that Poly1305 MACs are computed correctly when r_key=1, s_key=0, and the
> + * message consists of all-ones blocks.
> + *
> + * With r_key=1 and s_key=0, Poly1305 degrades to the sum of the padded blocks
> + * mod 2**130 - 5, then reduced mod 2**128. A padded all-ones block maps to
> + * 2**128 + (2**128 - 1) = 2**129 - 1. Two such blocks sum to 2**130 - 2, which
> + * is congruent to 3 mod 2**130 - 5. Thus, the expected MAC is just 3 *
> + * floor(nblocks / 2), minus 1 if nblocks is odd, then reduced mod 2**128. If
> + * nblocks == 1 this is 2**128 - 1, otherwise it's just a small integer.
> + *
> + * Inside the Poly1305 implementation in this case, the multiplication does
> + * nothing and each block just adds 2**129 - 1 to the accumulator. Without the
> + * multiplication to mix things up, this results in some interesting values
> + * being reached where the limbs are at or near their maximum values, even after
> + * (lazy) reduction. This can reproduce bugs that happen only in such cases.
> + *
> + * For example, this test case reproduces the bug fixed by commit f5602ce803dc
> + * ("lib/crypto: arm64: Fix lost Poly1305 carry when resuming NEON state").
> + *
> + * However, reaching that bug required two consecutive updates: one with >= 8
> + * blocks to cause NEON code to be used and leave the accumulator in base 2**26
> + * with its limbs in a certain pattern, then one with an odd number of blocks >=
> + * 9 to cause NEON to be used again, but first processing one block using scalar
> + * code as a special case, triggering a conversion to base 2**64 where the carry
> + * into the 2**128 bit was lost. To cover this and other similar edge cases
> + * that may exist in other Poly1305 implementations, just test all possible
> + * block-aligned splits between three poly1305_update() calls.
> + */
> +static void test_poly1305_split_update_carry(struct kunit *test)
> +{
> + static const u8 key[POLY1305_KEY_SIZE] = { 1 }; /* r_key=1, s_key=0 */
> + /*
> + * Use max_nblocks=66 so that it's a bit more than twice the AVX-512
> + * threshold of 32 blocks.
> + */
> + const int max_nblocks = 66;
> + u8 *data = alloc_buf(test, max_nblocks * POLY1305_BLOCK_SIZE);
> + u8 expected_mac[POLY1305_DIGEST_SIZE];
> + u8 actual_mac[POLY1305_DIGEST_SIZE];
> + struct poly1305_desc_ctx ctx;
> +
> + KUNIT_ASSERT_LE(test, 3 * (max_nblocks / 2), U8_MAX);
> +
> + memset(data, 0xff, max_nblocks * POLY1305_BLOCK_SIZE);
> +
> + for (int nblocks = 0; nblocks <= max_nblocks; nblocks++) {
> + size_t len = nblocks * POLY1305_BLOCK_SIZE;
> +
> + expected_mac[0] = 3 * (nblocks / 2) - (nblocks % 2);
> + memset(&expected_mac[1], nblocks == 1 ? 0xff : 0,
> + POLY1305_DIGEST_SIZE - 1);
> + for (size_t part1_len = 0; part1_len <= len;
> + part1_len += POLY1305_BLOCK_SIZE) {
> + for (size_t part2_len = 0; part2_len <= len - part1_len;
> + part2_len += POLY1305_BLOCK_SIZE) {
> + size_t part3_len = len - part1_len - part2_len;
> +
> + poly1305_init(&ctx, key);
> + poly1305_update(&ctx, data, part1_len);
> + poly1305_update(&ctx, &data[part1_len],
> + part2_len);
> + poly1305_update(&ctx,
> + &data[part1_len + part2_len],
> + part3_len);
> + poly1305_final(&ctx, actual_mac);
> + KUNIT_ASSERT_MEMEQ_MSG(
> + test, actual_mac, expected_mac,
> + POLY1305_DIGEST_SIZE,
> + "Failed with nblocks=%d, part1_len=%zu, part2_len=%zu, part3_len=%zu",
> + nblocks, part1_len, part2_len,
> + part3_len);
> + }
> + }
> + }
> +}
> +
> static struct kunit_case poly1305_test_cases[] = {
> HASH_KUNIT_CASES,
> KUNIT_CASE(test_poly1305_allones_keys_and_message),
> KUNIT_CASE(test_poly1305_reduction_edge_cases),
> + KUNIT_CASE(test_poly1305_split_update_carry),
> KUNIT_CASE(benchmark_hash),
> {},
> };
Oh man. I feel like we've written so many other tests that are
_almost_ this one that I feel silly we didn't catch it ourselves. In
any case, I'm glad to see this here, and somewhat generically composed
too, to check for similar bugs elsewhere.
Reviewed-by: Jason A. Donenfeld <Jason at zx2c4.com>
More information about the linux-arm-kernel
mailing list