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

[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