[4/6] crypto: hkdf - RFC5869 Key Derivation Function
diff mbox series

Message ID 2423373.Zd5ThvQH5g@positron.chronox.de
State Superseded
Delegated to: Herbert Xu
Headers show
Series
  • General Key Derivation Function Support
Related show

Commit Message

Stephan Mueller Jan. 11, 2019, 7:10 p.m. UTC
The RFC5869 compliant Key Derivation Function is implemented as a
random number generator considering that it behaves like a deterministic
RNG.

The extract and expand phases use different instances of the underlying
keyed message digest cipher to ensure that while the extraction phase
generates a new key for the expansion phase, the cipher for the
expansion phase can still be used. This approach is intended to aid
multi-threaded uses cases.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 crypto/Kconfig  |   6 +
 crypto/Makefile |   1 +
 crypto/hkdf.c   | 290 ++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 297 insertions(+)
 create mode 100644 crypto/hkdf.c

Comments

Eric Biggers Jan. 12, 2019, 5:12 a.m. UTC | #1
Hi Stephan,

On Fri, Jan 11, 2019 at 08:10:39PM +0100, Stephan Müller wrote:
> The RFC5869 compliant Key Derivation Function is implemented as a
> random number generator considering that it behaves like a deterministic
> RNG.
> 

Thanks for the proof of concept!  I guess it ended up okay.  But can you explain
more the benefits of using the crypto_rng interface, as opposed to just some
crypto_hkdf_*() helper functions that are exported for modules to use?

> The extract and expand phases use different instances of the underlying
> keyed message digest cipher to ensure that while the extraction phase
> generates a new key for the expansion phase, the cipher for the
> expansion phase can still be used. This approach is intended to aid
> multi-threaded uses cases.

I think you partially misunderstood what I was asking for.  One HMAC tfm is
sufficient as long as HKDF-Expand is separated from HKDF-Extract, which you've
done.  So just use one HMAC tfm, and in crypto_hkdf_seed() key it with the
'salt', and then afterwards with the 'prk'.

Also everywhere in this patchset, please avoid using the word "cipher" to refer
to algorithms that are not encryption/decryption.  I know a lot of the crypto
API docs do this, but I think it is a mistake and confusing.  Hash algorithms
and KDFs are not "ciphers".

> 
> Signed-off-by: Stephan Mueller <smueller@chronox.de>
> ---
>  crypto/Kconfig  |   6 +
>  crypto/Makefile |   1 +
>  crypto/hkdf.c   | 290 ++++++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 297 insertions(+)
>  create mode 100644 crypto/hkdf.c
> 
> diff --git a/crypto/Kconfig b/crypto/Kconfig
> index cc80d89e0cf5..0eee5e129fa3 100644
> --- a/crypto/Kconfig
> +++ b/crypto/Kconfig
> @@ -568,6 +568,12 @@ config CRYPTO_KDF
>  	  Support for KDF compliant to SP800-108. All three types of
>  	  KDF specified in SP800-108 are implemented.
>  
> +config CRYPTO_HKDF
> +	tristate "HMAC-based Extract-and expand Key Derivation Function"
> +	select CRYPTO_RNG
> +	help
> +	  Support for KDF compliant to RFC5869.
> +

Make the description
"HMAC-based Extract-and-Expand Key Derivation Function (HKDF)"?
There is a missing dash, and probably the acronym "HKDF" should be in there.

>  config CRYPTO_XCBC
>  	tristate "XCBC support"
>  	select CRYPTO_HASH
> diff --git a/crypto/Makefile b/crypto/Makefile
> index 69a0bb64b0ac..6bbb0a4dea13 100644
> --- a/crypto/Makefile
> +++ b/crypto/Makefile
> @@ -59,6 +59,7 @@ crypto_user-$(CONFIG_CRYPTO_STATS) += crypto_user_stat.o
>  obj-$(CONFIG_CRYPTO_CMAC) += cmac.o
>  obj-$(CONFIG_CRYPTO_HMAC) += hmac.o
>  obj-$(CONFIG_CRYPTO_KDF) += kdf.o
> +obj-$(CONFIG_CRYPTO_HKDF) += hkdf.o
>  obj-$(CONFIG_CRYPTO_VMAC) += vmac.o
>  obj-$(CONFIG_CRYPTO_XCBC) += xcbc.o
>  obj-$(CONFIG_CRYPTO_NULL2) += crypto_null.o
> diff --git a/crypto/hkdf.c b/crypto/hkdf.c
> new file mode 100644
> index 000000000000..35a975ed64a8
> --- /dev/null
> +++ b/crypto/hkdf.c
> @@ -0,0 +1,290 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +/*
> + * RFC 5869 Key-derivation function
> + *

People don't know what RFC xyz is.  Please be more explicit than just the RFC
number, e.g.

"HKDF: HMAC-based Extract-and-Expand Key Derivation Function (RFC 5869)"

> + * Copyright (C) 2019, Stephan Mueller <smueller@chronox.de>
> + */
> +
> +/*
> + * The HKDF extract phase is applied with crypto_rng_reset().
> + * The HKDF expand phase is applied with crypto_rng_generate().
> + *
> + * NOTE: In-place cipher operations are not supported.
> + */

What does an "in-place cipher operation" mean in this context?  That the 'info'
buffer must not overlap the 'dst' buffer?  Maybe crypto_rng_generate() should
check that for all crypto_rngs?  Or is it different for different crypto_rngs?

> +
> +#include <linux/module.h>
> +#include <crypto/rng.h>
> +#include <crypto/internal/rng.h>
> +#include <crypto/hash.h>
> +#include <crypto/internal/hash.h>
> +#include <linux/rtnetlink.h>
> +
> +struct crypto_hkdf_ctx {
> +	struct crypto_shash *extract_kmd;
> +	struct crypto_shash *expand_kmd;
> +};
> +
> +#define CRYPTO_HKDF_MAX_DIGESTSIZE	64
> +
> +/*
> + * HKDF expand phase
> + */
> +static int crypto_hkdf_random(struct crypto_rng *rng,
> +			      const u8 *info, unsigned int infolen,
> +			      u8 *dst, unsigned int dlen)

Why call it crypto_hkdf_random() instead of crypto_hkdf_generate()?  The latter
would match rng_alg::generate.

