(EC)DSA signature generation constant-time (not depend value of K)
NIIBE Yutaka via Gcrypt-devel <[email protected]>
| Newsgroups | gmane.comp.encryption.gpg.libgcrypt.devel |
|---|---|
| Message-ID | <[email protected]> |
Hello, For (EC)DSA signature generation, I created a ticket: https://dev.gnupg.org/T7519 And added some patches (including some *_lli routines). Here are more patches to be applied on top of master commit of: 58e72af4eac4711993191919b6890b5ebb554acc Major improvement for least leak might be the change of _gcry_dsa_modify_k. _gcry_dsa_modify_k was introduced for original Minerva attack so that the length of limbs for K is always same size, but use of mpi_add in the routine becomes the source of the signal for K. -- _______________________________________________ Gcrypt-devel mailing list [email protected] https://lists.gnupg.org/mailman/listinfo/gcrypt-devel
0001-cipher-EC-DSA-Fix-_gcry_dsa_modify_k-to-least-leak.patch
(text/x-diff, 1.5 KB)
>From 6970e93a7f45e0bd2d553239555f03e7ec3e25fa Mon Sep 17 00:00:00 2001 From: NIIBE Yutaka <[email protected]> Date: Mon, 10 Feb 2025 13:32:55 +0900 Subject: [PATCH 1/3] cipher:(EC)DSA: Fix _gcry_dsa_modify_k to least leak. * cipher/dsa-common.c (_gcry_dsa_modify_k): Use _gcry_mpih_add_lli. -- GnuPG-bug-id: 7519 Signed-off-by: NIIBE Yutaka <[email protected]> --- cipher/dsa-common.c | 25 ++++++++++++++++--------- 1 file changed, 16 insertions(+), 9 deletions(-) diff --git a/cipher/dsa-common.c b/cipher/dsa-common.c index 170dce12..8b401e78 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" @@ -42,15 +43,21 @@ void _gcry_dsa_modify_k (gcry_mpi_t k, gcry_mpi_t q, int qbits) { - gcry_mpi_t k1 = mpi_new (qbits+2); - - mpi_resize (k, (qbits+2+BITS_PER_MPI_LIMB-1) / BITS_PER_MPI_LIMB); - k->nlimbs = k->alloced; - mpi_add (k, k, q); - mpi_add (k1, k, q); - mpi_set_cond (k, k1, (1 - mpi_test_bit (k, qbits))); - - mpi_free (k1); + mpi_limb_t cy; + unsigned long once_more; + mpi_size_t ksize; + + ksize = (qbits+1+BITS_PER_MPI_LIMB-1) / BITS_PER_MPI_LIMB; + mpi_resize (k, ksize); + k->nlimbs = ksize; + + cy = _gcry_mpih_add_lli (k->d, k->d, q->d, q->nlimbs); + if (k->nlimbs > q->nlimbs) + k->d[k->nlimbs-1] = cy; + once_more = 1 - mpi_test_bit (k, qbits); + _gcry_mpih_add_n_cond (k->d, k->d, q->d, q->nlimbs, once_more); + if (k->nlimbs > q->nlimbs) + k->d[k->nlimbs-1] = 1; } /* -- 2.39.5
0002-cipher-EC-DSA-Avoid-MPI-normalize-by-mpi_rshift.patch
(text/x-diff, 1.2 KB)
>From 27cf880c80f7390e506bab0d8e0b43cb31cfe833 Mon Sep 17 00:00:00 2001 From: NIIBE Yutaka <[email protected]> Date: Mon, 17 Feb 2025 14:15:17 +0900 Subject: [PATCH 2/3] cipher:(EC)DSA: Avoid MPI normalize by mpi_rshift. * cipher/dsa-common.c (_gcry_dsa_gen_rfc6979_k): Use _gcry_mpi_set_buffer and _gcry_mpih_rshift, instead of _gcry_mpi_scan and mpi_rshift. -- GnuPG-bug-id: 7519 Signed-off-by: NIIBE Yutaka <[email protected]> --- cipher/dsa-common.c | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) diff --git a/cipher/dsa-common.c b/cipher/dsa-common.c index 8b401e78..0d8d121f 100644 --- a/cipher/dsa-common.c +++ b/cipher/dsa-common.c @@ -320,12 +320,14 @@ _gcry_dsa_gen_rfc6979_k (gcry_mpi_t *r_k, /* k = bits2int (T) */ mpi_free (k); - k = NULL; - rc = _gcry_mpi_scan (&k, GCRYMPI_FMT_USG, t, (tbits+7)/8, NULL); - if (rc) - goto leave; - if (tbits > qbits) - mpi_rshift (k, k, tbits - qbits); + k = mpi_alloc_secure ((qbits+7)/8); + _gcry_mpi_set_buffer (k, t, (qbits+7)/8, 0); + if (qbits % 8) + { + unsigned int nbits = 8 - (qbits % 8); + + _gcry_mpih_rshift (k->d, k->d, k->nlimbs, nbits); + } /* Check: k < q and k > 1 */ if (!(mpi_cmp (k, dsa_q) < 0 && mpi_cmp_ui (k, 0) > 0)) -- 2.39.5
0003-cipher-EC-DSA-Fix-_gcry_dsa_gen_-k-not-to-normalize-.patch
(text/x-diff, 1.6 KB)
>From a4f435e0920a0280465d0dceeac13e3624cabb8b Mon Sep 17 00:00:00 2001 From: NIIBE Yutaka <[email protected]> Date: Mon, 17 Feb 2025 14:18:38 +0900 Subject: [PATCH 3/3] cipher:(EC)DSA: Fix _gcry_dsa_gen_*k not to normalize MPI. * cipher/dsa-common.c (_gcry_dsa_gen_k): Use _gcry_mpih_cmp_lli and _gcry_mpih_cmp_ui. (_gcry_dsa_gen_rfc6979_k): Likewise. -- GnuPG-bug-id: 7519 Signed-off-by: NIIBE Yutaka <[email protected]> --- cipher/dsa-common.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/cipher/dsa-common.c b/cipher/dsa-common.c index 0d8d121f..d63defda 100644 --- a/cipher/dsa-common.c +++ b/cipher/dsa-common.c @@ -112,13 +112,13 @@ _gcry_dsa_gen_k (gcry_mpi_t q, int security_level) mpi_clear_bit (k, nbits-1); } - if (!(mpi_cmp (k, q) < 0)) /* check: k < q */ + if (!(_gcry_mpih_cmp_lli (k->d, q->d, k->nlimbs) < 0)) /* check: k < q */ { if (DBG_CIPHER) 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"); @@ -330,7 +330,8 @@ _gcry_dsa_gen_rfc6979_k (gcry_mpi_t *r_k, } /* Check: k < q and k > 1 */ - if (!(mpi_cmp (k, dsa_q) < 0 && mpi_cmp_ui (k, 0) > 0)) + if (!(_gcry_mpih_cmp_lli (k->d, dsa_q->d, k->nlimbs) < 0 + && _gcry_mpih_cmp_ui (k->d, k->nlimbs, 0) > 0)) { /* K = HMAC_K(V || 0x00) */ rc = _gcry_md_setkey (hd, K, hlen); -- 2.39.5