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

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

[Anastasia Tishchenko]

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.

Add proper handling for this boundary by accounting for the carry
from the lower addition.

This issue was discovered during formal verification of ECC functions.

Signed-off-by: Anastasia Tishchenko <sv3iry@gmail.com>
---
 crypto/ecc.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/crypto/ecc.c b/crypto/ecc.c
index 43b0def3a225..dfe96471407c 100644
--- a/crypto/ecc.c
+++ b/crypto/ecc.c
@@ -427,7 +427,10 @@ static void vli_mult(u64 *result, const u64 *left, const u64 *right,
 			product = mul_64_64(left[i], right[k - i]);
 
 			r01 = add_128_128(r01, product);
-			r2 += (r01.m_high < product.m_high);
+			if (r01.m_high != product.m_high)
+				r2 += (r01.m_high < product.m_high);
+			else
+				r2 += (r01.m_low < product.m_low);
 		}
 
 		result[k] = r01.m_low;
@@ -488,7 +491,10 @@ static void vli_square(u64 *result, const u64 *left, unsigned int ndigits)
 			}
 
 			r01 = add_128_128(r01, product);
-			r2 += (r01.m_high < product.m_high);
+			if (r01.m_high != product.m_high)
+				r2 += (r01.m_high < product.m_high);
+			else
+				r2 += (r01.m_low < product.m_low);
 		}
 
 		result[k] = r01.m_low;
-- 
2.43.0

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

[Stefan Berger]

On 5/8/26 7:48 AM, Anastasia Tishchenko wrote:
> 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.
> 
> Add proper handling for this boundary by accounting for the carry
> from the lower addition.
> 
> This issue was discovered during formal verification of ECC functions.

Thanks!

> 
> Signed-off-by: Anastasia Tishchenko <sv3iry@gmail.com>
> ---
>   crypto/ecc.c | 10 ++++++++--
>   1 file changed, 8 insertions(+), 2 deletions(-)
> 
> diff --git a/crypto/ecc.c b/crypto/ecc.c
> index 43b0def3a225..dfe96471407c 100644
> --- a/crypto/ecc.c
> +++ b/crypto/ecc.c
> @@ -427,7 +427,10 @@ static void vli_mult(u64 *result, const u64 *left, const u64 *right,
>   			product = mul_64_64(left[i], right[k - i]);
>   
>   			r01 = add_128_128(r01, product);
> -			r2 += (r01.m_high < product.m_high);

Maybe the following or something like lt_128(r01, product) would be 
'better' replacing 'r01 < product':

if (cmp_128(r01, product) < 0)
     r2++;

/* Compare two uint128_t; returns -1 if a<b, 0 if a == b, 1 otherwise */
static int cmp_128(uint128_t a, uint128_t b)
{
     if (a.m_high < b.m_high)
        return -1;
     if (a.m_high > b.m_high)
        return 1;
     if (a.m_low < b.m_low)
        return -1;
     if (a.m_low > b.m_low)
        return 1;
     return 0;
}



/* r01 < product */
if (lt_128(r01, product))
     r2++;

/* Check a < b; return 1 if a < b, 0 otherwise */
static int lt_128(uint128_t a, uint128_t b)
{
     if (a.m_high < b.m_high)
        return 1;
     if (a.m_high > b.m_high)
        return 0;
     if (a.m_low < b.m_low)
        return 1;
     return 0;
}

> +			if (r01.m_high != product.m_high)
> +				r2 += (r01.m_high < product.m_high);
> +			else
> +				r2 += (r01.m_low < product.m_low);
>   		}
>   
>   		result[k] = r01.m_low;
> @@ -488,7 +491,10 @@ static void vli_square(u64 *result, const u64 *left, unsigned int ndigits)
>   			}
>   
>   			r01 = add_128_128(r01, product);
> -			r2 += (r01.m_high < product.m_high);
> +			if (r01.m_high != product.m_high)
> +				r2 += (r01.m_high < product.m_high);
> +			else
> +				r2 += (r01.m_low < product.m_low);
>   		}
>   
>   		result[k] = r01.m_low;

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

[Lukas Wunner]

On Fri, May 08, 2026 at 02:48:44PM +0300, Anastasia Tishchenko wrote:
> 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.
> 
> Add proper handling for this boundary by accounting for the carry
> from the lower addition.
[...]
> +++ b/crypto/ecc.c
> @@ -427,7 +427,10 @@ static void vli_mult(u64 *result, const u64 *left, const u64 *right,
>  			product = mul_64_64(left[i], right[k - i]);
>  
>  			r01 = add_128_128(r01, product);
> -			r2 += (r01.m_high < product.m_high);
> +			if (r01.m_high != product.m_high)
> +				r2 += (r01.m_high < product.m_high);
> +			else
> +				r2 += (r01.m_low < product.m_low);
>  		}
>  
>  		result[k] = r01.m_low;

Thanks for spotting this.

crypto/ecc.c is derived from Ken MacKay's micro-ecc library and
that library has always had the check that you're adding here:

https://github.com/kmackay/micro-ecc/blob/master/uECC.c#L403

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.
The function names suggest that this was probably done to allow
moving them to include/linux/math64.h and/or lib/math/div64.c
in case they're needed elsewhere in the kernel later.

It seems the check got lost in translation.

However while your patch looks correct to me, I think the overflow
check isn't very obvious or readable.  And I don't like how it leaks
outside the add_128_128() helper.

The kernel gained a check_add_overflow() helper relatively recently
in include/linux/overflow.h.  What I'd prefer is if you could rename
add_128_128() to check_add_128_128_overflow() and let it return a bool
indicating whether an overflow occurred.  Then r2 is simply incremented
if the return value is true.  Optionally you could add a third parameter
for the result (like check_add_overflow() does), but that's not strictly
needed for the callers in crypto/ecc.c and would merely be in preparation
for reuse of the function by other code in the kernel.
Does that make sense?

Please add these tags if/when respinning:

Fixes: 3c4b23901a0c ("crypto: ecdh - Add ECDH software support")
Cc: stable@vger.kernel.org # v4.8+

Personally I order tags according to Bjorn's preference:

https://lore.kernel.org/r/20171026223701.GA25649@bhelgaas-glaptop.roam.corp.google.com/

It would also be good if you could include the backstory I've outlined
above in the commit message so that it's recorded in the git history
and doesn't have to be dug out from mailing list archives.

Thanks!

Lukas