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.
--
>From 6970e93a7f45e0bd2d553239555f03e7ec3e25fa Mon Sep 17 00:00:00 2001
From: NIIBE Yutaka <gni...@fsij.org>
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 <gni...@fsij.org>
---
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
>From 27cf880c80f7390e506bab0d8e0b43cb31cfe833 Mon Sep 17 00:00:00 2001
From: NIIBE Yutaka <gni...@fsij.org>
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 <gni...@fsij.org>
---
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
>From a4f435e0920a0280465d0dceeac13e3624cabb8b Mon Sep 17 00:00:00 2001
From: NIIBE Yutaka <gni...@fsij.org>
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 <gni...@fsij.org>
---
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
_______________________________________________
Gcrypt-devel mailing list
Gcrypt-devel@gnupg.org
https://lists.gnupg.org/mailman/listinfo/gcrypt-devel
