[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@xxxxxxxxxxxxxxx
Assisted-by: LLM
Signed-off-by: Jérémy Jean <Jeremy.Jean@xxxxxxxxxxxxxxxxx>
---

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@xxxxxxxxxxxxxxxxx/

 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