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<gni...@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
_______________________________________________
Gcrypt-devel mailing list
Gcrypt-devel@gnupg.org
https://lists.gnupg.org/mailman/listinfo/gcrypt-devel
