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

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

[Jérémy Jean]

When poly1305_blocks_neon() resumes from a base 2^26 accumulator with an
odd number of blocks, its base conversion can lose a carry into the top
limb and emit a wrong tag.

Patch 1 fixes the lost carry. Patch 2 adds a KUnit regression for the
split-update witness that triggers it.

Changes in v2:
 - detail the computations reaching the bug and improve commit message, 
 - add a KUnit regression test.

Jérémy Jean (2):
  lib/crypto: arm64: Fix lost Poly1305 carry when resuming NEON state
  lib/crypto: tests: Add Poly1305 split-update carry regression test

 lib/crypto/arm64/poly1305-armv8.pl |  2 +-
 lib/crypto/tests/poly1305_kunit.c  | 31 ++++++++++++++++++++++++++++++
 2 files changed, 32 insertions(+), 1 deletion(-)

-- 
2.47.3

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

[Jérémy Jean]

When poly1305_blocks_neon() resumes from a lazily reduced NEON
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 into the base 2^64
form used by poly1305_mult(). The final ADC stores the carry into d2,
but the following accumulation and poly1305_mult() use h2. If the
conversion overflows across bit 128, the carry is dropped and the
emitted tag is wrong.

This was introduced by Cryptogams 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.

That carry is possible because the NEON loop stores a lazily reduced,
redundant base 2^26 representation. Consider the reachable state
  [4,   2^26,   2^26 - 1,   2^26 - 1,   2^24 - 1].
These limbs in base 2^26 represent the value
      4 
    + (2^26    ) * 2^26
    + (2^26 - 1) * 2^52
    + (2^26 - 1) * 2^78
    + (2^24 - 1) * 2^104
  = 2^128 + 4,
so converting back to base 2^64 must produce
  h0 = 4, h1 = 0, h2 = 1,
so that h0 + h1 * 2^64 + h2 * 2^128 = 2^128 + 4.

The third limb starts at bit 52, so its low 12 bits belong in h0 and
its upper 14 bits belong in h1. The low-word ADDS starts from
  4 + 2^26 * 2^26 = 2^52 + 4
and adds the low 64 bits of
  (2^26 - 1) << 52 = 2^78 - 2^52,
namely 2^64 - 2^52. The sum is 2^64 + 4, so it leaves h0 = 4 and
carry = 1.

The middle word contains the upper 14 bits of the third limb, all of
the fourth limb, and the low 24 bits of the fifth limb. The next ADC
adds the carry from h0 to
  ((2^26 - 1) >> 12) + ((2^26 - 1) << 14),
giving
  (2^14 - 1) + (2^40 - 2^14) + 1 = 2^40.
The following ADDS adds the low 64 bits of
  (2^24 - 1) << 40 = 2^64 - 2^40,
so the sum is 2^64, h1 wraps to 0, and carry = 1.

The top word starts from the remaining bits of the fifth limb,
  (2^24 - 1) >> 24 = 0.
The final ADC must add the carry from h1 and set h2 = 1. Writing the
carry into d2 instead leaves h2 = 0, so the reconstructed value is 4
instead of 2^128 + 4.

More generally, for [a0, a1, a2, a3, a4], this carry exists only when 
  a1 >= 2^26,
  a2 = a3 = 2^26 - 1,
  a4 mod 2^24 = 2^24 - 1.
This is about 2^36 tuples out of about 2^130, or about one in 2^94 for
uniformly random tuples.

Store the carry back into h2. This matches the other conversion paths
and preserves the represented accumulator. Under regular use,
triggering this bug by chance is highly improbable; this fix addresses
arithmetic correctness only.

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>
---

Changes in v2:
 - Add an example of computations demonstrating the error.
 - Provide an estimate of the low probability it gets triggered.
 - Add a paragraph mentionning the introducing commit in Cryptogams
   repo, and non-impact on OpenSSL.

v1: https://lore.kernel.org/all/20261007220235.200818-2-Jeremy.Jean@oss.cyber.gouv.fr/

 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.47.3

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

[Eric Biggers]

On Thu, Oct 08, 2026 at 08:19:50PM +0000, Jérémy Jean wrote:
> These limbs in base 2^26 represent the value
>       4 
>     + (2^26    ) * 2^26
>     + (2^26 - 1) * 2^52
>     + (2^26 - 1) * 2^78
>     + (2^24 - 1) * 2^104
>   = 2^128 + 4,
> so converting back to base 2^64 must produce
>   h0 = 4, h1 = 0, h2 = 1,
> so that h0 + h1 * 2^64 + h2 * 2^128 = 2^128 + 4.
> 
> The third limb starts at bit 52, so its low 12 bits belong in h0 and
> its upper 14 bits belong in h1. The low-word ADDS starts from
>   4 + 2^26 * 2^26 = 2^52 + 4
> and adds the low 64 bits of
>   (2^26 - 1) << 52 = 2^78 - 2^52,
> namely 2^64 - 2^52. The sum is 2^64 + 4, so it leaves h0 = 4 and
> carry = 1.
> 
> The middle word contains the upper 14 bits of the third limb, all of
> the fourth limb, and the low 24 bits of the fifth limb. The next ADC
> adds the carry from h0 to
>   ((2^26 - 1) >> 12) + ((2^26 - 1) << 14),
> giving
>   (2^14 - 1) + (2^40 - 2^14) + 1 = 2^40.
> The following ADDS adds the low 64 bits of
>   (2^24 - 1) << 40 = 2^64 - 2^40,
> so the sum is 2^64, h1 wraps to 0, and carry = 1.
> 
> The top word starts from the remaining bits of the fifth limb,
>   (2^24 - 1) >> 24 = 0.
> The final ADC must add the carry from h1 and set h2 = 1. Writing the
> carry into d2 instead leaves h2 = 0, so the reconstructed value is 4
> instead of 2^128 + 4.

Thanks, but this LLM-generated "explanation" is way too verbose and
doesn't really say anything useful.  The new test in patch 2 is also
unnecessarily specialized to this exact issue and implementation, isn't
properly explained, and it's apparently LLM-generated too.  I'd normally
give a bit more time for submitters to fix things up, but since it will
likely just go back into the LLM, I don't think there's much point here.
So I went ahead and sent out a v3 that addresses these issues.

Thanks,

- Eric

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

[Jérémy Jean]

On 2026-10-09 15:03, Eric Biggers wrote:
> On Thu, Oct 08, 2026 at 08:19:50PM +0000, Jérémy Jean wrote:
>> These limbs in base 2^26 represent the value
>>       4
>>     + (2^26    ) * 2^26
>>     + (2^26 - 1) * 2^52
>>     + (2^26 - 1) * 2^78
>>     + (2^24 - 1) * 2^104
>>   = 2^128 + 4,
>> so converting back to base 2^64 must produce
>>   h0 = 4, h1 = 0, h2 = 1,
>> so that h0 + h1 * 2^64 + h2 * 2^128 = 2^128 + 4.
>> 
>> The third limb starts at bit 52, so its low 12 bits belong in h0 and
>> its upper 14 bits belong in h1. The low-word ADDS starts from
>>   4 + 2^26 * 2^26 = 2^52 + 4
>> and adds the low 64 bits of
>>   (2^26 - 1) << 52 = 2^78 - 2^52,
>> namely 2^64 - 2^52. The sum is 2^64 + 4, so it leaves h0 = 4 and
>> carry = 1.
>> 
>> The middle word contains the upper 14 bits of the third limb, all of
>> the fourth limb, and the low 24 bits of the fifth limb. The next ADC
>> adds the carry from h0 to
>>   ((2^26 - 1) >> 12) + ((2^26 - 1) << 14),
>> giving
>>   (2^14 - 1) + (2^40 - 2^14) + 1 = 2^40.
>> The following ADDS adds the low 64 bits of
>>   (2^24 - 1) << 40 = 2^64 - 2^40,
>> so the sum is 2^64, h1 wraps to 0, and carry = 1.
>> 
>> The top word starts from the remaining bits of the fifth limb,
>>   (2^24 - 1) >> 24 = 0.
>> The final ADC must add the carry from h1 and set h2 = 1. Writing the
>> carry into d2 instead leaves h2 = 0, so the reconstructed value is 4
>> instead of 2^128 + 4.
> 
> Thanks, but this LLM-generated "explanation" is way too verbose and
> doesn't really say anything useful.  The new test in patch 2 is also
> unnecessarily specialized to this exact issue and implementation, isn't
> properly explained, and it's apparently LLM-generated too.  I'd 
> normally
> give a bit more time for submitters to fix things up, but since it will
> likely just go back into the LLM, I don't think there's much point 
> here.
> So I went ahead and sent out a v3 that addresses these issues.

I did get help from LLM for the test, but I did write the explanation 
myself
to explain the carry propagation in the computations. I thought it 
explained
the carry bug nicely enough with an example, sorry that you disagree.
I also added a paragraph on the probability that this happens, because 
it's
very low and AFAICT, does not really impact current deployements.

Jérémy

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

[Eric Biggers]

