[PATCH 1/3] crypto: ecc - Fix carry overflow in vli multiplication

[PATCH 1/3] crypto: ecc - Fix carry overflow in vli multiplication

[Ahmad Fatoum]

This is an adoption of the corresponding Linux commit:

| commit 27b536a2ec8e2f85a0380c2d13c9ecbc7aaab406
|
|     crypto: ecc - Fix carry overflow in vli multiplication
|
|     The carry flag calculation fails when r01.m_high is saturated
|     (0xFFFFFFFFFFFFFFFF) and addition of lower bits overflows.
|
|     The condition (r01.m_high < product.m_high) doesn't handle the case
|     where r01.m_high == product.m_high and an additional carry exists
|     from lower-bit overflow.
|
|     When commit 3c4b23901a0c ("crypto: ecdh - Add ECDH software support")
|     introduced crypto/ecc.c, it split the muladd() function in the
|     micro-ecc library into separate mul_64_64() and add_128_128() helpers.
|     It seems the check got lost in translation.
|
|     Add proper handling for this boundary by accounting for the carry
|     from the lower addition.
|
|     Fixes: 3c4b23901a0c ("crypto: ecdh - Add ECDH software support")
|     Signed-off-by: Anastasia Tishchenko <sv3iry@gmail.com>
|     Cc: stable@vger.kernel.org # v4.8+
|     Reviewed-by: Lukas Wunner <lukas@wunner.de>
|     Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

Fixes: d2cc4152f483 ("Add elliptic curve cryptography (ECC) helper functions")
Reported-by: Lukas Wunner <lukas@wunner.de>
Closes: https://lore.kernel.org/barebox/agS_XfdyvX_1q9dt@wunner.de/
Signed-off-by: Ahmad Fatoum <a.fatoum@barebox.org>
---
 crypto/ecc.c | 33 +++++++++++++++++++++------------
 1 file changed, 21 insertions(+), 12 deletions(-)

diff --git a/crypto/ecc.c b/crypto/ecc.c
index b6abdbee67be..67faae0a68f9 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=d6ea871d73abbb6a1e00e71ed5762e394d06cb2b
+// SPDX-Comment: Origin-URL: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/crypto/ecc.c?id=27b536a2ec8e2f85a0380c2d13c9ecbc7aaab406
 /*
  * Copyright (c) 2013, 2014 Kenneth MacKay. All rights reserved.
  * Copyright (c) 2019 Vitaly Chikunov <vt@altlinux.org>
@@ -381,14 +381,26 @@ static uint128_t mul_64_64(u64 left, u64 right)
 	return result;
 }
 
-static uint128_t add_128_128(uint128_t a, uint128_t b)
+/* Calculate addition with overflow checking. Returns true on wrap-around,
+ * false otherwise.
+ */
+static bool check_add_128_128_overflow(uint128_t *result, uint128_t a,
+				       uint128_t b)
 {
-	uint128_t result;
+	bool carry;
 
-	result.m_low = a.m_low + b.m_low;
-	result.m_high = a.m_high + b.m_high + (result.m_low < a.m_low);
+	result->m_low = a.m_low + b.m_low;
+	carry = (result->m_low < a.m_low);
 
-	return result;
+	result->m_high = a.m_high + b.m_high + carry;
+
+	/* Using constant-time bitwise arithmetic to prevent timing
+	 * side-channels.
+	 */
+	carry = (result->m_high < a.m_high) |
+		((result->m_high == a.m_high) & carry);
+
+	return carry;
 }
 
 static void vli_mult(u64 *result, const u64 *left, const u64 *right,
@@ -413,9 +425,7 @@ static void vli_mult(u64 *result, const u64 *left, const u64 *right,
 			uint128_t product;
 
 			product = mul_64_64(left[i], right[k - i]);
-
-			r01 = add_128_128(r01, product);
-			r2 += (r01.m_high < product.m_high);
+			r2 += check_add_128_128_overflow(&r01, r01, product);
 		}
 
 		result[k] = r01.m_low;
@@ -438,7 +448,7 @@ static void vli_umult(u64 *result, const u64 *left, u32 right,
 		uint128_t product;
 
 		product = mul_64_64(left[k], right);
-		r01 = add_128_128(r01, product);
+		check_add_128_128_overflow(&r01, r01, product);
 		/* no carry */
 		result[k] = r01.m_low;
 		r01.m_low = r01.m_high;
@@ -475,8 +485,7 @@ static void vli_square(u64 *result, const u64 *left, unsigned int ndigits)
 				product.m_low <<= 1;
 			}
 
-			r01 = add_128_128(r01, product);
-			r2 += (r01.m_high < product.m_high);
+			r2 += check_add_128_128_overflow(&r01, r01, product);
 		}
 
 		result[k] = r01.m_low;
-- 
2.47.3

