[PATCH] MPI helper of comparison, Least Leak Intended

[Alicja Kario]

On Monday, 10 February 2025 05:02:12 CET, Jacob Bachmeyer via Gcrypt-devel 
wrote:
> On 2/9/25 08:06, Jussi Kivilinna wrote:
>> Hello,
>> 
>> On 9.2.2025 0.50, Jacob Bachmeyer via Gcrypt-devel wrote: ...
>
> I had not thought of that.  Thank you.
>
>>> ...
>> 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.

Proper CPUs (stuff that's running in servers or desktops) do not have
timing differences on operands of bitwise instructions. The only possibly
problematic one is integer division.

This kind of Hamming weight leakage is important for EM or power leakage on
super small embedded CPUs.

And that kind of leakage is outside the threat model of libgcrypt:
https://www.gnupg.org/documentation/security.html

> Those hardware related threats are out of scope in Libgcrypt's threat model. It is up to users not to offer any access to those side-channels. 

It's necessary to not use < or > operands in C code because of the jumps
the compiler creates, not because the actual hardware instruction takes
different amount of time depending on operands.
-- 
Regards,
Alicja (nee Hubert) Kario
Principal Quality Engineer, RHEL Crypto team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 115, 612 00, Brno, Czech Republic