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