[PATCH] MPI helper of comparison, Least Leak Intended

[Jacob Bachmeyer]

On 2/9/25 08:06, Jussi Kivilinna wrote:
> 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.
>
> [...]

I had not thought of that.  Thank you.

>>
>> 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 */

This still leaves a small difference between "equal" (Hamming weight of 
zero) and "not equal" (both with Hamming weight of one).  I was 
originally thinking of using 1, 2, and 4 as result codes to avoid that 
difference.

However, using 0 vs 1 vs INT_MIN certainly greatly reduces the potential 
leak.  Would it be expected to weaken the signal enough for it to be 
lost in the other noise in a practical system?

For example, the Hamming weights of the MPI limbs are definitely 
variable, and I am unsure if there is anything software can reasonably 
do to mitigate that.  Storing both true and complement might help, but 
would be a different in-memory representation and computing with both 
might even make a stronger signal.

I think using 0/1/INT_MIN as results is probably the best we can do if 
we want to keep to the C convention of using comparison to zero as a 
proxy for the result of a complex comparison.  There are still several 0 
vs 1 values used in the loop, but changing that would likely cascade 
throughout the MPI implementation.

Overall, I suggest using Jussi Kivilinna's last suggestion and leaving 
"fully charge balanced" for another day.


-- Jacob