Page MenuHome GnuPG

libgcrypt: (EC)DSA signature generation should be constant-time
Testing, WishlistPublic

Description

Current implementation of (EC)DSA signature generation is leaky for K.
Reportedly, for NIST384p curve, timing difference ~800 ns could be observed (by billion of invocations).

Details

Version
1.11

Event Timeline

gniibe triaged this task as Wishlist priority.
gniibe created this task.

This is needed for RFC6979 flag support.

And then, calls of mpi_cmp should be fixed (by using _gcry_mpih_cmp_lli), so that no timing difference by the value of K.

Commit rC35a6a6feb9dc: Fix _gcry_dsa_modify_k. is related, but it doesn't matter for usual compilers (it's an issue for MSVC).

This is needed before we remove leaks by mpi_add in _gcry_dsa_modify_k :

And this is for less leak for _gcry_dsa_modify_k:

And then, we need to use less leaky version of mpi_cmp (because mpi_cmp calls mpi_normalize, it's not good).

Use of mpi_cmp is now being fixed, by providing _gcry_mpih_cmp_lli function.
Along with that, we need to fix use of mpi_cmp_ui, since it's skips earlier depending its limbs.

diff --git a/cipher/dsa-common.c b/cipher/dsa-common.c
index 170dce12..e010e182 100644
--- a/cipher/dsa-common.c
+++ b/cipher/dsa-common.c
@@ -25,6 +25,7 @@
 
 #include "g10lib.h"
 #include "mpi.h"
+#include "mpi-internal.h"
 #include "cipher.h"
 #include "pubkey-internal.h"
 
@@ -111,7 +112,7 @@ _gcry_dsa_gen_k (gcry_mpi_t q, int security_level)
             log_debug ("\tk too large - again\n");
           continue; /* no  */
         }
-      if (!(mpi_cmp_ui (k, 0) > 0)) /* check: k > 0 */
+      if (!(_gcry_mpih_cmp_ui (k->d, k->nlimbs, 0) > 0)) /* check: k > 0 */
         {
           if (DBG_CIPHER)
             log_debug ("\tk is zero - again\n");
@@ -321,7 +322,7 @@ _gcry_dsa_gen_rfc6979_k (gcry_mpi_t *r_k,
     mpi_rshift (k, k, tbits - qbits);
 
   /* Check: k < q and k > 1 */
-  if (!(mpi_cmp (k, dsa_q) < 0 && mpi_cmp_ui (k, 0) > 0))
+  if (!(mpi_cmp (k, dsa_q) < 0 && _gcry_mpih_cmp_ui (k->d, k->nlimbs, 0) > 0))
     {
       /* K = HMAC_K(V || 0x00) */
       rc = _gcry_md_setkey (hd, K, hlen);
gniibe changed the task status from Open to Testing.Feb 19 2025, 5:36 AM

All changes are pushed to master.

I think that major signal sources for K have been killed so far.

Still, since our MPI routines are not written as const-time, it's somehow leaky and the difference of timing can be easily detected.

To have less variations for computation time, we need to avoid normalizing MPI.

Here is the first attempt.

Here is update (replacing ecc-no-normalize-2025-03-07.patch).
ec_subm and ec_mulm are modified to be less leaky.

There are three (or more) remaining things:
(1) ec_addm can be improved by adding U and V with mpih_add_lli , subtracting P with mpih_sub_n, and adding back P with mpih_add_n_cond
(2) Places with mpi_const for the argument when calling ec_mulm, ec_add or ec_subm should be fixed (it may modify the const MPI)
(3) make sure mpi_resize within ec_addm, ec_mulm, or ec_subm if needed

Here is another update (replacing ecc-no-normalize-2025-03-13.patch).
Further, ec_addm is modified to be less leaky.

I think that this may be the last update.
Don't use mpi_powm to avoid normalizing (and to be faster).

I applied some to master (generic improvement parts).

Here is update of the patch against rC17d5d3262c14: mpi:ec: Use ec_addm to multiply with small integer.