Less Leaky ECDSA signature generation (in master)

[NIIBE Yutaka]

Hello,

Thank you for your comments and questions.

Jacob Bachmeyer <jcb62281 at gmail.com> wrote:
> On 3/26/25 19:06, NIIBE Yutaka wrote:
>> [...]  For the first improvement,
>> I realized that runtime checks in ec_mod and its friends could be leaky,
>> because it depends on how small/big the value is.
>
> Could these checks instead be improved to run in constant time?

Possibly.  But I don't think it's worth the effort.

Let me explain a bit for libgcrypt ECC implementation (of Weierstrass
curve); ECC point is represented by (X, Y) in affine coordinates, or
(X:Y:Z) in projective coordinates.  It uses the MPI representation for
the finite field for X, Y, or Z.

While, arbitrary integers can be represented in the MPI representation,
for a specific curve, the finite field is the one of integers module P
(P: a prime defined by the curve).  Thus, for an ECC point, we can keep
the integer value in the range from 0 to P-1.  For an intermediate value
of integer (like multiplication), 2*P is enough size.

And our internal use of ec_mod is the reduction (from 0 to 2*P-1 to 0 to
P-1), actually, not general computation of % P.

>> Since it is (or can be) precondition for those routines in the code of
>> libgcrypt, it can be removed.  Since it could be leaky, it's good to be
>> removed.
>
> Hypothetically, if those preconditions are violated, what could go 
> wrong?  How badly does the math fall apart?  Could an invalid result 
> potentially (partially) expose the signing key?

For our internal use (signature generation, ECDH computation), there are
no places where it's violated.  No risk like exposing the private keys,
for libgcrypt's own public key crypto.

Because we expose the lower level API, it is possible for an application
to violate the preconditions, by supplying an ECC point with larger MPIs.

By the violation of the preconditions, it used to result the call of
log_bug (emitting a message and abort).  After the change of mine, it
results wrong value, by using lower bits and ignoring upper bits.

> Removing runtime checks in this type of code makes me nervous. Maybe it 
> is just paranoia.

No, I'd understand your point.  I appreciate your concerns.

If we'd take an approach of more kindness, we could add the check for
the external API to examine the field in ECC points for preconditions.
--