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

[David Laight]

On Tue, 12 May 2026 15:48:11 +0200
Lukas Wunner <lukas@xxxxxxxxx> 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
>