* [PATCH 0/3 v4] Key-agreement Protocol Primitives (KPP) API
@ 2016-05-05 9:17 Salvatore Benedetto
2016-05-05 9:17 ` [PATCH 1/3 v4] crypto: Key-agreement Protocol Primitives API (KPP) Salvatore Benedetto
` (2 more replies)
0 siblings, 3 replies; 5+ messages in thread
From: Salvatore Benedetto @ 2016-05-05 9:17 UTC (permalink / raw)
To: herbert; +Cc: salvatore.benedetto, linux-crypto
Hi Herb,
the following patchset introduces a new API for abstracting key-agreement
protocols such as DH and ECDH. It provides the primitives required for implementing
the protocol, thus the name KPP (Key-agreement Protocol Primitives).
Regards,
Salvatore
Changes from v1:
* Change check in dh_check_params_length based on Stephan review
Changed from v2:
* Add support for ECDH (curve P192 and P256). I reused the ecc module
already present in net/bluetooth and extended it in order to select
different curves at runtime. Code for P192 was taken from tinycrypt.
Changed from v3:
* Move curve ID definition to public header ecdh.h as users need to
have access to those ids when selecting the curve
Salvatore Benedetto (3):
crypto: Key-agreement Protocol Primitives API (KPP)
crypto: kpp - Add DH software implementation
crypto: kpp - Add ECDH software support
crypto/Kconfig | 23 +
crypto/Makefile | 6 +
crypto/crypto_user.c | 20 +
crypto/dh.c | 224 +++++++++
crypto/ecc.c | 1037 +++++++++++++++++++++++++++++++++++++++
crypto/ecc.h | 74 +++
crypto/ecc_curve_defs.h | 57 +++
crypto/ecdh.c | 171 +++++++
crypto/kpp.c | 123 +++++
crypto/testmgr.c | 275 +++++++++++
crypto/testmgr.h | 281 +++++++++++
include/crypto/dh.h | 23 +
include/crypto/ecdh.h | 20 +
include/crypto/internal/kpp.h | 64 +++
include/crypto/kpp.h | 333 +++++++++++++
include/linux/crypto.h | 1 +
include/uapi/linux/cryptouser.h | 5 +
17 files changed, 2737 insertions(+)
create mode 100644 crypto/dh.c
create mode 100644 crypto/ecc.c
create mode 100644 crypto/ecc.h
create mode 100644 crypto/ecc_curve_defs.h
create mode 100644 crypto/ecdh.c
create mode 100644 crypto/kpp.c
create mode 100644 include/crypto/dh.h
create mode 100644 include/crypto/ecdh.h
create mode 100644 include/crypto/internal/kpp.h
create mode 100644 include/crypto/kpp.h
--
1.9.1
^ permalink raw reply [flat|nested] 5+ messages in thread* [PATCH 1/3 v4] crypto: Key-agreement Protocol Primitives API (KPP) 2016-05-05 9:17 [PATCH 0/3 v4] Key-agreement Protocol Primitives (KPP) API Salvatore Benedetto @ 2016-05-05 9:17 ` Salvatore Benedetto 2016-05-05 9:17 ` [PATCH 2/3 v4] crypto: kpp - Add DH software implementation Salvatore Benedetto 2016-05-05 9:17 ` [PATCH 3/3 v4] crypto: kpp - Add ECDH software support Salvatore Benedetto 2 siblings, 0 replies; 5+ messages in thread From: Salvatore Benedetto @ 2016-05-05 9:17 UTC (permalink / raw) To: herbert; +Cc: salvatore.benedetto, linux-crypto Add key-agreement protocol primitives (kpp) API which allows to implement primitives required by protocols such as DH and ECDH. The API is composed mainly by the following functions * set_params() - It allows the user to set the parameters known to both parties involved in the key-agreement session * set_secret() - It allows the user to set his secret, also referred to as his private key * generate_public_key() - It generates the public key to be sent to the other counterpart involved in the key-agreement session. The function has to be called after set_params() and set_secret() * generate_secret() - It generates the shared secret for the session Other functions such as init() and exit() are provided for allowing cryptographic hardware to be inizialized properly before use Signed-off-by: Salvatore Benedetto <salvatore.benedetto@intel.com> --- crypto/Kconfig | 10 ++ crypto/Makefile | 1 + crypto/crypto_user.c | 20 +++ crypto/kpp.c | 123 +++++++++++++++ include/crypto/internal/kpp.h | 64 ++++++++ include/crypto/kpp.h | 333 ++++++++++++++++++++++++++++++++++++++++ include/linux/crypto.h | 1 + include/uapi/linux/cryptouser.h | 5 + 8 files changed, 557 insertions(+) create mode 100644 crypto/kpp.c create mode 100644 include/crypto/internal/kpp.h create mode 100644 include/crypto/kpp.h diff --git a/crypto/Kconfig b/crypto/Kconfig index 93a1fdc..31bf962 100644 --- a/crypto/Kconfig +++ b/crypto/Kconfig @@ -93,6 +93,15 @@ config CRYPTO_AKCIPHER select CRYPTO_AKCIPHER2 select CRYPTO_ALGAPI +config CRYPTO_KPP2 + tristate + select CRYPTO_ALGAPI2 + +config CRYPTO_KPP + tristate + select CRYPTO_ALGAPI + select CRYPTO_KPP2 + config CRYPTO_RSA tristate "RSA algorithm" select CRYPTO_AKCIPHER @@ -114,6 +123,7 @@ config CRYPTO_MANAGER2 select CRYPTO_HASH2 select CRYPTO_BLKCIPHER2 select CRYPTO_AKCIPHER2 + select CRYPTO_KPP2 config CRYPTO_USER tristate "Userspace cryptographic algorithm configuration" diff --git a/crypto/Makefile b/crypto/Makefile index 4f4ef7e..5b60890 100644 --- a/crypto/Makefile +++ b/crypto/Makefile @@ -30,6 +30,7 @@ crypto_hash-y += shash.o obj-$(CONFIG_CRYPTO_HASH2) += crypto_hash.o obj-$(CONFIG_CRYPTO_AKCIPHER2) += akcipher.o +obj-$(CONFIG_CRYPTO_KPP2) += kpp.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 diff --git a/crypto/crypto_user.c b/crypto/crypto_user.c index 43fe85f..d28513fb 100644 --- a/crypto/crypto_user.c +++ b/crypto/crypto_user.c @@ -28,6 +28,7 @@ #include <crypto/internal/skcipher.h> #include <crypto/internal/rng.h> #include <crypto/akcipher.h> +#include <crypto/kpp.h> #include "internal.h" @@ -126,6 +127,21 @@ nla_put_failure: return -EMSGSIZE; } +static int crypto_report_kpp(struct sk_buff *skb, struct crypto_alg *alg) +{ + struct crypto_report_kpp rkpp; + + strncpy(rkpp.type, "kpp", sizeof(rkpp.type)); + + if (nla_put(skb, CRYPTOCFGA_REPORT_KPP, + sizeof(struct crypto_report_kpp), &rkpp)) + goto nla_put_failure; + return 0; + +nla_put_failure: + return -EMSGSIZE; +} + static int crypto_report_one(struct crypto_alg *alg, struct crypto_user_alg *ualg, struct sk_buff *skb) { @@ -176,6 +192,10 @@ static int crypto_report_one(struct crypto_alg *alg, goto nla_put_failure; break; + case CRYPTO_ALG_TYPE_KPP: + if (crypto_report_kpp(skb, alg)) + goto nla_put_failure; + break; } out: diff --git a/crypto/kpp.c b/crypto/kpp.c new file mode 100644 index 0000000..d36ce05 --- /dev/null +++ b/crypto/kpp.c @@ -0,0 +1,123 @@ +/* + * Key-agreement Protocol Primitives (KPP) + * + * Copyright (c) 2016, Intel Corporation + * Authors: Salvatore Benedetto <salvatore.benedetto@intel.com> + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of 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. + * + */ +#include <linux/errno.h> +#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/seq_file.h> +#include <linux/slab.h> +#include <linux/string.h> +#include <linux/crypto.h> +#include <crypto/algapi.h> +#include <linux/cryptouser.h> +#include <net/netlink.h> +#include <crypto/kpp.h> +#include <crypto/internal/kpp.h> +#include "internal.h" + +#ifdef CONFIG_NET +static int crypto_kpp_report(struct sk_buff *skb, struct crypto_alg *alg) +{ + struct crypto_report_kpp rkpp; + + strncpy(rkpp.type, "kpp", sizeof(rkpp.type)); + + if (nla_put(skb, CRYPTOCFGA_REPORT_KPP, + sizeof(struct crypto_report_kpp), &rkpp)) + goto nla_put_failure; + return 0; + +nla_put_failure: + return -EMSGSIZE; +} +#else +static int crypto_kpp_report(struct sk_buff *skb, struct crypto_alg *alg) +{ + return -ENOSYS; +} +#endif + +static void crypto_kpp_show(struct seq_file *m, struct crypto_alg *alg) + __attribute__ ((unused)); + +static void crypto_kpp_show(struct seq_file *m, struct crypto_alg *alg) +{ + seq_puts(m, "type : kpp\n"); +} + +static void crypto_kpp_exit_tfm(struct crypto_tfm *tfm) +{ + struct crypto_kpp *kpp = __crypto_kpp_tfm(tfm); + struct kpp_alg *alg = crypto_kpp_alg(kpp); + + alg->exit(kpp); +} + +static int crypto_kpp_init_tfm(struct crypto_tfm *tfm) +{ + struct crypto_kpp *kpp = __crypto_kpp_tfm(tfm); + struct kpp_alg *alg = crypto_kpp_alg(kpp); + + if (alg->exit) + kpp->base.exit = crypto_kpp_exit_tfm; + + if (alg->init) + return alg->init(kpp); + + return 0; +} + +static const struct crypto_type crypto_kpp_type = { + .extsize = crypto_alg_extsize, + .init_tfm = crypto_kpp_init_tfm, +#ifdef CONFIG_PROC_FS + .show = crypto_kpp_show, +#endif + .report = crypto_kpp_report, + .maskclear = ~CRYPTO_ALG_TYPE_MASK, + .maskset = CRYPTO_ALG_TYPE_MASK, + .type = CRYPTO_ALG_TYPE_KPP, + .tfmsize = offsetof(struct crypto_kpp, base), +}; + +struct crypto_kpp *crypto_alloc_kpp(const char *alg_name, u32 type, u32 mask) +{ + return crypto_alloc_tfm(alg_name, &crypto_kpp_type, type, mask); +} +EXPORT_SYMBOL_GPL(crypto_alloc_kpp); + +static void kpp_prepare_alg(struct kpp_alg *alg) +{ + struct crypto_alg *base = &alg->base; + + base->cra_type = &crypto_kpp_type; + base->cra_flags &= ~CRYPTO_ALG_TYPE_MASK; + base->cra_flags |= CRYPTO_ALG_TYPE_KPP; +} + +int crypto_register_kpp(struct kpp_alg *alg) +{ + struct crypto_alg *base = &alg->base; + + kpp_prepare_alg(alg); + return crypto_register_alg(base); +} +EXPORT_SYMBOL_GPL(crypto_register_kpp); + +void crypto_unregister_kpp(struct kpp_alg *alg) +{ + crypto_unregister_alg(&alg->base); +} +EXPORT_SYMBOL_GPL(crypto_unregister_kpp); + +MODULE_LICENSE("GPL"); +MODULE_DESCRIPTION("Key-agreement Protocol Primitives"); diff --git a/include/crypto/internal/kpp.h b/include/crypto/internal/kpp.h new file mode 100644 index 0000000..ad3acf3 --- /dev/null +++ b/include/crypto/internal/kpp.h @@ -0,0 +1,64 @@ +/* + * Key-agreement Protocol Primitives (KPP) + * + * Copyright (c) 2016, Intel Corporation + * Authors: Salvatore Benedetto <salvatore.benedetto@intel.com> + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of 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. + * + */ +#ifndef _CRYPTO_KPP_INT_H +#define _CRYPTO_KPP_INT_H +#include <crypto/kpp.h> +#include <crypto/algapi.h> + +/* + * Transform internal helpers. + */ +static inline void *kpp_request_ctx(struct kpp_request *req) +{ + return req->__ctx; +} + +static inline void *kpp_tfm_ctx(struct crypto_kpp *tfm) +{ + return tfm->base.__crt_ctx; +} + +static inline void kpp_request_complete(struct kpp_request *req, int err) +{ + req->base.complete(&req->base, err); +} + +static inline const char *kpp_alg_name(struct crypto_kpp *tfm) +{ + return crypto_kpp_tfm(tfm)->__crt_alg->cra_name; +} + +/** + * crypto_register_kpp() -- Register key-agreement protocol primitives algorithm + * + * Function registers an implementation of a key-agreement protocol primitive + * algorithm + * + * @alg: algorithm definition + * + * Return: zero on success; error code in case of error + */ +int crypto_register_kpp(struct kpp_alg *alg); + +/** + * crypto_unregister_kpp() -- Unregister key-agreement protocol primitive + * algorithm + * + * Function unregisters an implementation of a key-agreement protocol primitive + * algorithm + * + * @alg: algorithm definition + */ +void crypto_unregister_kpp(struct kpp_alg *alg); + +#endif diff --git a/include/crypto/kpp.h b/include/crypto/kpp.h new file mode 100644 index 0000000..8eb14a6 --- /dev/null +++ b/include/crypto/kpp.h @@ -0,0 +1,333 @@ +/* + * Key-agreement Protocol Primitives (KPP) + * + * Copyright (c) 2016, Intel Corporation + * Authors: Salvatore Benedetto <salvatore.benedetto@intel.com> + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of 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. + * + */ + +#ifndef _CRYPTO_KPP_ +#define _CRYPTO_KPP_ +#include <linux/crypto.h> + +/** + * struct kpp_request + * + * @base: Common attributes for async crypto requests + * @src: Source data + * @dst: Destination data + * @src_len: Size of the input buffer + * @dst_len: Size of the output buffer. It needs to be at least + * as big as the expected result depending on the operation + * After operation it will be updated with the actual size of the + * result. In case of error where the dst sgl size was insufficient, + * it will be updated to the size required for the operation. + * @__ctx: Start of private context data + */ +struct kpp_request { + struct crypto_async_request base; + struct scatterlist *src; + struct scatterlist *dst; + unsigned int src_len; + unsigned int dst_len; + void *__ctx[] CRYPTO_MINALIGN_ATTR; +}; + +/** + * struct crypto_kpp - user-instantiated object which encapsulate + * algorithms and core processing logic + * + * @base: Common crypto API algorithm data structure + */ +struct crypto_kpp { + struct crypto_tfm base; +}; + +/** + * struct kpp_alg - generic key-agreement protocol primitives + * + * @set_params: Function invokes the protocol specific function + * which knows how to decode and interpret the buffer + * @set_secret: Function invokes the protocol specific function to + * store the secret private key. The implementation knows + * how to decode the buffer + * @generate_public_key: Function generate the public key to be sent to the + * counterpart. In case of error, where output is not big + * enough req->dst_len will be updated to the size + * required + * @compute_shared_secret: Function compute the shared secret as defined by + * the algorithm. The result is given back to the user. + * In case of error, where output is not big enough, + * req->dst_len will be updated to the size required + * @max_size: Function returns the size of the output buffer + * @init: Initialize the object. This is called only once at + * instantiation time. In case the cryptographic hardware + * needs to be initialized. Software fallback should be + * put in place here. + * @exit: Undo everything @init did. + * + * @reqsize: Request context size required by algorithm + * implementation + * @base Common crypto API algorithm data structure + */ +struct kpp_alg { + int (*set_params)(struct crypto_kpp *tfm, void *buffer, + unsigned int len); + int (*set_secret)(struct crypto_kpp *tfm, void *buffer, + unsigned int len); + int (*generate_public_key)(struct kpp_request *req); + int (*compute_shared_secret)(struct kpp_request *req); + + int (*max_size)(struct crypto_kpp *tfm); + + int (*init)(struct crypto_kpp *tfm); + void (*exit)(struct crypto_kpp *tfm); + + unsigned int reqsize; + struct crypto_alg base; +}; + +/** + * DOC: Generic Key-agreement Protocol Primitevs API + * + * The KPP API is used with the algorithm type + * CRYPTO_ALG_TYPE_KPP (listed as type "kpp" in /proc/crypto) + */ + +/** + * crypto_alloc_kpp() - allocate KPP tfm handle + * @alg_name: is the name of the kpp algorithm (e.g. "dh", "ecdh") + * @type: specifies the type of the algorithm + * @mask: specifies the mask for the algorithm + * + * Allocate a handle for kpp algorithm. The returned struct crypto_kpp + * is requeried for any following API invocation + * + * Return: allocated handle in case of success; IS_ERR() is true in case of + * an error, PTR_ERR() returns the error code. + */ +struct crypto_kpp *crypto_alloc_kpp(const char *alg_name, u32 type, u32 mask); + +static inline struct crypto_tfm *crypto_kpp_tfm(struct crypto_kpp *tfm) +{ + return &tfm->base; +} + +static inline struct kpp_alg *__crypto_kpp_alg(struct crypto_alg *alg) +{ + return container_of(alg, struct kpp_alg, base); +} + +static inline struct crypto_kpp *__crypto_kpp_tfm(struct crypto_tfm *tfm) +{ + return container_of(tfm, struct crypto_kpp, base); +} + +static inline struct kpp_alg *crypto_kpp_alg(struct crypto_kpp *tfm) +{ + return __crypto_kpp_alg(crypto_kpp_tfm(tfm)->__crt_alg); +} + +static inline unsigned int crypto_kpp_reqsize(struct crypto_kpp *tfm) +{ + return crypto_kpp_alg(tfm)->reqsize; +} + +static inline void kpp_request_set_tfm(struct kpp_request *req, + struct crypto_kpp *tfm) +{ + req->base.tfm = crypto_kpp_tfm(tfm); +} + +static inline struct crypto_kpp *crypto_kpp_reqtfm(struct kpp_request *req) +{ + return __crypto_kpp_tfm(req->base.tfm); +} + +/** + * crypto_free_kpp() - free KPP tfm handle + * + * @tfm: KPP tfm handle allocated with crypto_alloc_kpp() + */ +static inline void crypto_free_kpp(struct crypto_kpp *tfm) +{ + crypto_destroy_tfm(tfm, crypto_kpp_tfm(tfm)); +} + +/** + * kpp_request_alloc() - allocates kpp request + * + * @tfm: KPP tfm handle allocated with crypto_alloc_kpp() + * @gfp: allocation flags + * + * Return: allocated handle in case of success or NULL in case of an error. + */ +static inline struct kpp_request *kpp_request_alloc(struct crypto_kpp *tfm, + gfp_t gfp) +{ + struct kpp_request *req; + + req = kmalloc(sizeof(*req) + crypto_kpp_reqsize(tfm), gfp); + if (likely(req)) + kpp_request_set_tfm(req, tfm); + + return req; +} + +/** + * kpp_request_free() - zeroize and free kpp request + * + * @req: request to free + */ +static inline void kpp_request_free(struct kpp_request *req) +{ + kzfree(req); +} + +/** + * kpp_request_set_callback() - Sets an asynchronous callback. + * + * Callback will be called when an asynchronous operation on a given + * request is finished. + * + * @req: request that the callback will be set for + * @flgs: specify for instance if the operation may backlog + * @cmpl: callback which will be called + * @data: private data used by the caller + */ +static inline void kpp_request_set_callback(struct kpp_request *req, + u32 flgs, + crypto_completion_t cmpl, + void *data) +{ + req->base.complete = cmpl; + req->base.data = data; + req->base.flags = flgs; +} + +/** + * kpp_request_set_input() - Sets input buffer + * + * Sets parameters required by generate_public_key + * + * @req: kpp request + * @input: ptr to input scatter list + * @input_len: size of the input scatter list + */ +static inline void kpp_request_set_input(struct kpp_request *req, + struct scatterlist *input, + unsigned int input_len) +{ + req->src = input; + req->src_len = input_len; +} + +/** + * kpp_request_set_output() - Sets output buffer + * + * Sets parameters required by kpp operation + * + * @req: kpp request + * @output: ptr to output scatter list + * @output_len: size of the output scatter list + */ +static inline void kpp_request_set_output(struct kpp_request *req, + struct scatterlist *output, + unsigned int output_len) +{ + req->dst = output; + req->dst_len = output_len; +} + +/** + * crypto_kpp_set_params() - Invoke kpp operation + * + * Function invokes the specific kpp operation for a given alg + * + * @tfm: tfm handle + * + * Return: zero on success; error code in case of error + */ +static inline int crypto_kpp_set_params(struct crypto_kpp *tfm, + void *buffer, unsigned int len) +{ + struct kpp_alg *alg = crypto_kpp_alg(tfm); + + return alg->set_params(tfm, buffer, len); +} + +/** + * crypto_kpp_set_secret() - Invoke kpp operation + * + * Function invokes the specific kpp operation for a given alg. + * + * @tfm: tfm handle + * + * Return: zero on success; error code in case of error + */ +static inline int crypto_kpp_set_secret(struct crypto_kpp *tfm, void *buffer, + unsigned int len) +{ + struct kpp_alg *alg = crypto_kpp_alg(tfm); + + return alg->set_secret(tfm, buffer, len); +} + +/** + * crypto_kpp_generate_public_key() - Invoke kpp operation + * + * Function invokes the specific kpp operation for generating the public part + * for a given kpp algorithm + * + * @req: kpp key request + * + * Return: zero on success; error code in case of error + */ +static inline int crypto_kpp_generate_public_key(struct kpp_request *req) +{ + struct crypto_kpp *tfm = crypto_kpp_reqtfm(req); + struct kpp_alg *alg = crypto_kpp_alg(tfm); + + return alg->generate_public_key(req); +} + +/** + * crypto_kpp_compute_shared_secret() - Invoke kpp operation + * + * Function invokes the specific kpp operation for computing the shared secret + * for a given kpp algorithm. + * + * @req: kpp key request + * + * Return: zero on success; error code in case of error + */ +static inline int crypto_kpp_compute_shared_secret(struct kpp_request *req) +{ + struct crypto_kpp *tfm = crypto_kpp_reqtfm(req); + struct kpp_alg *alg = crypto_kpp_alg(tfm); + + return alg->compute_shared_secret(req); +} + +/** + * crypto_kpp_maxsize() - Get len for output buffer + * + * Function returns the output buffer size required + * + * @tfm: KPP tfm handle allocated with crypto_alloc_kpp() + * + * Return: minimum len for output buffer or error code if key hasn't been set + */ +static inline int crypto_kpp_maxsize(struct crypto_kpp *tfm) +{ + struct kpp_alg *alg = crypto_kpp_alg(tfm); + + return alg->max_size(tfm); +} + +#endif diff --git a/include/linux/crypto.h b/include/linux/crypto.h index 6e28c89..a4d1a05 100644 --- a/include/linux/crypto.h +++ b/include/linux/crypto.h @@ -54,6 +54,7 @@ #define CRYPTO_ALG_TYPE_AHASH 0x0000000a #define CRYPTO_ALG_TYPE_RNG 0x0000000c #define CRYPTO_ALG_TYPE_AKCIPHER 0x0000000d +#define CRYPTO_ALG_TYPE_KPP 0x0000000e #define CRYPTO_ALG_TYPE_HASH_MASK 0x0000000e #define CRYPTO_ALG_TYPE_AHASH_MASK 0x0000000c diff --git a/include/uapi/linux/cryptouser.h b/include/uapi/linux/cryptouser.h index 2e67bb6..79b5ded 100644 --- a/include/uapi/linux/cryptouser.h +++ b/include/uapi/linux/cryptouser.h @@ -45,6 +45,7 @@ enum crypto_attr_type_t { CRYPTOCFGA_REPORT_RNG, /* struct crypto_report_rng */ CRYPTOCFGA_REPORT_CIPHER, /* struct crypto_report_cipher */ CRYPTOCFGA_REPORT_AKCIPHER, /* struct crypto_report_akcipher */ + CRYPTOCFGA_REPORT_KPP, /* struct crypto_report_kpp */ __CRYPTOCFGA_MAX #define CRYPTOCFGA_MAX (__CRYPTOCFGA_MAX - 1) @@ -107,5 +108,9 @@ struct crypto_report_akcipher { char type[CRYPTO_MAX_NAME]; }; +struct crypto_report_kpp { + char type[CRYPTO_MAX_NAME]; +}; + #define CRYPTO_REPORT_MAXSIZE (sizeof(struct crypto_user_alg) + \ sizeof(struct crypto_report_blkcipher)) -- 1.9.1 ^ permalink raw reply related [flat|nested] 5+ messages in thread
* [PATCH 2/3 v4] crypto: kpp - Add DH software implementation 2016-05-05 9:17 [PATCH 0/3 v4] Key-agreement Protocol Primitives (KPP) API Salvatore Benedetto 2016-05-05 9:17 ` [PATCH 1/3 v4] crypto: Key-agreement Protocol Primitives API (KPP) Salvatore Benedetto @ 2016-05-05 9:17 ` Salvatore Benedetto 2016-05-05 9:17 ` [PATCH 3/3 v4] crypto: kpp - Add ECDH software support Salvatore Benedetto 2 siblings, 0 replies; 5+ messages in thread From: Salvatore Benedetto @ 2016-05-05 9:17 UTC (permalink / raw) To: herbert; +Cc: salvatore.benedetto, linux-crypto * Implement MPI based Diffie-Hellman under kpp API * Test provided uses data generad by OpenSSL Signed-off-by: Salvatore Benedetto <salvatore.benedetto@intel.com> --- crypto/Kconfig | 8 ++ crypto/Makefile | 2 + crypto/dh.c | 224 ++++++++++++++++++++++++++++++++++++++++++++++++++++ crypto/testmgr.c | 157 ++++++++++++++++++++++++++++++++++++ crypto/testmgr.h | 208 ++++++++++++++++++++++++++++++++++++++++++++++++ include/crypto/dh.h | 23 ++++++ 6 files changed, 622 insertions(+) create mode 100644 crypto/dh.c create mode 100644 include/crypto/dh.h diff --git a/crypto/Kconfig b/crypto/Kconfig index 31bf962..89db25c 100644 --- a/crypto/Kconfig +++ b/crypto/Kconfig @@ -110,6 +110,14 @@ config CRYPTO_RSA help Generic implementation of the RSA public key algorithm. +config CRYPTO_DH + tristate "Diffie-Hellman algorithm" + select CRYPTO_KPP + select MPILIB + help + Generic implementation of the Diffie-Hellman algorithm. + + config CRYPTO_MANAGER tristate "Cryptographic algorithm manager" select CRYPTO_MANAGER2 diff --git a/crypto/Makefile b/crypto/Makefile index 5b60890..101f8fd 100644 --- a/crypto/Makefile +++ b/crypto/Makefile @@ -32,6 +32,8 @@ obj-$(CONFIG_CRYPTO_HASH2) += crypto_hash.o obj-$(CONFIG_CRYPTO_AKCIPHER2) += akcipher.o obj-$(CONFIG_CRYPTO_KPP2) += kpp.o +obj-$(CONFIG_CRYPTO_DH) += dh.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 clean-files += rsapubkey-asn1.c rsapubkey-asn1.h diff --git a/crypto/dh.c b/crypto/dh.c new file mode 100644 index 0000000..06e4805 --- /dev/null +++ b/crypto/dh.c @@ -0,0 +1,224 @@ +/* Diffie-Hellman Key Agreement Method [RFC2631] + * + * Copyright (c) 2016, Intel Corporation + * Authors: Salvatore Benedetto <salvatore.benedetto@intel.com> + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public Licence + * as published by the Free Software Foundation; either version + * 2 of the Licence, or (at your option) any later version. + */ + +#include <linux/module.h> +#include <crypto/internal/kpp.h> +#include <crypto/kpp.h> +#include <crypto/dh.h> +#include <linux/mpi.h> + +struct dh_ctx { + MPI p; + MPI g; + MPI xa; +}; + +static void dh_free_ctx(struct dh_ctx *ctx) +{ + mpi_free(ctx->p); + mpi_free(ctx->g); + mpi_free(ctx->xa); + ctx->p = NULL; + ctx->g = NULL; + ctx->xa = NULL; +} + +/* + * Public key generation function [RFC2631 sec 2.1.1] + * ya = g^xa mod p; + */ +static int _generate_public_key(const struct dh_ctx *ctx, MPI ya) +{ + /* ya = g^xa mod p */ + return mpi_powm(ya, ctx->g, ctx->xa, ctx->p); +} + +/* + * ZZ generation function [RFC2631 sec 2.1.1] + * ZZ = yb^xa mod p; + */ +static int _compute_shared_secret(const struct dh_ctx *ctx, MPI yb, + MPI zz) +{ + /* ZZ = yb^xa mod p */ + return mpi_powm(zz, yb, ctx->xa, ctx->p); +} + +static inline struct dh_ctx *dh_get_ctx(struct crypto_kpp *tfm) +{ + return kpp_tfm_ctx(tfm); +} + +static int dh_check_params_length(unsigned int p_len) +{ + return (p_len < 1536) ? -EINVAL : 0; +} + +static int dh_set_params(struct crypto_kpp *tfm, void *buffer, + unsigned int len) +{ + struct dh_ctx *ctx = dh_get_ctx(tfm); + struct dh_params *params = (struct dh_params *)buffer; + + if (unlikely(!buffer || !len)) + return -EINVAL; + + if (unlikely(!params->p || !params->g)) + return -EINVAL; + + if (dh_check_params_length(params->p_size << 3)) + return -EINVAL; + + ctx->p = mpi_read_raw_data(params->p, params->p_size); + if (!ctx->p) + return -EINVAL; + + ctx->g = mpi_read_raw_data(params->g, params->g_size); + if (!ctx->g) { + mpi_free(ctx->p); + return -EINVAL; + } + + return 0; +} + +static int dh_set_secret(struct crypto_kpp *tfm, void *buffer, + unsigned int len) +{ + struct dh_ctx *ctx = dh_get_ctx(tfm); + + if (unlikely(!buffer || !len)) + return -EINVAL; + + ctx->xa = mpi_read_raw_data(buffer, len); + + if (!ctx->xa) + return -EINVAL; + + return 0; +} + +static int dh_generate_public_key(struct kpp_request *req) +{ + struct crypto_kpp *tfm = crypto_kpp_reqtfm(req); + const struct dh_ctx *ctx = dh_get_ctx(tfm); + MPI ya = mpi_alloc(0); + int ret = 0; + int sign; + + if (!ya) + return -ENOMEM; + + if (unlikely(!ctx->p || !ctx->g || !ctx->xa)) { + ret = -EINVAL; + goto err_free_ya; + } + ret = _generate_public_key(ctx, ya); + if (ret) + goto err_free_ya; + + ret = mpi_write_to_sgl(ya, req->dst, &req->dst_len, &sign); + if (ret) + goto err_free_ya; + + if (sign < 0) + ret = -EBADMSG; + +err_free_ya: + mpi_free(ya); + return ret; +} + +static int dh_compute_shared_secret(struct kpp_request *req) +{ + struct crypto_kpp *tfm = crypto_kpp_reqtfm(req); + struct dh_ctx *ctx = dh_get_ctx(tfm); + MPI yb, zz = mpi_alloc(0); + int ret = 0; + int sign; + + if (!zz) + return -ENOMEM; + + if (unlikely(!ctx->p || !ctx->xa)) { + ret = -EINVAL; + goto err_free_zz; + } + + yb = mpi_read_raw_from_sgl(req->src, req->src_len); + if (!yb) { + ret = EINVAL; + goto err_free_zz; + } + + ret = _compute_shared_secret(ctx, yb, zz); + if (ret) + goto err_free_yb; + + ret = mpi_write_to_sgl(zz, req->dst, &req->dst_len, &sign); + if (ret) + goto err_free_yb; + + if (sign < 0) + ret = -EBADMSG; + +err_free_yb: + mpi_free(yb); +err_free_zz: + mpi_free(zz); + return ret; +} + +static int dh_max_size(struct crypto_kpp *tfm) +{ + struct dh_ctx *ctx = dh_get_ctx(tfm); + + return mpi_get_size(ctx->p); +} + +static void dh_exit_tfm(struct crypto_kpp *tfm) +{ + struct dh_ctx *ctx = dh_get_ctx(tfm); + + dh_free_ctx(ctx); +} + +static struct kpp_alg dh = { + .set_params = dh_set_params, + .set_secret = dh_set_secret, + .generate_public_key = dh_generate_public_key, + .compute_shared_secret = dh_compute_shared_secret, + .max_size = dh_max_size, + .exit = dh_exit_tfm, + .base = { + .cra_name = "dh", + .cra_driver_name = "dh-generic", + .cra_priority = 100, + .cra_module = THIS_MODULE, + .cra_ctxsize = sizeof(struct dh_ctx), + }, +}; + +static int dh_init(void) +{ + return crypto_register_kpp(&dh); +} + +static void dh_exit(void) +{ + crypto_unregister_kpp(&dh); +} + +module_init(dh_init); +module_exit(dh_exit); +MODULE_ALIAS_CRYPTO("dh"); +MODULE_LICENSE("GPL"); +MODULE_DESCRIPTION("DH generic algorithm"); diff --git a/crypto/testmgr.c b/crypto/testmgr.c index b86883a..d68fa58 100644 --- a/crypto/testmgr.c +++ b/crypto/testmgr.c @@ -32,6 +32,8 @@ #include <crypto/rng.h> #include <crypto/drbg.h> #include <crypto/akcipher.h> +#include <crypto/kpp.h> +#include <crypto/dh.h> #include "internal.h" @@ -116,6 +118,11 @@ struct akcipher_test_suite { unsigned int count; }; +struct kpp_test_suite { + struct kpp_testvec_dh *vecs; + unsigned int count; +}; + struct alg_test_desc { const char *alg; int (*test)(const struct alg_test_desc *desc, const char *driver, @@ -130,6 +137,7 @@ struct alg_test_desc { struct cprng_test_suite cprng; struct drbg_test_suite drbg; struct akcipher_test_suite akcipher; + struct kpp_test_suite kpp; } suite; }; @@ -1773,6 +1781,145 @@ static int alg_test_drbg(const struct alg_test_desc *desc, const char *driver, } +static int do_test_dh(struct crypto_kpp *tfm, struct kpp_testvec_dh *vec) +{ + struct kpp_request *req; + void *input_buf = NULL; + void *output_buf = NULL; + struct tcrypt_result result; + unsigned int out_len_max; + int err = -ENOMEM; + struct scatterlist src, dst; + struct dh_params p; + + req = kpp_request_alloc(tfm, GFP_KERNEL); + if (!req) + return err; + + init_completion(&result.completion); + + /* Set p,g */ + p.p = vec->p; + p.g = vec->g; + p.p_size = vec->p_size; + p.g_size = vec->g_size; + err = crypto_kpp_set_params(tfm, (void *)&p, sizeof(p)); + if (err) + goto free_req; + + /* Set A private Key */ + err = crypto_kpp_set_secret(tfm, vec->xa, vec->xa_size); + if (err) + goto free_req; + + out_len_max = crypto_kpp_maxsize(tfm); + output_buf = kzalloc(out_len_max, GFP_KERNEL); + if (!output_buf) { + err = -ENOMEM; + goto free_req; + } + + sg_init_one(&dst, output_buf, out_len_max); + kpp_request_set_output(req, &dst, out_len_max); + kpp_request_set_callback(req, CRYPTO_TFM_REQ_MAY_BACKLOG, + tcrypt_complete, &result); + + /* Compute A public key = g^xa mod p */ + err = wait_async_op(&result, crypto_kpp_generate_public_key(req)); + if (err) { + pr_err("alg: dh: generate public key test failed. err %d\n", err); + goto free_output; + } + /* Verify calculated public key */ + if (memcmp(vec->expected_ya, sg_virt(req->dst), vec->expected_ya_size)) { + pr_err("alg: dh: generate public key test failed. Invalid output\n"); + err = -EINVAL; + goto free_output; + } + + /* Calculate shared secret key by using counter part public key. */ + input_buf = kzalloc(vec->yb_size, GFP_KERNEL); + if (!input_buf) { + err = -ENOMEM; + goto free_output; + } + + memcpy(input_buf, vec->yb, vec->yb_size); + sg_init_one(&src, input_buf, vec->yb_size); + sg_init_one(&dst, output_buf, out_len_max); + kpp_request_set_input(req, &src, vec->yb_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: dh: compute shard secret test failed. err %d\n", err); + goto free_all; + } + /* + * 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), + vec->expected_ss_size)) { + pr_err("alg: dh: compute shared secret test failed. Invalid output\n"); + err = -EINVAL; + } + +free_all: + kfree(input_buf); +free_output: + kfree(output_buf); +free_req: + kpp_request_free(req); + return err; +} + +static int test_dh(struct crypto_kpp *tfm, struct kpp_testvec_dh *vecs, + unsigned int tcount) +{ + int ret, i; + + for (i = 0; i < tcount; i++) { + ret = do_test_dh(tfm, vecs++); + if (ret) { + pr_err("alg: dh: test failed on vector %d, err=%d\n", + i + 1, ret); + return ret; + } + } + return 0; +} + +static int test_kpp(struct crypto_kpp *tfm, const char *alg, + struct kpp_testvec_dh *vecs, unsigned int tcount) +{ + if (strncmp(alg, "dh", 2) == 0) + return test_dh(tfm, vecs, tcount); + + return 0; +} + +static int alg_test_kpp(const struct alg_test_desc *desc, const char *driver, + u32 type, u32 mask) +{ + struct crypto_kpp *tfm; + int err = 0; + + tfm = crypto_alloc_kpp(driver, type | CRYPTO_ALG_INTERNAL, mask); + if (IS_ERR(tfm)) { + pr_err("alg: kpp: Failed to load tfm for %s: %ld\n", + driver, PTR_ERR(tfm)); + return PTR_ERR(tfm); + } + if (desc->suite.kpp.vecs) + err = test_kpp(tfm, desc->alg, desc->suite.kpp.vecs, + desc->suite.kpp.count); + + crypto_free_kpp(tfm); + return err; +} + static int do_test_rsa(struct crypto_akcipher *tfm, struct akcipher_testvec *vecs) { @@ -2708,6 +2855,16 @@ static const struct alg_test_desc alg_test_descs[] = { } } }, { + .alg = "dh", + .test = alg_test_kpp, + .fips_allowed = 1, + .suite = { + .kpp = { + .vecs = dh_tv_template, + .count = DH_TEST_VECTORS + } + } + }, { .alg = "digest_null", .test = alg_test_null, }, { diff --git a/crypto/testmgr.h b/crypto/testmgr.h index 487ec88..e9c34c7 100644 --- a/crypto/testmgr.h +++ b/crypto/testmgr.h @@ -133,6 +133,21 @@ struct akcipher_testvec { bool public_key_vec; }; +struct kpp_testvec_dh { + unsigned char *p; + unsigned char *g; + unsigned char *xa; + unsigned char *yb; + unsigned char *expected_ya; + unsigned char *expected_ss; + unsigned short p_size; + unsigned short g_size; + unsigned short xa_size; + unsigned short yb_size; + unsigned short expected_ya_size; + unsigned short expected_ss_size; +}; + static char zeroed_string[48]; /* @@ -330,6 +345,199 @@ static struct akcipher_testvec rsa_tv_template[] = { } }; +#define DH_TEST_VECTORS 2 + +struct kpp_testvec_dh dh_tv_template[] = { + { + .p = + "\xb9\x36\x3a\xf1\x82\x1f\x60\xd3\x22\x47\xb8\xbc\x2d\x22\x6b\x81" + "\x7f\xe8\x20\x06\x09\x23\x73\x49\x9a\x59\x8b\x35\x25\xf8\x31\xbc" + "\x7d\xa8\x1c\x9d\x56\x0d\x1a\xf7\x4b\x4f\x96\xa4\x35\x77\x6a\x89" + "\xab\x42\x00\x49\x21\x71\xed\x28\x16\x1d\x87\x5a\x10\xa7\x9c\x64" + "\x94\xd4\x87\x3d\x28\xef\x44\xfe\x4b\xe2\xb4\x15\x8c\x82\xa6\xf3" + "\x50\x5f\xa8\xe8\xa2\x60\xe7\x00\x86\x78\x05\xd4\x78\x19\xa1\x98" + "\x62\x4e\x4a\x00\x78\x56\x96\xe6\xcf\xd7\x10\x1b\x74\x5d\xd0\x26" + "\x61\xdb\x6b\x32\x09\x51\xd8\xa5\xfd\x54\x16\x71\x01\xb3\x39\xe6" + "\x4e\x69\xb1\xd7\x06\x8f\xd6\x1e\xdc\x72\x25\x26\x74\xc8\x41\x06" + "\x5c\xd1\x26\x5c\xb0\x2f\xf9\x59\x13\xc1\x2a\x0f\x78\xea\x7b\xf7" + "\xbd\x59\xa0\x90\x1d\xfc\x33\x5b\x4c\xbf\x05\x9c\x3a\x3f\x69\xa2" + "\x45\x61\x4e\x10\x6a\xb3\x17\xc5\x68\x30\xfb\x07\x5f\x34\xc6\xfb" + "\x73\x07\x3c\x70\xf6\xae\xe7\x72\x84\xc3\x18\x81\x8f\xe8\x11\x1f" + "\x3d\x83\x83\x01\x2a\x14\x73\xbf\x32\x32\x2e\xc9\x4d\xdb\x2a\xca" + "\xee\x71\xf9\xda\xad\xe8\x82\x0b\x4d\x0c\x1f\xb6\x1d\xef\x00\x67" + "\x74\x3d\x95\xe0\xb7\xc4\x30\x8a\x24\x87\x12\x47\x27\x70\x0d\x73", + .g = "\x02", + .xa = + "\x44\xc1\x48\x36\xa7\x2b\x6f\x4e\x43\x03\x68\xad\x31\x00\xda\xf3" + "\x2a\x01\xa8\x32\x63\x5f\x89\x32\x1f\xdf\x4c\xa1\x6a\xbc\x10\x15" + "\x90\x35\xc9\x26\x41\xdf\x7b\xaa\x56\x56\x3d\x85\x44\xb5\xc0\x8e" + "\x37\x83\x06\x50\xb3\x5f\x0e\x28\x2c\xd5\x46\x15\xe3\xda\x7d\x74" + "\x87\x13\x91\x4f\xd4\x2d\xf6\xc7\x5e\x14\x2c\x11\xc2\x26\xb4\x3a" + "\xe3\xb2\x36\x20\x11\x3b\x22\xf2\x06\x65\x66\xe2\x57\x58\xf8\x22" + "\x1a\x94\xbd\x2b\x0e\x8c\x55\xad\x61\x23\x45\x2b\x19\x1e\x63\x3a" + "\x13\x61\xe3\xa0\x79\x70\x3e\x6d\x98\x32\xbc\x7f\x82\xc3\x11\xd8" + "\xeb\x53\xb5\xfc\xb5\xd5\x3c\x4a\xea\x92\x3e\x01\xce\x15\x65\xd4" + "\xaa\x85\xc1\x11\x90\x83\x31\x6e\xfe\xe7\x7f\x7d\xed\xab\xf9\x29" + "\xf8\xc7\xf1\x68\xc6\xb7\xe4\x1f\x2f\x28\xa0\xc9\x1a\x50\x64\x29" + "\x4b\x01\x6d\x1a\xda\x46\x63\x21\x07\x40\x8c\x8e\x4c\x6f\xb5\xe5" + "\x12\xf3\xc2\x1b\x48\x27\x5e\x27\x01\xb1\xaa\xed\x68\x9b\x83\x18" + "\x8f\xb1\xeb\x1f\x04\xd1\x3c\x79\xed\x4b\xf7\x0a\x33\xdc\xe0\xc6" + "\xd8\x02\x51\x59\x00\x74\x30\x07\x4c\x2d\xac\xe4\x13\xf1\x80\xf0" + "\xce\xfa\xff\xa9\xce\x29\x46\xdd\x9d\xad\xd1\xc3\xc6\x58\x1a\x63", + .yb = + "\x2a\x67\x5c\xfd\x63\x5d\xc0\x97\x0a\x8b\xa2\x1f\xf8\x8a\xcb\x54" + "\xca\x2f\xd3\x49\x3f\x01\x8e\x87\xfe\xcc\x94\xa0\x3e\xd4\x26\x79" + "\x9a\x94\x3c\x11\x81\x58\x5c\x60\x3d\xf5\x98\x90\x89\x64\x62\x1f" + "\xbd\x05\x6d\x2b\xcd\x84\x40\x9b\x4a\x1f\xe0\x19\xf1\xca\x20\xb3" + "\x4e\xa0\x4f\x15\xcc\xa5\xfe\xa5\xb4\xf5\x0b\x18\x7a\x5a\x37\xaa" + "\x58\x00\x19\x7f\xe2\xa3\xd9\x1c\x44\x57\xcc\xde\x2e\xc1\x38\xea" + "\xeb\xe3\x90\x40\xc4\x6c\xf7\xcd\xe9\x22\x50\x71\xf5\x7c\xdb\x37" + "\x0e\x80\xc3\xed\x7e\xb1\x2b\x2f\xbe\x71\xa6\x11\xa5\x9d\xf5\x39" + "\xf1\xa2\xe5\x85\xbc\x25\x91\x4e\x84\x8d\x26\x9f\x4f\xe6\x0f\xa6" + "\x2b\x6b\xf9\x0d\xaf\x6f\xbb\xfa\x2d\x79\x15\x31\x57\xae\x19\x60" + "\x22\x0a\xf5\xfd\x98\x0e\xbf\x5d\x49\x75\x58\x37\xbc\x7f\xf5\x21" + "\x56\x1e\xd5\xb3\x50\x0b\xca\x96\xf3\xd1\x3f\xb3\x70\xa8\x6d\x63" + "\x48\xfb\x3d\xd7\x29\x91\x45\xb5\x48\xcd\xb6\x78\x30\xf2\x3f\x1e" + "\xd6\x22\xd6\x35\x9b\xf9\x1f\x85\xae\xab\x4b\xd7\xe0\xc7\x86\x67" + "\x3f\x05\x7f\xa6\x0d\x2f\x0d\xbf\x53\x5f\x4d\x2c\x6d\x5e\x57\x40" + "\x30\x3a\x23\x98\xf9\xb4\x32\xf5\x32\x83\xdd\x0b\xae\x33\x97\x2f", + .expected_ya = + "\x5c\x24\xdf\xeb\x5b\x4b\xf8\xc5\xef\x39\x48\x82\xe0\x1e\x62\xee" + "\x8a\xae\xdf\x93\x6c\x2b\x16\x95\x92\x16\x3f\x16\x7b\x75\x03\x85" + "\xd9\xf1\x69\xc2\x14\x87\x45\xfc\xa4\x19\xf6\xf0\xa4\xf3\xec\xd4" + "\x6c\x5c\x03\x3b\x94\xc2\x2f\x92\xe4\xce\xb3\xe4\x72\xe8\x17\xe6" + "\x23\x7e\x00\x01\x09\x59\x13\xbf\xc1\x2f\x99\xa9\x07\xaa\x02\x23" + "\x4a\xca\x39\x4f\xbc\xec\x0f\x27\x4f\x19\x93\x6c\xb9\x30\x52\xfd" + "\x2b\x9d\x86\xf1\x06\x1e\xb6\x56\x27\x4a\xc9\x8a\xa7\x8a\x48\x5e" + "\xb5\x60\xcb\xdf\xff\x03\x26\x10\xbf\x90\x8f\x46\x60\xeb\x9b\x9a" + "\xd6\x6f\x44\x91\x03\x92\x18\x2c\x96\x5e\x40\x19\xfb\xf4\x4f\x3a" + "\x02\x7b\xaf\xcc\x22\x20\x79\xb9\xf8\x9f\x8f\x85\x6b\xec\x44\xbb" + "\xe6\xa8\x8e\xb1\xe8\x2c\xee\x64\xee\xf8\xbd\x00\xf3\xe2\x2b\x93" + "\xcd\xe7\xc4\xdf\xc9\x19\x46\xfe\xb6\x07\x73\xc1\x8a\x64\x79\x26" + "\xe7\x30\xad\x2a\xdf\xe6\x8f\x59\xf5\x81\xbf\x4a\x29\x91\xe7\xb7" + "\xcf\x48\x13\x27\x75\x79\x40\xd9\xd6\x32\x52\x4e\x6a\x86\xae\x6f" + "\xc2\xbf\xec\x1f\xc2\x69\xb2\xb6\x59\xe5\xa5\x17\xa4\x77\xb7\x62" + "\x46\xde\xe8\xd2\x89\x78\x9a\xef\xa3\xb5\x8f\x26\xec\x80\xda\x39", + .expected_ss = + "\x8f\xf3\xac\xa2\xea\x22\x11\x5c\x45\x65\x1a\x77\x75\x2e\xcf\x46" + "\x23\x14\x1e\x67\x53\x4d\x35\xb0\x38\x1d\x4e\xb9\x41\x9a\x21\x24" + "\x6e\x9f\x40\xfe\x90\x51\xb1\x06\xa4\x7b\x87\x17\x2f\xe7\x5e\x22" + "\xf0\x7b\x54\x84\x0a\xac\x0a\x90\xd2\xd7\xe8\x7f\xe7\xe3\x30\x75" + "\x01\x1f\x24\x75\x56\xbe\xcc\x8d\x1e\x68\x0c\x41\x72\xd3\xfa\xbb" + "\xe5\x9c\x60\xc7\x28\x77\x0c\xbe\x89\xab\x08\xd6\x21\xe7\x2e\x1a" + "\x58\x7a\xca\x4f\x22\xf3\x2b\x30\xfd\xf4\x98\xc1\xa3\xf8\xf6\xcc" + "\xa9\xe4\xdb\x5b\xee\xd5\x5c\x6f\x62\x4c\xd1\x1a\x02\x2a\x23\xe4" + "\xb5\x57\xf3\xf9\xec\x04\x83\x54\xfe\x08\x5e\x35\xac\xfb\xa8\x09" + "\x82\x32\x60\x11\xb2\x16\x62\x6b\xdf\xda\xde\x9c\xcb\x63\x44\x6c" + "\x59\x26\x6a\x8f\xb0\x24\xcb\xa6\x72\x48\x1e\xeb\xe0\xe1\x09\x44" + "\xdd\xee\x66\x6d\x84\xcf\xa5\xc1\xb8\x36\x74\xd3\x15\x96\xc3\xe4" + "\xc6\x5a\x4d\x23\x97\x0c\x5c\xcb\xa9\xf5\x29\xc2\x0e\xff\x93\x82" + "\xd3\x34\x49\xad\x64\xa6\xb1\xc0\x59\x28\x75\x60\xa7\x8a\xb0\x11" + "\x56\x89\x42\x74\x11\xf5\xf6\x5e\x6f\x16\x54\x6a\xb1\x76\x4d\x50" + "\x8a\x68\xc1\x5b\x82\xb9\x0d\x00\x32\x50\xed\x88\x87\x48\x92\x17", + .p_size = 256, + .g_size = 1, + .xa_size = 256, + .yb_size = 256, + .expected_ya_size = 256, + .expected_ss_size = 256, + }, + { + .p = + "\xb9\x36\x3a\xf1\x82\x1f\x60\xd3\x22\x47\xb8\xbc\x2d\x22\x6b\x81" + "\x7f\xe8\x20\x06\x09\x23\x73\x49\x9a\x59\x8b\x35\x25\xf8\x31\xbc" + "\x7d\xa8\x1c\x9d\x56\x0d\x1a\xf7\x4b\x4f\x96\xa4\x35\x77\x6a\x89" + "\xab\x42\x00\x49\x21\x71\xed\x28\x16\x1d\x87\x5a\x10\xa7\x9c\x64" + "\x94\xd4\x87\x3d\x28\xef\x44\xfe\x4b\xe2\xb4\x15\x8c\x82\xa6\xf3" + "\x50\x5f\xa8\xe8\xa2\x60\xe7\x00\x86\x78\x05\xd4\x78\x19\xa1\x98" + "\x62\x4e\x4a\x00\x78\x56\x96\xe6\xcf\xd7\x10\x1b\x74\x5d\xd0\x26" + "\x61\xdb\x6b\x32\x09\x51\xd8\xa5\xfd\x54\x16\x71\x01\xb3\x39\xe6" + "\x4e\x69\xb1\xd7\x06\x8f\xd6\x1e\xdc\x72\x25\x26\x74\xc8\x41\x06" + "\x5c\xd1\x26\x5c\xb0\x2f\xf9\x59\x13\xc1\x2a\x0f\x78\xea\x7b\xf7" + "\xbd\x59\xa0\x90\x1d\xfc\x33\x5b\x4c\xbf\x05\x9c\x3a\x3f\x69\xa2" + "\x45\x61\x4e\x10\x6a\xb3\x17\xc5\x68\x30\xfb\x07\x5f\x34\xc6\xfb" + "\x73\x07\x3c\x70\xf6\xae\xe7\x72\x84\xc3\x18\x81\x8f\xe8\x11\x1f" + "\x3d\x83\x83\x01\x2a\x14\x73\xbf\x32\x32\x2e\xc9\x4d\xdb\x2a\xca" + "\xee\x71\xf9\xda\xad\xe8\x82\x0b\x4d\x0c\x1f\xb6\x1d\xef\x00\x67" + "\x74\x3d\x95\xe0\xb7\xc4\x30\x8a\x24\x87\x12\x47\x27\x70\x0d\x73", + .g = "\x02", + .xa = + "\x4d\x75\xa8\x6e\xba\x23\x3a\x0c\x63\x56\xc8\xc9\x5a\xa7\xd6\x0e" + "\xed\xae\x40\x78\x87\x47\x5f\xe0\xa7\x7b\xba\x84\x88\x67\x4e\xe5" + "\x3c\xcc\x5c\x6a\xe7\x4a\x20\xec\xbe\xcb\xf5\x52\x62\x9f\x37\x80" + "\x0c\x72\x7b\x83\x66\xa4\xf6\x7f\x95\x97\x1c\x6a\x5c\x7e\xf1\x67" + "\x37\xb3\x93\x39\x3d\x0b\x55\x35\xd9\xe5\x22\x04\x9f\xf8\xc1\x04" + "\xce\x13\xa5\xac\xe1\x75\x05\xd1\x2b\x53\xa2\x84\xef\xb1\x18\xf4" + "\x66\xdd\xea\xe6\x24\x69\x5a\x49\xe0\x7a\xd8\xdf\x1b\xb7\xf1\x6d" + "\x9b\x50\x2c\xc8\x1c\x1c\xa3\xb4\x37\xfb\x66\x3f\x67\x71\x73\xa9" + "\xff\x5f\xd9\xa2\x25\x6e\x25\x1b\x26\x54\xbf\x0c\xc6\xdb\xea\x0a" + "\x52\x6c\x16\x7c\x27\x68\x15\x71\x58\x73\x9d\xe6\xc2\x80\xaa\x97" + "\x31\x66\xfb\xa6\xfb\xfd\xd0\x9c\x1d\xbe\x81\x48\xf5\x9a\x32\xf1" + "\x69\x62\x18\x78\xae\x72\x36\xe6\x94\x27\xd1\xff\x18\x4f\x28\x6a" + "\x16\xbd\x6a\x60\xee\xe5\xf9\x6d\x16\xe4\xb8\xa6\x41\x9b\x23\x7e" + "\xf7\x9d\xd1\x1d\x03\x15\x66\x3a\xcf\xb6\x2c\x13\x96\x2c\x52\x21" + "\xe4\x2d\x48\x7a\x8a\x5d\xb2\x88\xed\x98\x61\x79\x8b\x6a\x1e\x5f" + "\xd0\x8a\x2d\x99\x5a\x2b\x0f\xbc\xef\x53\x8f\x32\xc1\xa2\x99\x26", + .yb = + "\x99\x4d\xd9\x01\x84\x8e\x4a\x5b\xb8\xa5\x64\x8c\x6c\x00\x5c\x0e" + "\x1e\x1b\xee\x5d\x9f\x53\xe3\x16\x70\x01\xed\xbf\x4f\x14\x36\x6e" + "\xe4\x43\x45\x43\x49\xcc\xb1\xb0\x2a\xc0\x6f\x22\x55\x42\x17\x94" + "\x18\x83\xd7\x2a\x5c\x51\x54\xf8\x4e\x7c\x10\xda\x76\x68\x57\x77" + "\x1e\x62\x03\x30\x04\x7b\x4c\x39\x9c\x54\x01\x54\xec\xef\xb3\x55" + "\xa4\xc0\x24\x6d\x3d\xbd\xcc\x46\x5b\x00\x96\xc7\xea\x93\xd1\x3f" + "\xf2\x6a\x72\xe3\xf2\xc1\x92\x24\x5b\xda\x48\x70\x2c\xa9\x59\x97" + "\x19\xb1\xd6\x54\xb3\x9c\x2e\xb0\x63\x07\x9b\x5e\xac\xb5\xf2\xb1" + "\x5b\xf8\xf3\xd7\x2d\x37\x9b\x68\x6c\xf8\x90\x07\xbc\x37\x9a\xa5" + "\xe2\x91\x12\x25\x47\x77\xe3\x3d\xb2\x95\x69\x44\x0b\x91\x1e\xaf" + "\x7c\x8c\x7c\x34\x41\x6a\xab\x60\x6e\xc6\x52\xec\x7e\x94\x0a\x37" + "\xec\x98\x90\xdf\x3f\x02\xbd\x23\x52\xdd\xd9\xe5\x31\x80\x74\x25" + "\xb6\xd2\xd3\xcc\xd5\xcc\x6d\xf9\x7e\x4d\x78\xab\x77\x51\xfa\x77" + "\x19\x94\x49\x8c\x05\xd4\x75\xed\xd2\xb3\x64\x57\xe0\x52\x99\xc0" + "\x83\xe3\xbb\x5e\x2b\xf1\xd2\xc0\xb1\x37\x36\x0b\x7c\xb5\x63\x96" + "\x8e\xde\x04\x23\x11\x95\x62\x11\x9a\xce\x6f\x63\xc8\xd5\xd1\x8f", + .expected_ya = + "\x90\x89\xe4\x82\xd6\x0a\xcf\x1a\xae\xce\x1b\x66\xa7\x19\x71\x18" + "\x8f\x95\x4b\x5b\x80\x45\x4a\x5a\x43\x99\x4d\x37\xcf\xa3\xa7\x28" + "\x9c\xc7\x73\xf1\xb2\x17\xf6\x99\xe3\x6b\x56\xcb\x3e\x35\x60\x7d" + "\x65\xc7\x84\x6b\x3e\x60\xee\xcd\xd2\x70\xe7\xc9\x32\x1c\xf0\xb4" + "\xf9\x52\xd9\x88\x75\xfd\x40\x2c\xa7\xbe\x19\x1c\x0a\xae\x93\xe1" + "\x71\xc7\xcd\x4f\x33\x5c\x10\x7d\x39\x56\xfc\x73\x84\xb2\x67\xc3" + "\x77\x26\x20\x97\x2b\xf8\x13\x43\x93\x9c\x9a\xa4\x08\xc7\x34\x83" + "\xe6\x98\x61\xe7\x16\x30\x2c\xb1\xdb\x2a\xb2\xcc\xc3\x02\xa5\x3c" + "\x71\x50\x14\x83\xc7\xbb\xa4\xbe\x98\x1b\xfe\xcb\x43\xe9\x97\x62" + "\xd6\xf0\x8c\xcb\x1c\xba\x1e\xa8\xa6\xa6\x50\xfc\x85\x7d\x47\xbf" + "\xf4\x3e\x23\xd3\x5f\xb2\x71\x3e\x40\x94\xaa\x87\x83\x2c\x6c\x8e" + "\x60\xfd\xdd\xf7\xf4\x76\x03\xd3\x1d\xec\x18\x51\xa3\xf2\x44\x1a" + "\x3f\xb4\x7c\x18\x0d\x68\x65\x92\x54\x0d\x2d\x81\x16\xf1\x84\x66" + "\x89\x92\xd0\x1a\x5e\x1f\x42\x46\x5b\xe5\x83\x86\x80\xd9\xcd\x3a" + "\x5a\x2f\xb9\x59\x9b\xe4\x43\x84\x64\xf3\x09\x1a\x0a\xa2\x64\x0f" + "\x77\x4e\x8d\x8b\xe6\x88\xd1\xfc\xaf\x8f\xdf\x1d\xbc\x31\xb3\xbd", + .expected_ss = + "\x34\xc3\x35\x14\x88\x46\x26\x23\x97\xbb\xdd\x28\x5c\x94\xf6\x47" + "\xca\xb3\x19\xaf\xca\x44\x9b\xc2\x7d\x89\xfd\x96\x14\xfd\x6d\x58" + "\xd8\xc4\x6b\x61\x2a\x0d\xf2\x36\x45\xc8\xe4\xa4\xed\x81\x53\x81" + "\x66\x1e\xe0\x5a\xb1\x78\x2d\x0b\x5c\xb4\xd1\xfc\x90\xc6\x9c\xdb" + "\x5a\x30\x0b\x14\x7d\xbe\xb3\x7d\xb1\xb2\x76\x3c\x6c\xef\x74\x6b" + "\xe7\x1f\x64\x0c\xab\x65\xe1\x76\x5c\x3d\x83\xb5\x8a\xfb\xaf\x0f" + "\xf2\x06\x14\x8f\xa0\xf6\xc1\x89\x78\xf2\xba\x72\x73\x3c\xf7\x76" + "\x21\x67\xbc\x24\x31\xb8\x09\x65\x0f\x0c\x02\x32\x4a\x98\x14\xfc" + "\x72\x2c\x25\x60\x68\x5f\x2f\x30\x1e\x5b\xf0\x3b\xd1\xa2\x87\xa0" + "\x54\xdf\xdb\xc0\xee\x0a\x0f\x47\xc9\x90\x20\x2c\xf9\xe3\x52\xad" + "\x27\x65\x8d\x54\x8d\xa8\xa1\xf3\xed\x15\xd4\x94\x28\x90\x31\x93" + "\x1b\xc0\x51\xbb\x43\x5d\x76\x3b\x1d\x2a\x71\x50\xea\x5d\x48\x94" + "\x7f\x6f\xf1\x48\xdb\x30\xe5\xae\x64\x79\xd9\x7a\xdb\xc6\xff\xd8" + "\x5e\x5a\x64\xbd\xf6\x85\x04\xe8\x28\x6a\xac\xef\xce\x19\x8e\x9a" + "\xfe\x75\xc0\x27\x69\xe3\xb3\x7b\x21\xa7\xb1\x16\xa4\x85\x23\xee" + "\xb0\x1b\x04\x6e\xbd\xab\x16\xde\xfd\x86\x6b\xa9\x95\xd7\x0b\xfd", + .p_size = 256, + .g_size = 1, + .xa_size = 256, + .yb_size = 256, + .expected_ya_size = 256, + .expected_ss_size = 256, + } +}; + /* * MD4 test vectors from RFC1320 */ diff --git a/include/crypto/dh.h b/include/crypto/dh.h new file mode 100644 index 0000000..ca61066 --- /dev/null +++ b/include/crypto/dh.h @@ -0,0 +1,23 @@ +/* + * Diffie-Hellman params to be used with kpp API + * + * Copyright (c) 2016, Intel Corporation + * Authors: Salvatore Benedetto <salvatore.benedetto@intel.com> + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of 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. + * + */ +#ifndef _CRYPTO_DH_ +#define _CRYPTO_DH_ + +struct dh_params { + void *p; + void *g; + unsigned int p_size; + unsigned int g_size; +}; + +#endif -- 1.9.1 ^ permalink raw reply related [flat|nested] 5+ messages in thread
* [PATCH 3/3 v4] crypto: kpp - Add ECDH software support 2016-05-05 9:17 [PATCH 0/3 v4] Key-agreement Protocol Primitives (KPP) API Salvatore Benedetto 2016-05-05 9:17 ` [PATCH 1/3 v4] crypto: Key-agreement Protocol Primitives API (KPP) Salvatore Benedetto 2016-05-05 9:17 ` [PATCH 2/3 v4] crypto: kpp - Add DH software implementation Salvatore Benedetto @ 2016-05-05 9:17 ` Salvatore Benedetto 2016-05-06 12:02 ` Stephan Mueller 2 siblings, 1 reply; 5+ messages in thread From: Salvatore Benedetto @ 2016-05-05 9:17 UTC (permalink / raw) To: herbert; +Cc: salvatore.benedetto, linux-crypto * Implement ECDH under kpp API * Provide ECC software support for curve P-192 and P-256. * Add kpp test for ECDH with data generated by OpenSSL Signed-off-by: Salvatore Benedetto <salvatore.benedetto@intel.com> --- crypto/Kconfig | 5 + crypto/Makefile | 3 + crypto/ecc.c | 1038 +++++++++++++++++++++++++++++++++++++++++++++++ crypto/ecc.h | 70 ++++ crypto/ecc_curve_defs.h | 57 +++ crypto/ecdh.c | 171 ++++++++ crypto/testmgr.c | 136 ++++++- crypto/testmgr.h | 73 ++++ include/crypto/ecdh.h | 24 ++ 9 files changed, 1568 insertions(+), 9 deletions(-) create mode 100644 crypto/ecc.c create mode 100644 crypto/ecc.h create mode 100644 crypto/ecc_curve_defs.h create mode 100644 crypto/ecdh.c create mode 100644 include/crypto/ecdh.h diff --git a/crypto/Kconfig b/crypto/Kconfig index 89db25c..08a1a3b 100644 --- a/crypto/Kconfig +++ b/crypto/Kconfig @@ -117,6 +117,11 @@ config CRYPTO_DH help Generic implementation of the Diffie-Hellman algorithm. +config CRYPTO_ECDH + tristate "ECDH algorithm" + select CRYTPO_KPP + help + Generic implementation of the ECDH algorithm config CRYPTO_MANAGER tristate "Cryptographic algorithm manager" diff --git a/crypto/Makefile b/crypto/Makefile index 101f8fd..ba03079 100644 --- a/crypto/Makefile +++ b/crypto/Makefile @@ -33,6 +33,9 @@ obj-$(CONFIG_CRYPTO_AKCIPHER2) += akcipher.o obj-$(CONFIG_CRYPTO_KPP2) += kpp.o obj-$(CONFIG_CRYPTO_DH) += dh.o +ecdh_generic-y := ecc.o +ecdh_generic-y += ecdh.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 diff --git a/crypto/ecc.c b/crypto/ecc.c new file mode 100644 index 0000000..c50f9c8 --- /dev/null +++ b/crypto/ecc.c @@ -0,0 +1,1038 @@ +/* + * Copyright (c) 2013, Kenneth MacKay + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include <linux/random.h> +#include <linux/slab.h> +#include <linux/swab.h> +#include <crypto/ecdh.h> + +#include "ecc.h" +#include "ecc_curve_defs.h" + +#define MAX_TRIES 16 + +typedef struct { + u64 m_low; + u64 m_high; +} uint128_t; + +static inline const struct ecc_curve *ecc_get_curve(unsigned int curve_id) +{ + switch (curve_id) { + case ECC_CURVE_NIST_P192: return &nist_p192; + case ECC_CURVE_NIST_P256: return &nist_p256; + default: return NULL; + } +} + +static u64 *ecc_alloc_digits_space(unsigned int ndigits) +{ + size_t len = ndigits * sizeof(u64); + + if (!len) + return NULL; + + return kmalloc(len, GFP_KERNEL); +} + +static void ecc_free_digits_space(u64 *space) +{ + kzfree(space); +} + +static struct ecc_point *ecc_alloc_point(unsigned int ndigits) +{ + struct ecc_point *p = kmalloc(sizeof(*p), GFP_KERNEL); + + if (!p) + return NULL; + + p->x = ecc_alloc_digits_space(ndigits); + if (!p->x) + goto err_alloc_x; + + p->y = ecc_alloc_digits_space(ndigits); + if (!p->y) + goto err_alloc_y; + + p->ndigits = ndigits; + + return p; + +err_alloc_y: + ecc_free_digits_space(p->x); +err_alloc_x: + kfree(p); + return NULL; +} + +static void ecc_free_point(struct ecc_point *p) +{ + if (!p) + return; + + kzfree(p->x); + kzfree(p->y); + kzfree(p); +} + +static void vli_clear(u64 *vli, unsigned int ndigits) +{ + int i; + + for (i = 0; i < ndigits; i++) + vli[i] = 0; +} + +/* Returns true if vli == 0, false otherwise. */ +static bool vli_is_zero(const u64 *vli, unsigned int ndigits) +{ + int i; + + for (i = 0; i < ndigits; i++) { + if (vli[i]) + return false; + } + + return true; +} + +/* Returns nonzero if bit bit of vli is set. */ +static u64 vli_test_bit(const u64 *vli, unsigned int bit) +{ + return (vli[bit / 64] & ((u64)1 << (bit % 64))); +} + +/* Counts the number of 64-bit "digits" in vli. */ +static unsigned int vli_num_digits(const u64 *vli, unsigned int ndigits) +{ + int i; + + /* Search from the end until we find a non-zero digit. + * We do it in reverse because we expect that most digits will + * be nonzero. + */ + for (i = ndigits - 1; i >= 0 && vli[i] == 0; i--); + + return (i + 1); +} + +/* Counts the number of bits required for vli. */ +static unsigned int vli_num_bits(const u64 *vli, unsigned int ndigits) +{ + unsigned int i, num_digits; + u64 digit; + + num_digits = vli_num_digits(vli, ndigits); + if (num_digits == 0) + return 0; + + digit = vli[num_digits - 1]; + for (i = 0; digit; i++) + digit >>= 1; + + return ((num_digits - 1) * 64 + i); +} + +/* Sets dest = src. */ +static void vli_set(u64 *dest, const u64 *src, unsigned int ndigits) +{ + int i; + + for (i = 0; i < ndigits; i++) + dest[i] = src[i]; +} + +/* Returns sign of left - right. */ +static int vli_cmp(const u64 *left, const u64 *right, unsigned int ndigits) +{ + int i; + + for (i = ndigits - 1; i >= 0; i--) { + if (left[i] > right[i]) + return 1; + else if (left[i] < right[i]) + return -1; + } + + return 0; +} + +/* Computes result = in << c, returning carry. Can modify in place + * (if result == in). 0 < shift < 64. + */ +static u64 vli_lshift(u64 *result, const u64 *in, unsigned int shift, + unsigned int ndigits) +{ + u64 carry = 0; + int i; + + for (i = 0; i < ndigits; i++) { + u64 temp = in[i]; + + result[i] = (temp << shift) | carry; + carry = temp >> (64 - shift); + } + + return carry; +} + +/* Computes vli = vli >> 1. */ +static void vli_rshift1(u64 *vli, unsigned int ndigits) +{ + u64 *end = vli; + u64 carry = 0; + + vli += ndigits; + + while (vli-- > end) { + u64 temp = *vli; + *vli = (temp >> 1) | carry; + carry = temp << 63; + } +} + +/* Computes result = left + right, returning carry. Can modify in place. */ +static u64 vli_add(u64 *result, const u64 *left, const u64 *right, + unsigned int ndigits) +{ + u64 carry = 0; + int i; + + for (i = 0; i < ndigits; i++) { + u64 sum; + + sum = left[i] + right[i] + carry; + if (sum != left[i]) + carry = (sum < left[i]); + + result[i] = sum; + } + + return carry; +} + +/* Computes result = left - right, returning borrow. Can modify in place. */ +static u64 vli_sub(u64 *result, const u64 *left, const u64 *right, + unsigned int ndigits) +{ + u64 borrow = 0; + int i; + + for (i = 0; i < ndigits; i++) { + u64 diff; + + diff = left[i] - right[i] - borrow; + if (diff != left[i]) + borrow = (diff > left[i]); + + result[i] = diff; + } + + return borrow; +} + +static uint128_t mul_64_64(u64 left, u64 right) +{ + u64 a0 = left & 0xffffffffull; + u64 a1 = left >> 32; + u64 b0 = right & 0xffffffffull; + u64 b1 = right >> 32; + u64 m0 = a0 * b0; + u64 m1 = a0 * b1; + u64 m2 = a1 * b0; + u64 m3 = a1 * b1; + uint128_t result; + + m2 += (m0 >> 32); + m2 += m1; + + /* Overflow */ + if (m2 < m1) + m3 += 0x100000000ull; + + result.m_low = (m0 & 0xffffffffull) | (m2 << 32); + result.m_high = m3 + (m2 >> 32); + + return result; +} + +static uint128_t add_128_128(uint128_t a, uint128_t b) +{ + uint128_t result; + + result.m_low = a.m_low + b.m_low; + result.m_high = a.m_high + b.m_high + (result.m_low < a.m_low); + + return result; +} + +static void vli_mult(u64 *result, const u64 *left, const u64 *right, + unsigned int ndigits) +{ + uint128_t r01 = { 0, 0 }; + u64 r2 = 0; + unsigned int i, k; + + /* Compute each digit of result in sequence, maintaining the + * carries. + */ + for (k = 0; k < ndigits * 2 - 1; k++) { + unsigned int min; + + if (k < ndigits) + min = 0; + else + min = (k + 1) - ndigits; + + for (i = min; i <= k && i < ndigits; i++) { + uint128_t product; + + product = mul_64_64(left[i], right[k - i]); + + r01 = add_128_128(r01, product); + r2 += (r01.m_high < product.m_high); + } + + result[k] = r01.m_low; + r01.m_low = r01.m_high; + r01.m_high = r2; + r2 = 0; + } + + result[ndigits * 2 - 1] = r01.m_low; +} + +static void vli_square(u64 *result, const u64 *left, unsigned int ndigits) +{ + uint128_t r01 = { 0, 0 }; + u64 r2 = 0; + int i, k; + + for (k = 0; k < ndigits * 2 - 1; k++) { + unsigned int min; + + if (k < ndigits) + min = 0; + else + min = (k + 1) - ndigits; + + for (i = min; i <= k && i <= k - i; i++) { + uint128_t product; + + product = mul_64_64(left[i], left[k - i]); + + if (i < k - i) { + r2 += product.m_high >> 63; + product.m_high = (product.m_high << 1) | + (product.m_low >> 63); + product.m_low <<= 1; + } + + r01 = add_128_128(r01, product); + r2 += (r01.m_high < product.m_high); + } + + result[k] = r01.m_low; + r01.m_low = r01.m_high; + r01.m_high = r2; + r2 = 0; + } + + result[ndigits * 2 - 1] = r01.m_low; +} + +/* Computes result = (left + right) % mod. + * Assumes that left < mod and right < mod, result != mod. + */ +static void vli_mod_add(u64 *result, const u64 *left, const u64 *right, + const u64 *mod, unsigned int ndigits) +{ + u64 carry; + + carry = vli_add(result, left, right, ndigits); + + /* result > mod (result = mod + remainder), so subtract mod to + * get remainder. + */ + if (carry || vli_cmp(result, mod, ndigits) >= 0) + vli_sub(result, result, mod, ndigits); +} + +/* Computes result = (left - right) % mod. + * Assumes that left < mod and right < mod, result != mod. + */ +static void vli_mod_sub(u64 *result, const u64 *left, const u64 *right, + const u64 *mod, unsigned int ndigits) +{ + u64 borrow = vli_sub(result, left, right, ndigits); + + /* In this case, p_result == -diff == (max int) - diff. + * Since -x % d == d - x, we can get the correct result from + * result + mod (with overflow). + */ + if (borrow) + vli_add(result, result, mod, ndigits); +} + +/* Computes p_result = p_product % curve_p. + * See algorithm 5 and 6 from + * http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf + */ +static void vli_mmod_fast_192(u64 *result, const u64 *product, + const u64 *curve_prime, u64 *tmp) +{ + const unsigned int ndigits = 3; + int carry; + + vli_set(result, product, ndigits); + + vli_set(tmp, &product[3], ndigits); + carry = vli_add(result, result, tmp, ndigits); + + tmp[0] = 0; + tmp[1] = product[3]; + tmp[2] = product[4]; + carry += vli_add(result, result, tmp, ndigits); + + tmp[0] = tmp[1] = product[5]; + tmp[2] = 0; + carry += vli_add(result, result, tmp, ndigits); + + while (carry || vli_cmp(curve_prime, result, ndigits) != 1) + carry -= vli_sub(result, result, curve_prime, ndigits); +} + +/* Computes result = product % curve_prime + * from http://www.nsa.gov/ia/_files/nist-routines.pdf + */ +static void vli_mmod_fast_256(u64 *result, const u64 *product, + const u64 *curve_prime, u64 *tmp) +{ + int carry; + const unsigned int ndigits = 4; + + /* t */ + vli_set(result, product, ndigits); + + /* s1 */ + tmp[0] = 0; + tmp[1] = product[5] & 0xffffffff00000000ull; + tmp[2] = product[6]; + tmp[3] = product[7]; + carry = vli_lshift(tmp, tmp, 1, ndigits); + carry += vli_add(result, result, tmp, ndigits); + + /* s2 */ + tmp[1] = product[6] << 32; + tmp[2] = (product[6] >> 32) | (product[7] << 32); + tmp[3] = product[7] >> 32; + carry += vli_lshift(tmp, tmp, 1, ndigits); + carry += vli_add(result, result, tmp, ndigits); + + /* s3 */ + tmp[0] = product[4]; + tmp[1] = product[5] & 0xffffffff; + tmp[2] = 0; + tmp[3] = product[7]; + carry += vli_add(result, result, tmp, ndigits); + + /* s4 */ + tmp[0] = (product[4] >> 32) | (product[5] << 32); + tmp[1] = (product[5] >> 32) | (product[6] & 0xffffffff00000000ull); + tmp[2] = product[7]; + tmp[3] = (product[6] >> 32) | (product[4] << 32); + carry += vli_add(result, result, tmp, ndigits); + + /* d1 */ + tmp[0] = (product[5] >> 32) | (product[6] << 32); + tmp[1] = (product[6] >> 32); + tmp[2] = 0; + tmp[3] = (product[4] & 0xffffffff) | (product[5] << 32); + carry -= vli_sub(result, result, tmp, ndigits); + + /* d2 */ + tmp[0] = product[6]; + tmp[1] = product[7]; + tmp[2] = 0; + tmp[3] = (product[4] >> 32) | (product[5] & 0xffffffff00000000ull); + carry -= vli_sub(result, result, tmp, ndigits); + + /* d3 */ + tmp[0] = (product[6] >> 32) | (product[7] << 32); + tmp[1] = (product[7] >> 32) | (product[4] << 32); + tmp[2] = (product[4] >> 32) | (product[5] << 32); + tmp[3] = (product[6] << 32); + carry -= vli_sub(result, result, tmp, ndigits); + + /* d4 */ + tmp[0] = product[7]; + tmp[1] = product[4] & 0xffffffff00000000ull; + tmp[2] = product[5]; + tmp[3] = product[6] & 0xffffffff00000000ull; + carry -= vli_sub(result, result, tmp, ndigits); + + if (carry < 0) { + do { + carry += vli_add(result, result, curve_prime, ndigits); + } while (carry < 0); + } else { + while (carry || vli_cmp(curve_prime, result, ndigits) != 1) + carry -= vli_sub(result, result, curve_prime, ndigits); + } +} + +/* Computes result = product % curve_prime + * from http://www.nsa.gov/ia/_files/nist-routines.pdf +*/ +static bool vli_mmod_fast(u64 *result, u64 *product, + const u64 *curve_prime, unsigned int ndigits) +{ + u64 tmp[2 * ndigits]; + + switch (ndigits) { + case 3: + vli_mmod_fast_192(result, product, curve_prime, tmp); + break; + case 4: + vli_mmod_fast_256(result, product, curve_prime, tmp); + break; + default: + pr_err("unsupports digits size!\n"); + return false; + } + + return true; +} + +/* Computes result = (left * right) % curve_prime. */ +static void vli_mod_mult_fast(u64 *result, const u64 *left, const u64 *right, + const u64 *curve_prime, unsigned int ndigits) +{ + u64 product[2 * ndigits]; + + vli_mult(product, left, right, ndigits); + vli_mmod_fast(result, product, curve_prime, ndigits); +} + +/* Computes result = left^2 % curve_prime. */ +static void vli_mod_square_fast(u64 *result, const u64 *left, + const u64 *curve_prime, unsigned int ndigits) +{ + u64 product[2 * ndigits]; + + vli_square(product, left, ndigits); + vli_mmod_fast(result, product, curve_prime, ndigits); +} + +#define EVEN(vli) (!(vli[0] & 1)) +/* Computes result = (1 / p_input) % mod. All VLIs are the same size. + * See "From Euclid's GCD to Montgomery Multiplication to the Great Divide" + * https://labs.oracle.com/techrep/2001/smli_tr-2001-95.pdf + */ +static void vli_mod_inv(u64 *result, const u64 *input, const u64 *mod, + unsigned int ndigits) +{ + u64 a[ndigits], b[ndigits]; + u64 u[ndigits], v[ndigits]; + u64 carry; + int cmp_result; + + if (vli_is_zero(input, ndigits)) { + vli_clear(result, ndigits); + return; + } + + vli_set(a, input, ndigits); + vli_set(b, mod, ndigits); + vli_clear(u, ndigits); + u[0] = 1; + vli_clear(v, ndigits); + + while ((cmp_result = vli_cmp(a, b, ndigits)) != 0) { + carry = 0; + + if (EVEN(a)) { + vli_rshift1(a, ndigits); + + if (!EVEN(u)) + carry = vli_add(u, u, mod, ndigits); + + vli_rshift1(u, ndigits); + if (carry) + u[ndigits - 1] |= 0x8000000000000000ull; + } else if (EVEN(b)) { + vli_rshift1(b, ndigits); + + if (!EVEN(v)) + carry = vli_add(v, v, mod, ndigits); + + vli_rshift1(v, ndigits); + if (carry) + v[ndigits - 1] |= 0x8000000000000000ull; + } else if (cmp_result > 0) { + vli_sub(a, a, b, ndigits); + vli_rshift1(a, ndigits); + + if (vli_cmp(u, v, ndigits) < 0) + vli_add(u, u, mod, ndigits); + + vli_sub(u, u, v, ndigits); + if (!EVEN(u)) + carry = vli_add(u, u, mod, ndigits); + + vli_rshift1(u, ndigits); + if (carry) + u[ndigits - 1] |= 0x8000000000000000ull; + } else { + vli_sub(b, b, a, ndigits); + vli_rshift1(b, ndigits); + + if (vli_cmp(v, u, ndigits) < 0) + vli_add(v, v, mod, ndigits); + + vli_sub(v, v, u, ndigits); + if (!EVEN(v)) + carry = vli_add(v, v, mod, ndigits); + + vli_rshift1(v, ndigits); + if (carry) + v[ndigits - 1] |= 0x8000000000000000ull; + } + } + + vli_set(result, u, ndigits); +} + +/* ------ Point operations ------ */ + +/* Returns true if p_point is the point at infinity, false otherwise. */ +static bool ecc_point_is_zero(const struct ecc_point *point) +{ + return (vli_is_zero(point->x, point->ndigits) && + vli_is_zero(point->y, point->ndigits)); +} + +/* Point multiplication algorithm using Montgomery's ladder with co-Z + * coordinates. From http://eprint.iacr.org/2011/338.pdf + */ + +/* Double in place */ +static void ecc_point_double_jacobian(u64 *x1, u64 *y1, u64 *z1, + u64 *curve_prime, unsigned int ndigits) +{ + /* t1 = x, t2 = y, t3 = z */ + u64 t4[ndigits]; + u64 t5[ndigits]; + + if (vli_is_zero(z1, ndigits)) + return; + + /* t4 = y1^2 */ + vli_mod_square_fast(t4, y1, curve_prime, ndigits); + /* t5 = x1*y1^2 = A */ + vli_mod_mult_fast(t5, x1, t4, curve_prime, ndigits); + /* t4 = y1^4 */ + vli_mod_square_fast(t4, t4, curve_prime, ndigits); + /* t2 = y1*z1 = z3 */ + vli_mod_mult_fast(y1, y1, z1, curve_prime, ndigits); + /* t3 = z1^2 */ + vli_mod_square_fast(z1, z1, curve_prime, ndigits); + + /* t1 = x1 + z1^2 */ + vli_mod_add(x1, x1, z1, curve_prime, ndigits); + /* t3 = 2*z1^2 */ + vli_mod_add(z1, z1, z1, curve_prime, ndigits); + /* t3 = x1 - z1^2 */ + vli_mod_sub(z1, x1, z1, curve_prime, ndigits); + /* t1 = x1^2 - z1^4 */ + vli_mod_mult_fast(x1, x1, z1, curve_prime, ndigits); + + /* t3 = 2*(x1^2 - z1^4) */ + vli_mod_add(z1, x1, x1, curve_prime, ndigits); + /* t1 = 3*(x1^2 - z1^4) */ + vli_mod_add(x1, x1, z1, curve_prime, ndigits); + if (vli_test_bit(x1, 0)) { + u64 carry = vli_add(x1, x1, curve_prime, ndigits); + + vli_rshift1(x1, ndigits); + x1[ndigits - 1] |= carry << 63; + } else { + vli_rshift1(x1, ndigits); + } + /* t1 = 3/2*(x1^2 - z1^4) = B */ + + /* t3 = B^2 */ + vli_mod_square_fast(z1, x1, curve_prime, ndigits); + /* t3 = B^2 - A */ + vli_mod_sub(z1, z1, t5, curve_prime, ndigits); + /* t3 = B^2 - 2A = x3 */ + vli_mod_sub(z1, z1, t5, curve_prime, ndigits); + /* t5 = A - x3 */ + vli_mod_sub(t5, t5, z1, curve_prime, ndigits); + /* t1 = B * (A - x3) */ + vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits); + /* t4 = B * (A - x3) - y1^4 = y3 */ + vli_mod_sub(t4, x1, t4, curve_prime, ndigits); + + vli_set(x1, z1, ndigits); + vli_set(z1, y1, ndigits); + vli_set(y1, t4, ndigits); +} + +/* Modify (x1, y1) => (x1 * z^2, y1 * z^3) */ +static void apply_z(u64 *x1, u64 *y1, u64 *z, u64 *curve_prime, + unsigned int ndigits) +{ + u64 t1[ndigits]; + + vli_mod_square_fast(t1, z, curve_prime, ndigits); /* z^2 */ + vli_mod_mult_fast(x1, x1, t1, curve_prime, ndigits); /* x1 * z^2 */ + vli_mod_mult_fast(t1, t1, z, curve_prime, ndigits); /* z^3 */ + vli_mod_mult_fast(y1, y1, t1, curve_prime, ndigits); /* y1 * z^3 */ +} + +/* P = (x1, y1) => 2P, (x2, y2) => P' */ +static void xycz_initial_double(u64 *x1, u64 *y1, u64 *x2, u64 *y2, + u64 *p_initial_z, u64 *curve_prime, + unsigned int ndigits) +{ + u64 z[ndigits]; + + vli_set(x2, x1, ndigits); + vli_set(y2, y1, ndigits); + + vli_clear(z, ndigits); + z[0] = 1; + + if (p_initial_z) + vli_set(z, p_initial_z, ndigits); + + apply_z(x1, y1, z, curve_prime, ndigits); + + ecc_point_double_jacobian(x1, y1, z, curve_prime, ndigits); + + apply_z(x2, y2, z, curve_prime, ndigits); +} + +/* Input P = (x1, y1, Z), Q = (x2, y2, Z) + * Output P' = (x1', y1', Z3), P + Q = (x3, y3, Z3) + * or P => P', Q => P + Q + */ +static void xycz_add(u64 *x1, u64 *y1, u64 *x2, u64 *y2, u64 *curve_prime, + unsigned int ndigits) +{ + /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */ + u64 t5[ndigits]; + + /* t5 = x2 - x1 */ + vli_mod_sub(t5, x2, x1, curve_prime, ndigits); + /* t5 = (x2 - x1)^2 = A */ + vli_mod_square_fast(t5, t5, curve_prime, ndigits); + /* t1 = x1*A = B */ + vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits); + /* t3 = x2*A = C */ + vli_mod_mult_fast(x2, x2, t5, curve_prime, ndigits); + /* t4 = y2 - y1 */ + vli_mod_sub(y2, y2, y1, curve_prime, ndigits); + /* t5 = (y2 - y1)^2 = D */ + vli_mod_square_fast(t5, y2, curve_prime, ndigits); + + /* t5 = D - B */ + vli_mod_sub(t5, t5, x1, curve_prime, ndigits); + /* t5 = D - B - C = x3 */ + vli_mod_sub(t5, t5, x2, curve_prime, ndigits); + /* t3 = C - B */ + vli_mod_sub(x2, x2, x1, curve_prime, ndigits); + /* t2 = y1*(C - B) */ + vli_mod_mult_fast(y1, y1, x2, curve_prime, ndigits); + /* t3 = B - x3 */ + vli_mod_sub(x2, x1, t5, curve_prime, ndigits); + /* t4 = (y2 - y1)*(B - x3) */ + vli_mod_mult_fast(y2, y2, x2, curve_prime, ndigits); + /* t4 = y3 */ + vli_mod_sub(y2, y2, y1, curve_prime, ndigits); + + vli_set(x2, t5, ndigits); +} + +/* Input P = (x1, y1, Z), Q = (x2, y2, Z) + * Output P + Q = (x3, y3, Z3), P - Q = (x3', y3', Z3) + * or P => P - Q, Q => P + Q + */ +static void xycz_add_c(u64 *x1, u64 *y1, u64 *x2, u64 *y2, u64 *curve_prime, + unsigned int ndigits) +{ + /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */ + u64 t5[ndigits]; + u64 t6[ndigits]; + u64 t7[ndigits]; + + /* t5 = x2 - x1 */ + vli_mod_sub(t5, x2, x1, curve_prime, ndigits); + /* t5 = (x2 - x1)^2 = A */ + vli_mod_square_fast(t5, t5, curve_prime, ndigits); + /* t1 = x1*A = B */ + vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits); + /* t3 = x2*A = C */ + vli_mod_mult_fast(x2, x2, t5, curve_prime, ndigits); + /* t4 = y2 + y1 */ + vli_mod_add(t5, y2, y1, curve_prime, ndigits); + /* t4 = y2 - y1 */ + vli_mod_sub(y2, y2, y1, curve_prime, ndigits); + + /* t6 = C - B */ + vli_mod_sub(t6, x2, x1, curve_prime, ndigits); + /* t2 = y1 * (C - B) */ + vli_mod_mult_fast(y1, y1, t6, curve_prime, ndigits); + /* t6 = B + C */ + vli_mod_add(t6, x1, x2, curve_prime, ndigits); + /* t3 = (y2 - y1)^2 */ + vli_mod_square_fast(x2, y2, curve_prime, ndigits); + /* t3 = x3 */ + vli_mod_sub(x2, x2, t6, curve_prime, ndigits); + + /* t7 = B - x3 */ + vli_mod_sub(t7, x1, x2, curve_prime, ndigits); + /* t4 = (y2 - y1)*(B - x3) */ + vli_mod_mult_fast(y2, y2, t7, curve_prime, ndigits); + /* t4 = y3 */ + vli_mod_sub(y2, y2, y1, curve_prime, ndigits); + + /* t7 = (y2 + y1)^2 = F */ + vli_mod_square_fast(t7, t5, curve_prime, ndigits); + /* t7 = x3' */ + vli_mod_sub(t7, t7, t6, curve_prime, ndigits); + /* t6 = x3' - B */ + vli_mod_sub(t6, t7, x1, curve_prime, ndigits); + /* t6 = (y2 + y1)*(x3' - B) */ + vli_mod_mult_fast(t6, t6, t5, curve_prime, ndigits); + /* t2 = y3' */ + vli_mod_sub(y1, t6, y1, curve_prime, ndigits); + + vli_set(x1, t7, ndigits); +} + +static void ecc_point_mult(struct ecc_point *result, + const struct ecc_point *point, const u64 *scalar, + u64 *initial_z, u64 *curve_prime, + unsigned int ndigits) +{ + /* R0 and R1 */ + u64 rx[2][ndigits]; + u64 ry[2][ndigits]; + u64 z[ndigits]; + int i, nb; + int num_bits = vli_num_bits(scalar, ndigits); + + vli_set(rx[1], point->x, ndigits); + vli_set(ry[1], point->y, ndigits); + + xycz_initial_double(rx[1], ry[1], rx[0], ry[0], initial_z, curve_prime, + ndigits); + + for (i = num_bits - 2; i > 0; i--) { + nb = !vli_test_bit(scalar, i); + xycz_add_c(rx[1 - nb], ry[1 - nb], rx[nb], ry[nb], curve_prime, + ndigits); + xycz_add(rx[nb], ry[nb], rx[1 - nb], ry[1 - nb], curve_prime, + ndigits); + } + + nb = !vli_test_bit(scalar, 0); + xycz_add_c(rx[1 - nb], ry[1 - nb], rx[nb], ry[nb], curve_prime, + ndigits); + + /* Find final 1/Z value. */ + /* X1 - X0 */ + vli_mod_sub(z, rx[1], rx[0], curve_prime, ndigits); + /* Yb * (X1 - X0) */ + vli_mod_mult_fast(z, z, ry[1 - nb], curve_prime, ndigits); + /* xP * Yb * (X1 - X0) */ + vli_mod_mult_fast(z, z, point->x, curve_prime, ndigits); + + /* 1 / (xP * Yb * (X1 - X0)) */ + vli_mod_inv(z, z, curve_prime, point->ndigits); + + /* yP / (xP * Yb * (X1 - X0)) */ + vli_mod_mult_fast(z, z, point->y, curve_prime, ndigits); + /* Xb * yP / (xP * Yb * (X1 - X0)) */ + vli_mod_mult_fast(z, z, rx[1 - nb], curve_prime, ndigits); + /* End 1/Z calculation */ + + xycz_add(rx[nb], ry[nb], rx[1 - nb], ry[1 - nb], curve_prime, ndigits); + + apply_z(rx[0], ry[0], z, curve_prime, ndigits); + + vli_set(result->x, rx[0], ndigits); + vli_set(result->y, ry[0], ndigits); +} + +static inline void ecc_swap_digits(const u64 *in, u64 *out, + unsigned int ndigits) +{ + int i; + + for (i = 0; i < ndigits; i++) + out[i] = __swab64(in[ndigits - 1 - i]); +} + +int ecdh_make_pub_key(unsigned int curve_id, + const u8 *private_key, unsigned int private_key_len, + u8 *public_key, unsigned int public_key_len) +{ + int ret = 0; + struct ecc_point *pk; + unsigned int tries = 0; + u64 *priv = NULL; + unsigned int ndigits; + unsigned int nbytes; + const struct ecc_curve *curve = ecc_get_curve(curve_id); + + if (!private_key || !curve) { + ret = -EINVAL; + goto out; + } + + ndigits = curve->g.ndigits; + nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT; + + if (private_key_len != nbytes) { + ret = -EINVAL; + goto out; + } + + if (vli_is_zero((const u64 *)&private_key[0], ndigits)) { + ret = -EINVAL; + goto out; + } + + /* Make sure the private key is in the range [1, n-1]. */ + if (vli_cmp(curve->n, (const u64 *)&private_key[0], ndigits) != 1) { + ret = -EINVAL; + goto out; + } + + priv = ecc_alloc_digits_space(ndigits); + if (!priv) { + ret = -ENOMEM; + goto out; + } + + ecc_swap_digits((const u64 *)private_key, priv, ndigits); + + pk = ecc_alloc_point(ndigits); + if (!pk) { + ret = -ENOMEM; + goto err_alloc_pk; + } + + do { + if (tries++ >= MAX_TRIES) + goto err_retries; + + ecc_point_mult(pk, &curve->g, priv, NULL, curve->p, ndigits); + + } while (ecc_point_is_zero(pk)); + + ecc_swap_digits(pk->x, (u64 *)public_key, ndigits); + ecc_swap_digits(pk->y, (u64 *)&public_key[nbytes], ndigits); + +err_retries: + ecc_free_point(pk); +err_alloc_pk: + ecc_free_digits_space(priv); +out: + return ret; +} + +int ecdh_shared_secret(unsigned int curve_id, + const u8 *private_key, unsigned int private_key_len, + const u8 *public_key, unsigned int public_key_len, + u8 *secret, unsigned int secret_len) +{ + int ret = 0; + struct ecc_point *product, *pk; + u64 *priv, *rand_z; + unsigned int ndigits; + unsigned int nbytes; + const struct ecc_curve *curve = ecc_get_curve(curve_id); + + if (!private_key || !public_key) { + ret = -EINVAL; + goto out; + } + + ndigits = curve->g.ndigits; + nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT; + + rand_z = ecc_alloc_digits_space(ndigits); + if (!rand_z) { + ret = -ENOMEM; + goto out; + } + + priv = ecc_alloc_digits_space(ndigits); + if (!priv) { + ret = -ENOMEM; + goto err_alloc_priv; + } + + get_random_bytes(rand_z, nbytes); + + pk = ecc_alloc_point(ndigits); + if (!pk) { + ret = -ENOMEM; + goto err_alloc_pk; + } + + product = ecc_alloc_point(ndigits); + if (!product) { + ret = -ENOMEM; + goto err_alloc_product; + } + + ecc_swap_digits((const u64 *)public_key, pk->x, ndigits); + ecc_swap_digits((const u64 *)&public_key[nbytes], pk->y, ndigits); + ecc_swap_digits((const u64 *)private_key, priv, ndigits); + + ecc_point_mult(product, pk, priv, rand_z, curve->p, ndigits); + + ecc_swap_digits(product->x, (u64 *)secret, ndigits); + + if (ecc_point_is_zero(product)) + ret = -EFAULT; + + ecc_free_point(product); +err_alloc_product: + ecc_free_point(pk); +err_alloc_pk: + ecc_free_digits_space(priv); +err_alloc_priv: + ecc_free_digits_space(rand_z); +out: + return ret; +} diff --git a/crypto/ecc.h b/crypto/ecc.h new file mode 100644 index 0000000..7889410 --- /dev/null +++ b/crypto/ecc.h @@ -0,0 +1,70 @@ +/* + * Copyright (c) 2013, Kenneth MacKay + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#ifndef _CRYPTO_ECC_H +#define _CRYPTO_ECC_H + +#define ECC_MAX_DIGITS 4 /* 256 */ + +#define ECC_DIGITS_TO_BYTES_SHIFT 3 + +/** + * ecdh_make_pub_key() - Compute an ECC public key + * + * @curve_id: id representing the curve to use + * @private_key: pregenerated private key for the given curve + * @private_key_len: length of private_key + * @public_key: buffer for storing the public key generated + * @public_key_len: length of the public_key buffer + * + * Returns 0 if the public key was generated successfully, a negative value + * if an error occurred. + */ +int ecdh_make_pub_key(const unsigned int curve_id, + const u8 *private_key, unsigned int private_key_len, + u8 *public_key, unsigned int public_key_len); + +/** + * ecdh_shared_secret() - Compute a shared secret + * + * @curve_id: id representing the curve to use + * @private_key: private key of part A + * @private_key_len: length of private_key + * @public_key: public key of counterpart B + * @public_key_len: length of public_key + * @secret: buffer for storing the calculated shared secret + * @secret_len: length of the secret buffer + * + * Note: It is recommended that you hash the result of ecdh_shared_secret + * before using it for symmetric encryption or HMAC. + * + * Returns 0 if the shared secret was generated successfully, a negative value + * if an error occurred. + */ +int ecdh_shared_secret(unsigned int curve_id, + const u8 *private_key, unsigned int private_key_len, + const u8 *public_key, unsigned int public_key_len, + u8 *secret, unsigned int secret_len); +#endif diff --git a/crypto/ecc_curve_defs.h b/crypto/ecc_curve_defs.h new file mode 100644 index 0000000..03ae5f7 --- /dev/null +++ b/crypto/ecc_curve_defs.h @@ -0,0 +1,57 @@ +#ifndef _CRYTO_ECC_CURVE_DEFS_H +#define _CRYTO_ECC_CURVE_DEFS_H + +struct ecc_point { + u64 *x; + u64 *y; + u8 ndigits; +}; + +struct ecc_curve { + char *name; + struct ecc_point g; + u64 *p; + u64 *n; +}; + +/* NIST P-192 */ +static u64 nist_p192_g_x[] = { 0xF4FF0AFD82FF1012ull, 0x7CBF20EB43A18800ull, + 0x188DA80EB03090F6ull }; +static u64 nist_p192_g_y[] = { 0x73F977A11E794811ull, 0x631011ED6B24CDD5ull, + 0x07192B95FFC8DA78ull }; +static u64 nist_p192_p[] = { 0xFFFFFFFFFFFFFFFFull, 0xFFFFFFFFFFFFFFFEull, + 0xFFFFFFFFFFFFFFFFull }; +static u64 nist_p192_n[] = { 0x146BC9B1B4D22831ull, 0xFFFFFFFF99DEF836ull, + 0xFFFFFFFFFFFFFFFFull }; +static struct ecc_curve nist_p192 = { + .name = "nist_192", + .g = { + .x = nist_p192_g_x, + .y = nist_p192_g_y, + .ndigits = 3, + }, + .p = nist_p192_p, + .n = nist_p192_n +}; + +/* NIST P-256 */ +static u64 nist_p256_g_x[] = { 0xF4A13945D898C296ull, 0x77037D812DEB33A0ull, + 0xF8BCE6E563A440F2ull, 0x6B17D1F2E12C4247ull }; +static u64 nist_p256_g_y[] = { 0xCBB6406837BF51F5ull, 0x2BCE33576B315ECEull, + 0x8EE7EB4A7C0F9E16ull, 0x4FE342E2FE1A7F9Bull }; +static u64 nist_p256_p[] = { 0xFFFFFFFFFFFFFFFFull, 0x00000000FFFFFFFFull, + 0x0000000000000000ull, 0xFFFFFFFF00000001ull }; +static u64 nist_p256_n[] = { 0xF3B9CAC2FC632551ull, 0xBCE6FAADA7179E84ull, + 0xFFFFFFFFFFFFFFFFull, 0xFFFFFFFF00000000ull }; +static struct ecc_curve nist_p256 = { + .name = "nist_256", + .g = { + .x = nist_p256_g_x, + .y = nist_p256_g_y, + .ndigits = 4, + }, + .p = nist_p256_p, + .n = nist_p256_n +}; + +#endif diff --git a/crypto/ecdh.c b/crypto/ecdh.c new file mode 100644 index 0000000..828aa14 --- /dev/null +++ b/crypto/ecdh.c @@ -0,0 +1,171 @@ +/* ECDH key-agreement protocol + * + * Copyright (c) 2016, Intel Corporation + * Authors: Salvator Benedetto <salvatore.benedetto@intel.com> + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public Licence + * as published by the Free Software Foundation; either version + * 2 of the Licence, or (at your option) any later version. + */ + +#include <linux/module.h> +#include <crypto/internal/kpp.h> +#include <crypto/kpp.h> +#include <crypto/ecdh.h> +#include <linux/scatterlist.h> +#include "ecc.h" + +struct ecdh_ctx { + unsigned int curve_id; + unsigned int ndigits; + u64 private_key[ECC_MAX_DIGITS]; + u64 public_key[2 * ECC_MAX_DIGITS]; + u64 shared_secret[ECC_MAX_DIGITS]; +}; + +static inline struct ecdh_ctx *ecdh_get_ctx(struct crypto_kpp *tfm) +{ + return kpp_tfm_ctx(tfm); +} + +static unsigned int ecdh_supported_curve(unsigned int curve_id) +{ + switch (curve_id) { + case ECC_CURVE_NIST_P192: return 3; + case ECC_CURVE_NIST_P256: return 4; + default: return 0; + } +} + +static int ecdh_set_params(struct crypto_kpp *tfm, void *buffer, + unsigned int len) +{ + struct ecdh_ctx *ctx = ecdh_get_ctx(tfm); + struct ecdh_params *params = (struct ecdh_params *)buffer; + + if (unlikely(!buffer || !len)) + return -EINVAL; + + ctx->ndigits = ecdh_supported_curve(params->curve_id); + if (unlikely(!ctx->ndigits)) + return -EINVAL; + + ctx->curve_id = params->curve_id; + + return 0; +} + +static int ecdh_set_secret(struct crypto_kpp *tfm, void *buffer, + unsigned int len) +{ + struct ecdh_ctx *ctx = ecdh_get_ctx(tfm); + + if (unlikely(!buffer || !len)) + return -EINVAL; + + if (unlikely(ctx->ndigits != (len >> ECC_DIGITS_TO_BYTES_SHIFT))) + return -EINVAL; + + memcpy(ctx->private_key, buffer, len); + + return 0; +} + +static int ecdh_generate_public_key(struct kpp_request *req) +{ + int ret = 0; + struct crypto_kpp *tfm = crypto_kpp_reqtfm(req); + const struct ecdh_ctx *ctx = ecdh_get_ctx(tfm); + size_t copied, nbytes; + + nbytes = ctx->ndigits << ECC_DIGITS_TO_BYTES_SHIFT; + + ret = ecdh_make_pub_key(ctx->curve_id, + (const u8 *)ctx->private_key, nbytes, + (u8 *)ctx->public_key, sizeof(ctx->public_key)); + if (ret < 0) + return ret; + + /* Public part is a point thus it has both coordinates */ + copied = sg_copy_from_buffer(req->dst, 1, ctx->public_key, + nbytes * 2); + + if (copied != 2 * nbytes) + return -EINVAL; + + return ret; +} + +static int ecdh_compute_shared_secret(struct kpp_request *req) +{ + int ret = 0; + struct crypto_kpp *tfm = crypto_kpp_reqtfm(req); + struct ecdh_ctx *ctx = ecdh_get_ctx(tfm); + size_t copied, nbytes; + + nbytes = ctx->ndigits << ECC_DIGITS_TO_BYTES_SHIFT; + + copied = sg_copy_to_buffer(req->src, 1, ctx->public_key, 2 * nbytes); + if (copied != 2 * nbytes) + return -EINVAL; + + ret = ecdh_shared_secret(ctx->curve_id, + (const u8 *)ctx->private_key, nbytes, + (const u8 *)ctx->public_key, 2 * nbytes, + (u8 *)ctx->shared_secret, nbytes); + if (ret < 0) + return ret; + + copied = sg_copy_from_buffer(req->dst, 1, ctx->shared_secret, nbytes); + if (copied != nbytes) + return -EINVAL; + + return ret; +} + +static int ecdh_max_size(struct crypto_kpp *tfm) +{ + struct ecdh_ctx *ctx = ecdh_get_ctx(tfm); + int nbytes = ctx->ndigits << ECC_DIGITS_TO_BYTES_SHIFT; + + /* Public key is made of two coordinates */ + return 2 * nbytes; +} + +static void no_exit_tfm(struct crypto_kpp *tfm) +{ + return; +} + +static struct kpp_alg ecdh = { + .set_params = ecdh_set_params, + .set_secret = ecdh_set_secret, + .generate_public_key = ecdh_generate_public_key, + .compute_shared_secret = ecdh_compute_shared_secret, + .max_size = ecdh_max_size, + .exit = no_exit_tfm, + .base = { + .cra_name = "ecdh", + .cra_driver_name = "ecdh-generic", + .cra_priority = 100, + .cra_module = THIS_MODULE, + .cra_ctxsize = sizeof(struct ecdh_ctx), + }, +}; + +static int ecdh_init(void) +{ + return crypto_register_kpp(&ecdh); +} + +static void ecdh_exit(void) +{ + crypto_unregister_kpp(&ecdh); +} + +module_init(ecdh_init); +module_exit(ecdh_exit); +MODULE_ALIAS_CRYPTO("ecdh"); +MODULE_LICENSE("GPL"); +MODULE_DESCRIPTION("ECDH generic algorithm"); diff --git a/crypto/testmgr.c b/crypto/testmgr.c index d68fa58..6d7b30c 100644 --- a/crypto/testmgr.c +++ b/crypto/testmgr.c @@ -34,6 +34,7 @@ #include <crypto/akcipher.h> #include <crypto/kpp.h> #include <crypto/dh.h> +#include <crypto/ecdh.h> #include "internal.h" @@ -119,7 +120,10 @@ struct akcipher_test_suite { }; struct kpp_test_suite { - struct kpp_testvec_dh *vecs; + union { + struct kpp_testvec_dh *dh; + struct kpp_testvec_ecdh *ecdh; + } vecs; unsigned int count; }; @@ -1891,12 +1895,113 @@ static int test_dh(struct crypto_kpp *tfm, struct kpp_testvec_dh *vecs, return 0; } -static int test_kpp(struct crypto_kpp *tfm, const char *alg, - struct kpp_testvec_dh *vecs, unsigned int tcount) +static int do_test_ecdh(struct crypto_kpp *tfm, struct kpp_testvec_ecdh *vec) +{ + struct kpp_request *req; + void *input_buf = NULL; + void *output_buf = NULL; + struct tcrypt_result result; + unsigned int out_len_max; + int err = -ENOMEM; + struct scatterlist src, dst; + struct ecdh_params p; + unsigned int nbytes = vec->ndigits << ECC_DIGITS_TO_BYTES_SHIFT; + + req = kpp_request_alloc(tfm, GFP_KERNEL); + if (!req) + return err; + + init_completion(&result.completion); + + /* Set curve_id */ + p.curve_id = vec->curve_id; + err = crypto_kpp_set_params(tfm, (void *)&p, sizeof(p)); + if (err) + goto free_req; + + /* Set A private Key */ + err = crypto_kpp_set_secret(tfm, vec->private_a, nbytes); + if (err) + goto free_req; + + out_len_max = crypto_kpp_maxsize(tfm); + output_buf = kzalloc(out_len_max, GFP_KERNEL); + if (!output_buf) { + err = -ENOMEM; + goto free_req; + } + + sg_init_one(&dst, output_buf, out_len_max); + kpp_request_set_output(req, &dst, out_len_max); + kpp_request_set_callback(req, CRYPTO_TFM_REQ_MAY_BACKLOG, + tcrypt_complete, &result); + + /* Compute A public key = aG mod p */ + err = wait_async_op(&result, crypto_kpp_generate_public_key(req)); + if (err) { + pr_err("alg: ecdh: generate public key test failed. err %d\n", + err); + goto free_output; + } + /* Verify calculated public key */ + if (memcmp(vec->expected_pub_a, sg_virt(req->dst), 2 * nbytes)) { + pr_err("alg: ecdh: generate public key test failed. Invalid output\n"); + err = -EINVAL; + goto free_output; + } + + /* Calculate shared secret key by using counter part public key. */ + input_buf = kzalloc(2 * nbytes, GFP_KERNEL); + if (!input_buf) { + err = -ENOMEM; + goto free_output; + } + + memcpy(input_buf, vec->public_b, 2 * nbytes); + sg_init_one(&src, input_buf, 2 * nbytes); + sg_init_one(&dst, output_buf, out_len_max); + kpp_request_set_input(req, &src, 2 * nbytes); + 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: ecdh: compute shard secret test failed. err %d\n", + err); + goto free_all; + } + + /* + * 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), nbytes)) { + pr_err("alg: ecdh: compute shared secret test failed. Invalid output\n"); + err = -EINVAL; + } + +free_all: + kfree(input_buf); +free_output: + kfree(output_buf); +free_req: + kpp_request_free(req); + return err; +} + +static int test_ecdh(struct crypto_kpp *tfm, struct kpp_testvec_ecdh *vecs, + unsigned int tcount) { - if (strncmp(alg, "dh", 2) == 0) - return test_dh(tfm, vecs, tcount); + int ret, i; + for (i = 0; i < tcount; i++) { + ret = do_test_ecdh(tfm, vecs++); + if (ret) { + pr_err("alg: ecdh: test failed on vector %d, err=%d\n", + i + 1, ret); + return ret; + } + } return 0; } @@ -1912,9 +2017,12 @@ static int alg_test_kpp(const struct alg_test_desc *desc, const char *driver, driver, PTR_ERR(tfm)); return PTR_ERR(tfm); } - if (desc->suite.kpp.vecs) - err = test_kpp(tfm, desc->alg, desc->suite.kpp.vecs, - desc->suite.kpp.count); + if (!strncmp(desc->alg, "dh", 2) && desc->suite.kpp.vecs.dh) + err = test_dh(tfm, desc->suite.kpp.vecs.dh, + desc->suite.kpp.count); + else if (!strncmp(desc->alg, "ecdh", 4) && desc->suite.kpp.vecs.ecdh) + err = test_ecdh(tfm, desc->suite.kpp.vecs.ecdh, + desc->suite.kpp.count); crypto_free_kpp(tfm); return err; @@ -2860,7 +2968,7 @@ static const struct alg_test_desc alg_test_descs[] = { .fips_allowed = 1, .suite = { .kpp = { - .vecs = dh_tv_template, + .vecs.dh = dh_tv_template, .count = DH_TEST_VECTORS } } @@ -3293,6 +3401,16 @@ static const struct alg_test_desc alg_test_descs[] = { } } }, { + .alg = "ecdh", + .test = alg_test_kpp, + .fips_allowed = 1, + .suite = { + .kpp = { + .vecs.ecdh = ecdh_tv_template, + .count = ECDH_TEST_VECTORS + } + } + }, { .alg = "gcm(aes)", .test = alg_test_aead, .fips_allowed = 1, diff --git a/crypto/testmgr.h b/crypto/testmgr.h index e9c34c7..74b3080 100644 --- a/crypto/testmgr.h +++ b/crypto/testmgr.h @@ -26,6 +26,8 @@ #include <linux/netlink.h> +#include "ecc.h" + #define MAX_DIGEST_SIZE 64 #define MAX_TAP 8 @@ -148,6 +150,15 @@ struct kpp_testvec_dh { unsigned short expected_ss_size; }; +struct kpp_testvec_ecdh { + unsigned int curve_id; + char *private_a; + char *expected_pub_a; + char *public_b; + char *expected_ss; + unsigned short ndigits; +}; + static char zeroed_string[48]; /* @@ -538,6 +549,68 @@ struct kpp_testvec_dh dh_tv_template[] = { } }; +#define ECDH_TEST_VECTORS 2 + +struct kpp_testvec_ecdh ecdh_tv_template[] = { + { + .curve_id = ECC_CURVE_NIST_P192, + .private_a = + "\xb5\x05\xb1\x71\x1e\xbf\x8c\xda" + "\x4e\x19\x1e\x62\x1f\x23\x23\x31" + "\x36\x1e\xd3\x84\x2f\xcc\x21\x72", + .expected_pub_a = + "\x1a\x04\xdb\xa5\xe1\xdd\x4e\x79" + "\xa3\xe6\xef\x0e\x5c\x80\x49\x85" + "\xfa\x78\xb4\xef\x49\xbd\x4c\x7c" + "\x22\x90\x21\x02\xf9\x1b\x81\x5d" + "\x0c\x8a\xa8\x98\xd6\x27\x69\x88" + "\x5e\xbc\x94\xd8\x15\x9e\x21\xce", + .public_b = + "\xc3\xba\x67\x4b\x71\xec\xd0\x76" + "\x7a\x99\x75\x64\x36\x13\x9a\x94" + "\x5d\x8b\xdc\x60\x90\x91\xfd\x3f" + "\xb0\x1f\x8a\x0a\x68\xc6\x88\x6e" + "\x83\x87\xdd\x67\x09\xf8\x8d\x96" + "\x07\xd6\xbd\x1c\xe6\x8d\x9d\x67", + .expected_ss = + "\xf4\x57\xcc\x4f\x1f\x4e\x31\xcc" + "\xe3\x40\x60\xc8\x06\x93\xc6\x2e" + "\x99\x80\x81\x28\xaf\xc5\x51\x74", + .ndigits = 3, + }, { + .curve_id = ECC_CURVE_NIST_P256, + .private_a = + "\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", + .expected_pub_a = + "\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", + .public_b = + "\xcc\xb4\xda\x74\xb1\x47\x3f\xea" + "\x6c\x70\x9e\x38\x2d\xc7\xaa\xb7" + "\x29\xb2\x47\x03\x19\xab\xdd\x34" + "\xbd\xa8\x2c\x93\xe1\xa4\x74\xd9" + "\x64\x63\xf7\x70\x20\x2f\xa4\xe6" + "\x9f\x4a\x38\xcc\xc0\x2c\x49\x2f" + "\xb1\x32\xbb\xaf\x22\x61\xda\xcb" + "\x6f\xdb\xa9\xaa\xfc\x77\x81\xf3", + .expected_ss = + "\xea\x17\x6f\x7e\x6e\x57\x26\x38" + "\x8b\xfb\x41\xeb\xba\xc8\x6d\xa5" + "\xa8\x72\xd1\xff\xc9\x47\x3d\xaa" + "\x58\x43\x9f\x34\x0f\x8c\xf3\xc9", + .ndigits = 4, + } +}; + /* * MD4 test vectors from RFC1320 */ diff --git a/include/crypto/ecdh.h b/include/crypto/ecdh.h new file mode 100644 index 0000000..438214b --- /dev/null +++ b/include/crypto/ecdh.h @@ -0,0 +1,24 @@ +/* + * ECDH params to be used with kpp API + * + * Copyright (c) 2016, Intel Corporation + * Authors: Salvatore Benedetto <salvatore.benedetto@intel.com> + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of 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. + * + */ +#ifndef _CRYPTO_ECDH_ +#define _CRYPTO_ECDH_ + +/* Curves IDs */ +#define ECC_CURVE_NIST_P192 0x0001 +#define ECC_CURVE_NIST_P256 0x0002 + +struct ecdh_params { + unsigned int curve_id; +}; + +#endif -- 1.9.1 ^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH 3/3 v4] crypto: kpp - Add ECDH software support 2016-05-05 9:17 ` [PATCH 3/3 v4] crypto: kpp - Add ECDH software support Salvatore Benedetto @ 2016-05-06 12:02 ` Stephan Mueller 0 siblings, 0 replies; 5+ messages in thread From: Stephan Mueller @ 2016-05-06 12:02 UTC (permalink / raw) To: Salvatore Benedetto; +Cc: herbert, linux-crypto Am Donnerstag, 5. Mai 2016, 10:17:37 schrieb Salvatore Benedetto: Hi Salvatore, > * Implement ECDH under kpp API > * Provide ECC software support for curve P-192 and > P-256. > * Add kpp test for ECDH with data generated by OpenSSL > > Signed-off-by: Salvatore Benedetto <salvatore.benedetto@intel.com> > --- > crypto/Kconfig | 5 + > crypto/Makefile | 3 + > crypto/ecc.c | 1038 > +++++++++++++++++++++++++++++++++++++++++++++++ crypto/ecc.h | > 70 ++++ > crypto/ecc_curve_defs.h | 57 +++ > crypto/ecdh.c | 171 ++++++++ > crypto/testmgr.c | 136 ++++++- > crypto/testmgr.h | 73 ++++ > include/crypto/ecdh.h | 24 ++ > 9 files changed, 1568 insertions(+), 9 deletions(-) > create mode 100644 crypto/ecc.c > create mode 100644 crypto/ecc.h > create mode 100644 crypto/ecc_curve_defs.h > create mode 100644 crypto/ecdh.c > create mode 100644 include/crypto/ecdh.h > > diff --git a/crypto/Kconfig b/crypto/Kconfig > index 89db25c..08a1a3b 100644 > --- a/crypto/Kconfig > +++ b/crypto/Kconfig > @@ -117,6 +117,11 @@ config CRYPTO_DH > help > Generic implementation of the Diffie-Hellman algorithm. > > +config CRYPTO_ECDH > + tristate "ECDH algorithm" > + select CRYTPO_KPP > + help > + Generic implementation of the ECDH algorithm > > config CRYPTO_MANAGER > tristate "Cryptographic algorithm manager" > diff --git a/crypto/Makefile b/crypto/Makefile > index 101f8fd..ba03079 100644 > --- a/crypto/Makefile > +++ b/crypto/Makefile > @@ -33,6 +33,9 @@ obj-$(CONFIG_CRYPTO_AKCIPHER2) += akcipher.o > obj-$(CONFIG_CRYPTO_KPP2) += kpp.o > > obj-$(CONFIG_CRYPTO_DH) += dh.o > +ecdh_generic-y := ecc.o > +ecdh_generic-y += ecdh.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 > diff --git a/crypto/ecc.c b/crypto/ecc.c > new file mode 100644 > index 0000000..c50f9c8 > --- /dev/null > +++ b/crypto/ecc.c > @@ -0,0 +1,1038 @@ > +/* > + * Copyright (c) 2013, Kenneth MacKay > + * All rights reserved. > + * > + * Redistribution and use in source and binary forms, with or without > + * modification, are permitted provided that the following conditions are > + * met: > + * * Redistributions of source code must retain the above copyright > + * notice, this list of conditions and the following disclaimer. > + * * Redistributions in binary form must reproduce the above copyright > + * notice, this list of conditions and the following disclaimer in the > + * documentation and/or other materials provided with the distribution. > + * > + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS > + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT > + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR > + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT > + * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, > + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT > + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, > + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY > + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT > + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE > + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. > + */ > + > +#include <linux/random.h> > +#include <linux/slab.h> > +#include <linux/swab.h> > +#include <crypto/ecdh.h> > + > +#include "ecc.h" > +#include "ecc_curve_defs.h" > + > +#define MAX_TRIES 16 > + > +typedef struct { > + u64 m_low; > + u64 m_high; > +} uint128_t; > + > +static inline const struct ecc_curve *ecc_get_curve(unsigned int curve_id) > +{ > + switch (curve_id) { > + case ECC_CURVE_NIST_P192: return &nist_p192; > + case ECC_CURVE_NIST_P256: return &nist_p256; > + default: return NULL; > + } > +} > + > +static u64 *ecc_alloc_digits_space(unsigned int ndigits) > +{ > + size_t len = ndigits * sizeof(u64); > + > + if (!len) > + return NULL; > + > + return kmalloc(len, GFP_KERNEL); > +} > + > +static void ecc_free_digits_space(u64 *space) > +{ > + kzfree(space); > +} > + > +static struct ecc_point *ecc_alloc_point(unsigned int ndigits) > +{ > + struct ecc_point *p = kmalloc(sizeof(*p), GFP_KERNEL); > + > + if (!p) > + return NULL; > + > + p->x = ecc_alloc_digits_space(ndigits); > + if (!p->x) > + goto err_alloc_x; > + > + p->y = ecc_alloc_digits_space(ndigits); > + if (!p->y) > + goto err_alloc_y; > + > + p->ndigits = ndigits; > + > + return p; > + > +err_alloc_y: > + ecc_free_digits_space(p->x); > +err_alloc_x: > + kfree(p); > + return NULL; > +} > + > +static void ecc_free_point(struct ecc_point *p) > +{ > + if (!p) > + return; > + > + kzfree(p->x); > + kzfree(p->y); > + kzfree(p); > +} > + > +static void vli_clear(u64 *vli, unsigned int ndigits) > +{ > + int i; > + > + for (i = 0; i < ndigits; i++) > + vli[i] = 0; > +} > + > +/* Returns true if vli == 0, false otherwise. */ > +static bool vli_is_zero(const u64 *vli, unsigned int ndigits) > +{ > + int i; > + > + for (i = 0; i < ndigits; i++) { > + if (vli[i]) > + return false; > + } > + > + return true; > +} > + > +/* Returns nonzero if bit bit of vli is set. */ > +static u64 vli_test_bit(const u64 *vli, unsigned int bit) > +{ > + return (vli[bit / 64] & ((u64)1 << (bit % 64))); > +} > + > +/* Counts the number of 64-bit "digits" in vli. */ > +static unsigned int vli_num_digits(const u64 *vli, unsigned int ndigits) > +{ > + int i; > + > + /* Search from the end until we find a non-zero digit. > + * We do it in reverse because we expect that most digits will > + * be nonzero. > + */ > + for (i = ndigits - 1; i >= 0 && vli[i] == 0; i--); > + > + return (i + 1); > +} > + > +/* Counts the number of bits required for vli. */ > +static unsigned int vli_num_bits(const u64 *vli, unsigned int ndigits) > +{ > + unsigned int i, num_digits; > + u64 digit; > + > + num_digits = vli_num_digits(vli, ndigits); > + if (num_digits == 0) > + return 0; > + > + digit = vli[num_digits - 1]; > + for (i = 0; digit; i++) > + digit >>= 1; > + > + return ((num_digits - 1) * 64 + i); > +} > + > +/* Sets dest = src. */ > +static void vli_set(u64 *dest, const u64 *src, unsigned int ndigits) > +{ > + int i; > + > + for (i = 0; i < ndigits; i++) > + dest[i] = src[i]; > +} > + > +/* Returns sign of left - right. */ > +static int vli_cmp(const u64 *left, const u64 *right, unsigned int ndigits) > +{ > + int i; > + > + for (i = ndigits - 1; i >= 0; i--) { > + if (left[i] > right[i]) > + return 1; > + else if (left[i] < right[i]) > + return -1; > + } > + > + return 0; > +} > + > +/* Computes result = in << c, returning carry. Can modify in place > + * (if result == in). 0 < shift < 64. > + */ > +static u64 vli_lshift(u64 *result, const u64 *in, unsigned int shift, > + unsigned int ndigits) > +{ > + u64 carry = 0; > + int i; > + > + for (i = 0; i < ndigits; i++) { > + u64 temp = in[i]; > + > + result[i] = (temp << shift) | carry; > + carry = temp >> (64 - shift); > + } > + > + return carry; > +} > + > +/* Computes vli = vli >> 1. */ > +static void vli_rshift1(u64 *vli, unsigned int ndigits) > +{ > + u64 *end = vli; > + u64 carry = 0; > + > + vli += ndigits; > + > + while (vli-- > end) { > + u64 temp = *vli; > + *vli = (temp >> 1) | carry; > + carry = temp << 63; > + } > +} > + > +/* Computes result = left + right, returning carry. Can modify in place. */ > +static u64 vli_add(u64 *result, const u64 *left, const u64 *right, + > unsigned int ndigits) > +{ > + u64 carry = 0; > + int i; > + > + for (i = 0; i < ndigits; i++) { > + u64 sum; > + > + sum = left[i] + right[i] + carry; > + if (sum != left[i]) > + carry = (sum < left[i]); > + > + result[i] = sum; > + } > + > + return carry; > +} > + > +/* Computes result = left - right, returning borrow. Can modify in place. > */ +static u64 vli_sub(u64 *result, const u64 *left, const u64 *right, + > unsigned int ndigits) > +{ > + u64 borrow = 0; > + int i; > + > + for (i = 0; i < ndigits; i++) { > + u64 diff; > + > + diff = left[i] - right[i] - borrow; > + if (diff != left[i]) > + borrow = (diff > left[i]); > + > + result[i] = diff; > + } > + > + return borrow; > +} > + > +static uint128_t mul_64_64(u64 left, u64 right) > +{ > + u64 a0 = left & 0xffffffffull; > + u64 a1 = left >> 32; > + u64 b0 = right & 0xffffffffull; > + u64 b1 = right >> 32; > + u64 m0 = a0 * b0; > + u64 m1 = a0 * b1; > + u64 m2 = a1 * b0; > + u64 m3 = a1 * b1; > + uint128_t result; > + > + m2 += (m0 >> 32); > + m2 += m1; > + > + /* Overflow */ > + if (m2 < m1) > + m3 += 0x100000000ull; > + > + result.m_low = (m0 & 0xffffffffull) | (m2 << 32); > + result.m_high = m3 + (m2 >> 32); > + > + return result; > +} > + > +static uint128_t add_128_128(uint128_t a, uint128_t b) > +{ > + uint128_t result; > + > + result.m_low = a.m_low + b.m_low; > + result.m_high = a.m_high + b.m_high + (result.m_low < a.m_low); > + > + return result; > +} > + > +static void vli_mult(u64 *result, const u64 *left, const u64 *right, > + unsigned int ndigits) > +{ > + uint128_t r01 = { 0, 0 }; > + u64 r2 = 0; > + unsigned int i, k; > + > + /* Compute each digit of result in sequence, maintaining the > + * carries. > + */ > + for (k = 0; k < ndigits * 2 - 1; k++) { > + unsigned int min; > + > + if (k < ndigits) > + min = 0; > + else > + min = (k + 1) - ndigits; > + > + for (i = min; i <= k && i < ndigits; i++) { > + uint128_t product; > + > + product = mul_64_64(left[i], right[k - i]); > + > + r01 = add_128_128(r01, product); > + r2 += (r01.m_high < product.m_high); > + } > + > + result[k] = r01.m_low; > + r01.m_low = r01.m_high; > + r01.m_high = r2; > + r2 = 0; > + } > + > + result[ndigits * 2 - 1] = r01.m_low; > +} > + > +static void vli_square(u64 *result, const u64 *left, unsigned int ndigits) > +{ > + uint128_t r01 = { 0, 0 }; > + u64 r2 = 0; > + int i, k; > + > + for (k = 0; k < ndigits * 2 - 1; k++) { > + unsigned int min; > + > + if (k < ndigits) > + min = 0; > + else > + min = (k + 1) - ndigits; > + > + for (i = min; i <= k && i <= k - i; i++) { > + uint128_t product; > + > + product = mul_64_64(left[i], left[k - i]); > + > + if (i < k - i) { > + r2 += product.m_high >> 63; > + product.m_high = (product.m_high << 1) | > + (product.m_low >> 63); > + product.m_low <<= 1; > + } > + > + r01 = add_128_128(r01, product); > + r2 += (r01.m_high < product.m_high); > + } > + > + result[k] = r01.m_low; > + r01.m_low = r01.m_high; > + r01.m_high = r2; > + r2 = 0; > + } > + > + result[ndigits * 2 - 1] = r01.m_low; > +} > + > +/* Computes result = (left + right) % mod. > + * Assumes that left < mod and right < mod, result != mod. > + */ > +static void vli_mod_add(u64 *result, const u64 *left, const u64 *right, > + const u64 *mod, unsigned int ndigits) > +{ > + u64 carry; > + > + carry = vli_add(result, left, right, ndigits); > + > + /* result > mod (result = mod + remainder), so subtract mod to > + * get remainder. > + */ > + if (carry || vli_cmp(result, mod, ndigits) >= 0) > + vli_sub(result, result, mod, ndigits); > +} > + > +/* Computes result = (left - right) % mod. > + * Assumes that left < mod and right < mod, result != mod. > + */ > +static void vli_mod_sub(u64 *result, const u64 *left, const u64 *right, > + const u64 *mod, unsigned int ndigits) > +{ > + u64 borrow = vli_sub(result, left, right, ndigits); > + > + /* In this case, p_result == -diff == (max int) - diff. > + * Since -x % d == d - x, we can get the correct result from > + * result + mod (with overflow). > + */ > + if (borrow) > + vli_add(result, result, mod, ndigits); > +} > + > +/* Computes p_result = p_product % curve_p. > + * See algorithm 5 and 6 from > + * http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf > + */ > +static void vli_mmod_fast_192(u64 *result, const u64 *product, > + const u64 *curve_prime, u64 *tmp) > +{ > + const unsigned int ndigits = 3; > + int carry; > + > + vli_set(result, product, ndigits); > + > + vli_set(tmp, &product[3], ndigits); > + carry = vli_add(result, result, tmp, ndigits); > + > + tmp[0] = 0; > + tmp[1] = product[3]; > + tmp[2] = product[4]; > + carry += vli_add(result, result, tmp, ndigits); > + > + tmp[0] = tmp[1] = product[5]; > + tmp[2] = 0; > + carry += vli_add(result, result, tmp, ndigits); > + > + while (carry || vli_cmp(curve_prime, result, ndigits) != 1) > + carry -= vli_sub(result, result, curve_prime, ndigits); > +} > + > +/* Computes result = product % curve_prime > + * from http://www.nsa.gov/ia/_files/nist-routines.pdf > + */ > +static void vli_mmod_fast_256(u64 *result, const u64 *product, > + const u64 *curve_prime, u64 *tmp) > +{ > + int carry; > + const unsigned int ndigits = 4; > + > + /* t */ > + vli_set(result, product, ndigits); > + > + /* s1 */ > + tmp[0] = 0; > + tmp[1] = product[5] & 0xffffffff00000000ull; > + tmp[2] = product[6]; > + tmp[3] = product[7]; > + carry = vli_lshift(tmp, tmp, 1, ndigits); > + carry += vli_add(result, result, tmp, ndigits); > + > + /* s2 */ > + tmp[1] = product[6] << 32; > + tmp[2] = (product[6] >> 32) | (product[7] << 32); > + tmp[3] = product[7] >> 32; > + carry += vli_lshift(tmp, tmp, 1, ndigits); > + carry += vli_add(result, result, tmp, ndigits); > + > + /* s3 */ > + tmp[0] = product[4]; > + tmp[1] = product[5] & 0xffffffff; > + tmp[2] = 0; > + tmp[3] = product[7]; > + carry += vli_add(result, result, tmp, ndigits); > + > + /* s4 */ > + tmp[0] = (product[4] >> 32) | (product[5] << 32); > + tmp[1] = (product[5] >> 32) | (product[6] & 0xffffffff00000000ull); > + tmp[2] = product[7]; > + tmp[3] = (product[6] >> 32) | (product[4] << 32); > + carry += vli_add(result, result, tmp, ndigits); > + > + /* d1 */ > + tmp[0] = (product[5] >> 32) | (product[6] << 32); > + tmp[1] = (product[6] >> 32); > + tmp[2] = 0; > + tmp[3] = (product[4] & 0xffffffff) | (product[5] << 32); > + carry -= vli_sub(result, result, tmp, ndigits); > + > + /* d2 */ > + tmp[0] = product[6]; > + tmp[1] = product[7]; > + tmp[2] = 0; > + tmp[3] = (product[4] >> 32) | (product[5] & 0xffffffff00000000ull); > + carry -= vli_sub(result, result, tmp, ndigits); > + > + /* d3 */ > + tmp[0] = (product[6] >> 32) | (product[7] << 32); > + tmp[1] = (product[7] >> 32) | (product[4] << 32); > + tmp[2] = (product[4] >> 32) | (product[5] << 32); > + tmp[3] = (product[6] << 32); > + carry -= vli_sub(result, result, tmp, ndigits); > + > + /* d4 */ > + tmp[0] = product[7]; > + tmp[1] = product[4] & 0xffffffff00000000ull; > + tmp[2] = product[5]; > + tmp[3] = product[6] & 0xffffffff00000000ull; > + carry -= vli_sub(result, result, tmp, ndigits); > + > + if (carry < 0) { > + do { > + carry += vli_add(result, result, curve_prime, ndigits); > + } while (carry < 0); > + } else { > + while (carry || vli_cmp(curve_prime, result, ndigits) != 1) > + carry -= vli_sub(result, result, curve_prime, ndigits); > + } > +} > + > +/* Computes result = product % curve_prime > + * from http://www.nsa.gov/ia/_files/nist-routines.pdf > +*/ > +static bool vli_mmod_fast(u64 *result, u64 *product, > + const u64 *curve_prime, unsigned int ndigits) > +{ > + u64 tmp[2 * ndigits]; > + > + switch (ndigits) { > + case 3: > + vli_mmod_fast_192(result, product, curve_prime, tmp); > + break; > + case 4: > + vli_mmod_fast_256(result, product, curve_prime, tmp); > + break; > + default: > + pr_err("unsupports digits size!\n"); > + return false; > + } > + > + return true; > +} > + > +/* Computes result = (left * right) % curve_prime. */ > +static void vli_mod_mult_fast(u64 *result, const u64 *left, const u64 > *right, + const u64 *curve_prime, unsigned int ndigits) > +{ > + u64 product[2 * ndigits]; > + > + vli_mult(product, left, right, ndigits); > + vli_mmod_fast(result, product, curve_prime, ndigits); > +} > + > +/* Computes result = left^2 % curve_prime. */ > +static void vli_mod_square_fast(u64 *result, const u64 *left, > + const u64 *curve_prime, unsigned int ndigits) > +{ > + u64 product[2 * ndigits]; > + > + vli_square(product, left, ndigits); > + vli_mmod_fast(result, product, curve_prime, ndigits); > +} > + > +#define EVEN(vli) (!(vli[0] & 1)) > +/* Computes result = (1 / p_input) % mod. All VLIs are the same size. > + * See "From Euclid's GCD to Montgomery Multiplication to the Great Divide" > + * https://labs.oracle.com/techrep/2001/smli_tr-2001-95.pdf > + */ > +static void vli_mod_inv(u64 *result, const u64 *input, const u64 *mod, > + unsigned int ndigits) > +{ > + u64 a[ndigits], b[ndigits]; > + u64 u[ndigits], v[ndigits]; > + u64 carry; > + int cmp_result; > + > + if (vli_is_zero(input, ndigits)) { > + vli_clear(result, ndigits); > + return; > + } > + > + vli_set(a, input, ndigits); > + vli_set(b, mod, ndigits); > + vli_clear(u, ndigits); > + u[0] = 1; > + vli_clear(v, ndigits); > + > + while ((cmp_result = vli_cmp(a, b, ndigits)) != 0) { > + carry = 0; > + > + if (EVEN(a)) { > + vli_rshift1(a, ndigits); > + > + if (!EVEN(u)) > + carry = vli_add(u, u, mod, ndigits); > + > + vli_rshift1(u, ndigits); > + if (carry) > + u[ndigits - 1] |= 0x8000000000000000ull; > + } else if (EVEN(b)) { > + vli_rshift1(b, ndigits); > + > + if (!EVEN(v)) > + carry = vli_add(v, v, mod, ndigits); > + > + vli_rshift1(v, ndigits); > + if (carry) > + v[ndigits - 1] |= 0x8000000000000000ull; > + } else if (cmp_result > 0) { > + vli_sub(a, a, b, ndigits); > + vli_rshift1(a, ndigits); > + > + if (vli_cmp(u, v, ndigits) < 0) > + vli_add(u, u, mod, ndigits); > + > + vli_sub(u, u, v, ndigits); > + if (!EVEN(u)) > + carry = vli_add(u, u, mod, ndigits); > + > + vli_rshift1(u, ndigits); > + if (carry) > + u[ndigits - 1] |= 0x8000000000000000ull; > + } else { > + vli_sub(b, b, a, ndigits); > + vli_rshift1(b, ndigits); > + > + if (vli_cmp(v, u, ndigits) < 0) > + vli_add(v, v, mod, ndigits); > + > + vli_sub(v, v, u, ndigits); > + if (!EVEN(v)) > + carry = vli_add(v, v, mod, ndigits); > + > + vli_rshift1(v, ndigits); > + if (carry) > + v[ndigits - 1] |= 0x8000000000000000ull; > + } > + } > + > + vli_set(result, u, ndigits); > +} > + > +/* ------ Point operations ------ */ > + > +/* Returns true if p_point is the point at infinity, false otherwise. */ > +static bool ecc_point_is_zero(const struct ecc_point *point) > +{ > + return (vli_is_zero(point->x, point->ndigits) && > + vli_is_zero(point->y, point->ndigits)); > +} > + > +/* Point multiplication algorithm using Montgomery's ladder with co-Z > + * coordinates. From http://eprint.iacr.org/2011/338.pdf > + */ > + > +/* Double in place */ > +static void ecc_point_double_jacobian(u64 *x1, u64 *y1, u64 *z1, > + u64 *curve_prime, unsigned int ndigits) > +{ > + /* t1 = x, t2 = y, t3 = z */ > + u64 t4[ndigits]; > + u64 t5[ndigits]; > + > + if (vli_is_zero(z1, ndigits)) > + return; > + > + /* t4 = y1^2 */ > + vli_mod_square_fast(t4, y1, curve_prime, ndigits); > + /* t5 = x1*y1^2 = A */ > + vli_mod_mult_fast(t5, x1, t4, curve_prime, ndigits); > + /* t4 = y1^4 */ > + vli_mod_square_fast(t4, t4, curve_prime, ndigits); > + /* t2 = y1*z1 = z3 */ > + vli_mod_mult_fast(y1, y1, z1, curve_prime, ndigits); > + /* t3 = z1^2 */ > + vli_mod_square_fast(z1, z1, curve_prime, ndigits); > + > + /* t1 = x1 + z1^2 */ > + vli_mod_add(x1, x1, z1, curve_prime, ndigits); > + /* t3 = 2*z1^2 */ > + vli_mod_add(z1, z1, z1, curve_prime, ndigits); > + /* t3 = x1 - z1^2 */ > + vli_mod_sub(z1, x1, z1, curve_prime, ndigits); > + /* t1 = x1^2 - z1^4 */ > + vli_mod_mult_fast(x1, x1, z1, curve_prime, ndigits); > + > + /* t3 = 2*(x1^2 - z1^4) */ > + vli_mod_add(z1, x1, x1, curve_prime, ndigits); > + /* t1 = 3*(x1^2 - z1^4) */ > + vli_mod_add(x1, x1, z1, curve_prime, ndigits); > + if (vli_test_bit(x1, 0)) { > + u64 carry = vli_add(x1, x1, curve_prime, ndigits); > + > + vli_rshift1(x1, ndigits); > + x1[ndigits - 1] |= carry << 63; > + } else { > + vli_rshift1(x1, ndigits); > + } > + /* t1 = 3/2*(x1^2 - z1^4) = B */ > + > + /* t3 = B^2 */ > + vli_mod_square_fast(z1, x1, curve_prime, ndigits); > + /* t3 = B^2 - A */ > + vli_mod_sub(z1, z1, t5, curve_prime, ndigits); > + /* t3 = B^2 - 2A = x3 */ > + vli_mod_sub(z1, z1, t5, curve_prime, ndigits); > + /* t5 = A - x3 */ > + vli_mod_sub(t5, t5, z1, curve_prime, ndigits); > + /* t1 = B * (A - x3) */ > + vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits); > + /* t4 = B * (A - x3) - y1^4 = y3 */ > + vli_mod_sub(t4, x1, t4, curve_prime, ndigits); > + > + vli_set(x1, z1, ndigits); > + vli_set(z1, y1, ndigits); > + vli_set(y1, t4, ndigits); > +} > + > +/* Modify (x1, y1) => (x1 * z^2, y1 * z^3) */ > +static void apply_z(u64 *x1, u64 *y1, u64 *z, u64 *curve_prime, > + unsigned int ndigits) > +{ > + u64 t1[ndigits]; > + > + vli_mod_square_fast(t1, z, curve_prime, ndigits); /* z^2 */ > + vli_mod_mult_fast(x1, x1, t1, curve_prime, ndigits); /* x1 * z^2 */ > + vli_mod_mult_fast(t1, t1, z, curve_prime, ndigits); /* z^3 */ > + vli_mod_mult_fast(y1, y1, t1, curve_prime, ndigits); /* y1 * z^3 */ > +} > + > +/* P = (x1, y1) => 2P, (x2, y2) => P' */ > +static void xycz_initial_double(u64 *x1, u64 *y1, u64 *x2, u64 *y2, > + u64 *p_initial_z, u64 *curve_prime, > + unsigned int ndigits) > +{ > + u64 z[ndigits]; > + > + vli_set(x2, x1, ndigits); > + vli_set(y2, y1, ndigits); > + > + vli_clear(z, ndigits); > + z[0] = 1; > + > + if (p_initial_z) > + vli_set(z, p_initial_z, ndigits); > + > + apply_z(x1, y1, z, curve_prime, ndigits); > + > + ecc_point_double_jacobian(x1, y1, z, curve_prime, ndigits); > + > + apply_z(x2, y2, z, curve_prime, ndigits); > +} > + > +/* Input P = (x1, y1, Z), Q = (x2, y2, Z) > + * Output P' = (x1', y1', Z3), P + Q = (x3, y3, Z3) > + * or P => P', Q => P + Q > + */ > +static void xycz_add(u64 *x1, u64 *y1, u64 *x2, u64 *y2, u64 *curve_prime, > + unsigned int ndigits) > +{ > + /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */ > + u64 t5[ndigits]; > + > + /* t5 = x2 - x1 */ > + vli_mod_sub(t5, x2, x1, curve_prime, ndigits); > + /* t5 = (x2 - x1)^2 = A */ > + vli_mod_square_fast(t5, t5, curve_prime, ndigits); > + /* t1 = x1*A = B */ > + vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits); > + /* t3 = x2*A = C */ > + vli_mod_mult_fast(x2, x2, t5, curve_prime, ndigits); > + /* t4 = y2 - y1 */ > + vli_mod_sub(y2, y2, y1, curve_prime, ndigits); > + /* t5 = (y2 - y1)^2 = D */ > + vli_mod_square_fast(t5, y2, curve_prime, ndigits); > + > + /* t5 = D - B */ > + vli_mod_sub(t5, t5, x1, curve_prime, ndigits); > + /* t5 = D - B - C = x3 */ > + vli_mod_sub(t5, t5, x2, curve_prime, ndigits); > + /* t3 = C - B */ > + vli_mod_sub(x2, x2, x1, curve_prime, ndigits); > + /* t2 = y1*(C - B) */ > + vli_mod_mult_fast(y1, y1, x2, curve_prime, ndigits); > + /* t3 = B - x3 */ > + vli_mod_sub(x2, x1, t5, curve_prime, ndigits); > + /* t4 = (y2 - y1)*(B - x3) */ > + vli_mod_mult_fast(y2, y2, x2, curve_prime, ndigits); > + /* t4 = y3 */ > + vli_mod_sub(y2, y2, y1, curve_prime, ndigits); > + > + vli_set(x2, t5, ndigits); > +} > + > +/* Input P = (x1, y1, Z), Q = (x2, y2, Z) > + * Output P + Q = (x3, y3, Z3), P - Q = (x3', y3', Z3) > + * or P => P - Q, Q => P + Q > + */ > +static void xycz_add_c(u64 *x1, u64 *y1, u64 *x2, u64 *y2, u64 > *curve_prime, + unsigned int ndigits) > +{ > + /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */ > + u64 t5[ndigits]; > + u64 t6[ndigits]; > + u64 t7[ndigits]; > + > + /* t5 = x2 - x1 */ > + vli_mod_sub(t5, x2, x1, curve_prime, ndigits); > + /* t5 = (x2 - x1)^2 = A */ > + vli_mod_square_fast(t5, t5, curve_prime, ndigits); > + /* t1 = x1*A = B */ > + vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits); > + /* t3 = x2*A = C */ > + vli_mod_mult_fast(x2, x2, t5, curve_prime, ndigits); > + /* t4 = y2 + y1 */ > + vli_mod_add(t5, y2, y1, curve_prime, ndigits); > + /* t4 = y2 - y1 */ > + vli_mod_sub(y2, y2, y1, curve_prime, ndigits); > + > + /* t6 = C - B */ > + vli_mod_sub(t6, x2, x1, curve_prime, ndigits); > + /* t2 = y1 * (C - B) */ > + vli_mod_mult_fast(y1, y1, t6, curve_prime, ndigits); > + /* t6 = B + C */ > + vli_mod_add(t6, x1, x2, curve_prime, ndigits); > + /* t3 = (y2 - y1)^2 */ > + vli_mod_square_fast(x2, y2, curve_prime, ndigits); > + /* t3 = x3 */ > + vli_mod_sub(x2, x2, t6, curve_prime, ndigits); > + > + /* t7 = B - x3 */ > + vli_mod_sub(t7, x1, x2, curve_prime, ndigits); > + /* t4 = (y2 - y1)*(B - x3) */ > + vli_mod_mult_fast(y2, y2, t7, curve_prime, ndigits); > + /* t4 = y3 */ > + vli_mod_sub(y2, y2, y1, curve_prime, ndigits); > + > + /* t7 = (y2 + y1)^2 = F */ > + vli_mod_square_fast(t7, t5, curve_prime, ndigits); > + /* t7 = x3' */ > + vli_mod_sub(t7, t7, t6, curve_prime, ndigits); > + /* t6 = x3' - B */ > + vli_mod_sub(t6, t7, x1, curve_prime, ndigits); > + /* t6 = (y2 + y1)*(x3' - B) */ > + vli_mod_mult_fast(t6, t6, t5, curve_prime, ndigits); > + /* t2 = y3' */ > + vli_mod_sub(y1, t6, y1, curve_prime, ndigits); > + > + vli_set(x1, t7, ndigits); > +} > + > +static void ecc_point_mult(struct ecc_point *result, > + const struct ecc_point *point, const u64 *scalar, > + u64 *initial_z, u64 *curve_prime, > + unsigned int ndigits) > +{ > + /* R0 and R1 */ > + u64 rx[2][ndigits]; > + u64 ry[2][ndigits]; > + u64 z[ndigits]; > + int i, nb; > + int num_bits = vli_num_bits(scalar, ndigits); > + > + vli_set(rx[1], point->x, ndigits); > + vli_set(ry[1], point->y, ndigits); > + > + xycz_initial_double(rx[1], ry[1], rx[0], ry[0], initial_z, curve_prime, > + ndigits); > + > + for (i = num_bits - 2; i > 0; i--) { > + nb = !vli_test_bit(scalar, i); > + xycz_add_c(rx[1 - nb], ry[1 - nb], rx[nb], ry[nb], curve_prime, > + ndigits); > + xycz_add(rx[nb], ry[nb], rx[1 - nb], ry[1 - nb], curve_prime, > + ndigits); > + } > + > + nb = !vli_test_bit(scalar, 0); > + xycz_add_c(rx[1 - nb], ry[1 - nb], rx[nb], ry[nb], curve_prime, > + ndigits); > + > + /* Find final 1/Z value. */ > + /* X1 - X0 */ > + vli_mod_sub(z, rx[1], rx[0], curve_prime, ndigits); > + /* Yb * (X1 - X0) */ > + vli_mod_mult_fast(z, z, ry[1 - nb], curve_prime, ndigits); > + /* xP * Yb * (X1 - X0) */ > + vli_mod_mult_fast(z, z, point->x, curve_prime, ndigits); > + > + /* 1 / (xP * Yb * (X1 - X0)) */ > + vli_mod_inv(z, z, curve_prime, point->ndigits); > + > + /* yP / (xP * Yb * (X1 - X0)) */ > + vli_mod_mult_fast(z, z, point->y, curve_prime, ndigits); > + /* Xb * yP / (xP * Yb * (X1 - X0)) */ > + vli_mod_mult_fast(z, z, rx[1 - nb], curve_prime, ndigits); > + /* End 1/Z calculation */ > + > + xycz_add(rx[nb], ry[nb], rx[1 - nb], ry[1 - nb], curve_prime, ndigits); > + > + apply_z(rx[0], ry[0], z, curve_prime, ndigits); > + > + vli_set(result->x, rx[0], ndigits); > + vli_set(result->y, ry[0], ndigits); > +} > + > +static inline void ecc_swap_digits(const u64 *in, u64 *out, > + unsigned int ndigits) > +{ > + int i; > + > + for (i = 0; i < ndigits; i++) > + out[i] = __swab64(in[ndigits - 1 - i]); > +} > + > +int ecdh_make_pub_key(unsigned int curve_id, > + const u8 *private_key, unsigned int private_key_len, > + u8 *public_key, unsigned int public_key_len) > +{ > + int ret = 0; > + struct ecc_point *pk; > + unsigned int tries = 0; > + u64 *priv = NULL; > + unsigned int ndigits; > + unsigned int nbytes; > + const struct ecc_curve *curve = ecc_get_curve(curve_id); > + > + if (!private_key || !curve) { > + ret = -EINVAL; > + goto out; > + } > + > + ndigits = curve->g.ndigits; > + nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT; > + > + if (private_key_len != nbytes) { > + ret = -EINVAL; > + goto out; > + } > + > + if (vli_is_zero((const u64 *)&private_key[0], ndigits)) { > + ret = -EINVAL; > + goto out; > + } > + > + /* Make sure the private key is in the range [1, n-1]. */ > + if (vli_cmp(curve->n, (const u64 *)&private_key[0], ndigits) != 1) { > + ret = -EINVAL; > + goto out; > + } > + > + priv = ecc_alloc_digits_space(ndigits); > + if (!priv) { > + ret = -ENOMEM; > + goto out; > + } > + > + ecc_swap_digits((const u64 *)private_key, priv, ndigits); > + > + pk = ecc_alloc_point(ndigits); > + if (!pk) { > + ret = -ENOMEM; > + goto err_alloc_pk; > + } > + > + do { > + if (tries++ >= MAX_TRIES) > + goto err_retries; > + > + ecc_point_mult(pk, &curve->g, priv, NULL, curve->p, ndigits); > + > + } while (ecc_point_is_zero(pk)); > + > + ecc_swap_digits(pk->x, (u64 *)public_key, ndigits); > + ecc_swap_digits(pk->y, (u64 *)&public_key[nbytes], ndigits); > + > +err_retries: > + ecc_free_point(pk); > +err_alloc_pk: > + ecc_free_digits_space(priv); > +out: > + return ret; > +} > + > +int ecdh_shared_secret(unsigned int curve_id, > + const u8 *private_key, unsigned int private_key_len, > + const u8 *public_key, unsigned int public_key_len, > + u8 *secret, unsigned int secret_len) > +{ > + int ret = 0; > + struct ecc_point *product, *pk; > + u64 *priv, *rand_z; > + unsigned int ndigits; > + unsigned int nbytes; > + const struct ecc_curve *curve = ecc_get_curve(curve_id); > + > + if (!private_key || !public_key) { > + ret = -EINVAL; > + goto out; > + } > + > + ndigits = curve->g.ndigits; > + nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT; > + > + rand_z = ecc_alloc_digits_space(ndigits); > + if (!rand_z) { > + ret = -ENOMEM; > + goto out; > + } > + > + priv = ecc_alloc_digits_space(ndigits); > + if (!priv) { > + ret = -ENOMEM; > + goto err_alloc_priv; > + } > + > + get_random_bytes(rand_z, nbytes); > + > + pk = ecc_alloc_point(ndigits); > + if (!pk) { > + ret = -ENOMEM; > + goto err_alloc_pk; > + } > + > + product = ecc_alloc_point(ndigits); > + if (!product) { > + ret = -ENOMEM; > + goto err_alloc_product; > + } > + > + ecc_swap_digits((const u64 *)public_key, pk->x, ndigits); > + ecc_swap_digits((const u64 *)&public_key[nbytes], pk->y, ndigits); > + ecc_swap_digits((const u64 *)private_key, priv, ndigits); > + > + ecc_point_mult(product, pk, priv, rand_z, curve->p, ndigits); > + > + ecc_swap_digits(product->x, (u64 *)secret, ndigits); > + > + if (ecc_point_is_zero(product)) > + ret = -EFAULT; > + > + ecc_free_point(product); > +err_alloc_product: > + ecc_free_point(pk); > +err_alloc_pk: > + ecc_free_digits_space(priv); > +err_alloc_priv: > + ecc_free_digits_space(rand_z); > +out: > + return ret; > +} > diff --git a/crypto/ecc.h b/crypto/ecc.h > new file mode 100644 > index 0000000..7889410 > --- /dev/null > +++ b/crypto/ecc.h > @@ -0,0 +1,70 @@ > +/* > + * Copyright (c) 2013, Kenneth MacKay > + * All rights reserved. > + * > + * Redistribution and use in source and binary forms, with or without > + * modification, are permitted provided that the following conditions are > + * met: > + * * Redistributions of source code must retain the above copyright > + * notice, this list of conditions and the following disclaimer. > + * * Redistributions in binary form must reproduce the above copyright > + * notice, this list of conditions and the following disclaimer in the > + * documentation and/or other materials provided with the distribution. > + * > + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS > + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT > + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR > + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT > + * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, > + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT > + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, > + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY > + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT > + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE > + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. > + */ > +#ifndef _CRYPTO_ECC_H > +#define _CRYPTO_ECC_H > + > +#define ECC_MAX_DIGITS 4 /* 256 */ > + > +#define ECC_DIGITS_TO_BYTES_SHIFT 3 > + > +/** > + * ecdh_make_pub_key() - Compute an ECC public key > + * > + * @curve_id: id representing the curve to use > + * @private_key: pregenerated private key for the given curve > + * @private_key_len: length of private_key > + * @public_key: buffer for storing the public key generated > + * @public_key_len: length of the public_key buffer > + * > + * Returns 0 if the public key was generated successfully, a negative value > + * if an error occurred. > + */ > +int ecdh_make_pub_key(const unsigned int curve_id, > + const u8 *private_key, unsigned int private_key_len, > + u8 *public_key, unsigned int public_key_len); > + > +/** > + * ecdh_shared_secret() - Compute a shared secret > + * > + * @curve_id: id representing the curve to use > + * @private_key: private key of part A > + * @private_key_len: length of private_key > + * @public_key: public key of counterpart B > + * @public_key_len: length of public_key > + * @secret: buffer for storing the calculated shared secret > + * @secret_len: length of the secret buffer > + * > + * Note: It is recommended that you hash the result of ecdh_shared_secret > + * before using it for symmetric encryption or HMAC. > + * > + * Returns 0 if the shared secret was generated successfully, a negative > value + * if an error occurred. > + */ > +int ecdh_shared_secret(unsigned int curve_id, > + const u8 *private_key, unsigned int private_key_len, > + const u8 *public_key, unsigned int public_key_len, > + u8 *secret, unsigned int secret_len); > +#endif > diff --git a/crypto/ecc_curve_defs.h b/crypto/ecc_curve_defs.h > new file mode 100644 > index 0000000..03ae5f7 > --- /dev/null > +++ b/crypto/ecc_curve_defs.h > @@ -0,0 +1,57 @@ > +#ifndef _CRYTO_ECC_CURVE_DEFS_H > +#define _CRYTO_ECC_CURVE_DEFS_H > + > +struct ecc_point { > + u64 *x; > + u64 *y; > + u8 ndigits; > +}; > + > +struct ecc_curve { > + char *name; > + struct ecc_point g; > + u64 *p; > + u64 *n; > +}; > + > +/* NIST P-192 */ > +static u64 nist_p192_g_x[] = { 0xF4FF0AFD82FF1012ull, > 0x7CBF20EB43A18800ull, + 0x188DA80EB03090F6ull }; > +static u64 nist_p192_g_y[] = { 0x73F977A11E794811ull, > 0x631011ED6B24CDD5ull, + 0x07192B95FFC8DA78ull }; > +static u64 nist_p192_p[] = { 0xFFFFFFFFFFFFFFFFull, 0xFFFFFFFFFFFFFFFEull, > + 0xFFFFFFFFFFFFFFFFull }; > +static u64 nist_p192_n[] = { 0x146BC9B1B4D22831ull, 0xFFFFFFFF99DEF836ull, > + 0xFFFFFFFFFFFFFFFFull }; > +static struct ecc_curve nist_p192 = { > + .name = "nist_192", > + .g = { > + .x = nist_p192_g_x, > + .y = nist_p192_g_y, > + .ndigits = 3, > + }, > + .p = nist_p192_p, > + .n = nist_p192_n > +}; > + > +/* NIST P-256 */ > +static u64 nist_p256_g_x[] = { 0xF4A13945D898C296ull, > 0x77037D812DEB33A0ull, + 0xF8BCE6E563A440F2ull, 0x6B17D1F2E12C4247ull }; > +static u64 nist_p256_g_y[] = { 0xCBB6406837BF51F5ull, > 0x2BCE33576B315ECEull, + 0x8EE7EB4A7C0F9E16ull, 0x4FE342E2FE1A7F9Bull }; > +static u64 nist_p256_p[] = { 0xFFFFFFFFFFFFFFFFull, 0x00000000FFFFFFFFull, > + 0x0000000000000000ull, 0xFFFFFFFF00000001ull }; > +static u64 nist_p256_n[] = { 0xF3B9CAC2FC632551ull, 0xBCE6FAADA7179E84ull, > + 0xFFFFFFFFFFFFFFFFull, 0xFFFFFFFF00000000ull }; > +static struct ecc_curve nist_p256 = { > + .name = "nist_256", > + .g = { > + .x = nist_p256_g_x, > + .y = nist_p256_g_y, > + .ndigits = 4, > + }, > + .p = nist_p256_p, > + .n = nist_p256_n > +}; > + > +#endif > diff --git a/crypto/ecdh.c b/crypto/ecdh.c > new file mode 100644 > index 0000000..828aa14 > --- /dev/null > +++ b/crypto/ecdh.c > @@ -0,0 +1,171 @@ > +/* ECDH key-agreement protocol > + * > + * Copyright (c) 2016, Intel Corporation > + * Authors: Salvator Benedetto <salvatore.benedetto@intel.com> > + * > + * This program is free software; you can redistribute it and/or > + * modify it under the terms of the GNU General Public Licence > + * as published by the Free Software Foundation; either version > + * 2 of the Licence, or (at your option) any later version. > + */ > + > +#include <linux/module.h> > +#include <crypto/internal/kpp.h> > +#include <crypto/kpp.h> > +#include <crypto/ecdh.h> > +#include <linux/scatterlist.h> > +#include "ecc.h" > + > +struct ecdh_ctx { > + unsigned int curve_id; > + unsigned int ndigits; > + u64 private_key[ECC_MAX_DIGITS]; > + u64 public_key[2 * ECC_MAX_DIGITS]; > + u64 shared_secret[ECC_MAX_DIGITS]; > +}; > + > +static inline struct ecdh_ctx *ecdh_get_ctx(struct crypto_kpp *tfm) > +{ > + return kpp_tfm_ctx(tfm); > +} > + > +static unsigned int ecdh_supported_curve(unsigned int curve_id) > +{ > + switch (curve_id) { > + case ECC_CURVE_NIST_P192: return 3; > + case ECC_CURVE_NIST_P256: return 4; Sorry for the late review: As we have fips_allowed=1 for the entire system, I would ask for a change here: Only allow P256 in FIPS mode (or P384 or P521). All other curves are not supported in FIPS mode. > + default: return 0; > + } > +} > + > +static int ecdh_set_params(struct crypto_kpp *tfm, void *buffer, > + unsigned int len) > +{ > + struct ecdh_ctx *ctx = ecdh_get_ctx(tfm); > + struct ecdh_params *params = (struct ecdh_params *)buffer; > + > + if (unlikely(!buffer || !len)) > + return -EINVAL; > + > + ctx->ndigits = ecdh_supported_curve(params->curve_id); > + if (unlikely(!ctx->ndigits)) > + return -EINVAL; > + > + ctx->curve_id = params->curve_id; > + > + return 0; > +} > + > +static int ecdh_set_secret(struct crypto_kpp *tfm, void *buffer, > + unsigned int len) > +{ > + struct ecdh_ctx *ctx = ecdh_get_ctx(tfm); > + > + if (unlikely(!buffer || !len)) > + return -EINVAL; > + > + if (unlikely(ctx->ndigits != (len >> ECC_DIGITS_TO_BYTES_SHIFT))) > + return -EINVAL; > + > + memcpy(ctx->private_key, buffer, len); > + > + return 0; > +} > + > +static int ecdh_generate_public_key(struct kpp_request *req) > +{ > + int ret = 0; > + struct crypto_kpp *tfm = crypto_kpp_reqtfm(req); > + const struct ecdh_ctx *ctx = ecdh_get_ctx(tfm); > + size_t copied, nbytes; > + > + nbytes = ctx->ndigits << ECC_DIGITS_TO_BYTES_SHIFT; > + > + ret = ecdh_make_pub_key(ctx->curve_id, > + (const u8 *)ctx->private_key, nbytes, > + (u8 *)ctx->public_key, sizeof(ctx- >public_key)); > + if (ret < 0) > + return ret; > + > + /* Public part is a point thus it has both coordinates */ > + copied = sg_copy_from_buffer(req->dst, 1, ctx->public_key, > + nbytes * 2); > + > + if (copied != 2 * nbytes) > + return -EINVAL; > + > + return ret; > +} > + > +static int ecdh_compute_shared_secret(struct kpp_request *req) > +{ > + int ret = 0; > + struct crypto_kpp *tfm = crypto_kpp_reqtfm(req); > + struct ecdh_ctx *ctx = ecdh_get_ctx(tfm); > + size_t copied, nbytes; > + > + nbytes = ctx->ndigits << ECC_DIGITS_TO_BYTES_SHIFT; > + > + copied = sg_copy_to_buffer(req->src, 1, ctx->public_key, 2 * nbytes); > + if (copied != 2 * nbytes) > + return -EINVAL; > + > + ret = ecdh_shared_secret(ctx->curve_id, > + (const u8 *)ctx->private_key, nbytes, > + (const u8 *)ctx->public_key, 2 * nbytes, > + (u8 *)ctx->shared_secret, nbytes); > + if (ret < 0) > + return ret; > + > + copied = sg_copy_from_buffer(req->dst, 1, ctx->shared_secret, nbytes); > + if (copied != nbytes) > + return -EINVAL; > + > + return ret; > +} > + > +static int ecdh_max_size(struct crypto_kpp *tfm) > +{ > + struct ecdh_ctx *ctx = ecdh_get_ctx(tfm); > + int nbytes = ctx->ndigits << ECC_DIGITS_TO_BYTES_SHIFT; > + > + /* Public key is made of two coordinates */ > + return 2 * nbytes; > +} > + > +static void no_exit_tfm(struct crypto_kpp *tfm) > +{ > + return; > +} > + > +static struct kpp_alg ecdh = { > + .set_params = ecdh_set_params, > + .set_secret = ecdh_set_secret, > + .generate_public_key = ecdh_generate_public_key, > + .compute_shared_secret = ecdh_compute_shared_secret, > + .max_size = ecdh_max_size, > + .exit = no_exit_tfm, > + .base = { > + .cra_name = "ecdh", > + .cra_driver_name = "ecdh-generic", > + .cra_priority = 100, > + .cra_module = THIS_MODULE, > + .cra_ctxsize = sizeof(struct ecdh_ctx), > + }, > +}; > + > +static int ecdh_init(void) > +{ > + return crypto_register_kpp(&ecdh); > +} > + > +static void ecdh_exit(void) > +{ > + crypto_unregister_kpp(&ecdh); > +} > + > +module_init(ecdh_init); > +module_exit(ecdh_exit); > +MODULE_ALIAS_CRYPTO("ecdh"); > +MODULE_LICENSE("GPL"); > +MODULE_DESCRIPTION("ECDH generic algorithm"); > diff --git a/crypto/testmgr.c b/crypto/testmgr.c > index d68fa58..6d7b30c 100644 > --- a/crypto/testmgr.c > +++ b/crypto/testmgr.c > @@ -34,6 +34,7 @@ > #include <crypto/akcipher.h> > #include <crypto/kpp.h> > #include <crypto/dh.h> > +#include <crypto/ecdh.h> > > #include "internal.h" > > @@ -119,7 +120,10 @@ struct akcipher_test_suite { > }; > > struct kpp_test_suite { > - struct kpp_testvec_dh *vecs; > + union { > + struct kpp_testvec_dh *dh; > + struct kpp_testvec_ecdh *ecdh; > + } vecs; > unsigned int count; > }; > > @@ -1891,12 +1895,113 @@ static int test_dh(struct crypto_kpp *tfm, struct > kpp_testvec_dh *vecs, return 0; > } > > -static int test_kpp(struct crypto_kpp *tfm, const char *alg, > - struct kpp_testvec_dh *vecs, unsigned int tcount) > +static int do_test_ecdh(struct crypto_kpp *tfm, struct kpp_testvec_ecdh > *vec) +{ > + struct kpp_request *req; > + void *input_buf = NULL; > + void *output_buf = NULL; > + struct tcrypt_result result; > + unsigned int out_len_max; > + int err = -ENOMEM; > + struct scatterlist src, dst; > + struct ecdh_params p; > + unsigned int nbytes = vec->ndigits << ECC_DIGITS_TO_BYTES_SHIFT; > + > + req = kpp_request_alloc(tfm, GFP_KERNEL); > + if (!req) > + return err; > + > + init_completion(&result.completion); > + > + /* Set curve_id */ > + p.curve_id = vec->curve_id; > + err = crypto_kpp_set_params(tfm, (void *)&p, sizeof(p)); > + if (err) > + goto free_req; > + > + /* Set A private Key */ > + err = crypto_kpp_set_secret(tfm, vec->private_a, nbytes); > + if (err) > + goto free_req; > + > + out_len_max = crypto_kpp_maxsize(tfm); > + output_buf = kzalloc(out_len_max, GFP_KERNEL); > + if (!output_buf) { > + err = -ENOMEM; > + goto free_req; > + } > + > + sg_init_one(&dst, output_buf, out_len_max); > + kpp_request_set_output(req, &dst, out_len_max); > + kpp_request_set_callback(req, CRYPTO_TFM_REQ_MAY_BACKLOG, > + tcrypt_complete, &result); > + > + /* Compute A public key = aG mod p */ > + err = wait_async_op(&result, crypto_kpp_generate_public_key(req)); > + if (err) { > + pr_err("alg: ecdh: generate public key test failed. err %d\n", > + err); > + goto free_output; > + } > + /* Verify calculated public key */ > + if (memcmp(vec->expected_pub_a, sg_virt(req->dst), 2 * nbytes)) { > + pr_err("alg: ecdh: generate public key test failed. Invalid output\n"); > + err = -EINVAL; > + goto free_output; > + } > + > + /* Calculate shared secret key by using counter part public key. */ > + input_buf = kzalloc(2 * nbytes, GFP_KERNEL); > + if (!input_buf) { > + err = -ENOMEM; > + goto free_output; > + } > + > + memcpy(input_buf, vec->public_b, 2 * nbytes); > + sg_init_one(&src, input_buf, 2 * nbytes); > + sg_init_one(&dst, output_buf, out_len_max); > + kpp_request_set_input(req, &src, 2 * nbytes); > + 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: ecdh: compute shard secret test failed. err %d\n", > + err); > + goto free_all; > + } > + > + /* > + * 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), nbytes)) { > + pr_err("alg: ecdh: compute shared secret test failed. Invalid output\n"); > + err = -EINVAL; > + } > + > +free_all: > + kfree(input_buf); > +free_output: > + kfree(output_buf); > +free_req: > + kpp_request_free(req); > + return err; > +} > + > +static int test_ecdh(struct crypto_kpp *tfm, struct kpp_testvec_ecdh *vecs, > + unsigned int tcount) > { > - if (strncmp(alg, "dh", 2) == 0) > - return test_dh(tfm, vecs, tcount); > + int ret, i; > > + for (i = 0; i < tcount; i++) { > + ret = do_test_ecdh(tfm, vecs++); > + if (ret) { > + pr_err("alg: ecdh: test failed on vector %d, err=%d\n", > + i + 1, ret); > + return ret; > + } > + } > return 0; > } > > @@ -1912,9 +2017,12 @@ static int alg_test_kpp(const struct alg_test_desc > *desc, const char *driver, driver, PTR_ERR(tfm)); > return PTR_ERR(tfm); > } > - if (desc->suite.kpp.vecs) > - err = test_kpp(tfm, desc->alg, desc->suite.kpp.vecs, > - desc->suite.kpp.count); > + if (!strncmp(desc->alg, "dh", 2) && desc->suite.kpp.vecs.dh) > + err = test_dh(tfm, desc->suite.kpp.vecs.dh, > + desc->suite.kpp.count); > + else if (!strncmp(desc->alg, "ecdh", 4) && desc->suite.kpp.vecs.ecdh) > + err = test_ecdh(tfm, desc->suite.kpp.vecs.ecdh, > + desc->suite.kpp.count); > > crypto_free_kpp(tfm); > return err; > @@ -2860,7 +2968,7 @@ static const struct alg_test_desc alg_test_descs[] = { > .fips_allowed = 1, > .suite = { > .kpp = { > - .vecs = dh_tv_template, > + .vecs.dh = dh_tv_template, > .count = DH_TEST_VECTORS > } > } > @@ -3293,6 +3401,16 @@ static const struct alg_test_desc alg_test_descs[] = > { } > } > }, { > + .alg = "ecdh", > + .test = alg_test_kpp, > + .fips_allowed = 1, > + .suite = { > + .kpp = { > + .vecs.ecdh = ecdh_tv_template, > + .count = ECDH_TEST_VECTORS > + } > + } > + }, { > .alg = "gcm(aes)", > .test = alg_test_aead, > .fips_allowed = 1, > diff --git a/crypto/testmgr.h b/crypto/testmgr.h > index e9c34c7..74b3080 100644 > --- a/crypto/testmgr.h > +++ b/crypto/testmgr.h > @@ -26,6 +26,8 @@ > > #include <linux/netlink.h> > > +#include "ecc.h" > + > #define MAX_DIGEST_SIZE 64 > #define MAX_TAP 8 > > @@ -148,6 +150,15 @@ struct kpp_testvec_dh { > unsigned short expected_ss_size; > }; > > +struct kpp_testvec_ecdh { > + unsigned int curve_id; > + char *private_a; > + char *expected_pub_a; > + char *public_b; > + char *expected_ss; > + unsigned short ndigits; > +}; > + > static char zeroed_string[48]; > > /* > @@ -538,6 +549,68 @@ struct kpp_testvec_dh dh_tv_template[] = { > } > }; > > +#define ECDH_TEST_VECTORS 2 > + > +struct kpp_testvec_ecdh ecdh_tv_template[] = { > + { > + .curve_id = ECC_CURVE_NIST_P192, > + .private_a = > + "\xb5\x05\xb1\x71\x1e\xbf\x8c\xda" > + "\x4e\x19\x1e\x62\x1f\x23\x23\x31" > + "\x36\x1e\xd3\x84\x2f\xcc\x21\x72", > + .expected_pub_a = > + "\x1a\x04\xdb\xa5\xe1\xdd\x4e\x79" > + "\xa3\xe6\xef\x0e\x5c\x80\x49\x85" > + "\xfa\x78\xb4\xef\x49\xbd\x4c\x7c" > + "\x22\x90\x21\x02\xf9\x1b\x81\x5d" > + "\x0c\x8a\xa8\x98\xd6\x27\x69\x88" > + "\x5e\xbc\x94\xd8\x15\x9e\x21\xce", > + .public_b = > + "\xc3\xba\x67\x4b\x71\xec\xd0\x76" > + "\x7a\x99\x75\x64\x36\x13\x9a\x94" > + "\x5d\x8b\xdc\x60\x90\x91\xfd\x3f" > + "\xb0\x1f\x8a\x0a\x68\xc6\x88\x6e" > + "\x83\x87\xdd\x67\x09\xf8\x8d\x96" > + "\x07\xd6\xbd\x1c\xe6\x8d\x9d\x67", > + .expected_ss = > + "\xf4\x57\xcc\x4f\x1f\x4e\x31\xcc" > + "\xe3\x40\x60\xc8\x06\x93\xc6\x2e" > + "\x99\x80\x81\x28\xaf\xc5\x51\x74", > + .ndigits = 3, > + }, { > + .curve_id = ECC_CURVE_NIST_P256, > + .private_a = > + "\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", > + .expected_pub_a = > + "\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", > + .public_b = > + "\xcc\xb4\xda\x74\xb1\x47\x3f\xea" > + "\x6c\x70\x9e\x38\x2d\xc7\xaa\xb7" > + "\x29\xb2\x47\x03\x19\xab\xdd\x34" > + "\xbd\xa8\x2c\x93\xe1\xa4\x74\xd9" > + "\x64\x63\xf7\x70\x20\x2f\xa4\xe6" > + "\x9f\x4a\x38\xcc\xc0\x2c\x49\x2f" > + "\xb1\x32\xbb\xaf\x22\x61\xda\xcb" > + "\x6f\xdb\xa9\xaa\xfc\x77\x81\xf3", > + .expected_ss = > + "\xea\x17\x6f\x7e\x6e\x57\x26\x38" > + "\x8b\xfb\x41\xeb\xba\xc8\x6d\xa5" > + "\xa8\x72\xd1\xff\xc9\x47\x3d\xaa" > + "\x58\x43\x9f\x34\x0f\x8c\xf3\xc9", > + .ndigits = 4, > + } > +}; > + > /* > * MD4 test vectors from RFC1320 > */ > diff --git a/include/crypto/ecdh.h b/include/crypto/ecdh.h > new file mode 100644 > index 0000000..438214b > --- /dev/null > +++ b/include/crypto/ecdh.h > @@ -0,0 +1,24 @@ > +/* > + * ECDH params to be used with kpp API > + * > + * Copyright (c) 2016, Intel Corporation > + * Authors: Salvatore Benedetto <salvatore.benedetto@intel.com> > + * > + * This program is free software; you can redistribute it and/or modify it > + * under the terms of 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. > + * > + */ > +#ifndef _CRYPTO_ECDH_ > +#define _CRYPTO_ECDH_ > + > +/* Curves IDs */ > +#define ECC_CURVE_NIST_P192 0x0001 > +#define ECC_CURVE_NIST_P256 0x0002 > + > +struct ecdh_params { > + unsigned int curve_id; > +}; > + > +#endif Ciao Stephan ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2016-05-06 14:50 UTC | newest] Thread overview: 5+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2016-05-05 9:17 [PATCH 0/3 v4] Key-agreement Protocol Primitives (KPP) API Salvatore Benedetto 2016-05-05 9:17 ` [PATCH 1/3 v4] crypto: Key-agreement Protocol Primitives API (KPP) Salvatore Benedetto 2016-05-05 9:17 ` [PATCH 2/3 v4] crypto: kpp - Add DH software implementation Salvatore Benedetto 2016-05-05 9:17 ` [PATCH 3/3 v4] crypto: kpp - Add ECDH software support Salvatore Benedetto 2016-05-06 12:02 ` Stephan Mueller
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox