<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<div class="moz-cite-prefix">On 2/6/25 23:28, NIIBE Yutaka via
Gcrypt-devel wrote:<br>
</div>
<blockquote type="cite" cite="mid:87plju492s.fsf@akagi.fsij.org">
<pre wrap="" class="moz-quote-pre">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.</pre>
</blockquote>
<p>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.</p>
<p><span style="white-space: pre-wrap">
</span><span style="white-space: pre-wrap">
</span></p>
<blockquote type="cite" cite="mid:87plju492s.fsf@akagi.fsij.org">
<pre wrap="" class="moz-quote-pre">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;</pre>
</blockquote>
<p>If you can initialize an mpi_limb_t to literal zero, then I know
that mpi_limb_t is an integer type.</p>
<blockquote type="cite" cite="mid:87plju492s.fsf@akagi.fsij.org">
<pre wrap="" class="moz-quote-pre">+
+ 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]);</pre>
</blockquote>
<p>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?<span
style="white-space: pre-wrap">
</span></p>
<blockquote type="cite" cite="mid:87plju492s.fsf@akagi.fsij.org">
<pre wrap="" class="moz-quote-pre">+ /* result = gt ? 1 : result; */
+ result = (result & (- mpih_limb_is_zero (gt))) | gt;
+ /* result = lt ? -1 : result; */
+ result = (result & (- mpih_limb_is_zero (lt))) | -lt;</pre>
</blockquote>
<p>Why are these using mpih_limb_is_zero when mpi_limb_t is an
integer type?</p>
<p>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:</p>
<pre>result = (result & (- mpih_limb_is_zero (lt))) | gt;
result = (result & (- mpih_limb_is_zero (gt))) | -lt;
</pre>
<p>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.<span
style="white-space: pre-wrap">
</span></p>
<blockquote type="cite" cite="mid:87plju492s.fsf@akagi.fsij.org">
<pre wrap="" class="moz-quote-pre">+ }
+
+ return result;
+}
</pre>
</blockquote>
<p>Overall comments and questions:</p>
<p>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.</p>
<p>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?)<br>
</p>
<p><br>
</p>
<p>-- Jacob<br>
</p>
<p><br>
</p>
</body>
</html>