Hi Stephan,
first of all, many thanks for your review!
Stephan Müller <smueller@xxxxxxxxxx> writes:
> Am Mittwoch, 1. Dezember 2021, 01:48:49 CET schrieb Nicolai Stange:
>
>> The support for NVME in-band authentication currently in the works ([1])
>> needs to generate ephemeral DH keys.
>>
>> Implement crypto_dh_gen_privkey() which is intended to be used from
>> the DH implementations just in analogy to how ecc_gen_privkey() is used
>> for ECDH.
>>
>> Make the new crypto_dh_gen_privkey() to follow the approach specified
>> in SP800-56Arev3, sec. 5.6.1.1.3 ("Key-Pair Generation Using Extra Random
>> Bits").
>>
>> SP800-56Arev3 specifies a lower as well as an upper bound on the generated
>> key's length:
>> - it must be >= two times the maximum supported security strength of
>> the group in question and
>> - it must be <= the length of the domain parameter Q.
>> Both of these are available only for the safe-prime groups from
>> RFC 3526 or RFC 7919, which had been introduced to the kernel with previous
>> patches: for any safe-prime group Q = (P - 1)/2 by definition and the
>> individual maximum supported security strength as specified by
>> SP800-56Arev3 has already been made available alongside the resp. domain
>> parameters with said previous patches. Restrict crypto_dh_gen_privkey() to
>> these safe-prime groups, i.e. to those groups with any group_id but
>> dh_group_id_unknown. Make it pick twice the maximum supported strength
>> rounded up to the next power of two for the output key size. This choice
>> respects both, the lower and upper bounds given by SP800-90Arev3 for
>> all safe-prime groups known to the kernel by now and is also in line with
>> the NVME base spec 2.0, which requires the key size to be >= 256bits.
>>
>> [1] https://lkml.kernel.org/r/20211122074727.25988-4-hare@xxxxxxx
>>
>> Signed-off-by: Nicolai Stange <nstange@xxxxxxx>
>> ---
>> crypto/Kconfig | 1 +
>> crypto/dh_helper.c | 128 ++++++++++++++++++++++++++++++++++++++++++++
>> include/crypto/dh.h | 22 ++++++++
>> 3 files changed, 151 insertions(+)
>>
>> diff --git a/crypto/Kconfig b/crypto/Kconfig
>> index fcb044bdc90a..578711b02bb3 100644
>> --- a/crypto/Kconfig
>> +++ b/crypto/Kconfig
>> @@ -228,6 +228,7 @@ menuconfig CRYPTO_DH
>> tristate "Diffie-Hellman algorithm"
>> select CRYPTO_KPP
>> select MPILIB
>> + select CRYPTO_RNG_DEFAULT
>> help
>> Generic implementation of the Diffie-Hellman algorithm.
>>
>> diff --git a/crypto/dh_helper.c b/crypto/dh_helper.c
>> index fb8df4734dc1..5a8c9c50297f 100644
>> --- a/crypto/dh_helper.c
>> +++ b/crypto/dh_helper.c
>> @@ -9,6 +9,7 @@
>> #include <linux/string.h>
>> #include <crypto/dh.h>
>> #include <crypto/kpp.h>
>> +#include <crypto/rng.h>
>>
>> #define DH_KPP_SECRET_MIN_SIZE (sizeof(struct kpp_secret) + \
>> sizeof(enum dh_group_id) + 3 * sizeof(int))
>> @@ -592,3 +593,130 @@ int crypto_dh_decode_key(const char *buf, unsigned int
>> len, struct dh *params) return 0;
>> }
>> EXPORT_SYMBOL_GPL(crypto_dh_decode_key);
>> +
>> +static u64 __add_u64_to_be(__be64 *dst, unsigned int n, u64 val)
>> +{
>> + unsigned int i;
>> +
>> + for (i = n; val && i > 0; --i) {
>> + u64 tmp = be64_to_cpu(dst[i - 1]);
>> +
>> + tmp += val;
>> + val = tmp >= val ? 0 : 1;
>> + dst[i - 1] = cpu_to_be64(tmp);
>> + }
>> +
>> + return val;
>> +}
>> +
>> +int crypto_dh_gen_privkey(enum dh_group_id group_id,
>> + char key[CRYPTO_DH_MAX_PRIVKEY_SIZE],
>> + unsigned int *key_size)
>> +{
>> + const struct safe_prime_group *g;
>> + unsigned int n, tmp_size;
>> + __be64 *tmp;
>> + int err;
>> + u64 h, o;
>> +
>> + /*
>> + * Generate a private key following NIST SP800-56Ar3,
>> + * sec. 5.6.1.1.1 and 5.6.1.1.3 resp.. This is supported only
>> + * for the (approved) safe-prime groups.
>> + */
>> + g = get_safe_prime_group(group_id);
>> + if (!g)
>
> What about
>
> if (g == dh_group_id_unknown)
>
> ?
No, I think this is correct: get_safe_prime_group() returns a pointer to
a struct safe_prime_group instances looked up from the
safe_prime_groups[] array and for dh_group_id_unknown NULL is returned.
>
>> + return -EINVAL;
>> +
>> + /*
>> + * 5.6.1.1.1: choose key length N such that
>> + * 2 * ->max_strength <= N <= log2(q) + 1 = ->p_size * 8 - 1
>> + * with q = (p - 1) / 2 for the safe-prime groups.
>> + * Choose the lower bound's next power of two for N in order to
>> + * avoid excessively large private keys while still
>> + * maintaining some extra reserve beyond the bare minimum in
>> + * most cases. Note that for each entry in safe_prime_groups[],
>> + * the following holds for such N:
>> + * - N >= 256, in particular it is a multiple of 2^6 = 64
>> + * bits and
>> + * - N < log2(q) + 1, i.e. N respects the upper bound.
>> + */
>> + n = roundup_pow_of_two(2 * g->max_strength);
>> + WARN_ON_ONCE(n & ((1u << 6) - 1));
>> + n >>= 6; /* Convert N into units of u64. */
>
> Couldn't we pre-compute that value for each of the safeprime groups? This
> value should be static for each of them.
Can you elaborate why this would be better? As long as the value
calculated above is considered reasonable for every usecase, I don't see
the advantage of storing it somewhere.
OTOH, calculating the value on the fly
- enforces conformance to 5.6.1.1.1 (>= twice the sec strength)
- and guarantees that it is a multiple of 64 bits, as required
by the implementation,
whereas you'd had to examine each and every individual group's setting
for correctness when storing precomputed values alongside the other,
"primary" group parameters.
Thanks,
Nicolai
>> +
>> + /*
>> + * Reserve one extra u64 to hold the extra random bits
>> + * required as per 5.6.1.1.3.
>> + */
>> + tmp_size = (n + 1) * sizeof(__be64);
>
> Maybe add this to the pre-computed value?
>
>
>> + tmp = kmalloc(tmp_size, GFP_KERNEL);
>> + if (!tmp)
>> + return -ENOMEM;
>> +
>> + /*
>> + * 5.6.1.1.3, step 3 (and implicitly step 4): obtain N + 64
>> + * random bits and interpret them as a big endian integer.
>> + */
>> + err = -EFAULT;
>> + if (crypto_get_default_rng())
>> + goto out;
>> +
>> + err = crypto_rng_get_bytes(crypto_default_rng, (u8 *)tmp, tmp_size);
>> + crypto_put_default_rng();
>> + if (err)
>> + goto out;
>> +
>> + /*
>> + * 5.6.1.1.3, step 5 is implicit: 2^N < q and thus,
>> + * M = min(2^N, q) = 2^N.
>> + *
>> + * For step 6, calculate
>> + * key = (tmp[] mod (M - 1)) + 1 = (tmp[] mod (2^N - 1)) + 1.
>> + *
>> + * In order to avoid expensive divisions, note that
>> + * 2^N mod (2^N - 1) = 1 and thus, for any integer h,
>> + * 2^N * h mod (2^N - 1) = h mod (2^N - 1) always holds.
>> + * The big endian integer tmp[] composed of n + 1 64bit words
>> + * may be written as tmp[] = h * 2^N + l, with h = tmp[0]
>> + * representing the 64 most significant bits and l
>> + * corresponding to the remaining 2^N bits. With the remark
>> + * from above,
>> + * h * 2^N + l mod (2^N - 1) = l + h mod (2^N - 1).
>> + * As both, l and h are less than 2^N, their sum after
>> + * this first reduction is guaranteed to be <= 2^(N + 1) - 2.
>> + * Or equivalently, that their sum can again be written as
>> + * h' * 2^N + l' with h' now either zero or one and if one,
>> + * then l' <= 2^N - 2. Thus, all bits at positions >= N will
>> + * be zero after a second reduction:
>> + * h' * 2^N + l' mod (2^N - 1) = l' + h' mod (2^N - 1).
>> + * At this point, it is still possible that
>> + * l' + h' = 2^N - 1, i.e. that l' + h' mod (2^N - 1)
>> + * is zero. This condition will be detected below by means of
>> + * the final increment overflowing in this case.
>> + */
>> + h = be64_to_cpu(tmp[0]);
>> + h = __add_u64_to_be(tmp + 1, n, h);
>> + h = __add_u64_to_be(tmp + 1, n, h);
>> + WARN_ON_ONCE(h);
>> +
>> + /* Increment to obtain the final result. */
>> + o = __add_u64_to_be(tmp + 1, n, 1);
>> + /*
>> + * The overflow bit o from the increment is either zero or
>> + * one. If zero, tmp[1:n] holds the final result in big-endian
>> + * order. If one, tmp[1:n] is zero now, but needs to be set to
>> + * one, c.f. above.
>> + */
>> + if (o)
>> + tmp[n] = cpu_to_be64(1);
>> +
>> + /* n is in units of u64, convert to bytes. */
>> + *key_size = n << 3;
>> + memcpy(key, &tmp[1], *key_size);
>> +
>> +out:
>> + kfree_sensitive(tmp);
>> + return err;
>> +}
>> +EXPORT_SYMBOL_GPL(crypto_dh_gen_privkey);
>> diff --git a/include/crypto/dh.h b/include/crypto/dh.h
>> index 7eb1fad93d02..182100395bbb 100644
>> --- a/include/crypto/dh.h
>> +++ b/include/crypto/dh.h
>> @@ -99,4 +99,26 @@ int crypto_dh_encode_key(char *buf, unsigned int len,
>> const struct dh *params); */
>> int crypto_dh_decode_key(const char *buf, unsigned int len, struct dh
>> *params);
>>
>> +/*
>> + * The maximum key length is two times the max. sec. strength of the
>> + * safe-prime groups, rounded up to the next power of two.
>> + */
>> +#define CRYPTO_DH_MAX_PRIVKEY_SIZE (512 / 8)
>> +
>> +/**
>> + * crypto_dh_gen_privkey() - generate a DH private key
>> + * @buf: The DH group to generate a key for
>> + * @key: Buffer provided by the caller to receive the generated
>> + * key
>> + * @key_size: Pointer to an unsigned integer the generated key's length
>> + * will be stored in
>> + *
>> + * This function is intended to generate an ephemeral DH key.
>> + *
>> + * Return: Negative error code on failure, 0 on success
>> + */
>> +int crypto_dh_gen_privkey(enum dh_group_id group_id,
>> + char key[CRYPTO_DH_MAX_PRIVKEY_SIZE],
>> + unsigned int *key_size);
>> +
>> #endif
--
SUSE Software Solutions Germany GmbH, Maxfeldstr. 5, 90409 Nürnberg, Germany
(HRB 36809, AG Nürnberg), GF: Ivo Totev
