Side-channel leakage in the mpz_powm_sec interface

[marco.bodrato at tutanota.com]

Ciao,

25 ago 2023, 08:11 da nisse at lysator.liu.se:

> Niels Möller <nisse at lysator.liu.se> writes:
>
>> It's preferable to use the mpn_powm_sec. When using mpz_t, I see no
>> reasonable to avoid leakage of the normalized size (or number of
>> all-zero limbs at the most significant end).
>>
> One possibly unreasonable approach for consideration:
>
> 1. Document that the mpz_t result from mpz_powm_sec always has an alloc
> size >= n, where n is the limb size of the modulo input, and that the
> limb array is zero padded up to n.
>

You write ">= n" and not "=n" because if it was larger we avoid to re-allocate it, right?


> 2. Ensure that the implementation complies with (1) (probably easy, if
> array is written by a call to mpn_sec_powm).
>

The current implementation uses a buffer, and copies only the relevant (non-zero) limbs at the end. As usual, this is done to handle reuse of an operand as the result variable.


> 3. Do the normalization, i.e., assignment of the size field, by
> side-channel silent logic iterating over all n limbs.
>

This sounds not too complex to do. Even if, as usual, C code is prone to compiler optimizations...
I think this is a good idea.

> However, any application taking advantage of (1) (and thus avoiding
> calling any other mpz functions on the result) could maybe just as well
> use mpn_sec_powm directly?
>
The application does not really need to "take advantage of" the fact that allocated space may be larger than the strictly-needed space, should it?
But this can heal the allocation problem on the result-side. If the operand to be passed to mpz_powm_sec is previously handled by some other mpz_ non _sec function, then its size in memory can be different...

A possible implementation of your 2-3 points (I didn't look at documentation) could be the following.
Also the if branch could be replaced with silent logic, but I'd rather document that the function is silent if the base is positive.

Gis,m

--- a/mpz/powm_sec.c    Fri Oct 28 16:31:44 2022 +0200
+++ b/mpz/powm_sec.c    Fri Aug 25 10:38:35 2023 +0200
@@ -85,7 +85,13 @@
 
   rn = n;
 
-  MPN_NORMALIZE (rp, rn);
+  {
+    int z = ! rp[--rn];
+    mp_size_t cz = z;
+    for (; rn; cz += (z &= ! rp[--rn]) )
+      ;
+    rn = n - cz;
+  }
 
   if ((ep[0] & 1) && SIZ(b) < 0 && rn != 0)
     {
@@ -94,9 +100,9 @@
       MPN_NORMALIZE (rp, rn);
     }
 
-  MPZ_NEWALLOC (r, rn);
+  MPZ_NEWALLOC (r, n);
   SIZ(r) = rn;
-  MPN_COPY (PTR(r), rp, rn);
+  MPN_COPY (PTR(r), rp, n);
 
   TMP_FREE;
}