crypto : ecc - Fix carry overflow in vli multiplication

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

Posted by Anastasia Tishchenko 1 month ago

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

Posted by Lukas Wunner 1 month ago

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;

ICYMI, sashiko's AI-generated review alleges that the if-else condition
may cause a timing side channel vis-à-vis binary arithmetic:

https://sashiko.dev/#/patchset/20260508114844.29694-1-sv3iry%40gmail.com

You may want to address this if/when respinning your patch.  If you do,
a code comment is probably merited to explain this subtlety.

Thanks,

Lukas

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

Posted by David Laight 1 month ago

On Tue, 12 May 2026 15:48:11 +0200
Lukas Wunner <lukas@wunner.de> wrote:

> 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;  
> 
> ICYMI, sashiko's AI-generated review alleges that the if-else condition
> may cause a timing side channel vis-à-vis binary arithmetic:
> 
> https://sashiko.dev/#/patchset/20260508114844.29694-1-sv3iry%40gmail.com
> 
> You may want to address this if/when respinning your patch.  If you do,
> a code comment is probably merited to explain this subtlety.

Something like:	
	r2 += (r01.m_high < product.m_high);
	r2 += (r01.m_high == product.m_high) & (r01.m_low < product.m_low);
would be constant time - but the compiler is very unlikely to generate
the object code you want on all (any?) architectures.

On x86 you want something like (pardon the pigeon assembler):
	xor %rax,%rax
	cmp r01.m_high, product.m_high
	setc %al
	lea r2, (r2, %rax)
	sete %al
	cmp r01.m_low, product.m_low
	cmovnc %al, %ah
	add r2, %rax
but I bet (two beers) you can't get it.

-- David

> 
> Thanks,
> 
> Lukas
>

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

Posted by Lukas Wunner 1 month ago

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

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

Posted by Stefan Berger 1 month ago


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;