lkml.org 
[lkml]   [2021]   [Nov]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH 09/18] crypto: dh - implement private key generation primitive
    Date
    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@suse.de

    Signed-off-by: Nicolai Stange <nstange@suse.de>
    ---
    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)
    + 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. */
    +
    + /*
    + * Reserve one extra u64 to hold the extra random bits
    + * required as per 5.6.1.1.3.
    + */
    + tmp_size = (n + 1) * sizeof(__be64);
    + 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
    --
    2.26.2
    \
     
     \ /
      Last update: 2021-12-01 01:51    [W:2.429 / U:0.480 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site