[PATCH 2/3] crypto: ecc - Optimize vli additive operations using compiler builtins

[Ahmad Fatoum]

This is an adoption of the corresponding Linux commit:

| commit 9deef9c5b8fcc702e69252bef46735d8b0d1f70c
| Author:     Fabian Blatter <fabianblatter09@gmail.com>
| AuthorDate: Sun Jun 7 13:24:35 2026 +0200
|
|     crypto: ecc - Optimize vli additive operations using compiler builtins
|
|     Replace the software carry flag emulation with compiler builtins.
|
|     Even the newest compilers struggle with taking advantage of the
|     hardware carry flag. Compiler builtins allow the compiler to
|     much more easily achieve this while still remaining constant-time.
|
|     This yields an approximately 6-7% performance improvement
|     on the ecc_gen_privkey, ecc_make_pub_key and crypto_ecdh_shared_secret
|     functions on x86_64 on all curve sizes.
|
|     Additionally, the code becomes much more readable.
|
|     Signed-off-by: Fabian Blatter <fabianblatter09@gmail.com>
|     Reviewed-by: Stefan Berger <stefanb@linux.ibm.com>
|     Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

We take this mainly to stay in sync with Linux, so the Origin-URL can
follow along with the next fix.

Signed-off-by: Ahmad Fatoum <a.fatoum@barebox.org>
---
 crypto/ecc.c | 100 +++++++++++++++++++++++++++++++--------------------
 1 file changed, 61 insertions(+), 39 deletions(-)

diff --git a/crypto/ecc.c b/crypto/ecc.c
index 67faae0a68f9..01cb1ae88ead 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=27b536a2ec8e2f85a0380c2d13c9ecbc7aaab406
+// SPDX-Comment: Origin-URL: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/crypto/ecc.c?id=9deef9c5b8fcc702e69252bef46735d8b0d1f70c
 /*
  * Copyright (c) 2013, 2014 Kenneth MacKay. All rights reserved.
  * Copyright (c) 2019 Vitaly Chikunov <vt@altlinux.org>
@@ -267,6 +267,48 @@ static void vli_rshift1(u64 *vli, unsigned int ndigits)
 	}
 }
 
+#ifdef __has_builtin
+#if __has_builtin(__builtin_addcll)
+#define USE_BUILTIN_ADDC
+#endif
+#endif
+
+/* Computes result = left + right + carry_in and updates carry_out */
+static inline void add_carry(u64 left, u64 right, u64 *result, u64 carry_in,
+			     u64 *carry_out)
+{
+#ifdef USE_BUILTIN_ADDC
+	*result = __builtin_addcll(left, right, carry_in, carry_out);
+#else
+	u64 sum1, sum2;
+	u64 c1 = __builtin_uaddll_overflow(left, right, &sum1);
+	u64 c2 = __builtin_uaddll_overflow(sum1, carry_in, &sum2);
+	*result = sum2;
+	*carry_out = c1 | c2;
+#endif
+}
+
+#ifdef __has_builtin
+#if __has_builtin(__builtin_subcll)
+#define USE_BUILTIN_SUBC
+#endif
+#endif
+
+/* Computes result = left - right - borrow_in and updates borrow_out */
+static inline void sub_borrow(u64 left, u64 right, u64 *result, u64 borrow_in,
+			      u64 *borrow_out)
+{
+#ifdef USE_BUILTIN_SUBC
+	*result = __builtin_subcll(left, right, borrow_in, borrow_out);
+#else
+	u64 diff1, diff2;
+	u64 b1 = __builtin_usubll_overflow(left, right, &diff1);
+	u64 b2 = __builtin_usubll_overflow(diff1, borrow_in, &diff2);
+	*result = diff2;
+	*borrow_out = b1 | b2;
+#endif
+}
+
 /* Computes result = left + right, returning carry. Can modify in place. */
 static u64 vli_add(u64 *result, const u64 *left, const u64 *right,
 		   unsigned int ndigits)
@@ -274,15 +316,8 @@ static u64 vli_add(u64 *result, const u64 *left, const u64 *right,
 	u64 carry = 0;
 	int i;
 
-	for (i = 0; i < ndigits; i++) {
-		u64 sum;
-
-		sum = left[i] + right[i] + carry;
-		if (sum != left[i])
-			carry = (sum < left[i]);
-
-		result[i] = sum;
-	}
+	for (i = 0; i < ndigits; i++)
+		add_carry(left[i], right[i], &result[i], carry, &carry);
 
 	return carry;
 }
