[PATCH v3 0/2] lib/crypto: arm64: Fix Poly1305 NEON resume carry loss

[PATCH v3 0/2] lib/crypto: arm64: Fix Poly1305 NEON resume carry loss

[Eric Biggers]

This series fixes a lost carry bit in the arm64 Poly1305 implementation,
then adds a regression test for it.

Compared to v2 sent by Jérémy Jean, I cleaned up the verbose
LLM-generated text in the commit message of the fix commit, and I
replaced the LLM-generated minimal test case with a more comprehensive
one similar to the existing test cases in the file.

Note: the second commit has references to the commit ID of the first,
which I'll fix up when applying.

Eric Biggers (1):
  lib/crypto: tests: Add Poly1305 split-update carry regression test

Jérémy Jean (1):
  lib/crypto: arm64: Fix lost Poly1305 carry when resuming NEON state

 lib/crypto/arm64/poly1305-armv8.pl |  2 +-
 lib/crypto/tests/poly1305_kunit.c  | 97 +++++++++++++++++++++++++++---
 2 files changed, 89 insertions(+), 10 deletions(-)


base-commit: 572af6872e520c7102e58362ef7cd7c2ed4342be
-- 
2.56.0

[PATCH v3 1/2] lib/crypto: arm64: Fix lost Poly1305 carry when resuming NEON state

[Eric Biggers]

From: Jérémy Jean <Jeremy.Jean@oss.cyber.gouv.fr>

When poly1305_blocks_neon() resumes from a base 2^26 accumulator and the
next update contains an odd number of full 16-byte blocks, it processes
one leading block through poly1305_mult() so that the remaining NEON
work has an even block count.  That requires converting the accumulator
to the base 2^64 form used by poly1305_mult().  The final ADC of that
conversion stores the carry into d2, but the following accumulation and
poly1305_mult() use h2.  If the conversion carries across bit 128, the
carry is dropped and the emitted tag is wrong.

This was introduced by Cryptogams commit 03dc4adf91c8
("arm/poly1305-armv*.pl: optimize branches."), which removed the
reduction that consumed d2 shortly before Linux imported the code.
OpenSSL's copy did not take that change.

The carry is possible because the NEON code stores the accumulator [h0,
h1, h2, h3, h4] in a lazily reduced, redundant base 2^26 form: its final
carry chain leaves h0, h2, h3 < 2^26, but h1 and h4 may slightly exceed
2^26 - 1.  For example, the reachable state

  h0 = 4
  h1 = 2^26
  h2 = 2^26 - 1
  h3 = 2^26 - 1
  h4 = 2^24 - 1

represents 2^128 + 4, so the conversion must produce the base 2^64 limbs
h0 = 4, h1 = 0, h2 = 1.  The low 64-bit word sums to 2^64 + 4 and the
middle 64-bit word (including the carry from the low word) sums to 2^64,
so both carry out.  However, the carry out of the middle word goes to
d2, leaving h2 = 0 and the value 4 instead of 2^128 + 4.

Given the above bounds, a carry across bit 128 happens exactly when
h1 >= 2^26, h2 = h3 = 2^26 - 1, and h4 mod 2^24 = 2^24 - 1.

Store the carry into h2, matching the other base 2^26 to base 2^64
conversions in poly1305_blocks() and poly1305_emit().

This bug causes an incorrect tag to be emitted.  However, this is
unlikely to happen in practice where Poly1305 is used with a random key,
since the random key tends to distribute the accumulator values
throughout their valid range.  There isn't an obvious way for an
attacker without knowledge of the r_key to cause [h0, h1, h2, h3, h4] to
land on the precise values where this bug occurs.

Fixes: f569ca164751 ("crypto: arm64/poly1305 - incorporate OpenSSL/CRYPTOGAMS NEON implementation")
Cc: stable@vger.kernel.org
Assisted-by: LLM
Signed-off-by: Jérémy Jean <Jeremy.Jean@oss.cyber.gouv.fr>
[EB: Rewrote the commit message to more clearly describe the bug and
 its impact, and removed a lot of pointless LLM-generated text.]
Signed-off-by: Eric Biggers <ebiggers@kernel.org>
---
 lib/crypto/arm64/poly1305-armv8.pl | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/crypto/arm64/poly1305-armv8.pl b/lib/crypto/arm64/poly1305-armv8.pl