On Fri, Oct 09, 2026 at 03:26:23PM +0200, Jérémy Jean wrote:
> On 2026-10-09 15:03, Eric Biggers wrote:
> > On Thu, Oct 08, 2026 at 08:19:50PM +0000, Jérémy Jean wrote:
> > > These limbs in base 2^26 represent the value
> > >       4
> > >     + (2^26    ) * 2^26
> > >     + (2^26 - 1) * 2^52
> > >     + (2^26 - 1) * 2^78
> > >     + (2^24 - 1) * 2^104
> > >   = 2^128 + 4,
> > > so converting back to base 2^64 must produce
> > >   h0 = 4, h1 = 0, h2 = 1,
> > > so that h0 + h1 * 2^64 + h2 * 2^128 = 2^128 + 4.
> > > 
> > > The third limb starts at bit 52, so its low 12 bits belong in h0 and
> > > its upper 14 bits belong in h1. The low-word ADDS starts from
> > >   4 + 2^26 * 2^26 = 2^52 + 4
> > > and adds the low 64 bits of
> > >   (2^26 - 1) << 52 = 2^78 - 2^52,
> > > namely 2^64 - 2^52. The sum is 2^64 + 4, so it leaves h0 = 4 and
> > > carry = 1.
> > > 
> > > The middle word contains the upper 14 bits of the third limb, all of
> > > the fourth limb, and the low 24 bits of the fifth limb. The next ADC
> > > adds the carry from h0 to
> > >   ((2^26 - 1) >> 12) + ((2^26 - 1) << 14),
> > > giving
> > >   (2^14 - 1) + (2^40 - 2^14) + 1 = 2^40.
> > > The following ADDS adds the low 64 bits of
> > >   (2^24 - 1) << 40 = 2^64 - 2^40,
> > > so the sum is 2^64, h1 wraps to 0, and carry = 1.
> > > 
> > > The top word starts from the remaining bits of the fifth limb,
> > >   (2^24 - 1) >> 24 = 0.
> > > The final ADC must add the carry from h1 and set h2 = 1. Writing the
> > > carry into d2 instead leaves h2 = 0, so the reconstructed value is 4
> > > instead of 2^128 + 4.
> > 
> > Thanks, but this LLM-generated "explanation" is way too verbose and
> > doesn't really say anything useful.  The new test in patch 2 is also
> > unnecessarily specialized to this exact issue and implementation, isn't
> > properly explained, and it's apparently LLM-generated too.  I'd normally
> > give a bit more time for submitters to fix things up, but since it will
> > likely just go back into the LLM, I don't think there's much point here.
> > So I went ahead and sent out a v3 that addresses these issues.
> 
> I did get help from LLM for the test, but I did write the explanation myself
> to explain the carry propagation in the computations. I thought it explained
> the carry bug nicely enough with an example, sorry that you disagree.

Well, it was written in the repetitive LLM style and basically took a
whole page to explain that there's a carry bit, which seems fairly self-
explanatory when unreduced limbs are allowed.  The space is better used
for other details.  If you wrote it by hand, then I'm sorry, but if you
don't want me to think your text is LLM-generated you shouldn't mix it
together with other LLM-generated stuff.

> I also added a paragraph on the probability that this happens, because it's
> very low and AFAICT, does not really impact current deployements.

Yes, but that part needed some elaboration, which I added.

Anyway, thanks for finding this.

- Eric

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

[Jérémy Jean]

Add a Poly1305 KUnit test for a split-update sequence that forces an
implementation to resume from an intermediate accumulator state and still
produce the same final tag.

The witness uses r=1, s=0, a 304-byte message with block 5 equal to
2^128 - 6, and update lengths 128, 144, and 32.  On arm64 before the
preceding fix, the NEON backend emits 0e000000000000000000000000000000
instead of 13000000000000000000000000000000 because the odd-block resume
path drops a carry while converting a base 2^26 accumulator back to
base 2^64.

Assisted-by: LLM
Signed-off-by: Jérémy Jean <Jeremy.Jean@oss.cyber.gouv.fr>
---
 lib/crypto/tests/poly1305_kunit.c | 31 +++++++++++++++++++++++++++++++
 1 file changed, 31 insertions(+)

diff --git a/lib/crypto/tests/poly1305_kunit.c b/lib/crypto/tests/poly1305_kunit.c
index f3cb6245bc29..752b503d7a7b 100644
--- a/lib/crypto/tests/poly1305_kunit.c
+++ b/lib/crypto/tests/poly1305_kunit.c
@@ -141,10 +141,41 @@ static void test_poly1305_reduction_edge_cases(struct kunit *test)
 	}
 }
 
+/*
+ * Poly1305 test case which uses r_key=1, s_key=0 and a split update sequence
+ * that exercises a carry while resuming from a base 2^26 accumulator.
+ *
+ * The first update leaves the arm64 NEON implementation in base 2^26. The
+ * second update contains an odd number of blocks, so it converts that
+ * accumulator back to base 2^64 before processing the first block.
+ */
+static void test_poly1305_split_update_carry(struct kunit *test)
+{
+	static const u8 key[POLY1305_KEY_SIZE] = { 1 }; /* r_key=1, s_key=0 */
+	static const u8 expected_mac[POLY1305_DIGEST_SIZE] = { 0x13 };
+	u8 data[304] = {};
+	struct poly1305_desc_ctx ctx;
+	u8 actual_mac[POLY1305_DIGEST_SIZE];
+
+	/* Set the fifth data block to 2**128 - 6. */
+	data[64] = 0xfa;
+	memset(&data[65], 0xff, POLY1305_BLOCK_SIZE - 1);
+
+	poly1305_init(&ctx, key);
+	poly1305_update(&ctx, data, 128);
+	poly1305_update(&ctx, data + 128, 144);
+	poly1305_update(&ctx, data + 272, 32);
+	poly1305_final(&ctx, actual_mac);
+
+	KUNIT_ASSERT_MEMEQ(test, actual_mac, expected_mac,
+			   POLY1305_DIGEST_SIZE);
+}
+
 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.47.3