[PATCH] MPI helper of comparison, Least Leak Intended

[Jussi Kivilinna]

Hello,

On 9.2.2025 0.50, Jacob Bachmeyer via Gcrypt-devel wrote:
> On 2/7/25 20:05, NIIBE Yutaka via Gcrypt-devel wrote:
>> NIIBE Yutaka<gniibe at fsij.org> wrote:
>>> I think that this implementation could be improved.
>> I should use ct_limb_gen_inv_mask function instead of directly use unary
>> minus operator.
> 
> Could it make more sense to write:
> 
> result &= ct_limb_gen_inv_mask (gt) & ct_limb_gen_inv_mask (lt);
> result |= gt | -lt;
> 
> Assuming that ct_limb_gen_inv_mask returns all-bits-set if its argument is zero and all-bits-clear otherwise, the first line clears result if a previous value is to be overwritten and the second sets the new value.
> 
> I also still suggest considering an alternate encoding for the comparison result.  The Hamming distance between 0 and 1 is 1, but the Hamming distance between 0 and -1 is the maximum on a 2's complement machine, which means that any information leakage on the power rail will be at its strongest when the comparison result is "less than".

I'd move final result generation outside from the loop and instead generate separate result_lt and result_gt values in loop. These would then be combined at the end of function to form final result code. That should mostly mitigate the 0/1/-1 hamming distance EM leakage from inside the loop.

   int
   _gcry_mpih_cmp_lli (mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size)
   {
     mpi_size_t i;
     mpi_limb_t res_gt = 0;
     mpi_limb_t res_lt = 0;

     for (i = 0; i < size ; i++)
       {
         mpi_limb_t gt, lt, eq, neq;
         gt = mpih_ct_limb_greater_than (up[i], vp[i]);
         lt = mpih_ct_limb_less_than (up[i], vp[i]);
         neq = ct_limb_gen_mask(gt | lt);
         eq = ct_limb_gen_inv_mask(gt | lt);
         res_gt = (eq & res_gt) | (neq & gt);
         res_lt = (eq & res_lt) | (neq & lt);
       }

     return (int)(res_gt - res_lt); /* return 0 if U==V, 1 if U>V, -1 if U<V */
   }

> 
> A one-hot encoding would have a constant Hamming distance (of 2) between any pair of valid values.

If returned value (0 vs 1 vs -1) could cause EM leakage, last line of function could be changed to something like:

   return (int)(res_gt | (res_lt << 1)); /* return 0 if U==V, 1 if U>V, 2 if U<V */

Or if having sign-bit set is important but we want to avoid "set all bits to ones" case, then only set sign-bit for "U<V":

   return (int)(res_gt | (res_lt << (sizeof(int) * CHAR_BIT - 1))); /* return 0 if U==V, 1 if U>V, INT_MIN if U<V */

-Jussi