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).
Description
Details
- Version
- 1.11
Revisions and Commits
rC libgcrypt | |||
rC54caef02afa9 cipher:(EC)DSA: Simply use mpi_clear_highbit in _gcry_dsa_gen_k. | |||
rCc1da86e45a6e mpi: Avoid normalizing MPI in _gcry_mpi_invm. | |||
rCbd53c51b0338 mpi: Fix _gcry_mpih_add_lli, as macro. | |||
rCbb5e893456b1 cipher:(EC)DSA: Fix _gcry_dsa_gen_*k not to normalize MPI. | |||
rC0b794c208db3 cipher:(EC)DSA: Avoid MPI normalize by mpi_rshift. | |||
rCd05cdb31689a cipher:(EC)DSA: Fix _gcry_dsa_modify_k to least leak. | |||
rC58e72af4eac4 mpi: Add _gcry_mpih_add_lli. |
Related Objects
Event Timeline
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).
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);
One more change for mpi_invm in rCc1da86e45a6e: mpi: Avoid normalizing MPI in _gcry_mpi_invm.
One more change for _gcry_dsa_gen_k in rC54caef02afa9: cipher:(EC)DSA: Simply use mpi_clear_highbit in _gcry_dsa_gen_k.
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.