[PATCH 3/3] crypto: ecc - Handle exceptional points in Shamir multiplication

[Ahmad Fatoum]

This is an adaptation of the corresponding Linux commit:

| commit 6fd70bc8bc01a578c7728b7bd1cb5689c62cc5b7 (HEAD)
| Author:     Jérémy Jean <Jeremy.Jean at oss.cyber.gouv.fr>
| AuthorDate: Sat Sep 26 20:43:26 2026 +0000
|
|     crypto: ecc - Handle exceptional points in Shamir multiplication
|
|     Shamir multiplication mishandles equal points, opposite points and the
|     point at infinity. This rejects valid ECDSA signatures and can accept
|     invalid digest/signature tuples when the public key is G or -G. The
|     kernel incorrectly rejects 16 valid signatures from Wycheproof.
|
|     Handle doubling, cancellation and the point at infinity in precomputation
|     and accumulation. Add regression tests for P-256 ECDSA and 256/512-bit
|     EC-RDSA. The valid vectors are Wycheproof P1363 secp256r1/SHA-256 cases
|     60 and 210 converted to X9.62, two constructed ECDSA signatures for
|     Q = +/-G with k = 2, and six constructed EC-RDSA signatures for Q = G,
|     -G and -2G. Also add two invalid P-256 digest/signature tuples for
|     Q = +/-G that must return -EKEYREJECTED.
|
|     Fixes: 0d7a78643f69 ("crypto: ecrdsa - add EC-RDSA (GOST 34.10) algorithm")
|     Cc: stable at vger.kernel.org
|     Assisted-by: LLM
|     Signed-off-by: Jérémy Jean <Jeremy.Jean at oss.cyber.gouv.fr>
|     Reviewed-by: Ignat Korchagin <ignat at linux.win>
|     Reviewed-by: Stefan Berger <stefanb at linux.ibm.com>
|     Signed-off-by: Herbert Xu <herbert at gondor.apana.org.au>

barebox has no testmgr, so only the crypto/ecc.c hunks are ported.

Fixes: d2cc4152f483 ("Add elliptic curve cryptography (ECC) helper functions")
Signed-off-by: Ahmad Fatoum <a.fatoum at barebox.org>
---
 crypto/ecc.c | 35 ++++++++++++++++++++++++++++++++---
 1 file changed, 32 insertions(+), 3 deletions(-)

diff --git a/crypto/ecc.c b/crypto/ecc.c
index 01cb1ae88ead..00ffd18cbf52 100644
--- a/crypto/ecc.c
+++ b/crypto/ecc.c
@@ -1,4 +1,4 @@
-// SPDX-Comment: Origin-URL: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/crypto/ecc.c?id=9deef9c5b8fcc702e69252bef46735d8b0d1f70c
+// SPDX-Comment: Origin-URL: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/crypto/ecc.c?id=6fd70bc8bc01a578c7728b7bd1cb5689c62cc5b7
 /*
  * Copyright (c) 2013, 2014 Kenneth MacKay. All rights reserved.
  * Copyright (c) 2019 Vitaly Chikunov <vt at altlinux.org>
@@ -1411,9 +1411,22 @@ static void ecc_point_add(const struct ecc_point *result,
 	vli_set(result->x, q->x, ndigits);
 	vli_set(result->y, q->y, ndigits);
 	vli_mod_sub(z, result->x, p->x, curve->p, ndigits);
+	if (vli_is_zero(z, ndigits)) {
+		if (vli_cmp(p->y, q->y, ndigits)) {
+			/* P + (-P) is the point at infinity. */
+			vli_clear(result->x, ndigits);
+			vli_clear(result->y, ndigits);
+			return;
+		}
+		/* The co-Z addition formula does not handle P == Q. */
+		z[0] = 1;
+		ecc_point_double_jacobian(result->x, result->y, z, curve);
+		goto out;
+	}
 	vli_set(px, p->x, ndigits);
 	vli_set(py, p->y, ndigits);
 	xycz_add(px, py, result->x, result->y, curve);
+out:
 	vli_mod_inv(z, z, curve->p, ndigits);
 	apply_z(result->x, result->y, z, curve);
 }
@@ -1455,22 +1468,38 @@ void ecc_point_mult_shamir(const struct ecc_point *result,
 	vli_set(rx, point->x, ndigits);
 	vli_set(ry, point->y, ndigits);
 	vli_clear(z + 1, ndigits - 1);
-	z[0] = 1;
+	z[0] = !ecc_point_is_zero(point);
 
 	for (--i; i >= 0; i--) {
 		ecc_point_double_jacobian(rx, ry, z, curve);
 		idx = !!vli_test_bit(u1, i);
 		idx |= (!!vli_test_bit(u2, i)) << 1;
 		point = points[idx];
-		if (point) {
+		if (point && !ecc_point_is_zero(point)) {
 			u64 tx[ECC_MAX_DIGITS];
 			u64 ty[ECC_MAX_DIGITS];
 			u64 tz[ECC_MAX_DIGITS];
 
+			if (vli_is_zero(z, ndigits)) {
+				/* Adding to infinity starts a new accumulator. */
+				vli_set(rx, point->x, ndigits);
+				vli_set(ry, point->y, ndigits);
+				z[0] = 1;
+				continue;
+			}
 			vli_set(tx, point->x, ndigits);
 			vli_set(ty, point->y, ndigits);
 			apply_z(tx, ty, z, curve);
 			vli_mod_sub(tz, rx, tx, curve->p, ndigits);
+			if (vli_is_zero(tz, ndigits)) {
+				if (!vli_cmp(ry, ty, ndigits))
+					ecc_point_double_jacobian(rx, ry, z,
+								  curve);
+				else
+					/* Adding opposite points yields infinity. */
+					vli_clear(z, ndigits);
+				continue;
+			}
 			xycz_add(tx, ty, rx, ry, curve);
 			vli_mod_mult_fast(z, z, tz, curve);
 		}
-- 
2.47.3