> +{
> +	struct crypto_hkdf_ctx *ctx = crypto_tfm_ctx(crypto_rng_tfm(rng));

const

> +	struct crypto_shash *expand_kmd = ctx->expand_kmd;
> +	SHASH_DESC_ON_STACK(desc, expand_kmd);

> +	unsigned int h = crypto_shash_digestsize(expand_kmd);

const

> +	int err = 0;
> +	u8 *dst_orig = dst;
> +	const u8 *prev = NULL;

> +	uint8_t ctr = 0x01;

u8 instead of uint8_t

> +
> +	if (dlen > h * 255)
> +		return -EINVAL;
> +
> +	desc->tfm = expand_kmd;

> +	desc->flags = crypto_shash_get_flags(expand_kmd) &
> +		      CRYPTO_TFM_REQ_MAY_SLEEP;

This line setting desc->flags doesn't make sense.  How is the user meant to
control whether crypto_rng_generate() can sleep or not?  Or can it always sleep?
Either way this part is wrong since the user can't get access to the HMAC tfm to
set this flag being checked for.

> +
> +	/* T(1) and following */
> +	while (dlen) {
> +		err = crypto_shash_init(desc);
> +		if (err)
> +			goto out;
> +
> +		if (prev) {
> +			err = crypto_shash_update(desc, prev, h);
> +			if (err)
> +				goto out;
> +		}
> +
> +		if (info) {
> +			err = crypto_shash_update(desc, info, infolen);
> +			if (err)
> +				goto out;
> +		}
> +
> +		if (dlen < h) {
> +			u8 tmpbuffer[CRYPTO_HKDF_MAX_DIGESTSIZE];
> +
> +			err = crypto_shash_finup(desc, &ctr, 1, tmpbuffer);
> +			if (err)
> +				goto out;
> +			memcpy(dst, tmpbuffer, dlen);
> +			memzero_explicit(tmpbuffer, h);
> +			goto out;
> +		} else {

No need for the 'else'.

> +			err = crypto_shash_finup(desc, &ctr, 1, dst);
> +			if (err)
> +				goto out;
> +
> +			prev = dst;
> +			dst += h;
> +			dlen -= h;
> +			ctr++;
> +		}
> +	}
> +
> +out:
> +	if (err)
> +		memzero_explicit(dst_orig, dlen);
> +	shash_desc_zero(desc);
> +	return err;
> +}
> +
> +/*
> + * HKDF extract phase.
> + *
> + * The seed is defined to be a concatenation of the salt and the IKM.
> + * The data buffer is pre-pended by an rtattr which provides an u32 value
> + * with the length of the salt. Thus, the buffer length - salt length is the
> + * IKM length.
> + */
> +static int crypto_hkdf_seed(struct crypto_rng *rng,
> +			    const u8 *seed, unsigned int slen)
> +{
> +	struct crypto_hkdf_ctx *ctx = crypto_tfm_ctx(crypto_rng_tfm(rng));

const

> +	struct crypto_shash *extract_kmd = ctx->extract_kmd;
> +	struct crypto_shash *expand_kmd = ctx->expand_kmd;
> +	struct rtattr *rta = (struct rtattr *)seed;
> +	SHASH_DESC_ON_STACK(desc, extract_kmd);
> +	u32 saltlen;
> +	unsigned int h = crypto_shash_digestsize(extract_kmd);
> +	int err;
> +	const uint8_t null_salt[CRYPTO_HKDF_MAX_DIGESTSIZE] = { 0 };

static const

> +	u8 prk[CRYPTO_HKDF_MAX_DIGESTSIZE] = { 0 };

No need to initialize this.

> +
> +	/* Require aligned buffer to directly read out saltlen below */
> +	if (WARN_ON((unsigned long)seed & (sizeof(saltlen) - 1)))
> +		return -EINVAL;
> +
> +	if (!RTA_OK(rta, slen))
> +		return -EINVAL;
> +	if (rta->rta_type != 1)
> +		return -EINVAL;
> +	if (RTA_PAYLOAD(rta) < sizeof(saltlen))
> +		return -EINVAL;
> +	saltlen = *((u32 *)RTA_DATA(rta));

I'm guessing you copied the weird "length as a rtattr payload" approach from the
authenc template.  I think it's not necessary.  And it's overly error-prone, as
shown by the authenc template getting the parsing wrong for years and you making
the exact same mistake again here...
(See https://patchwork.kernel.org/patch/10732803/)  How about just using a u32
at the beginning without the 'rtattr' preceding it?

Also it should use get_unaligned() so there is no alignment requirement the
caller has to comply with.

> +
> +	seed += RTA_ALIGN(rta->rta_len);
> +	slen -= RTA_ALIGN(rta->rta_len);
> +
> +	if (slen < saltlen)
> +		return -EINVAL;
> +

> +	desc->tfm = extract_kmd;

desc->flags needs to be set.

> +
> +	/* Set the salt as HMAC key */
> +	if (saltlen)
> +		err = crypto_shash_setkey(extract_kmd, seed, saltlen);
> +	else
> +		err = crypto_shash_setkey(extract_kmd, null_salt, h);
> +	if (err)
> +		return err;
> +
> +	/* Extract the PRK */
> +	err = crypto_shash_digest(desc, seed + saltlen, slen - saltlen, prk);
> +	if (err)
> +		goto err;
> +
> +	/* Set the PRK for the expand phase */
> +	err = crypto_shash_setkey(expand_kmd, prk, h);
> +	if (err)
> +		goto err;
> +
> +err:
> +	shash_desc_zero(desc);
> +	memzero_explicit(prk, h);
> +	return err;
> +}
> +
> +static int crypto_hkdf_init_tfm(struct crypto_tfm *tfm)
> +{
> +	struct crypto_instance *inst = crypto_tfm_alg_instance(tfm);
> +	struct crypto_shash_spawn *spawn = crypto_instance_ctx(inst);
> +	struct crypto_hkdf_ctx *ctx = crypto_tfm_ctx(tfm);
> +	struct crypto_shash *extract_kmd = NULL, *expand_kmd = NULL;
> +	unsigned int ds;
> +
> +	extract_kmd = crypto_spawn_shash(spawn);
> +	if (IS_ERR(extract_kmd))
> +		return PTR_ERR(extract_kmd);
> +
> +	expand_kmd = crypto_spawn_shash(spawn);
> +	if (IS_ERR(expand_kmd)) {
> +		crypto_free_shash(extract_kmd);
> +		return PTR_ERR(expand_kmd);
> +	}
> +
> +	ds = crypto_shash_digestsize(extract_kmd);
> +	/* Hashes with no digest size are not allowed for KDFs. */
> +	if (!ds || ds > CRYPTO_HKDF_MAX_DIGESTSIZE) {
> +		crypto_free_shash(extract_kmd);
> +		crypto_free_shash(expand_kmd);
> +		return -EOPNOTSUPP;
> +	}

The digest size should be validated when instantiating the template, not here.

> +
> +	ctx->extract_kmd = extract_kmd;
> +	ctx->expand_kmd = expand_kmd;
> +
> +	return 0;
> +}
> +
> +static void crypto_hkdf_exit_tfm(struct crypto_tfm *tfm)
> +{
> +	struct crypto_hkdf_ctx *ctx = crypto_tfm_ctx(tfm);
> +
> +	crypto_free_shash(ctx->extract_kmd);
> +	crypto_free_shash(ctx->expand_kmd);
> +}
> +
> +static void crypto_kdf_free(struct rng_instance *inst)
> +{
> +	crypto_drop_spawn(rng_instance_ctx(inst));
> +	kfree(inst);
> +}
> +
> +static int crypto_hkdf_create(struct crypto_template *tmpl, struct rtattr **tb)
> +{
> +	struct rng_instance *inst;
> +	struct crypto_alg *alg;
> +	struct shash_alg *salg;
> +	int err;
> +	unsigned int ds, ss;
> +
> +	err = crypto_check_attr_type(tb, CRYPTO_ALG_TYPE_RNG);
> +	if (err)
> +		return err;
> +
> +	salg = shash_attr_alg(tb[1], 0, 0);
> +	if (IS_ERR(salg))
> +		return PTR_ERR(salg);
> +
> +	ds = salg->digestsize;
> +	ss = salg->statesize;

I don't see what the 'statesize' is needed for.

> +	alg = &salg->base;

Check here that the underlying algorithm really is "hmac(" something?

Alternatively it may be a good idea to simplify usage by making the template
just take the unkeyed hash directly, like "hkdf(sha512)".  And if any users
really need to specify a specific HMAC implementation then another template
usable as "hkdf_base(hmac(sha512))" could be added later.

> +
> +	inst = rng_alloc_instance("hkdf", alg);
> +	err = PTR_ERR(inst);
> +	if (IS_ERR(inst))
> +		goto out_put_alg;
> +
> +	err = crypto_init_shash_spawn(rng_instance_ctx(inst), salg,
> +				      rng_crypto_instance(inst));
> +	if (err)
> +		goto out_free_inst;

This error path calls crypto_drop_spawn() without a prior successful
crypto_init_spawn().

> +
> +	inst->alg.base.cra_priority	= alg->cra_priority;
> +	inst->alg.base.cra_blocksize	= alg->cra_blocksize;
> +	inst->alg.base.cra_alignmask	= alg->cra_alignmask;
> +
> +	inst->alg.generate		= crypto_hkdf_random;
> +	inst->alg.seed			= crypto_hkdf_seed;
> +	inst->alg.seedsize		= ds;

What does the seedsize mean here, given that crypto_hkdf_seed() actually takes a
variable length seed?

> +
> +	inst->alg.base.cra_init		= crypto_hkdf_init_tfm;
> +	inst->alg.base.cra_exit		= crypto_hkdf_exit_tfm;

> +	inst->alg.base.cra_ctxsize	= ALIGN(sizeof(struct crypto_hkdf_ctx) +
> +					  ss * 2, crypto_tfm_ctx_alignment());

Why isn't this simply sizeof(struct crypto_hkdf_ctx)?

> +
> +	inst->free			= crypto_kdf_free;
> +
> +	err = rng_register_instance(tmpl, inst);
> +
> +	if (err) {
> +out_free_inst:
> +		crypto_kdf_free(inst);
> +	}
> +
> +out_put_alg:
> +	crypto_mod_put(alg);
> +	return err;
> +}
> +
> +static struct crypto_template crypto_hkdf_tmpl = {
> +	.name = "hkdf",
> +	.create = crypto_hkdf_create,
> +	.module = THIS_MODULE,
> +};
> +
> +static int __init crypto_hkdf_init(void)
> +{
> +	return crypto_register_template(&crypto_hkdf_tmpl);
> +}
> +
> +static void __exit crypto_hkdf_exit(void)
> +{
> +	crypto_unregister_template(&crypto_hkdf_tmpl);
> +}
> +
> +module_init(crypto_hkdf_init);
> +module_exit(crypto_hkdf_exit);
> +
> +MODULE_LICENSE("GPL");

MODULE_LICENSE("GPL") means GPLv2+ but the SPDX header says GPLv2 only.

> +MODULE_AUTHOR("Stephan Mueller <smueller@chronox.de>");
> +MODULE_DESCRIPTION("Key Derivation Function according to RFC 5869");

Mention "HKDF" in the module description?

> +MODULE_ALIAS_CRYPTO("hkdf");
> -- 
> 2.20.1

Thanks!

- Eric
Herbert Xu Jan. 12, 2019, 9:55 a.m. UTC | #2
On Fri, Jan 11, 2019 at 09:12:54PM -0800, Eric Biggers wrote:
> Hi Stephan,
> 
> On Fri, Jan 11, 2019 at 08:10:39PM +0100, Stephan Müller wrote:
> > The RFC5869 compliant Key Derivation Function is implemented as a
> > random number generator considering that it behaves like a deterministic
> > RNG.
> > 
> 
> Thanks for the proof of concept!  I guess it ended up okay.  But can you explain
> more the benefits of using the crypto_rng interface, as opposed to just some
> crypto_hkdf_*() helper functions that are exported for modules to use?

I agree.  I see no benefit in adding this through the RNG API as
opposed to just providing it as a helper.  If some form of hardware
acceleration were to eventuate in the future we could always revisit
this.

Cheers,
Stephan Mueller Jan. 13, 2019, 7:56 a.m. UTC | #3
Am Samstag, 12. Januar 2019, 10:55:35 CET schrieb Herbert Xu:

Hi Herbert,

> On Fri, Jan 11, 2019 at 09:12:54PM -0800, Eric Biggers wrote:
> > Hi Stephan,
> > 
> > On Fri, Jan 11, 2019 at 08:10:39PM +0100, Stephan Müller wrote:
> > > The RFC5869 compliant Key Derivation Function is implemented as a
> > > random number generator considering that it behaves like a deterministic
> > > RNG.
> > 
> > Thanks for the proof of concept!  I guess it ended up okay.  But can you
> > explain more the benefits of using the crypto_rng interface, as opposed
> > to just some crypto_hkdf_*() helper functions that are exported for
> > modules to use?
> I agree.  I see no benefit in adding this through the RNG API as
> opposed to just providing it as a helper.  If some form of hardware
> acceleration were to eventuate in the future we could always revisit
> this.

The advantages for using the kernel crypto API to add KDFs as opposed to 
adding helper wrappers are the following in my view:

- employment of the kernel crypto API testmgr - invocation of the testmgr is 
transparent and thus already provided without any additional code to link to 
it

- FIPS 140-2 compliance: To mark a KDF as FIPS 140-2 approved cipher, it must 
be subject to a known-answer self test (implemented by the testmgr) as well as 
to an enforcement of the integrity check verification. In FIPS 140-2 mode, the 
kernel crypto API panic()s when a kernel crypto API module is loaded and its 
signature does not check out. As this is only relevant for crypto modules (and 
not arbitrary other kernel modules), this is implemented with the invocations 
the crypto_register_alg as well as crypto_register_template functions. Thus, 
when using a wrapper code to implement the KDF, they can per definition not be 
FIPS 140-2 approved.

- The invoker of a KDF has one consistent API. This implies that the KDF 
selection now becomes more of a "configuration" choice. For example, when you 
look at the KDF use case for the keys subsystem (security/keys/dh.c), 
selecting the type of KDF would only necessitate a change of a string 
referencing the KDF. A lot of people somehow favor the extract-and-expand KDFs 
over the traditional KDFs. Now, that the RFC5869 HKDF is also approved as per 
SP800-56A rev3, I could see that folks may want to switch to HKDF for the key 
management. When we have a common API, this choice could even be left to the 
caller.

The question may arise why to plug the KDFs into RNGs. The answer is quite 
simple: KDFs are a form of random number generator. In that they take some 
input for initialization (aka seed, salt, key, personalization string). Then 
they produce pseudo-random bit sequences of arbitrary length. Possibly the 
generation operation can be modified by providing some additional input to be 
used by the generation process (aka label, context, info string, additional 
information string). Thus, the RNG interface is a natural fit for the KDFs.

Ciao
Stephan
James Bottomley Jan. 13, 2019, 4:52 p.m. UTC | #4
On Sun, 2019-01-13 at 08:56 +0100, Stephan Müller wrote:
> The question may arise why to plug the KDFs into RNGs. The answer is
> quite simple: KDFs are a form of random number generator. In that
> they take some input for initialization (aka seed, salt, key,
> personalization string). Then they produce pseudo-random bit
> sequences of arbitrary length. Possibly the generation operation can
> be modified by providing some additional input to be used by the
> generation process (aka label, context, info string, additional 
> information string). Thus, the RNG interface is a natural fit for the
> KDFs.

Philosophically, that's quite wrong.  KDFs are a class of pseudorandom
functions (PRFs).  PRFs are designed so that the output is
indistinguishable from a random number generator to observers who don't
know the input but is deterministically useful for participants who do.
 That means the're definitely not RNGs they're functions whose output
is designed to look like the output of an RNG.

I suppose the mathematical thing that distinguishes PRFs and RNGs is
entropy: PRFs have zero entropy because given the same inputs you
expect the same output. Now whether it makes sense to use the RNG API
or not I'll leave that up to the crypto people.  I would have expected
any cryptographic RNG API to be mostly about entropy management (the
Linux core internal one certainly is), but it appears that the one in
crypto isn't.

James
Stephan Mueller Jan. 14, 2019, 9:30 a.m. UTC | #5
Am Samstag, 12. Januar 2019, 06:12:54 CET schrieb Eric Biggers:

Hi Eric,

[...]

> > The extract and expand phases use different instances of the underlying
> > keyed message digest cipher to ensure that while the extraction phase
> > generates a new key for the expansion phase, the cipher for the
> > expansion phase can still be used. This approach is intended to aid
> > multi-threaded uses cases.
> 
> I think you partially misunderstood what I was asking for.  One HMAC tfm is
> sufficient as long as HKDF-Expand is separated from HKDF-Extract, which
> you've done.  So just use one HMAC tfm, and in crypto_hkdf_seed() key it
> with the 'salt', and then afterwards with the 'prk'.

Ok, thanks for the clarification. I will remove the 2nd HMAC TFM then.
> 
> Also everywhere in this patchset, please avoid using the word "cipher" to
> refer to algorithms that are not encryption/decryption.  I know a lot of
> the crypto API docs do this, but I think it is a mistake and confusing. 
> Hash algorithms and KDFs are not "ciphers".

As you wish, I will refer to specific name of the cryptographic operation.

[...]

> > + * NOTE: In-place cipher operations are not supported.
> > + */
> 
> What does an "in-place cipher operation" mean in this context?  That the
> 'info' buffer must not overlap the 'dst' buffer? 

Correct, no overlapping.

> Maybe
> crypto_rng_generate() should check that for all crypto_rngs?  Or is it
> different for different crypto_rngs?

This is the case in general for all KDFs (and even RNGs). It is no technical 
or cryptographic error to have overlapping buffers. The only issue is that the 
result will not match the expected value.

The issue is that the input buffer to the generate function is an input to 
every round of the KDF. If the input and output buffer overlap, starting with 
the 2nd iteration of the KDF, the input is the output of the 1st round. Again, 
I do not think it is a cryptographic error though.

(To support my conclusion: A colleague of mine has proposed an update to the 
HKDF specification where the input data changes for each KDF round. This 
proposal was considered appropriate by one of the authors of HKDF.)

If the requested output is smaller or equal to the output block size of the 
KDF, overlapping buffers are even harmless since the implementation will 
calculate the correct output.

Due to that, I removed the statement. But I am not sure we should add a 
technical block to deny overlapping input/output buffers.

[...]
> > 
> > +	desc->flags = crypto_shash_get_flags(expand_kmd) &
> > +		      CRYPTO_TFM_REQ_MAY_SLEEP;
> 
> This line setting desc->flags doesn't make sense.  How is the user meant to
> control whether crypto_rng_generate() can sleep or not?  Or can it always
> sleep? Either way this part is wrong since the user can't get access to the
> HMAC tfm to set this flag being checked for.

Could you please help me why a user should set this flag? Isn't the 
implementation specifying that flag to allow identifying whether the 
implementation could or could not sleep? Thus, we simply copy the sleeping 
flag from the lower level keyed message digest implementation.

At least that is also the implementation found in crypto/hmac.c.

[...]

> > +		if (dlen < h) {
> > +			u8 tmpbuffer[CRYPTO_HKDF_MAX_DIGESTSIZE];
> > +
> > +			err = crypto_shash_finup(desc, &ctr, 1, tmpbuffer);
> > +			if (err)
> > +				goto out;
> > +			memcpy(dst, tmpbuffer, dlen);
> > +			memzero_explicit(tmpbuffer, h);
> > +			goto out;
> > +		} else {
> 
> No need for the 'else'.

Could you please help me why that else branch is not needed? If the buffer to 
be generated is equal or larger than the output block length of the keyed 
message digest, I would like to directly operate on the output buffer to avoid 
a memcpy.
> 
> > +			err = crypto_shash_finup(desc, &ctr, 1, dst);
> > +			if (err)
> > +				goto out;
> > +
> > +			prev = dst;
> > +			dst += h;
> > +			dlen -= h;
> > +			ctr++;
> > +		}
> > +	}

[...]
> 
> > +	struct crypto_shash *extract_kmd = ctx->extract_kmd;
> > +	struct crypto_shash *expand_kmd = ctx->expand_kmd;
> > +	struct rtattr *rta = (struct rtattr *)seed;
> > +	SHASH_DESC_ON_STACK(desc, extract_kmd);
> > +	u32 saltlen;
> > +	unsigned int h = crypto_shash_digestsize(extract_kmd);
> > +	int err;
> > +	const uint8_t null_salt[CRYPTO_HKDF_MAX_DIGESTSIZE] = { 0 };
> 
> static const
> 

Why would I want to turn that buffer into a static variable? All we need it 
for is in case there is no salt provided.

[...]

> > +
> > +	if (!RTA_OK(rta, slen))
> > +		return -EINVAL;
> > +	if (rta->rta_type != 1)
> > +		return -EINVAL;
> > +	if (RTA_PAYLOAD(rta) < sizeof(saltlen))
> > +		return -EINVAL;
> > +	saltlen = *((u32 *)RTA_DATA(rta));
> 
> I'm guessing you copied the weird "length as a rtattr payload" approach from
> the authenc template.  I think it's not necessary.  And it's overly
> error-prone, as shown by the authenc template getting the parsing wrong for
> years and you making the exact same mistake again here...
> (See https://patchwork.kernel.org/patch/10732803/)  How about just using a
> u32 at the beginning without the 'rtattr' preceding it?

I was not sure whether this approach would be acceptable. I very much would 
love to have a u32 pre-pended only without the RTA business.

I updated the implementation accordingly.
> 
[...]

> 
> > +	alg = &salg->base;
> 
> Check here that the underlying algorithm really is "hmac(" something?

I added a check for the presence of salg->setkey.
> 
> Alternatively it may be a good idea to simplify usage by making the template
> just take the unkeyed hash directly, like "hkdf(sha512)".  And if any users
> really need to specify a specific HMAC implementation then another template
> usable as "hkdf_base(hmac(sha512))" could be added later.
> 

I would not suggest this, because that rounds contrary to the concept of the 
kernel crypto API IMHO. The caller has to provide the wrapping cipher. It is 
perfectly viable to allow a caller to invoke a specific keyed message digest.

[...]

Thank you very much for your code review.

Ciao
Stephan
Eric Biggers Jan. 14, 2019, 5:53 p.m. UTC | #6
On Mon, Jan 14, 2019 at 10:30:39AM +0100, Stephan Müller wrote:
> Am Samstag, 12. Januar 2019, 06:12:54 CET schrieb Eric Biggers:
> 
> Hi Eric,
> 
> [...]
> 
> > > The extract and expand phases use different instances of the underlying
> > > keyed message digest cipher to ensure that while the extraction phase
> > > generates a new key for the expansion phase, the cipher for the
> > > expansion phase can still be used. This approach is intended to aid
> > > multi-threaded uses cases.
> > 
> > I think you partially misunderstood what I was asking for.  One HMAC tfm is
> > sufficient as long as HKDF-Expand is separated from HKDF-Extract, which
> > you've done.  So just use one HMAC tfm, and in crypto_hkdf_seed() key it
> > with the 'salt', and then afterwards with the 'prk'.
> 
> Ok, thanks for the clarification. I will remove the 2nd HMAC TFM then.
> > 
> > Also everywhere in this patchset, please avoid using the word "cipher" to
> > refer to algorithms that are not encryption/decryption.  I know a lot of
> > the crypto API docs do this, but I think it is a mistake and confusing. 
> > Hash algorithms and KDFs are not "ciphers".
> 
> As you wish, I will refer to specific name of the cryptographic operation.
> 
> [...]
> 
> > > + * NOTE: In-place cipher operations are not supported.
> > > + */
> > 
> > What does an "in-place cipher operation" mean in this context?  That the
> > 'info' buffer must not overlap the 'dst' buffer? 
> 
> Correct, no overlapping.
> 
> > Maybe
> > crypto_rng_generate() should check that for all crypto_rngs?  Or is it
> > different for different crypto_rngs?
> 
> This is the case in general for all KDFs (and even RNGs). It is no technical 
> or cryptographic error to have overlapping buffers. The only issue is that the 
> result will not match the expected value.
> 
> The issue is that the input buffer to the generate function is an input to 
> every round of the KDF. If the input and output buffer overlap, starting with 
> the 2nd iteration of the KDF, the input is the output of the 1st round. Again, 
> I do not think it is a cryptographic error though.
> 
> (To support my conclusion: A colleague of mine has proposed an update to the 
> HKDF specification where the input data changes for each KDF round. This 
> proposal was considered appropriate by one of the authors of HKDF.)
> 
> If the requested output is smaller or equal to the output block size of the 
> KDF, overlapping buffers are even harmless since the implementation will 
> calculate the correct output.
> 
> Due to that, I removed the statement. But I am not sure we should add a 
> technical block to deny overlapping input/output buffers.
> 
> [...]
> > > 
> > > +	desc->flags = crypto_shash_get_flags(expand_kmd) &
> > > +		      CRYPTO_TFM_REQ_MAY_SLEEP;
> > 
> > This line setting desc->flags doesn't make sense.  How is the user meant to
> > control whether crypto_rng_generate() can sleep or not?  Or can it always
> > sleep? Either way this part is wrong since the user can't get access to the
> > HMAC tfm to set this flag being checked for.
> 
> Could you please help me why a user should set this flag? Isn't the 
> implementation specifying that flag to allow identifying whether the 
> implementation could or could not sleep? Thus, we simply copy the sleeping 
> flag from the lower level keyed message digest implementation.
> 
> At least that is also the implementation found in crypto/hmac.c.
> 
> [...]

Whether the crypto_shash* stuff can sleep is controlled on a per-request basis,
not a per-implementation basis.  So I don't understand what you are talking
about here.

> 
> > > +		if (dlen < h) {
> > > +			u8 tmpbuffer[CRYPTO_HKDF_MAX_DIGESTSIZE];
> > > +
> > > +			err = crypto_shash_finup(desc, &ctr, 1, tmpbuffer);
> > > +			if (err)
> > > +				goto out;
> > > +			memcpy(dst, tmpbuffer, dlen);
> > > +			memzero_explicit(tmpbuffer, h);
> > > +			goto out;
> > > +		} else {
> > 
> > No need for the 'else'.
> 
> Could you please help me why that else branch is not needed? If the buffer to 
> be generated is equal or larger than the output block length of the keyed 
> message digest, I would like to directly operate on the output buffer to avoid 
> a memcpy.

I'm simply saying you don't need the 'else' keyword as the previous block ends
with a goto.

> > 
> > > +			err = crypto_shash_finup(desc, &ctr, 1, dst);
> > > +			if (err)
> > > +				goto out;
> > > +
> > > +			prev = dst;
> > > +			dst += h;
> > > +			dlen -= h;
> > > +			ctr++;
> > > +		}
> > > +	}
> 
> [...]
> > 
> > > +	struct crypto_shash *extract_kmd = ctx->extract_kmd;
> > > +	struct crypto_shash *expand_kmd = ctx->expand_kmd;
> > > +	struct rtattr *rta = (struct rtattr *)seed;
> > > +	SHASH_DESC_ON_STACK(desc, extract_kmd);
> > > +	u32 saltlen;
> > > +	unsigned int h = crypto_shash_digestsize(extract_kmd);
> > > +	int err;
> > > +	const uint8_t null_salt[CRYPTO_HKDF_MAX_DIGESTSIZE] = { 0 };
> > 
> > static const
> > 
> 
> Why would I want to turn that buffer into a static variable? All we need it 
> for is in case there is no salt provided.
> 
> [...]
> 
> > > +
> > > +	if (!RTA_OK(rta, slen))
> > > +		return -EINVAL;
> > > +	if (rta->rta_type != 1)
> > > +		return -EINVAL;
> > > +	if (RTA_PAYLOAD(rta) < sizeof(saltlen))
> > > +		return -EINVAL;
> > > +	saltlen = *((u32 *)RTA_DATA(rta));
> > 
> > I'm guessing you copied the weird "length as a rtattr payload" approach from
> > the authenc template.  I think it's not necessary.  And it's overly
> > error-prone, as shown by the authenc template getting the parsing wrong for
> > years and you making the exact same mistake again here...
> > (See https://patchwork.kernel.org/patch/10732803/)  How about just using a
> > u32 at the beginning without the 'rtattr' preceding it?
> 
> I was not sure whether this approach would be acceptable. I very much would 
> love to have a u32 pre-pended only without the RTA business.
> 
> I updated the implementation accordingly.
> > 
> [...]
> 
> > 
> > > +	alg = &salg->base;
> > 
> > Check here that the underlying algorithm really is "hmac(" something?
> 
> I added a check for the presence of salg->setkey.
> > 
> > Alternatively it may be a good idea to simplify usage by making the template
> > just take the unkeyed hash directly, like "hkdf(sha512)".  And if any users
> > really need to specify a specific HMAC implementation then another template
> > usable as "hkdf_base(hmac(sha512))" could be added later.
> > 
> 
> I would not suggest this, because that rounds contrary to the concept of the 
> kernel crypto API IMHO. The caller has to provide the wrapping cipher. It is 
> perfectly viable to allow a caller to invoke a specific keyed message digest.
> 

Sure, but it would not conform to the HKDF specification.  Are you sure it is
okay to specify an arbitrary keyed hash?

> [...]
> 
> Thank you very much for your code review.
> 
> Ciao
> Stephan
> 
> 

- Eric
Stephan Mueller Jan. 14, 2019, 6:44 p.m. UTC | #7
Am Montag, 14. Januar 2019, 18:53:16 CET schrieb Eric Biggers:

Hi Eric,

> > I would not suggest this, because that rounds contrary to the concept of
> > the kernel crypto API IMHO. The caller has to provide the wrapping
> > cipher. It is perfectly viable to allow a caller to invoke a specific
> > keyed message digest.
> Sure, but it would not conform to the HKDF specification.  Are you sure it
> is okay to specify an arbitrary keyed hash?

Technically, I see no issue why this should not be possible. You see that with 
the SP800-108 KDF implementations where using CMAC is perfectly legal (and 
which I also test).

Though, using another keyed hash implementation like CMAC is not covered by 
the HKDF spec. If a caller would use hkdf(cmac(aes)), it would produce 
cryptographically strong values. Though this implementation does not conform 
to any standard. I do not think we should prevent a caller to select such 
combination in the kernel crypto API.

IMHO there would even be valid reasons why one would use cmac(aes) for a kdf. 
For example, when you would want to use a hardware AES which somehow also 
employs a hardware key that is inaccessible to software in order to tie the 
KDF result to the local hardware. This could even be a valid use case for Ext4 
FBE encryption where you derive a key. The KDF could be used to link the 
derived key to the local hardware to prevent the encrypted data could be 
copied to another system and decrypted successfully there.

Ciao
Stephan

Patch
diff mbox series

diff --git a/crypto/Kconfig b/crypto/Kconfig
index cc80d89e0cf5..0eee5e129fa3 100644
--- a/crypto/Kconfig
+++ b/crypto/Kconfig
@@ -568,6 +568,12 @@  config CRYPTO_KDF
 	  Support for KDF compliant to SP800-108. All three types of
 	  KDF specified in SP800-108 are implemented.
 
+config CRYPTO_HKDF
+	tristate "HMAC-based Extract-and expand Key Derivation Function"
+	select CRYPTO_RNG
+	help
+	  Support for KDF compliant to RFC5869.
+
 config CRYPTO_XCBC
 	tristate "XCBC support"
 	select CRYPTO_HASH
diff --git a/crypto/Makefile b/crypto/Makefile
index 69a0bb64b0ac..6bbb0a4dea13 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -59,6 +59,7 @@  crypto_user-$(CONFIG_CRYPTO_STATS) += crypto_user_stat.o
 obj-$(CONFIG_CRYPTO_CMAC) += cmac.o
 obj-$(CONFIG_CRYPTO_HMAC) += hmac.o
 obj-$(CONFIG_CRYPTO_KDF) += kdf.o
+obj-$(CONFIG_CRYPTO_HKDF) += hkdf.o
 obj-$(CONFIG_CRYPTO_VMAC) += vmac.o
 obj-$(CONFIG_CRYPTO_XCBC) += xcbc.o
 obj-$(CONFIG_CRYPTO_NULL2) += crypto_null.o
diff --git a/crypto/hkdf.c b/crypto/hkdf.c
new file mode 100644
index 000000000000..35a975ed64a8
--- /dev/null
+++ b/crypto/hkdf.c
@@ -0,0 +1,290 @@ 
+// SPDX-License-Identifier: GPL-2.0
+
+/*
+ * RFC 5869 Key-derivation function
+ *
+ * Copyright (C) 2019, Stephan Mueller <smueller@chronox.de>
+ */
+
+/*
+ * The HKDF extract phase is applied with crypto_rng_reset().
+ * The HKDF expand phase is applied with crypto_rng_generate().
+ *
+ * NOTE: In-place cipher operations are not supported.
+ */
+
+#include <linux/module.h>
+#include <crypto/rng.h>
+#include <crypto/internal/rng.h>
+#include <crypto/hash.h>
+#include <crypto/internal/hash.h>
+#include <linux/rtnetlink.h>
+
+struct crypto_hkdf_ctx {
+	struct crypto_shash *extract_kmd;
+	struct crypto_shash *expand_kmd;
+};
+
+#define CRYPTO_HKDF_MAX_DIGESTSIZE	64
+
+/*
+ * HKDF expand phase
+ */
+static int crypto_hkdf_random(struct crypto_rng *rng,
+			      const u8 *info, unsigned int infolen,
+			      u8 *dst, unsigned int dlen)
+{
+	struct crypto_hkdf_ctx *ctx = crypto_tfm_ctx(crypto_rng_tfm(rng));
+	struct crypto_shash *expand_kmd = ctx->expand_kmd;
+	SHASH_DESC_ON_STACK(desc, expand_kmd);
+	unsigned int h = crypto_shash_digestsize(expand_kmd);
+	int err = 0;
+	u8 *dst_orig = dst;
+	const u8 *prev = NULL;
+	uint8_t ctr = 0x01;
+
+	if (dlen > h * 255)
+		return -EINVAL;
+
+	desc->tfm = expand_kmd;
+	desc->flags = crypto_shash_get_flags(expand_kmd) &
+		      CRYPTO_TFM_REQ_MAY_SLEEP;
+
+	/* T(1) and following */
+	while (dlen) {
+		err = crypto_shash_init(desc);
+		if (err)
+			goto out;
+
+		if (prev) {
+			err = crypto_shash_update(desc, prev, h);
+			if (err)
+				goto out;
+		}
+
+		if (info) {
+			err = crypto_shash_update(desc, info, infolen);
+			if (err)
+				goto out;
+		}
+
+		if (dlen < h) {
+			u8 tmpbuffer[CRYPTO_HKDF_MAX_DIGESTSIZE];
+
+			err = crypto_shash_finup(desc, &ctr, 1, tmpbuffer);
+			if (err)
+				goto out;
+			memcpy(dst, tmpbuffer, dlen);
+			memzero_explicit(tmpbuffer, h);
+			goto out;
+		} else {
+			err = crypto_shash_finup(desc, &ctr, 1, dst);
+			if (err)
+				goto out;
+
+			prev = dst;
+			dst += h;
+			dlen -= h;
+			ctr++;
+		}
+	}
+
+out:
+	if (err)
+		memzero_explicit(dst_orig, dlen);
+	shash_desc_zero(desc);
+	return err;
+}
+
+/*
+ * HKDF extract phase.
+ *
+ * The seed is defined to be a concatenation of the salt and the IKM.
+ * The data buffer is pre-pended by an rtattr which provides an u32 value
+ * with the length of the salt. Thus, the buffer length - salt length is the
+ * IKM length.
+ */
+static int crypto_hkdf_seed(struct crypto_rng *rng,
+			    const u8 *seed, unsigned int slen)
+{
+	struct crypto_hkdf_ctx *ctx = crypto_tfm_ctx(crypto_rng_tfm(rng));
+	struct crypto_shash *extract_kmd = ctx->extract_kmd;
+	struct crypto_shash *expand_kmd = ctx->expand_kmd;
+	struct rtattr *rta = (struct rtattr *)seed;
+	SHASH_DESC_ON_STACK(desc, extract_kmd);
+	u32 saltlen;
+	unsigned int h = crypto_shash_digestsize(extract_kmd);
+	int err;
+	const uint8_t null_salt[CRYPTO_HKDF_MAX_DIGESTSIZE] = { 0 };
+	u8 prk[CRYPTO_HKDF_MAX_DIGESTSIZE] = { 0 };
+
+	/* Require aligned buffer to directly read out saltlen below */
+	if (WARN_ON((unsigned long)seed & (sizeof(saltlen) - 1)))
+		return -EINVAL;
+
+	if (!RTA_OK(rta, slen))
+		return -EINVAL;
+	if (rta->rta_type != 1)
+		return -EINVAL;
+	if (RTA_PAYLOAD(rta) < sizeof(saltlen))
+		return -EINVAL;
+	saltlen = *((u32 *)RTA_DATA(rta));
+
+	seed += RTA_ALIGN(rta->rta_len);
+	slen -= RTA_ALIGN(rta->rta_len);
+
+	if (slen < saltlen)
+		return -EINVAL;
+
+	desc->tfm = extract_kmd;
+
+	/* Set the salt as HMAC key */
+	if (saltlen)
+		err = crypto_shash_setkey(extract_kmd, seed, saltlen);
+	else
+		err = crypto_shash_setkey(extract_kmd, null_salt, h);
+	if (err)
+		return err;
+
+	/* Extract the PRK */
+	err = crypto_shash_digest(desc, seed + saltlen, slen - saltlen, prk);
+	if (err)
+		goto err;
+
+	/* Set the PRK for the expand phase */
+	err = crypto_shash_setkey(expand_kmd, prk, h);
+	if (err)
+		goto err;
+
+err:
+	shash_desc_zero(desc);
+	memzero_explicit(prk, h);
+	return err;
+}
+
+static int crypto_hkdf_init_tfm(struct crypto_tfm *tfm)
+{
+	struct crypto_instance *inst = crypto_tfm_alg_instance(tfm);
+	struct crypto_shash_spawn *spawn = crypto_instance_ctx(inst);
+	struct crypto_hkdf_ctx *ctx = crypto_tfm_ctx(tfm);
+	struct crypto_shash *extract_kmd = NULL, *expand_kmd = NULL;
+	unsigned int ds;
+
+	extract_kmd = crypto_spawn_shash(spawn);
+	if (IS_ERR(extract_kmd))
+		return PTR_ERR(extract_kmd);
+
+	expand_kmd = crypto_spawn_shash(spawn);
+	if (IS_ERR(expand_kmd)) {
+		crypto_free_shash(extract_kmd);
+		return PTR_ERR(expand_kmd);
+	}
+
+	ds = crypto_shash_digestsize(extract_kmd);
+	/* Hashes with no digest size are not allowed for KDFs. */
+	if (!ds || ds > CRYPTO_HKDF_MAX_DIGESTSIZE) {
+		crypto_free_shash(extract_kmd);
+		crypto_free_shash(expand_kmd);
+		return -EOPNOTSUPP;
+	}
+
+	ctx->extract_kmd = extract_kmd;
+	ctx->expand_kmd = expand_kmd;
+
+	return 0;
+}
+
+static void crypto_hkdf_exit_tfm(struct crypto_tfm *tfm)
+{
+	struct crypto_hkdf_ctx *ctx = crypto_tfm_ctx(tfm);
+
+	crypto_free_shash(ctx->extract_kmd);
+	crypto_free_shash(ctx->expand_kmd);
+}
+
+static void crypto_kdf_free(struct rng_instance *inst)
+{
+	crypto_drop_spawn(rng_instance_ctx(inst));
+	kfree(inst);
+}
+
+static int crypto_hkdf_create(struct crypto_template *tmpl, struct rtattr **tb)
+{
+	struct rng_instance *inst;
+	struct crypto_alg *alg;
+	struct shash_alg *salg;
+	int err;
+	unsigned int ds, ss;
+
+	err = crypto_check_attr_type(tb, CRYPTO_ALG_TYPE_RNG);
+	if (err)
+		return err;
+
+	salg = shash_attr_alg(tb[1], 0, 0);
+	if (IS_ERR(salg))
+		return PTR_ERR(salg);
+
+	ds = salg->digestsize;
+	ss = salg->statesize;
+	alg = &salg->base;
+
+	inst = rng_alloc_instance("hkdf", alg);
+	err = PTR_ERR(inst);
+	if (IS_ERR(inst))
+		goto out_put_alg;
+
+	err = crypto_init_shash_spawn(rng_instance_ctx(inst), salg,
+				      rng_crypto_instance(inst));
+	if (err)
+		goto out_free_inst;
+
+	inst->alg.base.cra_priority	= alg->cra_priority;
+	inst->alg.base.cra_blocksize	= alg->cra_blocksize;
+	inst->alg.base.cra_alignmask	= alg->cra_alignmask;
+
+	inst->alg.generate		= crypto_hkdf_random;
+	inst->alg.seed			= crypto_hkdf_seed;
+	inst->alg.seedsize		= ds;
+
+	inst->alg.base.cra_init		= crypto_hkdf_init_tfm;
+	inst->alg.base.cra_exit		= crypto_hkdf_exit_tfm;
+	inst->alg.base.cra_ctxsize	= ALIGN(sizeof(struct crypto_hkdf_ctx) +
+					  ss * 2, crypto_tfm_ctx_alignment());
+
+	inst->free			= crypto_kdf_free;
+
+	err = rng_register_instance(tmpl, inst);
+
+	if (err) {
+out_free_inst:
+		crypto_kdf_free(inst);
+	}
+
+out_put_alg:
+	crypto_mod_put(alg);
+	return err;
+}
+
+static struct crypto_template crypto_hkdf_tmpl = {
+	.name = "hkdf",
+	.create = crypto_hkdf_create,
+	.module = THIS_MODULE,
+};
+
+static int __init crypto_hkdf_init(void)
+{
+	return crypto_register_template(&crypto_hkdf_tmpl);
+}
+
+static void __exit crypto_hkdf_exit(void)
+{
+	crypto_unregister_template(&crypto_hkdf_tmpl);
+}
+
+module_init(crypto_hkdf_init);
+module_exit(crypto_hkdf_exit);
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Stephan Mueller <smueller@chronox.de>");
+MODULE_DESCRIPTION("Key Derivation Function according to RFC 5869");
+MODULE_ALIAS_CRYPTO("hkdf");