nettle: add functions for deterministic ECDSA/DSA

This adds functions to perform deterministic ECDSA/DSA, namely
_gnutls_{ecdsa,dsa}_compute_k(), which computes the k value according
to RFC 6979.  The retrieved k value can be given to
nettle_{ecdsa,dsa}_sign() through a wrapper random function.

Signed-off-by: Daiki Ueno <dueno@redhat.com>

6 files changed, 523 insertions, 0 deletions

diff --git a/lib/nettle/int/dsa-compute-k.c b/lib/nettle/int/dsa-compute-k.c
new file mode 100644
index 0000000000..17d63318c4
--- /dev/null
+++ b/lib/nettle/int/dsa-compute-k.c
@@ -0,0 +1,209 @@
+/*
+ * Copyright (C) 2019 Red Hat, Inc.
+ *
+ * Author: Daiki Ueno
+ *
+ * This file is part of GNUTLS.
+ *
+ * The GNUTLS library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * as published by the Free Software Foundation; either version 2.1 of
+ * the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>
+ *
+ */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "dsa-compute-k.h"
+
+#include "gnutls_int.h"
+#include "mem.h"
+#include "mpn-base256.h"
+#include <string.h>
+
+#define BITS_TO_LIMBS(bits) (((bits) + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS)
+
+/* The maximum size of q, choosen from the fact that we support
+ * 521-bit elliptic curve generator and 512-bit DSA subgroup at
+ * maximum. */
+#define MAX_Q_BITS 521
+#define MAX_Q_SIZE ((MAX_Q_BITS + 7) / 8)
+#define MAX_Q_LIMBS BITS_TO_LIMBS(MAX_Q_BITS)
+
+#define MAX_HASH_BITS (MAX_HASH_SIZE * 8)
+#define MAX_HASH_LIMBS BITS_TO_LIMBS(MAX_HASH_BITS)
+
+int
+_gnutls_dsa_compute_k(mpz_t k,
+		      const mpz_t q,
+		      const mpz_t x,
+		      gnutls_mac_algorithm_t mac,
+		      const uint8_t *digest,
+		      size_t length)
+{
+	uint8_t V[MAX_HASH_SIZE];
+	uint8_t K[MAX_HASH_SIZE];
+	uint8_t xp[MAX_Q_SIZE];
+	uint8_t tp[MAX_Q_SIZE];
+	mp_limb_t h[MAX(MAX_Q_LIMBS, MAX_HASH_LIMBS)];
+	mp_bitcnt_t q_bits = mpz_sizeinbase (q, 2);
+	mp_size_t qn = mpz_size(q);
+	mp_bitcnt_t h_bits = length * 8;
+	mp_size_t hn = BITS_TO_LIMBS(h_bits);
+	size_t nbytes = (q_bits + 7) / 8;
+	const uint8_t c0 = 0x00;
+	const uint8_t c1 = 0x01;
+	mp_limb_t cy;
+	gnutls_hmac_hd_t hd;
+	int ret = 0;
+
+	if (unlikely(q_bits > MAX_Q_BITS))
+		return gnutls_assert_val(GNUTLS_E_INVALID_REQUEST);
+	if (unlikely(length > MAX_HASH_SIZE))
+		return gnutls_assert_val(GNUTLS_E_INVALID_REQUEST);
+
+	/* int2octets(x) */
+	mpn_get_base256(xp, nbytes, mpz_limbs_read(x), qn);
+
+	/* bits2octets(h) */
+	mpn_set_base256(h, hn, digest, length);
+
+	if (hn < qn)
+		/* qlen > blen: add zero bits to the left */
+		mpn_zero(&h[hn], qn - hn);
+	else if (h_bits > q_bits) {
+		/* qlen < blen: keep the leftmost qlen bits.  We do this in 2
+		 * steps because mpn_rshift only accepts shift count in the
+		 * range 1 to mp_bits_per_limb-1.
+		 */
+		mp_bitcnt_t shift = h_bits - q_bits;
+
+		if (shift / GMP_NUMB_BITS > 0) {
+			mpn_copyi(h, &h[shift / GMP_NUMB_BITS], qn);
+			hn -= shift / GMP_NUMB_BITS;
+		}
+
+		if (shift % GMP_NUMB_BITS > 0)
+			mpn_rshift(h, h, hn, shift % GMP_NUMB_BITS);
+	}
+
+	cy = mpn_sub_n(h, h, mpz_limbs_read(q), qn);
+	/* Fall back to addmul_1, if nettle is linked with mini-gmp. */
+#ifdef mpn_cnd_add_n
+	mpn_cnd_add_n(cy, h, h, mpz_limbs_read(q), qn);
+#else
+	mpn_addmul_1(h, mpz_limbs_read(q), qn, cy != 0);
+#endif
+	mpn_get_base256(tp, nbytes, h, qn);
+
+	/* Step b */
+	memset(V, c1, length);
+
+	/* Step c */
+	memset(K, c0, length);
+
+	/* Step d */
+	ret = gnutls_hmac_init(&hd, mac, K, length);
+	if (ret < 0)
+		goto out;
+	ret = gnutls_hmac(hd, V, length);
+	if (ret < 0)
+		goto out;
+	ret = gnutls_hmac(hd, &c0, 1);
+	if (ret < 0)
+		goto out;
+	ret = gnutls_hmac(hd, xp, nbytes);
+	if (ret < 0)
+		goto out;
+	ret = gnutls_hmac(hd, tp, nbytes);
+	if (ret < 0)
+		goto out;
+	gnutls_hmac_deinit(hd, K);
+
+	/* Step e */
+	ret = gnutls_hmac_fast(mac, K, length, V, length, V);
+	if (ret < 0)
+		goto out;
+
+	/* Step f */
+	ret = gnutls_hmac_init(&hd, mac, K, length);
+	if (ret < 0)
+		goto out;
+	ret = gnutls_hmac(hd, V, length);
+	if (ret < 0)
+		goto out;
+	ret = gnutls_hmac(hd, &c1, 1);
+	if (ret < 0)
+		goto out;
+	ret = gnutls_hmac(hd, xp, nbytes);
+	if (ret < 0)
+		goto out;
+	ret = gnutls_hmac(hd, tp, nbytes);
+	if (ret < 0)
+		goto out;
+	gnutls_hmac_deinit(hd, K);
+
+	/* Step g */
+	ret = gnutls_hmac_fast(mac, K, length, V, length, V);
+	if (ret < 0)
+		goto out;
+
+	/* Step h */
+	for (;;) {
+		/* Step 1 */
+		size_t tlen = 0;
+
+		/* Step 2 */
+		while (tlen < nbytes) {
+			size_t remaining = MIN(nbytes - tlen, length);
+			ret = gnutls_hmac_fast(mac, K, length, V, length, V);
+			if (ret < 0)
+				goto out;
+			memcpy (&tp[tlen], V, remaining);
+			tlen += remaining;
+		}
+
+		/* Step 3 */
+		mpn_set_base256 (h, qn, tp, tlen);
+		if (tlen * 8 > q_bits)
+			mpn_rshift (h, h, qn, tlen * 8 - q_bits);
+		/* Check if k is in [1,q-1] */
+		if (!mpn_zero_p (h, qn) &&
+		    mpn_cmp (h, mpz_limbs_read(q), qn) < 0) {
+			mpn_copyi(mpz_limbs_write(k, qn), h, qn);
+			mpz_limbs_finish(k, qn);
+			break;
+		}
+
+		ret = gnutls_hmac_init(&hd, mac, K, length);
+		if (ret < 0)
+			goto out;
+		ret = gnutls_hmac(hd, V, length);
+		if (ret < 0)
+			goto out;
+		ret = gnutls_hmac(hd, &c0, 1);
+		if (ret < 0)
+			goto out;
+		gnutls_hmac_deinit(hd, K);
+
+		ret = gnutls_hmac_fast(mac, K, length, V, length, V);
+		if (ret < 0)
+			goto out;
+	}
+
+ out:
+	zeroize_key(xp, sizeof(xp));
+	zeroize_key(tp, sizeof(tp));
+
+	return ret;
+}
diff --git a/lib/nettle/int/dsa-compute-k.h b/lib/nettle/int/dsa-compute-k.h
new file mode 100644
index 0000000000..64e90e0ca2
--- /dev/null
+++ b/lib/nettle/int/dsa-compute-k.h
@@ -0,0 +1,37 @@
+/*
+ * Copyright (C) 2019 Red Hat, Inc.
+ *
+ * Author: Daiki Ueno
+ *
+ * This file is part of GnuTLS.
+ *
+ * The GnuTLS is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * as published by the Free Software Foundation; either version 2.1 of
+ * the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>
+ *
+ */
+
+#ifndef GNUTLS_LIB_NETTLE_INT_DSA_COMPUTE_K_H
+#define GNUTLS_LIB_NETTLE_INT_DSA_COMPUTE_K_H
+
+#include <gnutls/gnutls.h>
+#include <nettle/bignum.h> /* includes gmp.h */
+
+int
+_gnutls_dsa_compute_k(mpz_t k,
+		      const mpz_t q,
+		      const mpz_t x,
+		      gnutls_mac_algorithm_t mac,
+		      const uint8_t *digest,
+		      size_t length);
+
+#endif /* GNUTLS_LIB_NETTLE_INT_DSA_COMPUTE_K_H */
diff --git a/lib/nettle/int/ecdsa-compute-k.c b/lib/nettle/int/ecdsa-compute-k.c
new file mode 100644
index 0000000000..94914ebdfa
--- /dev/null
+++ b/lib/nettle/int/ecdsa-compute-k.c
@@ -0,0 +1,95 @@
+/*
+ * Copyright (C) 2019 Red Hat, Inc.
+ *
+ * Author: Daiki Ueno
+ *
+ * This file is part of GNUTLS.
+ *
+ * The GNUTLS library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * as published by the Free Software Foundation; either version 2.1 of
+ * the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>
+ *
+ */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "ecdsa-compute-k.h"
+
+#include "dsa-compute-k.h"
+#include "gnutls_int.h"
+
+static inline int
+_gnutls_ecc_curve_to_dsa_q(mpz_t *q, gnutls_ecc_curve_t curve)
+{
+	switch (curve) {
+#ifdef ENABLE_NON_SUITEB_CURVES
+	case GNUTLS_ECC_CURVE_SECP192R1:
+		mpz_init_set_str(*q,
+				 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836"
+				 "146BC9B1B4D22831",
+				 16);
+		return 0;
+	case GNUTLS_ECC_CURVE_SECP224R1:
+		mpz_init_set_str(*q,
+				 "FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2"
+				 "E0B8F03E13DD29455C5C2A3D",
+				 16);
+		return 0;
+#endif
+	case GNUTLS_ECC_CURVE_SECP256R1:
+		mpz_init_set_str(*q,
+				 "FFFFFFFF00000000FFFFFFFFFFFFFFFF"
+				 "BCE6FAADA7179E84F3B9CAC2FC632551",
+				 16);
+		return 0;
+	case GNUTLS_ECC_CURVE_SECP384R1:
+		mpz_init_set_str(*q,
+				 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+				 "FFFFFFFFFFFFFFFFC7634D81F4372DDF"
+				 "581A0DB248B0A77AECEC196ACCC52973",
+				 16);
+		return 0;
+	case GNUTLS_ECC_CURVE_SECP521R1:
+		mpz_init_set_str(*q,
+				 "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+				 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+				 "FFA51868783BF2F966B7FCC0148F709A"
+				 "5D03BB5C9B8899C47AEBB6FB71E91386"
+				 "409",
+				 16);
+		return 0;
+	default:
+		return gnutls_assert_val(GNUTLS_E_UNSUPPORTED_SIGNATURE_ALGORITHM);
+	}
+}
+
+int
+_gnutls_ecdsa_compute_k (mpz_t k,
+			 gnutls_ecc_curve_t curve,
+			 const mpz_t x,
+			 gnutls_mac_algorithm_t mac,
+			 const uint8_t *digest,
+			 size_t length)
+{
+	mpz_t q;
+	int ret;
+
+	ret = _gnutls_ecc_curve_to_dsa_q(&q, curve);
+	if (ret < 0)
+		return gnutls_assert_val(ret);
+
+	ret = _gnutls_dsa_compute_k (k, q, x, mac, digest, length);
+	mpz_clear(q);
+	return ret;
+}
diff --git a/lib/nettle/int/ecdsa-compute-k.h b/lib/nettle/int/ecdsa-compute-k.h
new file mode 100644
index 0000000000..7ca401d6e4
--- /dev/null
+++ b/lib/nettle/int/ecdsa-compute-k.h
@@ -0,0 +1,37 @@
+/*
+ * Copyright (C) 2019 Red Hat, Inc.
+ *
+ * Author: Daiki Ueno
+ *
+ * This file is part of GnuTLS.
+ *
+ * The GnuTLS is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * as published by the Free Software Foundation; either version 2.1 of
+ * the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>
+ *
+ */
+
+#ifndef GNUTLS_LIB_NETTLE_INT_ECDSA_COMPUTE_K_H
+#define GNUTLS_LIB_NETTLE_INT_ECDSA_COMPUTE_K_H
+
+#include <gnutls/gnutls.h>
+#include <nettle/bignum.h> /* includes gmp.h */
+
+int
+_gnutls_ecdsa_compute_k (mpz_t k,
+			 gnutls_ecc_curve_t curve,
+			 const mpz_t x,
+			 gnutls_mac_algorithm_t mac,
+			 const uint8_t *digest,
+			 size_t length);
+
+#endif /* GNUTLS_LIB_NETTLE_INT_ECDSA_COMPUTE_K_H */
diff --git a/lib/nettle/int/mpn-base256.c b/lib/nettle/int/mpn-base256.c
new file mode 100644
index 0000000000..88dd00bd20
--- /dev/null
+++ b/lib/nettle/int/mpn-base256.c
@@ -0,0 +1,97 @@
+/* gmp-glue.c
+
+   Copyright (C) 2013 Niels Möller
+   Copyright (C) 2013 Red Hat
+
+   This file is part of GNU Nettle.
+
+   GNU Nettle is free software: you can redistribute it and/or
+   modify it under the terms of either:
+
+     * the GNU Lesser General Public License as published by the Free
+       Software Foundation; either version 3 of the License, or (at your
+       option) any later version.
+
+   or
+
+     * the GNU General Public License as published by the Free
+       Software Foundation; either version 2 of the License, or (at your
+       option) any later version.
+
+   or both in parallel, as here.
+
+   GNU Nettle is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see http://www.gnu.org/licenses/.
+*/
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "mpn-base256.h"
+
+void
+mpn_set_base256 (mp_limb_t *rp, mp_size_t rn,
+		 const uint8_t *xp, size_t xn)
+{
+  size_t xi;
+  mp_limb_t out;
+  unsigned bits;
+  for (xi = xn, out = bits = 0; xi > 0 && rn > 0; )
+    {
+      mp_limb_t in = xp[--xi];
+      out |= (in << bits) & GMP_NUMB_MASK;
+      bits += 8;
+      if (bits >= GMP_NUMB_BITS)
+	{
+	  *rp++ = out;
+	  rn--;
+
+	  bits -= GMP_NUMB_BITS;
+	  out = in >> (8 - bits);
+	}
+    }
+  if (rn > 0)
+    {
+      *rp++ = out;
+      if (--rn > 0)
+	mpn_zero (rp, rn);
+    }
+}
+
+void
+mpn_get_base256 (uint8_t *rp, size_t rn,
+		 const mp_limb_t *xp, mp_size_t xn)
+{
+  unsigned bits;
+  mp_limb_t in;
+  for (bits = in = 0; xn > 0 && rn > 0; )
+    {
+      if (bits >= 8)
+	{
+	  rp[--rn] = in;
+	  in >>= 8;
+	  bits -= 8;
+	}
+      else
+	{
+	  uint8_t old = in;
+	  in = *xp++;
+	  xn--;
+	  rp[--rn] = old | (in << bits);
+	  in >>= (8 - bits);
+	  bits += GMP_NUMB_BITS - 8;
+	}
+    }
+  while (rn > 0)
+    {
+      rp[--rn] = in;
+      in >>= 8;
+    }
+}
diff --git a/lib/nettle/int/mpn-base256.h b/lib/nettle/int/mpn-base256.h
new file mode 100644
index 0000000000..b5ca4af038
--- /dev/null
+++ b/lib/nettle/int/mpn-base256.h
@@ -0,0 +1,48 @@
+/* gmp-glue.h
+
+   Copyright (C) 2013 Niels Möller
+   Copyright (C) 2013 Red Hat
+
+   This file is part of GNU Nettle.
+
+   GNU Nettle is free software: you can redistribute it and/or
+   modify it under the terms of either:
+
+     * the GNU Lesser General Public License as published by the Free
+       Software Foundation; either version 3 of the License, or (at your
+       option) any later version.
+
+   or
+
+     * the GNU General Public License as published by the Free
+       Software Foundation; either version 2 of the License, or (at your
+       option) any later version.
+
+   or both in parallel, as here.
+
+   GNU Nettle is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see http://www.gnu.org/licenses/.
+*/
+
+#ifndef NETTLE_GMP_GLUE_H_INCLUDED
+#define NETTLE_GMP_GLUE_H_INCLUDED
+
+#include <nettle/bignum.h>
+
+/* Like mpn_set_str, but always writes rn limbs. If input is larger,
+   higher bits are ignored. */
+void
+mpn_set_base256 (mp_limb_t *rp, mp_size_t rn,
+		 const uint8_t *xp, size_t xn);
+
+void
+mpn_get_base256 (uint8_t *rp, size_t rn,
+	         const mp_limb_t *xp, mp_size_t xn);
+
+#endif /* NETTLE_GMP_GLUE_H_INCLUDED */