index f1930c6b55ce..234398ff6b60 100644
--- a/lib/crypto/arm64/poly1305-armv8.pl
+++ b/lib/crypto/arm64/poly1305-armv8.pl
@@ -375,7 +375,7 @@ poly1305_blocks_neon:
 	adc	$h1,$h1,xzr
 	lsr	$h2,x14,#24
 	adds	$h1,$h1,x14,lsl#40
-	adc	$d2,$h2,xzr		// can be partially reduced...
+	adc	$h2,$h2,xzr		// preserve carry into top limb
 
 	ldp	$d0,$d1,[$inp],#16	// load input
 	sub	$len,$len,#16
-- 
2.56.0

[PATCH v3 2/2] lib/crypto: tests: Add Poly1305 split-update carry regression test

[Eric Biggers]

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@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),
 	{},
 };
-- 
2.56.0

Re: [PATCH v3 1/2] lib/crypto: arm64: Fix lost Poly1305 carry when resuming NEON state

[Eric Biggers]

On Fri, Oct 09, 2026 at 02:53:53PM +0200, Eric Biggers wrote:
> represents 2^128 + 4, so the conversion must produce the base 2^64 limbs
> h0 = 4, h1 = 0, h2 = 1.  The low 64-bit word sums to 2^64 + 4 and the
> middle 64-bit word (including the carry from the low word) sums to 2^64,
> so both carry out.  However, the carry out of the middle word goes to
> d2, leaving h2 = 0 and the value 4 instead of 2^128 + 4.

Going to change it to this instead, which should be clearer:

    represents 4 + 2^26*2^26 + (2^26-1)*2^52 + (2^26-1)*2^78 +
    (2^24-1)*2^104 = 2^128 + 4, despite the bit representing the 2^128
    term (bit 24 of h4) not being set; the extra comes from the h1 limb
    being above the normal base 2^26 range.  When this value is
    converted into the non-redundant base 2^64 form, a carry into the
    new 2^128 bit (in bit 0 of h2) is necessary to preserve the value.

> [EB: Rewrote the commit message to more clearly describe the bug and
>  its impact, and removed a lot of pointless LLM-generated text.]

Changed to

 [EB: Rewrote the commit message to more clearly describe the bug and
  its impact, and simplified explanation about why there's a carry bit.]

since Jérémy said it actually wasn't LLM generated.

- Eric

Re: [PATCH v3 1/2] lib/crypto: arm64: Fix lost Poly1305 carry when resuming NEON state

[Jason A. Donenfeld]

This is a nice catch. Thanks for this, Jeremy.

    Reviewed-by: Jason A. Donenfeld <Jason@zx2c4.com>

Re: [PATCH v3 2/2] lib/crypto: tests: Add Poly1305 split-update carry regression test

[Jason A. Donenfeld]

On Fri, Oct 9, 2026 at 2:54 PM Eric Biggers <ebiggers@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@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@zx2c4.com>

Re: [PATCH v3 0/2] lib/crypto: arm64: Fix Poly1305 NEON resume carry loss

[Eric Biggers]

On Fri, Oct 09, 2026 at 02:53:52PM +0200, Eric Biggers wrote:
> This series fixes a lost carry bit in the arm64 Poly1305 implementation,
> then adds a regression test for it.
> 
> Compared to v2 sent by Jérémy Jean, I cleaned up the verbose
> LLM-generated text in the commit message of the fix commit, and I
> replaced the LLM-generated minimal test case with a more comprehensive
> one similar to the existing test cases in the file.
> 
> Note: the second commit has references to the commit ID of the first,
> which I'll fix up when applying.
> 
> Eric Biggers (1):
>   lib/crypto: tests: Add Poly1305 split-update carry regression test
> 
> Jérémy Jean (1):
>   lib/crypto: arm64: Fix lost Poly1305 carry when resuming NEON state
> 
>  lib/crypto/arm64/poly1305-armv8.pl |  2 +-
>  lib/crypto/tests/poly1305_kunit.c  | 97 +++++++++++++++++++++++++++---
>  2 files changed, 89 insertions(+), 10 deletions(-)
> 
> 
> base-commit: 572af6872e520c7102e58362ef7cd7c2ed4342be

Applied to https://git.kernel.org/pub/scm/linux/kernel/git/ebiggers/linux.git/log/?h=libcrypto-fixes

- Eric