Re: [PATCH] crypto: ecc - Optimize vli additive operations using compiler builtins

[Fabian]

On Wed, 10 Jun 2026 at 16:52, Stefan Berger <stefanb@xxxxxxxxxxxxx> wrote:
>
>
>
> On 6/9/26 4:51 PM, Fabian wrote:
> > On Tue, 9 Jun 2026 at 20:58, Stefan Berger <stefanb@xxxxxxxxxxxxx> wrote:
> >>
> >>
> >>
> >> On 6/7/26 7:24 AM, Fabian Blatter wrote:
> >>> 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.
> >>
> >> It looks like you made vli_usub and vli_uadd constant-time now because
> >> otherwise the loops could be ended early once borrow == 0 or carry == 0
> >> respectively. Are all the other functions that operate on the private
> >> keys constant-time?
> >>
> >
> > Thanks for the reply,
> >
> > My primary goal with this patch was performance optimization.
> > I did not add early exiting because the original version didn't either.
> >
> > To answer your question: No, some other functions in ecc.c
> > are not constant-time. For example, vli_is_zero and vli_cmp both
> > contain early exits.
>  > > My patch does remove the branches in the inner loop,
> > however, the original ones were already constant-time in practice,
> > because the compiler replaces the branches with cmov's.
>  > > I am happy to make any changes to this patch if you like.
>
> ecrdsa calls ecc_is_pubkey_valid_partial -> vli_mod_square_fast ->
> vli_mmod_fast and then may call vli_usub or vli_uadd via
> vli_mmod_special2 or vli_mmod_barret.
>
> ecc_point_mult operates on a private key and will call vli_mmod_fast and
> for some non-NIST keys it may call either one of vli_usub or vli_uadd
> via vli_mmod_special2 or vli_mmod_barret.
>
> Due to the private key operations it's probably better to keep the
> functions constant-time for now.

Agreed.

>
> > I could also look into making `vli_cmp` and `vli_is_zero`,
> > or others constant-time in a future patch.
>
> I wonder whether it would be practical to suffix constant-time functions
> with _ct so that it becomes visible whether the call paths of functions
> operation on private keys only call _ct functions? Sometimes one could
> optimize functions shared by private and public key operations for
> performance -- call them with 'bool ct' in this case and suffix them
> with _oct (o=optimized + ct) indicating that they support both variants?
>

I am unsure whether constant-time operations are even slower than
early-exit variants by a significant margin. vli_uadd and vli_usub
don't seem to be called that often anyways. I believe this probably
doesn't justify the resulting binary size and complexity increase.

Let me know how you'd like to move forward.