[PATCH] MPI helper of comparison, Least Leak Intended

[Jacob Bachmeyer]

On 2/6/25 23:28, NIIBE Yutaka via Gcrypt-devel wrote:
> Hello,
>
> This is not related to modular exponentiation, but another function for
> constant-time; MPI comparison by a helper function.
>
> I think that this implementation could be improved.  Anyhow, let us
> start having the function for comparison.

While I am not entirely familiar with the details of the Gcryipt MPI 
implementation, I am unsure of the equivalence some of the comments 
imply.  Details inline below.

> diff --git a/mpi/mpi-internal.h b/mpi/mpi-internal.h
> index ffe8140a..0840d1fd 100644
> [...]
> diff --git a/mpi/mpih-const-time.c b/mpi/mpih-const-time.c
> index e684b956..4549ebca 100644
> --- a/mpi/mpih-const-time.c
> +++ b/mpi/mpih-const-time.c
> @@ -239,3 +239,25 @@ _gcry_mpih_cmp_ui (mpi_ptr_t up, mpi_size_t usize, unsigned long v)
>       }
>     return 1;
>   }
> +
> +/* Do same calculation as _gcry_mpih_cmp does, but Least Leak Intended.
> + * Return 1 if U > V, 0 if they are equal, and -1 if U < V.  */
> +int
> +_gcry_mpih_cmp_lli (mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size)
> +{
> +  mpi_size_t i;
> +  mpi_limb_t gt, lt;
> +  mpi_limb_t result = 0;

If you can initialize an mpi_limb_t to literal zero, then I know that 
mpi_limb_t is an integer type.

> +
> +  for (i = 0; i < size ; i++)
> +    {
> +      gt = mpih_ct_limb_greater_than (up[i], vp[i]);
> +      lt = mpih_ct_limb_less_than (up[i], vp[i]);

To check my understanding:  at most one of GT, LT can be non-zero; both 
are zero if UP[I]==VP[I].  I assume that the comparisons are done using 
function calls because "<" and ">" are not guaranteed to be constant-time?

> +      /* result = gt ? 1 : result; */
> +      result = (result & (- mpih_limb_is_zero (gt))) | gt;
> +      /* result = lt ? -1 : result; */
> +      result = (result & (- mpih_limb_is_zero (lt))) | -lt;

Why are these using mpih_limb_is_zero when mpi_limb_t is an integer type?

Assuming that mpih_liimb_is zero returns 1 if its argument is zero and 0 
otherwise, in constant time, and we work from least-significant to 
most-significant, such that the last non-equal result determines the 
overall result, should these two lines instead be:

result = (result & (- mpih_limb_is_zero (lt))) |  gt;
result = (result & (- mpih_limb_is_zero (gt))) | -lt;

Since at most one of the flags can be set, each result line should pass 
the old value iff the /other/ flag is clear/zero.

> +    }
> +
> +  return result;
> +}
>
Overall comments and questions:

Could this be made more efficient by defining an mpih_ct_limb_cmp 
function and then only needing to reduce it in constant time? Then we 
could work from the least-significant to most-significant limb and only 
need to find a constant-time evaluation of ({previous, this}) {X, -1} -> 
-1, {X, 1} -> 1, {X, 0} -> X.

There might be a potential power-usage leak between setting 1 and -1 
(the population counts radically differ); could we instead use 1 and 2 
(adjacent bits, each one-hot) as the running flag values or even as the 
result codes?  (Maybe 1, 2, and 4 for one-hot encodings of less, equal, 
greater?)


-- Jacob

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.gnupg.org/pipermail/gcrypt-devel/attachments/20250207/219c54ff/attachment.html>