@@ -291,40 +326,29 @@ static u64 vli_add(u64 *result, const u64 *left, const u64 *right,
 static u64 vli_uadd(u64 *result, const u64 *left, u64 right,
 		    unsigned int ndigits)
 {
-	u64 carry = right;
+	u64 carry;
 	int i;
 
-	for (i = 0; i < ndigits; i++) {
-		u64 sum;
+	if (ndigits == 0)
+		return right;
 
-		sum = left[i] + carry;
-		if (sum != left[i])
-			carry = (sum < left[i]);
-		else
-			carry = !!carry;
+	carry = __builtin_uaddll_overflow(left[0], right, &result[0]);
 
-		result[i] = sum;
-	}
+	for (i = 1; i < ndigits; i++)
+		carry = __builtin_uaddll_overflow(left[i], carry, &result[i]);
 
 	return carry;
 }
 
 /* Computes result = left - right, returning borrow. Can modify in place. */
 u64 vli_sub(u64 *result, const u64 *left, const u64 *right,
-		   unsigned int ndigits)
+	    unsigned int ndigits)
 {
 	u64 borrow = 0;
 	int i;
 
-	for (i = 0; i < ndigits; i++) {
-		u64 diff;
-
-		diff = left[i] - right[i] - borrow;
-		if (diff != left[i])
-			borrow = (diff > left[i]);
-
-		result[i] = diff;
-	}
+	for (i = 0; i < ndigits; i++)
+		sub_borrow(left[i], right[i], &result[i], borrow, &borrow);
 
 	return borrow;
 }
@@ -332,20 +356,18 @@ EXPORT_SYMBOL(vli_sub);
 
 /* Computes result = left - right, returning borrow. Can modify in place. */
 static u64 vli_usub(u64 *result, const u64 *left, u64 right,
-	     unsigned int ndigits)
+		    unsigned int ndigits)
 {
-	u64 borrow = right;
+	u64 borrow;
 	int i;
 
-	for (i = 0; i < ndigits; i++) {
-		u64 diff;
+	if (ndigits == 0)
+		return right;
 
-		diff = left[i] - borrow;
-		if (diff != left[i])
-			borrow = (diff > left[i]);
+	borrow = __builtin_usubll_overflow(left[0], right, &result[0]);
 
-		result[i] = diff;
-	}
+	for (i = 1; i < ndigits; i++)
+		borrow = __builtin_usubll_overflow(left[i], borrow, &result[i]);
 
 	return borrow;
 }
-- 
2.47.3

[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@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@vger.kernel.org
|     Assisted-by: LLM
|     Signed-off-by: Jérémy Jean <Jeremy.Jean@oss.cyber.gouv.fr>
|     Reviewed-by: Ignat Korchagin <ignat@linux.win>
|     Reviewed-by: Stefan Berger <stefanb@linux.ibm.com>
|     Signed-off-by: Herbert Xu <herbert@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@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@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

Re: [PATCH 1/3] crypto: ecc - Fix carry overflow in vli multiplication

[Sascha Hauer]

On Sun, 25 Oct 2026 09:54:44 +0100, Ahmad Fatoum wrote:
> This is an adoption of the corresponding Linux commit:
> 
> | commit 27b536a2ec8e2f85a0380c2d13c9ecbc7aaab406
> |
> |     crypto: ecc - Fix carry overflow in vli multiplication
> |
> |     The carry flag calculation fails when r01.m_high is saturated
> |     (0xFFFFFFFFFFFFFFFF) and addition of lower bits overflows.
> |
> |     The condition (r01.m_high < product.m_high) doesn't handle the case
> |     where r01.m_high == product.m_high and an additional carry exists
> |     from lower-bit overflow.
> |
> |     When commit 3c4b23901a0c ("crypto: ecdh - Add ECDH software support")
> |     introduced crypto/ecc.c, it split the muladd() function in the
> |     micro-ecc library into separate mul_64_64() and add_128_128() helpers.
> |     It seems the check got lost in translation.
> |
> |     Add proper handling for this boundary by accounting for the carry
> |     from the lower addition.
> |
> |     Fixes: 3c4b23901a0c ("crypto: ecdh - Add ECDH software support")
> |     Signed-off-by: Anastasia Tishchenko <sv3iry@gmail.com>
> |     Cc: stable@vger.kernel.org # v4.8+
> |     Reviewed-by: Lukas Wunner <lukas@wunner.de>
> |     Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
> 
> [...]

Applied, thanks!

[1/3] crypto: ecc - Fix carry overflow in vli multiplication
      https://git.pengutronix.de/cgit/barebox/commit/?id=ee1ddfaf4e91 (link may not be stable)
[2/3] crypto: ecc - Optimize vli additive operations using compiler builtins
      https://git.pengutronix.de/cgit/barebox/commit/?id=a6a5e2e775ea (link may not be stable)
[3/3] crypto: ecc - Handle exceptional points in Shamir multiplication
      https://git.pengutronix.de/cgit/barebox/commit/?id=7423e4755ecd (link may not be stable)

Best regards,
-- 
Sascha Hauer <s.hauer@pengutronix.de>