Add support for NIST P521 to ecdsa and ecdh
Subsystems (5)
Stefan Berger
reviewercover Add support for NIST P521 to ecdsa and ecdh
This series of patches adds support for NIST P521 curve to ecdsa and ecdh. Test cases are added to both modules.
An issue with the current code in ecdsa and ecdh is that it assumes that input arrays providing key coordinates for example are arrays of digits (a 'digit' is a 'u64'). This works well for existing curves, such as NIST P192/256/384, but does not work for NIST P521 where coordinates are 8 digits + 2 bytes long. So some of the changes deal with converting byte arrays to digits and digits to byte array.
Regards,
Stefan
Stefan Berger (14):
crypto: ecdsa - Convert byte arrays with key coordinates to digits
crypto: ecdsa - Adjust tests on length of key material
crypto: ecdsa - Adjust res.x mod n for NIST P521
crypto: ecc - Implement vli_mmod_fast_521 for NIST p521
crypto: ecc - For NIST P521 use vli_num_bits to get number of bits
crypto: ecc - Add NIST P521 curve parameters
crypto: ecdsa - Register NIST P521 and extend test suite
x509: Add OID for NIST P521 and extend parser for it
crypto: ecdh - Use properly formatted digits to check for valid key
crypto: ecc - Implement ecc_digits_to_array to convert digits to byte
array
crypto: Add nbits field to ecc_curve structure
crypto: ecc - Implement and use ecc_curve_get_nbytes to get curve's
nbytes
crypto: ecdh - Use functions to copy digits from and to array
crypto: ecdh - Add support for NIST P521 and add test case
crypto/asymmetric_keys/x509_cert_parser.c | 3 + crypto/ecc.c | 71 +++++-- crypto/ecc_curve_defs.h | 45 +++++ crypto/ecdh.c | 59 +++++- crypto/ecdsa.c | 51 ++++- crypto/testmgr.c | 14 ++ crypto/testmgr.h | 225 ++++++++++++++++++++++ include/crypto/ecc_curve.h | 3 + include/crypto/ecdh.h | 1 + include/crypto/internal/ecc.h | 61 +++++- include/linux/oid_registry.h | 1 + 11 files changed, 497 insertions(+), 37 deletions(-)
Signature · 1 line
2.43.0
Stefan Berger
reviewerPATCH 1/14 crypto: ecdsa - Convert byte arrays with key coordinates to digits
For NIST P192/256/384 the public key's x and y parameters could be copied directly from a given array since both parameters each filled 'ndigits' of digits (a 'digit' is a u64). For support of NIST P521 the key parameters first have to be copied right-aligned into a temporary byte array and can then be copied into the final digit array using ecc_swap_digits.
Implement ecc_digits_from_array to convert a byte array into an array of digits and use this function in ecdsa_set_pub_key where an input byte array needs to be converted into digits.
--- crypto/ecdsa.c | 15 ++++++++++----- include/crypto/internal/ecc.h | 19 +++++++++++++++++++ 2 files changed, 29 insertions(+), 5 deletions(-)
crypto/ecdsa.c +10 -5
@@ -222,9 +222,8 @@ static int ecdsa_ecc_ctx_reset(struct ecc_ctx *ctx)static int ecdsa_set_pub_key (struct crypto_akcipher *tfm,const void *key,unsigned int keylen) {struct ecc_ctx *ctx =akcipher_tfm_ctx (tfm); +unsigned int digitlen, ndigits, nbytes;const unsigned char *d = key; -const u64 *digits = (const u64 *)&d[1 ]; -unsigned int ndigits;int ret; ret =ecdsa_ecc_ctx_reset (ctx);
@@ -238,12 +237,18 @@ static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsigreturn -EINVAL ; keylen--; - ndigits = (keylen >>1 ) /sizeof (u64); + digitlen = keylen >>1 ; + + ndigits = digitlen /sizeof (u64);if (ndigits != ctx->curve->g.ndigits)return -EINVAL ; -ecc_swap_digits (digits, ctx->pub_key.x, ndigits); -ecc_swap_digits (&digits[ndigits], ctx->pub_key.y, ndigits); + nbytes = ndigits *sizeof (u64); + d++; + +ecc_digits_from_array (d, digitlen, ctx->pub_key.x, ndigits); +ecc_digits_from_array (&d[digitlen], digitlen, ctx->pub_key.y, ndigits); + ret =ecc_is_pubkey_valid_full (ctx->curve, &ctx->pub_key); ctx->pub_key_set = ret ==0 ;
include/crypto/internal/ecc.h +19 -0
@@ -56,6 +56,25 @@ static inline void ecc_swap_digits(const void *in, u64 *out, unsigned int ndigit out[i] =get_unaligned_be64 (&src[ndigits -1 - i]); } +/** +* ecc_digits_from_array() - Create ndigits from a byte array of nbytes +* @in: Input byte array +* @nbytes Size of input byte array +* @out Output digits array +* @ndigits: Number of digits to create from byte array +*/ +static inline void ecc_digits_from_array (const u8 *in,unsigned int nbytes, +u64 *out,unsigned int ndigits) +{ +unsigned int sz = ndigits *sizeof (u64); +u8 tmp[ECC_MAX_DIGITS *sizeof (u64)]; +unsigned int o = sz - nbytes; + +memset (tmp,0 , o); +memcpy (&tmp[o], in, nbytes); +ecc_swap_digits (tmp, out, ndigits); +} +/** * ecc_is_key_valid() - Validate a given ECDH private key *
Signature · 1 line
2.43.0
kernel test robot
build botRe: [PATCH 01/14] crypto: ecdsa - Convert byte arrays with key coordinates to digits
kernel test robot noticed the following build warnings:
Hi Stefan,
kernel test robot noticed the following build warnings:
[auto build test WARNING on herbert-cryptodev-2.6/master]
[also build test WARNING on herbert-crypto-2.6/master linus/master v6.8-rc3 next-20240209] [If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]
url: https://github.com/intel-lab-lkp/linux/commits/Stefan-Berger/crypto-ecdsa-Convert-byte-arrays-with-key-coordinates-to-digits/20240209-062415 base: https://git.kernel.org/pub/scm/linux/kernel/git/herbert/cryptodev-2.6.git master patch link: https://lore.kernel.org/r/20240208221840.3665874-2-stefanb%40linux.ibm.com patch subject: [PATCH 01/14] crypto: ecdsa - Convert byte arrays with key coordinates to digits config: x86_64-randconfig-101-20240209 (https://download.01.org/0day-ci/archive/20240210/[email protected]/config) compiler: clang version 17.0.6 (https://github.com/llvm/llvm-project 6009708b4367171ccdbf4b5905cb6a803753fe18) reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20240210/[email protected]/reproduce)
If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/
All warnings (new ones prefixed by >>):
>> crypto/ecdsa.c:225:34: warning: variable 'nbytes' set but not used [-Wunused-but-set-variable]
225 | unsigned int digitlen, ndigits, nbytes;
| ^1 warning generated.
vim +/nbytes +225 crypto/ecdsa.c
216
217 /*
218 * Set the public key given the raw uncompressed key data from an X509
219 * certificate. The key data contain the concatenated X and Y coordinates of
220 * the public key.
221 */
222 static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsigned int keylen)
223 {
224 struct ecc_ctx *ctx = akcipher_tfm_ctx(tfm);
> 225 unsigned int digitlen, ndigits, nbytes;
226 const unsigned char *d = key;
227 int ret;
228
229 ret = ecdsa_ecc_ctx_reset(ctx);
230 if (ret < 0)
231 return ret;
232
233 if (keylen < 1 || (((keylen - 1) >> 1) % sizeof(u64)) != 0)
234 return -EINVAL;
235 /* we only accept uncompressed format indicated by '4' */
236 if (d[0] != 4)
237 return -EINVAL;
238
239 keylen--;
240 digitlen = keylen >> 1;
241
242 ndigits = digitlen / sizeof(u64);
243 if (ndigits != ctx->curve->g.ndigits)
244 return -EINVAL;
245
246 nbytes = ndigits * sizeof(u64);
247 d++;
248
249 ecc_digits_from_array(d, digitlen, ctx->pub_key.x, ndigits);
250 ecc_digits_from_array(&d[digitlen], digitlen, ctx->pub_key.y, ndigits);
251
252 ret = ecc_is_pubkey_valid_full(ctx->curve, &ctx->pub_key);
253
254 ctx->pub_key_set = ret == 0;
255
256 return ret;
257 }
258
Signature · 2 lines
0-DAY CI Kernel Test Service https://github.com/intel/lkp-tests/wiki
Stefan Berger
reviewerPATCH 2/14 crypto: ecdsa - Adjust tests on length of key material
In reply to Stefan BergerIn preparation for support of NIST P521, adjust the basic tests on the length of the provided key parameter to only ensure that the length of the x plus y coordinates parameter array is not an odd number and that each coordinate fits into an array of 'ndigits' digits. Mathematical tests on the key's parameters are then done in ecc_is_pubkey_valid_full eliminating invalid keys.
The change is necessary since NIST P521 keys do not have keys with coordinates that each fully require 'full' digits (= u64), unlike NIST P192/256/384 that all require multiple 'full' digits.
--- crypto/ecdsa.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
crypto/ecdsa.c +2 -2
@@ -230,7 +230,7 @@ static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsigif (ret <0 )return ret; -if (keylen <1 || (((keylen -1 ) >>1 ) %sizeof (u64)) !=0 ) +if (keylen <1 || ((keylen -1 ) &1 ) !=0 )return -EINVAL ;/* we only accept uncompressed format indicated by '4' */ if (d[0 ] !=4 )
@@ -239,7 +239,7 @@ static int ecdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key, unsig keylen--; digitlen = keylen >>1 ; - ndigits = digitlen /sizeof (u64); + ndigits =DIV_ROUND_UP (digitlen,sizeof (u64));if (ndigits != ctx->curve->g.ndigits)return -EINVAL ;
Signature · 1 line
2.43.0
Stefan Berger
reviewerPATCH 3/14 crypto: ecdsa - Adjust res.x mod n for NIST P521
In reply to Stefan BergerWhen res.x >= n then res.x mod n can be calculated by iteratively sub- tracting n from res.x until n > res.x. For NIST P192/256/384 this is done in a single subtraction since these curves' 'n' use all the 64bit digits. This is also significantly faster than a modulo operation. For NIST P521 the same could take multiple subtractions. However, during testing with varying NIST P521 keys it was never necessary to do any subtraction at all.
--- crypto/ecdsa.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
crypto/ecdsa.c +2 -2
@@ -121,8 +121,8 @@ static int _ecdsa_verify(struct ecc_ctx *ctx, const u64 *hash, const u64 *r, conecc_point_mult_shamir (&res, u1, &curve->g, u2, &ctx->pub_key, curve);/* res.x = res.x mod n (if res.x > order) */ -if (unlikely (vli_cmp (res.x, curve->n, ndigits) ==1 )) -/* faster alternative for NIST p384, p256 & p192 */ +while (unlikely (vli_cmp (res.x, curve->n, ndigits) ==1 )) +/* faster alternative for NIST p521, p384, p256 & p192 */ vli_sub (res.x, res.x, curve->n, ndigits);if (!vli_cmp (res.x, r, ndigits))
Signature · 1 line
2.43.0
Stefan Berger
reviewerPATCH 4/14 crypto: ecc - Implement vli_mmod_fast_521 for NIST p521
In reply to Stefan BergerImplement vli_mmod_fast_521 following the description for how to calculate the modulus for NIST P521 in the NIST publication "Recommendations for Discrete Logarithm-Based Cryptography: Elliptic Curve Domain Parameters" section G.1.4.
NIST p521 requires 9 64bit digits, so increase the ECC_MAX_DIGITS so that arrays fit the larger numbers.
--- crypto/ecc.c | 31 +++++++++++++++++++++++++++++++ include/crypto/internal/ecc.h | 2 +- 2 files changed, 32 insertions(+), 1 deletion(-)
crypto/ecc.c +31 -0
@@ -902,6 +902,31 @@ static void vli_mmod_fast_384(u64 *result, const u64 *product,#undef AND64H#undef AND64L +/* Computes result = product % curve_prime +* from "Recommendations for Discrete Logarithm-Based Cryptography: +* Elliptic Curve Domain Parameters" G.1.4 +*/ +static void vli_mmod_fast_521 (u64 *result,const u64 *product, +const u64 *curve_prime,u64 *tmp) +{ +const unsigned int ndigits =9 ; +size_t i; + +for (i =0 ; i < ndigits; i++) + tmp[i] = product[i]; + tmp[8 ] &=0x1ff ; + +vli_set (result, tmp, ndigits); + + +for (i =0 ; i < ndigits; i++) + tmp[i] = (product[8 + i] >>9 ) | (product[9 + i] <<55 ); + tmp[8 ] &=0x1ff ; + +vli_mod_add (result, result, tmp, curve_prime, ndigits); +} + +/* Computes result = product % curve_prime for different curve_primes. * * Note that curve_primes are distinguished just by heuristic check and
@@ -941,6 +966,12 @@ static bool vli_mmod_fast(u64 *result, u64 *product,case 6 :vli_mmod_fast_384 (result, product, curve_prime, tmp);break ; +case 9 : +if (!strcmp (curve->name,"nist_521" )) { +vli_mmod_fast_521 (result, product, curve_prime, tmp); +break ; + } + fallthrough;default :pr_err_ratelimited ("ecc: unsupported digits size!\n" );return false;
include/crypto/internal/ecc.h +1 -1
@@ -33,7 +33,7 @@#define ECC_CURVE_NIST_P192_DIGITS 3#define ECC_CURVE_NIST_P256_DIGITS 4#define ECC_CURVE_NIST_P384_DIGITS 6 -#define ECC_MAX_DIGITS (512 / 64)/* due to ecrdsa */ +#define ECC_MAX_DIGITS (576 / 64)/* due to NIST P521 */ #define ECC_DIGITS_TO_BYTES_SHIFT 3
Signature · 1 line
2.43.0
Stefan Berger
reviewerPATCH 5/14 crypto: ecc - For NIST P521 use vli_num_bits to get number of bits
In reply to Stefan BergerIn ecc_point_mult use vli_num_bits to determine the number of bits when using NIST P521. The change is required specifically for NIST P521 to pass tests on the public key.
--- crypto/ecc.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-)
crypto/ecc.c +4 -1
@@ -1326,7 +1326,10 @@ static void ecc_point_mult(struct ecc_point *result, carry =vli_add (sk[0 ], scalar, curve->n, ndigits);vli_add (sk[1 ], sk[0 ], curve->n, ndigits); scalar = sk[!carry]; - num_bits =sizeof (u64) * ndigits *8 +1 ; +if (ndigits ==9 && !strcmp (curve->name,"nist_521" )) + num_bits =vli_num_bits (scalar, ndigits); +else + num_bits =sizeof (u64) * ndigits *8 +1 ;vli_set (rx[1 ], point->x, ndigits);vli_set (ry[1 ], point->y, ndigits);
Signature · 1 line
2.43.0
Stefan Berger
reviewerPATCH 6/14 crypto: ecc - Add NIST P521 curve parameters
In reply to Stefan BergerAdd the parameters for the NIST P521 curve and define a new curve ID for it. Make the curve available in ecc_get_curve.
--- crypto/ecc.c | 2 ++ crypto/ecc_curve_defs.h | 44 +++++++++++++++++++++++++++++++++++++++++ include/crypto/ecdh.h | 1 + 3 files changed, 47 insertions(+)
crypto/ecc.c +2 -0
@@ -60,6 +60,8 @@ const struct ecc_curve *ecc_get_curve(unsigned int curve_id)return &nist_p256;case ECC_CURVE_NIST_P384 :return &nist_p384; +case ECC_CURVE_NIST_P521 : +return &nist_p521;default :return NULL ; }
crypto/ecc_curve_defs.h +44 -0
50 lines not on this page · raw message
include/crypto/ecdh.h +1 -0
@@ -26,6 +26,7 @@#define ECC_CURVE_NIST_P192 0x0001#define ECC_CURVE_NIST_P256 0x0002#define ECC_CURVE_NIST_P384 0x0003 +#define ECC_CURVE_NIST_P521 0x0004/** * struct ecdh - define an ECDH private key
Signature · 1 line
2.43.0
Stefan Berger
reviewerPATCH 7/14 crypto: ecdsa - Register NIST P521 and extend test suite
In reply to Stefan BergerRegister NIST P521 as an akcipher and extend the testmgr with NIST P521-specific test vectors.
--- crypto/ecdsa.c | 30 ++++++++++ crypto/testmgr.c | 7 +++ crypto/testmgr.h | 146 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 183 insertions(+)
crypto/ecdsa.c +30 -0
@@ -270,6 +270,28 @@ static unsigned int ecdsa_max_size(struct crypto_akcipher *tfm)return ctx->pub_key.ndigits <<ECC_DIGITS_TO_BYTES_SHIFT ; } +static int ecdsa_nist_p521_init_tfm (struct crypto_akcipher *tfm) +{ +struct ecc_ctx *ctx =akcipher_tfm_ctx (tfm); + +return ecdsa_ecc_ctx_init (ctx,ECC_CURVE_NIST_P521 ); +} + +static struct akcipher_alg ecdsa_nist_p521 = { + .verify = ecdsa_verify, + .set_pub_key = ecdsa_set_pub_key, + .max_size = ecdsa_max_size, + .init = ecdsa_nist_p521_init_tfm, + .exit = ecdsa_exit_tfm, + .base = { + .cra_name ="ecdsa-nist-p521" , + .cra_driver_name ="ecdsa-nist-p521-generic" , + .cra_priority =100 , + .cra_module =THIS_MODULE , + .cra_ctxsize =sizeof (struct ecc_ctx ), + }, +}; +static int ecdsa_nist_p384_init_tfm (struct crypto_akcipher *tfm) {struct ecc_ctx *ctx =akcipher_tfm_ctx (tfm);
@@ -353,8 +375,15 @@ static int __init ecdsa_init(void)if (ret) goto nist_p384_error; + ret =crypto_register_akcipher (&ecdsa_nist_p521); +if (ret) + goto nist_p521_error; +return 0 ; +nist_p521_error: +crypto_unregister_akcipher (&ecdsa_nist_p384); + nist_p384_error:crypto_unregister_akcipher (&ecdsa_nist_p256);
@@ -370,6 +399,7 @@ static void __exit ecdsa_exit(void)crypto_unregister_akcipher (&ecdsa_nist_p192);crypto_unregister_akcipher (&ecdsa_nist_p256);crypto_unregister_akcipher (&ecdsa_nist_p384); +crypto_unregister_akcipher (&ecdsa_nist_p521); }subsys_initcall (ecdsa_init);
crypto/testmgr.c +7 -0
@@ -5097,6 +5097,13 @@ static const struct alg_test_desc alg_test_descs[] = { .suite = { .akcipher = __VECS(ecdsa_nist_p384_tv_template) } + }, { + .alg = "ecdsa-nist-p521", + .test = alg_test_akcipher, + .fips_allowed = 1, + .suite = { + .akcipher = __VECS(ecdsa_nist_p521_tv_template) + } }, { .alg = "ecrdsa", .test = alg_test_akcipher,
crypto/testmgr.h +146 -0
152 lines not on this page · raw message
Signature · 1 line
2.43.0
Stefan Berger
reviewerPATCH 8/14 x509: Add OID for NIST P521 and extend parser for it
In reply to Stefan BergerPrepare the x509 parser to accept NIST P521 certificates and add the OID for ansip521r1, which is the identifier for NIST P521.
--- crypto/asymmetric_keys/x509_cert_parser.c | 3 +++ include/linux/oid_registry.h | 1 + 2 files changed, 4 insertions(+)
crypto/asymmetric_keys/x509_cert_parser.c +3 -0
@@ -538,6 +538,9 @@ int x509_extract_key_data(void *context, size_t hdrlen,case OID_id_ansip384r1: ctx->cert->pub->pkey_algo ="ecdsa-nist-p384" ;break ; +case OID_id_ansip521r1: + ctx->cert->pub->pkey_algo ="ecdsa-nist-p521" ; +break ;default :return -ENOPKG ; }
include/linux/oid_registry.h +1 -0
@@ -65,6 +65,7 @@ enum OID { OID_Scram,/* 1.3.6.1.5.5.14 */ OID_certAuthInfoAccess,/* 1.3.6.1.5.5.7.1.1 */ OID_id_ansip384r1,/* 1.3.132.0.34 */ + OID_id_ansip521r1,/* 1.3.132.0.35 */ OID_sha256,/* 2.16.840.1.101.3.4.2.1 */ OID_sha384,/* 2.16.840.1.101.3.4.2.2 */ OID_sha512, /* 2.16.840.1.101.3.4.2.3 */
Signature · 1 line
2.43.0
Stefan Berger
reviewerPATCH 9/14 crypto: ecdh - Use properly formatted digits to check for valid key
In reply to Stefan Bergerecc_is_key_valid expects a key with the most significant digit in the last entry of the digit array. Currently a reverse key is passed to ecc_is_key_valid that then passes that rather simple test checking whether the private key is in range [2, n-3]. For all current ecdh-supported curves (NIST P192/256/384) n is a rather large number, therefore easily passing this test. However, this will not work for NIST P521 anymore but the properly prepared array of digits will need to be passed. Therefore, use ecc_digits_from_array to create the digits array from the byte array and pass the result to this test function. Use a swapped key in ctx->private_key.
Note: The ctx->private_key is currently (unnecessarily) swapped and will be swapped into proper order in ecc_make_pub_key and crypto_ecdh_shared_secret before usage. Also the key generated in ecc_gen_privkey, that is assigned to ctx->private_key, is currently swapped. The above mention 'swap' and the ones mention here could likely all be removed.
--- crypto/ecdh.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-)
crypto/ecdh.c +7 -2
@@ -27,6 +27,8 @@ static int ecdh_set_secret(struct crypto_kpp *tfm, const void *buf, unsigned int len) {struct ecdh_ctx *ctx =ecdh_get_ctx (tfm); +u64 priv[ECC_MAX_DIGITS ]; +unsigned int nbytes;struct ecdh params; if (crypto_ecdh_decode_key(buf, len, ¶ms) < 0 ||
@@ -37,10 +39,13 @@ static int ecdh_set_secret(struct crypto_kpp *tfm, const void *buf,return ecc_gen_privkey (ctx->curve_id, ctx->ndigits, ctx->private_key); -memcpy (ctx->private_key, params.key, params.key_size); + nbytes = ctx->ndigits <<ECC_DIGITS_TO_BYTES_SHIFT ; + +ecc_digits_from_array (params.key, nbytes, priv, ctx->ndigits); +ecc_swap_digits (priv, ctx->private_key, ctx->ndigits);if (ecc_is_key_valid (ctx->curve_id, ctx->ndigits, - ctx->private_key, params.key_size) <0 ) { + priv, params.key_size) <0 ) {memzero_explicit (ctx->private_key, params.key_size);return -EINVAL ; }
Signature · 1 line
2.43.0
Stefan Berger
reviewerPATCH 10/14 crypto: ecc - Implement ecc_digits_to_array to convert digits to byte array
In reply to Stefan BergerImplement ecc_digits_to_array to convert an array of ndigits into an nbytes-sized byte array.
--- include/crypto/internal/ecc.h | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+)
include/crypto/internal/ecc.h +18 -0
@@ -75,6 +75,24 @@ static inline void ecc_digits_from_array(const u8 *in, unsigned int nbytes,ecc_swap_digits (tmp, out, ndigits); } +/** +* ecc_digits_to_array() - Copy nbytes from an ndigits array into a byte array +* @in: Input digits array +* @ndigits: Number of digits in input digits array +* @out: Output byte array +* @nbytes: Number of digits to create from byte array +*/ +static inline void ecc_digits_to_array (const u64 *in,unsigned int ndigits, +u8 *out,unsigned int nbytes) +{ +unsigned int sz = ndigits *sizeof (u64); +u8 tmp[ECC_MAX_DIGITS *sizeof (u64)]; +unsigned int o = sz - nbytes; + +ecc_swap_digits (in, (u64 *)tmp, ndigits); +memcpy (out, &tmp[o], nbytes); +} +/** * ecc_is_key_valid() - Validate a given ECDH private key *
Signature · 1 line
2.43.0
Stefan Berger
reviewerPATCH 11/14 crypto: Add nbits field to ecc_curve structure
In reply to Stefan BergerAdd the number of bits a curve has to the ecc_curve definition. This field only needs to be set for curves that don't fill up all bytes in their digits, such as NIST P521 which has only 9 bits in the most significant digit. This field will be used to determine the number of bytes a curve requires for its key coordinates for example.
--- crypto/ecc_curve_defs.h | 1 + include/crypto/ecc_curve.h | 3 +++ 2 files changed, 4 insertions(+)
crypto/ecc_curve_defs.h +1 -0
@@ -119,6 +119,7 @@ static u64 nist_p521_b[] = { 0xef451fd46b503f00ull, 0x3573df883d2c34f1ull, 0x051ull };static struct ecc_curve nist_p521 = { .name ="nist_521" , + .nbits =521 , .g = { .x = nist_p521_g_x, .y = nist_p521_g_y,
include/crypto/ecc_curve.h +3 -0
@@ -23,6 +23,8 @@ struct ecc_point {* struct ecc_curve - definition of elliptic curve * * @name: Short name of the curve. +* @nbits: Curves that do not use all bits in their ndigits must specify +* their number of bits here, otherwise can leave at 0. * @g: Generator point of the curve. * @p: Prime number, if Barrett's reduction is used for this curve * pre-calculated value 'mu' is appended to the @p after ndigits.
@@ -34,6 +36,7 @@ struct ecc_point {*/ struct ecc_curve {char *name; +unsigned int nbits;struct ecc_point g;u64 *p;u64 *n;
Signature · 1 line
2.43.0
Stefan Berger
reviewerPATCH 12/14 crypto: ecc - Implement and use ecc_curve_get_nbytes to get curve's nbytes
In reply to Stefan BergerImplement ecc_curve_get_nbytes to get a curve's number of bytes (nbytes). The number of bytes can be derived from the nbits field of a curve, if set, otherwise from the ndigits field.
--- crypto/ecc.c | 6 ++---- include/crypto/internal/ecc.h | 11 +++++++++++ 2 files changed, 13 insertions(+), 4 deletions(-)
crypto/ecc.c +2 -4
@@ -1478,10 +1478,8 @@ static int __ecc_is_key_valid(const struct ecc_curve *curve,int ecc_is_key_valid (unsigned int curve_id,unsigned int ndigits,const u64 *private_key,unsigned int private_key_len) { -int nbytes;const struct ecc_curve *curve =ecc_get_curve (curve_id); - - nbytes = ndigits <<ECC_DIGITS_TO_BYTES_SHIFT ; +int nbytes =ecc_curve_get_nbytes (curve);if (private_key_len != nbytes)return -EINVAL ;
@@ -1506,7 +1504,7 @@ int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey) {const struct ecc_curve *curve =ecc_get_curve (curve_id);u64 priv[ECC_MAX_DIGITS ]; -unsigned int nbytes = ndigits <<ECC_DIGITS_TO_BYTES_SHIFT ; +unsigned int nbytes =ecc_curve_get_nbytes (curve);unsigned int nbits =vli_num_bits (curve->n, ndigits);int err;
include/crypto/internal/ecc.h +11 -0
@@ -93,6 +93,17 @@ static inline void ecc_digits_to_array(const u64 *in, unsigned int ndigits,memcpy (out, &tmp[o], nbytes); } +/** +* ecc_curve_get_nbytes() - Get the number of bytes the curve requires +* @curve: The curve +*/ +static inline unsigned int ecc_curve_get_nbytes (const struct ecc_curve *curve) +{ +if (curve->nbits) +return DIV_ROUND_UP (curve->nbits,8 ); +return curve->g.ndigits <<ECC_DIGITS_TO_BYTES_SHIFT ; +} +/** * ecc_is_key_valid() - Validate a given ECDH private key *
Signature · 1 line
2.43.0
Stefan Berger
reviewerPATCH 13/14 crypto: ecdh - Use functions to copy digits from and to array
In reply to Stefan BergerAll curves supported so far provide digit arrays with ndigits to convert coordinates from and to. For NIST P521 only 8 digits and 2 bytes will be given per coordinate so that conversion from ndigits (= 9) does not work since some bytes are missing. Therefore, regard the input (and output) arrays as byte arrays that need to be converted to digits (from digits). Use ecc_digits_from array to convert a byte array to digits and ecc_digits_to_array to convert digits to a byte array.
crypt_ecdh_shared_secret creates nbytes into a byte array from which to create rand_z from. The most significant digit of rand_z needs to be adjusted to mask out unnecessary bits beyond the 521 bits of the NIST P521 curve. Therefore, apply a mask to the most significant digit.
--- crypto/ecc.c | 27 +++++++++++++++------------ crypto/ecdh.c | 24 ++++++++++++++---------- include/crypto/internal/ecc.h | 10 +++++++--- 3 files changed, 36 insertions(+), 25 deletions(-)
crypto/ecc.c +15 -12
@@ -1542,7 +1542,8 @@ int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)EXPORT_SYMBOL (ecc_gen_privkey);int ecc_make_pub_key (unsigned int curve_id,unsigned int ndigits, -const u64 *private_key,u64 *public_key) +const u64 *private_key,u8 *public_key, +unsigned int nbytes) {int ret =0 ;struct ecc_point *pk;
@@ -1570,8 +1571,8 @@ int ecc_make_pub_key(unsigned int curve_id, unsigned int ndigits, goto err_free_point; } -ecc_swap_digits (pk->x, public_key, ndigits); -ecc_swap_digits (pk->y, &public_key[ndigits], ndigits); +ecc_digits_to_array (pk->x, ndigits, public_key, nbytes); +ecc_digits_to_array (pk->y, ndigits, &public_key[nbytes], nbytes); err_free_point:ecc_free_point (pk);
@@ -1641,14 +1642,14 @@ int ecc_is_pubkey_valid_full(const struct ecc_curve *curve,EXPORT_SYMBOL (ecc_is_pubkey_valid_full);int crypto_ecdh_shared_secret (unsigned int curve_id,unsigned int ndigits, -const u64 *private_key,const u64 *public_key, -u64 *secret) +const u64 *private_key,const u8 *public_key, +unsigned int nbytes,u8 *secret,u64 msd_mask) {int ret =0 ;struct ecc_point *product, *pk;u64 priv[ECC_MAX_DIGITS ];u64 rand_z[ECC_MAX_DIGITS ]; -unsigned int nbytes; +u8 tmp[ECC_MAX_DIGITS <<ECC_DIGITS_TO_BYTES_SHIFT ];const struct ecc_curve *curve =ecc_get_curve (curve_id); if (!private_key || !public_key || !curve ||
@@ -1657,9 +1658,10 @@ int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits, goto out; } - nbytes = ndigits <<ECC_DIGITS_TO_BYTES_SHIFT ; - -get_random_bytes (rand_z, nbytes); +get_random_bytes (tmp, nbytes); +ecc_digits_from_array (tmp, nbytes, rand_z, ndigits); +if (msd_mask) + rand_z[ndigits -1 ] &= msd_mask; pk =ecc_alloc_point (ndigits);if (!pk) {
@@ -1667,8 +1669,9 @@ int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits, goto out; } -ecc_swap_digits (public_key, pk->x, ndigits); -ecc_swap_digits (&public_key[ndigits], pk->y, ndigits); +ecc_digits_from_array (public_key, nbytes, pk->x, ndigits); +ecc_digits_from_array (&public_key[nbytes], nbytes, pk->y, ndigits); + ret =ecc_is_pubkey_valid_partial (curve, pk);if (ret) goto err_alloc_product;
@@ -1688,7 +1691,7 @@ int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits, goto err_validity; } -ecc_swap_digits (product->x, secret, ndigits); +ecc_digits_to_array (product->x, ndigits, secret, nbytes); err_validity:memzero_explicit (priv,sizeof (priv));
crypto/ecdh.c +14 -10
@@ -15,6 +15,8 @@struct ecdh_ctx {unsigned int curve_id;unsigned int ndigits; +unsigned int nbytes; +u64 msd_mask;u64 private_key[ECC_MAX_DIGITS ]; };
@@ -28,7 +30,6 @@ static int ecdh_set_secret(struct crypto_kpp *tfm, const void *buf, {struct ecdh_ctx *ctx =ecdh_get_ctx (tfm);u64 priv[ECC_MAX_DIGITS ]; -unsigned int nbytes;struct ecdh params; if (crypto_ecdh_decode_key(buf, len, ¶ms) < 0 ||
@@ -39,9 +40,7 @@ static int ecdh_set_secret(struct crypto_kpp *tfm, const void *buf,return ecc_gen_privkey (ctx->curve_id, ctx->ndigits, ctx->private_key); - nbytes = ctx->ndigits <<ECC_DIGITS_TO_BYTES_SHIFT ; - -ecc_digits_from_array (params.key, nbytes, priv, ctx->ndigits); +ecc_digits_from_array (params.key, ctx->nbytes, priv, ctx->ndigits);ecc_swap_digits (priv, ctx->private_key, ctx->ndigits); if (ecc_is_key_valid(ctx->curve_id, ctx->ndigits,
@@ -56,13 +55,13 @@ static int ecdh_compute_value(struct kpp_request *req) {struct crypto_kpp *tfm =crypto_kpp_reqtfm (req);struct ecdh_ctx *ctx =ecdh_get_ctx (tfm); -u64 *public_key; -u64 *shared_secret =NULL ; +unsigned int nbytes = ctx->nbytes; +u8 *public_key; +u8 *shared_secret =NULL ;void *buf; -size_t copied, nbytes, public_key_sz; +size_t copied, public_key_sz;int ret = -ENOMEM ; - nbytes = ctx->ndigits <<ECC_DIGITS_TO_BYTES_SHIFT ;/* Public part is a point thus it has both coordinates */ public_key_sz =2 * nbytes;
@@ -91,12 +90,14 @@ static int ecdh_compute_value(struct kpp_request *req) ret =crypto_ecdh_shared_secret (ctx->curve_id, ctx->ndigits, ctx->private_key, public_key, - shared_secret); + nbytes, shared_secret, + ctx->msd_mask); buf = shared_secret; }else { ret =ecc_make_pub_key (ctx->curve_id, ctx->ndigits, - ctx->private_key, public_key); + ctx->private_key, public_key, + nbytes); buf = public_key; nbytes = public_key_sz; }
@@ -134,6 +135,7 @@ static int ecdh_nist_p192_init_tfm(struct crypto_kpp *tfm) ctx->curve_id =ECC_CURVE_NIST_P192 ; ctx->ndigits =ECC_CURVE_NIST_P192_DIGITS ; + ctx->nbytes = ctx->ndigits <<ECC_DIGITS_TO_BYTES_SHIFT ;return 0 ; }
@@ -159,6 +161,7 @@ static int ecdh_nist_p256_init_tfm(struct crypto_kpp *tfm) ctx->curve_id =ECC_CURVE_NIST_P256 ; ctx->ndigits =ECC_CURVE_NIST_P256_DIGITS ; + ctx->nbytes = ctx->ndigits <<ECC_DIGITS_TO_BYTES_SHIFT ;return 0 ; }
@@ -184,6 +187,7 @@ static int ecdh_nist_p384_init_tfm(struct crypto_kpp *tfm) ctx->curve_id =ECC_CURVE_NIST_P384 ; ctx->ndigits =ECC_CURVE_NIST_P384_DIGITS ; + ctx->nbytes = ctx->ndigits <<ECC_DIGITS_TO_BYTES_SHIFT ;return 0 ; }
include/crypto/internal/ecc.h +7 -3
@@ -138,12 +138,14 @@ int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey);* @ndigits: curve's number of digits * @private_key: pregenerated private key for the given curve * @public_key: buffer for storing the generated public key +* @nbytes: number of bytes per coordinate of public key * * Returns 0 if the public key was generated successfully, a negative value * if an error occurred. */ int ecc_make_pub_key (const unsigned int curve_id,unsigned int ndigits, -const u64 *private_key,u64 *public_key); +const u64 *private_key,u8 *public_key, +unsigned int nbytes);/** * crypto_ecdh_shared_secret() - Compute a shared secret
@@ -152,7 +154,9 @@ int ecc_make_pub_key(const unsigned int curve_id, unsigned int ndigits,* @ndigits: curve's number of digits * @private_key: private key of part A * @public_key: public key of counterpart B +* @nbytes: number of bytes per coordinate of public key * @secret: buffer for storing the calculated shared secret +* @msd_mask: optional mask to apply to the most significant digit * * Note: It is recommended that you hash the result of crypto_ecdh_shared_secret * before using it for symmetric encryption or HMAC.
@@ -161,8 +165,8 @@ int ecc_make_pub_key(const unsigned int curve_id, unsigned int ndigits,* if an error occurred. */ int crypto_ecdh_shared_secret (unsigned int curve_id,unsigned int ndigits, -const u64 *private_key,const u64 *public_key, -u64 *secret); +const u64 *private_key,const u8 *public_key, +unsigned int nbytes,u8 *secret,u64 msd_mask);/** * ecc_is_pubkey_valid_partial() - Partial public key validation
Signature · 1 line
2.43.0
Stefan Berger
reviewerPATCH 14/14 crypto: ecdh - Add support for NIST P521 and add test case
In reply to Stefan BergerImplement ecdh support with NIST P521 and add a test case from RFC5903.
--- crypto/ecdh.c | 34 +++++++++++++++ crypto/testmgr.c | 7 ++++ crypto/testmgr.h | 79 +++++++++++++++++++++++++++++++++++ include/crypto/internal/ecc.h | 1 + 4 files changed, 121 insertions(+)
crypto/ecdh.c +34 -0
@@ -207,6 +207,32 @@ static struct kpp_alg ecdh_nist_p384 = { }, }; +static int ecdh_nist_p521_init_tfm (struct crypto_kpp *tfm) +{ +struct ecdh_ctx *ctx =ecdh_get_ctx (tfm); + + ctx->curve_id =ECC_CURVE_NIST_P521 ; + ctx->ndigits =ECC_CURVE_NIST_P521_DIGITS ; + ctx->nbytes =DIV_ROUND_UP (521 ,8 ); + ctx->msd_mask =0x1ff ; + +return 0 ; +} +static struct kpp_alg ecdh_nist_p521 = { + .set_secret = ecdh_set_secret, + .generate_public_key = ecdh_compute_value, + .compute_shared_secret = ecdh_compute_value, + .max_size = ecdh_max_size, + .init = ecdh_nist_p521_init_tfm, + .base = { + .cra_name ="ecdh-nist-p521" , + .cra_driver_name ="ecdh-nist-p521-generic" , + .cra_priority =100 , + .cra_module =THIS_MODULE , + .cra_ctxsize =sizeof (struct ecdh_ctx ), + }, +}; +static bool ecdh_nist_p192_registered;static int __init ecdh_init (void )
@@ -225,8 +251,15 @@ static int __init ecdh_init(void)if (ret) goto nist_p384_error; + ret =crypto_register_kpp (&ecdh_nist_p521); +if (ret) + goto nist_p521_error; +return 0 ; +nist_p521_error: +crypto_unregister_kpp (&ecdh_nist_p384); + nist_p384_error:crypto_unregister_kpp (&ecdh_nist_p256);
@@ -242,6 +275,7 @@ static void __exit ecdh_exit(void)crypto_unregister_kpp (&ecdh_nist_p192);crypto_unregister_kpp (&ecdh_nist_p256);crypto_unregister_kpp (&ecdh_nist_p384); +crypto_unregister_kpp (&ecdh_nist_p521); }subsys_initcall (ecdh_init);
crypto/testmgr.c +7 -0
@@ -5077,6 +5077,13 @@ static const struct alg_test_desc alg_test_descs[] = { .suite = { .kpp = __VECS(ecdh_p384_tv_template) } + }, { + .alg = "ecdh-nist-p521", + .test = alg_test_kpp, + .fips_allowed = 1, + .suite = { + .kpp = __VECS(ecdh_p521_tv_template) + } }, { .alg = "ecdsa-nist-p192", .test = alg_test_akcipher,
crypto/testmgr.h +79 -0
85 lines not on this page · raw message
include/crypto/internal/ecc.h +1 -0
@@ -33,6 +33,7 @@#define ECC_CURVE_NIST_P192_DIGITS 3#define ECC_CURVE_NIST_P256_DIGITS 4#define ECC_CURVE_NIST_P384_DIGITS 6 +#define ECC_CURVE_NIST_P521_DIGITS 9#define ECC_MAX_DIGITS (576 / 64)/* due to NIST P521 */ #define ECC_DIGITS_TO_BYTES_SHIFT 3
Signature · 1 line
2.43.0