[PATCH v3 0/2] crypto: ecdh - add privkey generation support

[PATCH v3 0/2] crypto: ecdh - add privkey generation support

[Tudor Ambarus]

Hi,

This patch set adds support for generating ecc private keys.
ecc private keys are generated using the method of extra random bits,
equivalent to that described in FIPS 186-4, Appendix B.4.1.

Generation of ecc private keys is helpful in a user-space to kernel
ecdh offload because the keys are not revealed to user-space.

Private key generation is also helpful to implement forward secrecy.
A public/private key system demonstrates the property of forward secrecy
if it creates new key pairs for each communication session. These key pairs
are generated on an as-needed basis and are destroyed after the session
is over. If an attacker were to record previous encrypted session data,
they wouldn't be able to decrypt it with possession of a long-term key.

There are crypto accelerators that are capable of generating and retaining
ecdh private keys without revealing them to software. This patch set is a
prerequisite for hardware ecdh with private key generation support.

Changes in v3:
 - make ecc priv key generation compliant with FIPS 186-4.
 - drop dh privkey generation. The implementation was broken because
   was generating private keys based on the length of p, instead of q.
   As of know the dh implementation does not provide a pointer to q,
   so just drop the dh pursue.
 - correct the length in memcpy in testmgr.
 - rebase on top of "[PATCH v4 00/14] fixes for kpp and akcipher"

v2 can be found at:
http://www.mail-archive.com/linux-crypto@vger.kernel.org/msg25193.html

Tudor Ambarus (2):
  crypto: ecdh - add privkey generation support
  crypto: testmgr - add genkey kpp test

 crypto/Kconfig   |  1 +
 crypto/Makefile  |  9 ++++---
 crypto/ecc.c     | 56 +++++++++++++++++++++++++++++++++++++++++
 crypto/ecc.h     | 14 +++++++++++
 crypto/ecdh.c    |  4 +++
 crypto/testmgr.c | 76 ++++++++++++++++++++++++++++++++++++++++++++++++--------
 crypto/testmgr.h | 47 +++++++++++++++++++++++++++++++++++
 7 files changed, 192 insertions(+), 15 deletions(-)

-- 
2.7.4

[PATCH v3 1/2] crypto: ecdh - add privkey generation support

[Tudor Ambarus]

Add support for generating ecc private keys.

Generation of ecc private keys is helpful in a user-space to kernel
ecdh offload because the keys are not revealed to user-space. Private
key generation is also helpful to implement forward secrecy.

If the user provides a NULL ecc private key, the kernel will generate it
and further use it for ecdh.

Move ecdh's object files below drbg's. drbg must be present in the kernel
at the time of calling.

Signed-off-by: Tudor Ambarus <tudor.ambarus@microchip.com>
---
 crypto/Kconfig  |  1 +
 crypto/Makefile |  9 +++++----
 crypto/ecc.c    | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 crypto/ecc.h    | 14 ++++++++++++++
 crypto/ecdh.c   |  4 ++++
 5 files changed, 80 insertions(+), 4 deletions(-)

diff --git a/crypto/Kconfig b/crypto/Kconfig
index aac4bc9..caa770e 100644
--- a/crypto/Kconfig
+++ b/crypto/Kconfig
@@ -130,6 +130,7 @@ config CRYPTO_DH
 config CRYPTO_ECDH
 	tristate "ECDH algorithm"
 	select CRYTPO_KPP
+	select CRYPTO_RNG_DEFAULT
 	help
 	  Generic implementation of the ECDH algorithm
 
diff --git a/crypto/Makefile b/crypto/Makefile
index 8a44057..d41f033 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -33,10 +33,6 @@ obj-$(CONFIG_CRYPTO_KPP2) += kpp.o
 dh_generic-y := dh.o
 dh_generic-y += dh_helper.o
 obj-$(CONFIG_CRYPTO_DH) += dh_generic.o
-ecdh_generic-y := ecc.o
-ecdh_generic-y += ecdh.o
-ecdh_generic-y += ecdh_helper.o
-obj-$(CONFIG_CRYPTO_ECDH) += ecdh_generic.o
 
 $(obj)/rsapubkey-asn1.o: $(obj)/rsapubkey-asn1.c $(obj)/rsapubkey-asn1.h
 $(obj)/rsaprivkey-asn1.o: $(obj)/rsaprivkey-asn1.c $(obj)/rsaprivkey-asn1.h
@@ -138,6 +134,11 @@ obj-$(CONFIG_CRYPTO_USER_API_SKCIPHER) += algif_skcipher.o
 obj-$(CONFIG_CRYPTO_USER_API_RNG) += algif_rng.o
 obj-$(CONFIG_CRYPTO_USER_API_AEAD) += algif_aead.o
 
+ecdh_generic-y := ecc.o
+ecdh_generic-y += ecdh.o
+ecdh_generic-y += ecdh_helper.o
+obj-$(CONFIG_CRYPTO_ECDH) += ecdh_generic.o
+
 #
 # generic algorithms and the async_tx api
 #
diff --git a/crypto/ecc.c b/crypto/ecc.c
index 6c33c43..633a9bc 100644
--- a/crypto/ecc.c
+++ b/crypto/ecc.c
@@ -29,6 +29,7 @@
 #include <linux/swab.h>
 #include <linux/fips.h>
 #include <crypto/ecdh.h>
+#include <crypto/rng.h>
 
 #include "ecc.h"
 #include "ecc_curve_defs.h"
@@ -927,6 +928,61 @@ int ecc_is_key_valid(unsigned int curve_id, unsigned int ndigits,
 	return 0;
 }
 
+/*
+ * ECC private keys are generated using the method of extra random bits,
+ * equivalent to that described in FIPS 186-4, Appendix B.4.1.
+ *
+ * d = (c mod(n–1)) + 1    where c is a string of random bits, 64 bits longer
+ *                         than requested
+ * 0 <= c mod(n-1) <= n-2  and implies that
+ * 1 <= d <= n-1
+ *
+ * This method generates a private key uniformly distributed in the range
+ * [1, n-1].
+ */
+int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)
+{
+	const struct ecc_curve *curve = ecc_get_curve(curve_id);
+	u64 priv[ndigits];
+	unsigned int nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
+	unsigned int nbits = vli_num_bits(curve->n, ndigits);
+	int err;
+
+	/* Check that N is included in Table 1 of FIPS 186-4, section 6.1.1 */
+	if (nbits < 160)
+		return -EINVAL;
+
+	/*
+	 * FIPS 186-4 recommends that the private key should be obtained from a
+	 * RBG with a security strength equal to or greater than the security
+	 * strength associated with N.
+	 *
+	 * The maximum security strength identified by NIST SP800-57pt1r4 for
+	 * ECC is 256 (N >= 512).
+	 *
+	 * This condition is met by the default RNG because it selects a favored
+	 * DRBG with a security strength of 256.
+	 */
+	if (crypto_get_default_rng())
+		err = -EFAULT;
+
+	err = crypto_rng_get_bytes(crypto_default_rng, (u8 *)priv, nbytes);
+	crypto_put_default_rng();
+	if (err)
+		return err;
+
+	if (vli_is_zero(priv, ndigits))
+		return -EINVAL;
+
+	/* Make sure the private key is in the range [1, n-1]. */
+	if (vli_cmp(curve->n, priv, ndigits) != 1)
+		return -EINVAL;
+
+	ecc_swap_digits(priv, privkey, ndigits);
+
+	return 0;
+}
+
 int ecc_make_pub_key(unsigned int curve_id, unsigned int ndigits,
 		     const u64 *private_key, u64 *public_key)
 {
diff --git a/crypto/ecc.h b/crypto/ecc.h
index e13fe88..e4fd449 100644
--- a/crypto/ecc.h
+++ b/crypto/ecc.h
@@ -44,6 +44,20 @@ int ecc_is_key_valid(unsigned int curve_id, unsigned int ndigits,
 		     const u64 *private_key, unsigned int private_key_len);
 
 /**
+ * ecc_gen_privkey() -  Generates an ECC private key.
+ * The private key is a random integer in the range 0 < random < n, where n is a
+ * prime that is the order of the cyclic subgroup generated by the distinguished
+ * point G.
+ * @curve_id:		id representing the curve to use
+ * @ndigits:		curve number of digits
+ * @private_key:	buffer for storing the generated private key
+ *
+ * Returns 0 if the private key was generated successfully, a negative value
+ * if an error occurred.
+ */
+int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey);
+
+/**
  * ecc_make_pub_key() - Compute an ECC public key
  *
  * @curve_id:		id representing the curve to use
diff --git a/crypto/ecdh.c b/crypto/ecdh.c
index 4aa0b0c..61c7708 100644
--- a/crypto/ecdh.c
+++ b/crypto/ecdh.c
@@ -55,6 +55,10 @@ static int ecdh_set_secret(struct crypto_kpp *tfm, const void *buf,
 	ctx->curve_id = params.curve_id;
 	ctx->ndigits = ndigits;
 
+	if (!params.key || !params.key_size)
+		return ecc_gen_privkey(ctx->curve_id, ctx->ndigits,
+				       ctx->private_key);
+
 	if (ecc_is_key_valid(ctx->curve_id, ctx->ndigits,
 			     (const u64 *)params.key, params.key_size) < 0)
 		return -EINVAL;
-- 
2.7.4

[PATCH v3 2/2] crypto: testmgr - add genkey kpp test

[Tudor Ambarus]

The test considers a party that already has a private-public
key pair and a party that provides a NULL key. The kernel will
generate the private-public key pair for the latter, computes
the shared secret on both ends and verifies if it's the same.

The explicit private-public key pair was copied from
the previous test vector.

Signed-off-by: Tudor Ambarus <tudor.ambarus@microchip.com>
---
 crypto/testmgr.c | 76 ++++++++++++++++++++++++++++++++++++++++++++++++--------
 crypto/testmgr.h | 47 +++++++++++++++++++++++++++++++++++
 2 files changed, 112 insertions(+), 11 deletions(-)

diff --git a/crypto/testmgr.c b/crypto/testmgr.c
index 6f5f3ed..5f8e683 100644
--- a/crypto/testmgr.c
+++ b/crypto/testmgr.c
@@ -1997,6 +1997,9 @@ static int do_test_kpp(struct crypto_kpp *tfm, const struct kpp_testvec *vec,
 	struct kpp_request *req;
 	void *input_buf = NULL;
 	void *output_buf = NULL;
+	void *a_public = NULL;
+	void *a_ss = NULL;
+	void *shared_secret = NULL;
 	struct tcrypt_result result;
 	unsigned int out_len_max;
 	int err = -ENOMEM;
@@ -2026,20 +2029,31 @@ static int do_test_kpp(struct crypto_kpp *tfm, const struct kpp_testvec *vec,
 	kpp_request_set_callback(req, CRYPTO_TFM_REQ_MAY_BACKLOG,
 				 tcrypt_complete, &result);
 
-	/* Compute public key */
+	/* Compute party A's public key */
 	err = wait_async_op(&result, crypto_kpp_generate_public_key(req));
 	if (err) {
-		pr_err("alg: %s: generate public key test failed. err %d\n",
+		pr_err("alg: %s: Party A: generate public key test failed. err %d\n",
 		       alg, err);
 		goto free_output;
 	}
-	/* Verify calculated public key */
-	if (memcmp(vec->expected_a_public, sg_virt(req->dst),
-		   vec->expected_a_public_size)) {
-		pr_err("alg: %s: generate public key test failed. Invalid output\n",
-		       alg);
-		err = -EINVAL;
-		goto free_output;
+
+	if (vec->genkey) {
+		/* Save party A's public key */
+		a_public = kzalloc(out_len_max, GFP_KERNEL);
+		if (!a_public) {
+			err = -ENOMEM;
+			goto free_output;
+		}
+		memcpy(a_public, sg_virt(req->dst), out_len_max);
+	} else {
+		/* Verify calculated public key */
+		if (memcmp(vec->expected_a_public, sg_virt(req->dst),
+			   vec->expected_a_public_size)) {
+			pr_err("alg: %s: Party A: generate public key test failed. Invalid output\n",
+			       alg);
+			err = -EINVAL;
+			goto free_output;
+		}
 	}
 
 	/* Calculate shared secret key by using counter part (b) public key. */
@@ -2058,15 +2072,53 @@ static int do_test_kpp(struct crypto_kpp *tfm, const struct kpp_testvec *vec,
 				 tcrypt_complete, &result);
 	err = wait_async_op(&result, crypto_kpp_compute_shared_secret(req));
 	if (err) {
-		pr_err("alg: %s: compute shard secret test failed. err %d\n",
+		pr_err("alg: %s: Party A: compute shared secret test failed. err %d\n",
 		       alg, err);
 		goto free_all;
 	}
+
+	if (vec->genkey) {
+		/* Save the shared secret obtained by party A */
+		a_ss = kzalloc(vec->expected_ss_size, GFP_KERNEL);
+		if (!a_ss) {
+			err = -ENOMEM;
+			goto free_all;
+		}
+		memcpy(a_ss, sg_virt(req->dst), vec->expected_ss_size);
+
+		/*
+		 * Calculate party B's shared secret by using party A's
+		 * public key.
+		 */
+		err = crypto_kpp_set_secret(tfm, vec->b_secret,
+					    vec->b_secret_size);
+		if (err < 0)
+			goto free_all;
+
+		sg_init_one(&src, a_public, vec->expected_a_public_size);
+		sg_init_one(&dst, output_buf, out_len_max);
+		kpp_request_set_input(req, &src, vec->expected_a_public_size);
+		kpp_request_set_output(req, &dst, out_len_max);
+		kpp_request_set_callback(req, CRYPTO_TFM_REQ_MAY_BACKLOG,
+					 tcrypt_complete, &result);
+		err = wait_async_op(&result,
+				    crypto_kpp_compute_shared_secret(req));
+		if (err) {
+			pr_err("alg: %s: Party B: compute shared secret failed. err %d\n",
+			       alg, err);
+			goto free_all;
+		}
+
+		shared_secret = a_ss;
+	} else {
+		shared_secret = (void *)vec->expected_ss;
+	}
+
 	/*
 	 * verify shared secret from which the user will derive
 	 * secret key by executing whatever hash it has chosen
 	 */
-	if (memcmp(vec->expected_ss, sg_virt(req->dst),
+	if (memcmp(shared_secret, sg_virt(req->dst),
 		   vec->expected_ss_size)) {
 		pr_err("alg: %s: compute shared secret test failed. Invalid output\n",
 		       alg);
@@ -2074,8 +2126,10 @@ static int do_test_kpp(struct crypto_kpp *tfm, const struct kpp_testvec *vec,
 	}
 
 free_all:
+	kfree(a_ss);
 	kfree(input_buf);
 free_output:
+	kfree(a_public);
 	kfree(output_buf);
 free_req:
 	kpp_request_free(req);
diff --git a/crypto/testmgr.h b/crypto/testmgr.h
index 4293573..db2e26c 100644
--- a/crypto/testmgr.h
+++ b/crypto/testmgr.h
@@ -137,13 +137,16 @@ struct akcipher_testvec {
 
 struct kpp_testvec {
 	const unsigned char *secret;
+	const unsigned char *b_secret;
 	const unsigned char *b_public;
 	const unsigned char *expected_a_public;
 	const unsigned char *expected_ss;
 	unsigned short secret_size;
+	unsigned short b_secret_size;
 	unsigned short b_public_size;
 	unsigned short expected_a_public_size;
 	unsigned short expected_ss_size;
+	bool genkey;
 };
 
 static const char zeroed_string[48];
@@ -840,6 +843,50 @@ static const struct kpp_testvec ecdh_tv_template[] = {
 	.b_public_size = 64,
 	.expected_a_public_size = 64,
 	.expected_ss_size = 32
+	}, {
+	.secret =
+#ifdef __LITTLE_ENDIAN
+	"\x02\x00" /* type */
+	"\x08\x00" /* len */
+	"\x02\x00" /* curve_id */
+	"\x00\x00", /* key_size */
+#else
+	"\x00\x02" /* type */
+	"\x00\x08" /* len */
+	"\x00\x02" /* curve_id */
+	"\x00\x00", /* key_size */
+#endif
+	.b_secret =
+#ifdef __LITTLE_ENDIAN
+	"\x02\x00" /* type */
+	"\x28\x00" /* len */
+	"\x02\x00" /* curve_id */
+	"\x20\x00" /* key_size */
+#else
+	"\x00\x02" /* type */
+	"\x00\x28" /* len */
+	"\x00\x02" /* curve_id */
+	"\x00\x20" /* key_size */
+#endif
+	"\x24\xd1\x21\xeb\xe5\xcf\x2d\x83"
+	"\xf6\x62\x1b\x6e\x43\x84\x3a\xa3"
+	"\x8b\xe0\x86\xc3\x20\x19\xda\x92"
+	"\x50\x53\x03\xe1\xc0\xea\xb8\x82",
+	.b_public =
+	"\x1a\x7f\xeb\x52\x00\xbd\x3c\x31"
+	"\x7d\xb6\x70\xc1\x86\xa6\xc7\xc4"
+	"\x3b\xc5\x5f\x6c\x6f\x58\x3c\xf5"
+	"\xb6\x63\x82\x77\x33\x24\xa1\x5f"
+	"\x6a\xca\x43\x6f\xf7\x7e\xff\x02"
+	"\x37\x08\xcc\x40\x5e\x7a\xfd\x6a"
+	"\x6a\x02\x6e\x41\x87\x68\x38\x77"
+	"\xfa\xa9\x44\x43\x2d\xef\x09\xdf",
+	.secret_size = 8,
+	.b_secret_size = 40,
+	.b_public_size = 64,
+	.expected_a_public_size = 64,
+	.expected_ss_size = 32,
+	.genkey = true,
 	}
 };
 
-- 
2.7.4

Re: [PATCH v3 1/2] crypto: ecdh - add privkey generation support

[Stephan Müller]

Am Dienstag, 30. Mai 2017, 16:52:48 CEST schrieb Tudor Ambarus:

Hi Tudor,

> +	if (!params.key || !params.key_size)
> +		return ecc_gen_privkey(ctx->curve_id, ctx->ndigits,
> +				       ctx->private_key);
> +
>  	if (ecc_is_key_valid(ctx->curve_id, ctx->ndigits,
>  			     (const u64 *)params.key, params.key_size) < 0)

Hm, wouldn't this check be a problem in case a private key is generated by the 
kernel? The ecc_gen_privkey stores the key in ctx whereas this check operates 
on the input buffer. Furthermore, there is an unconditional memcpy further 
down that would overwrite the key in the ctx, no?

Ciao
Stephan

Re: [PATCH v3 1/2] crypto: ecdh - add privkey generation support

[Tudor Ambarus]

Hi, Stephan,

On 30.05.2017 18:10, Stephan Müller wrote:
> Am Dienstag, 30. Mai 2017, 16:52:48 CEST schrieb Tudor Ambarus:
> 
> Hi Tudor,
> 
>> +	if (!params.key || !params.key_size)
>> +		return ecc_gen_privkey(ctx->curve_id, ctx->ndigits,
>> +				       ctx->private_key);
>> +
>>   	if (ecc_is_key_valid(ctx->curve_id, ctx->ndigits,
>>   			     (const u64 *)params.key, params.key_size) < 0)
> 
> Hm, wouldn't this check be a problem in case a private key is generated by the
> kernel? The ecc_gen_privkey stores the key in ctx whereas this check operates
> on the input buffer. Furthermore, there is an unconditional memcpy further
> down that would overwrite the key in the ctx, no?

You missed the return. When generating the key I just exit with the
return value of ecc_gen_privkey().

Thanks,
ta

Re: [PATCH v3 1/2] crypto: ecdh - add privkey generation support

[Stephan Müller]

Am Dienstag, 30. Mai 2017, 17:18:41 CEST schrieb Tudor Ambarus:

Hi Tudor,

> You missed the return. When generating the key I just exit with the
> return value of ecc_gen_privkey().

Rrrright :-)

Reviewed-by: Stephan Müller <smueller@chronox.de>

Ciao
Stephan

Re: [PATCH v3 0/2] crypto: ecdh - add privkey generation support

[Herbert Xu]

On Tue, May 30, 2017 at 05:52:47PM +0300, Tudor Ambarus wrote:
> Hi,
> 
> This patch set adds support for generating ecc private keys.
> ecc private keys are generated using the method of extra random bits,
> equivalent to that described in FIPS 186-4, Appendix B.4.1.
> 
> Generation of ecc private keys is helpful in a user-space to kernel
> ecdh offload because the keys are not revealed to user-space.
> 
> Private key generation is also helpful to implement forward secrecy.
> A public/private key system demonstrates the property of forward secrecy
> if it creates new key pairs for each communication session. These key pairs
> are generated on an as-needed basis and are destroyed after the session
> is over. If an attacker were to record previous encrypted session data,
> they wouldn't be able to decrypt it with possession of a long-term key.
> 
> There are crypto accelerators that are capable of generating and retaining
> ecdh private keys without revealing them to software. This patch set is a
> prerequisite for hardware ecdh with private key generation support.
> 
> Changes in v3:

All applied.  Thanks.
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt