RE: inconsistent references for HKDF-CTR

I can answer for Windows and not for other libraries. That said, SP 800-108 is pretty easy to layer on top of HMAC so I'm not sure library support matters as much in this case.

The only decisions that SP800-108 leaves to the implementer are the lengths of i (the iteration counter) and L (the output length). The document does say (Section 5, top of page 12) that the KDF must not be used to generate more than 2^32 -1 blocks of output, so 32 bits is a natural choice for i. For L, Windows uses 32 bits - it is a convenient choice across architectures, and we haven't seen a real need to generate more KDF output than this. Also note that due to the restriction on i, it doesn't really make sense to have L be more than 41 bits (assuming SHA512, the largest-output hash function in common use).

Both i and L are represented in little endian because that is consistent with pretty much all protocols (and NIST standards) out there.

I believe that Jim's objections are overstating the situation. There is not much more leeway in SP 800-108 for a crypto implementer to make choices. To address his specific points:


1.       Yes, we implemented the KDF from section 5.1. I don't understand your point about "all of the modes defined here are counter modes" - AFAIK that is the only counter mode KDF in SP 800-108.

2.       I'm not sure how discussion of SP 800-56C is relevant to implementing SP 800-108. Also note that SP 800-56C does not define an algorithm, only a way of thinking about secure KDFs. By the definition of SP 800-56C, the SP 800-108 KDF is a Key Expansion function (this is explicitly stated in SP 800-56C).

3.       SP 800-108 explicitly states that the input to the HMAC is built by concatenation of a number of input parameters which are themselves binary strings. How those input parameters are created is not relevant to the KDF, so I am not sure why this is a KDF implementation decision.

4.       Actually, 32 bits. See above for rationale.

5.       Binary string. And there is no reason to say it cannot include zero bytes. A KDF is a one way function. You can take any binary input parameters and concatenate them in the manner of SP 800-108 to form an input to the HMAC. There is never a case when you need to work backwards from the input of the HMAC to unambiguously parse what Context and Label were used to create that input.

We use this SP800-108 primitive internally in various protocols, including [MS-GKDI]. It's amazing how many uses there are for a primitive like this. The most common use case that we have found is to generate a small number of keys (often 1 but can be up to 3 or 4) and associated IVs and nonces. No single logical operation needs more than that, and if you have multiple logical operations then you can vary Label and Context accordingly.

From: Mark Watson [mailto:watsonm@netflix.com]
Sent: Friday, February 28, 2014 8:01 AM
To: Jim Schaad
Cc: Vijay Bharadwaj; public-webcrypto@w3.org
Subject: Re: inconsistent references for HKDF-CTR

Does anyone else have an opinion on which we should support ? RFC5869, SP800-108, both ?

Vijay - could you say what assumptions you made in your SP800-108 implementation and the rationalle for those ? Were they based on the requirements of pre-existing applications of this KDF ? What is the status of library support more generally ?

...Mark

On Thu, Feb 27, 2014 at 2:23 PM, Jim Schaad <ietf@augustcellars.com<mailto:ietf@augustcellars.com>> wrote:
In order to have done this implementation there a set of decisions that must
have been made.  I would have no problems with documenting these decisions
as part of the description of the algorithm in our specification, however
they do need to be specified.

I am going to assume that the decisions you made are:

1. We are saying that this is the KDF in Counter Mode that is defined in
section 5.1 of SP800-108.  All of the modes defined here are counter modes
so we need to be specific.
2.  I don't know if you implemented the Key Expansion function which is
required by SP800-56C, but is not documented in SP800-108.
3. The value to be process is formed by simple concatenation and not by
something like ASN.1 encoding
4. The lengths of i and L are one byte
5. Label is either a binary string (as you suggest below) or a UTF8 encoded
string.  In all cases it does not encode a trailing zero as that is supplied
by the encoding function.  There is a restriction that needs to be imposed
if we say that Label is a binary array.  Specifically it cannot include a
zero byte.

Jim


> -----Original Message-----
> From: Vijay Bharadwaj [mailto:Vijay.Bharadwaj@microsoft.com<mailto:Vijay.Bharadwaj@microsoft.com>]
> Sent: Thursday, February 27, 2014 12:59 PM
> To: Jim Schaad; 'Mark Watson'; public-webcrypto@w3.org<mailto:public-webcrypto@w3.org>
> Subject: RE: inconsistent references for HKDF-CTR
>
> From an editorial perspective, I think if you are calling it HKDF-CTR then
you
> need to refer to RFC 5869 since that is what uses the HKDF name.
>
> However, as an implementer, we do have SP800-108 implemented in the
> platform and currently no implementation of HKDF. So I would prefer the
> former to be standardized since it is also potentially a little faster
(HKDF is like
> the SP800-108 feedback mode in that the HMAC invocations are serialized).
>
> SP800-108 specifies the Label and Context as binary strings (section 7.4).
So I
> think we should ask for these parameters to be supplied as base64 to avoid
> the encoding issue that Jim points out.
>
> It seems to me that SP800-56C is at best an informational reference here.
It
> defines a general way of thinking about KDFs that includes RFC 5869 and
> SP800-108 but defers to those documents for specific realizations.
>
> -----Original Message-----
> From: Jim Schaad [mailto:ietf@augustcellars.com<mailto:ietf@augustcellars.com>]
> Sent: Thursday, February 27, 2014 11:53 AM
> To: 'Mark Watson'; public-webcrypto@w3.org<mailto:public-webcrypto@w3.org>
> Subject: RE: inconsistent references for HKDF-CTR
>
> First, I will note that both of the algorithms do the Key Extraction step.
> So both of the algorithms will compute
>
> PRK = HMAC-HASH(s, ZZ)
>
> So that portion of the two algorithms is not any different.
>
> I will note that RFC 5869 is complete and has test vectors, however
> SP800-108 does not specify how the encoding of P is to be done.  Thus item
> such as the length of [L] is not specified by the document.
>
> I can implement 5869, I can't do that for SP800-108 without a couple of
> additional items being specified.  You end up needing some additional data
> such as is provided in section 5.9 of SP 800-56B (ASN.1 or concatenation
> encoding of the input).
>
> Jim
>
>
> From: Mark Watson [mailto:watsonm@netflix.com<mailto:watsonm@netflix.com>]
> Sent: Thursday, February 27, 2014 10:00 AM
> To: public-webcrypto@w3.org<mailto:public-webcrypto@w3.org>
> Subject: inconsistent references for HKDF-CTR
>
> https://www.w3.org/Bugs/Public/show_bug.cgi?id=24838
>
> HKDF-CTR references RFC5869, NIST SP800-56C and NIST SP800-108.
>
> These references specify different algorithms.
>
> RFC5869 calculates output keying material as the concatenation of T(i)
i=1, ...,
> N where T(i) = HMAC-Hash(PRK, T(i-1) | info | [i] ) where PRK is a key
derived
> from the base key through an extraction step and [i] is a single octet
> representation of i.
>
> By contrast, SP800-108 calculates the output keying material as the
> concatenation of K(i) i=1,...,N where K(i) := PRF(KI, [i] || Label || 0x00
> || Context || [L] ) where KI is the key derivation key and [L] is the
> || binary
> representation of the number of output bits.
>
> Which reference should we use, or should we support both as separate
> algorithms ?
> ...Mark