Subject: [Cfrg] NIST crypto group and HKDF (and therefore TLS 1.3)

From: "Salz, Rich" <[email-masked]>
Date: Fri, 8 May 2020 20:21:19 +0000

If you don’t care about FIPS-140, just delete this message, and avoid the temptation to argue how bad it is.

NIST SP 800-56C (Recommendation for Key-Derivation Methods in Key-Establishment Schemes) is currently a draft in review. The document is at https://csrc.nist.gov/publications/detail/sp/800-56c/rev-2/draft  Email comments can be sent to [email-masked] with a deadline of May 15.  That is not a lot of time.  The NIST crypto group is currently unlikely to include HKDF, which means that TLS 1.3 would not be part of FIPS. The CMVP folks at NIST understand this, and agree that this would be bad; they are looking at adding it, perhaps via an Implementation Guidance update.

If you have a view of HKDF (and perhaps TLS 1.3), I strongly encourage you to comment at the above address.  Please do not comment here. I know that many members of industry and academia have been involved with TLS 1.3, and performed security analysis of it. If you are one of those people, *please* send email and ask the NIST Crypto Team to reconsider.

Thank you.
	/r$

---

From: Dan Brown <[email-masked]>
Date: Fri, 8 May 2020 20:49:31 +0000

> -----Original Message-----
> From: Cfrg <[email-masked]> On Behalf Of Salz, Rich
> Subject: [Cfrg] NIST crypto group and HKDF (and therefore TLS 1.3)
>
> NIST SP 800-56C (Recommendation for Key-Derivation Methods in Key-
> Establishment Schemes) is currently a draft in review.... with a deadline of
> May 15.  That is not a lot of time.  The NIST crypto group is currently 
> unlikely
> to include HKDF, which means that TLS 1.3 would not be part of FIPS. The
> CMVP folks at NIST understand this, and agree that this would be bad; they 
> are
> looking at adding it, perhaps via an Implementation Guidance update.

[DB] But NIST Draft SP 800-56Cr2 cites RFC 5869, which is HKDF, and says HKDF 
is a version of 56C Section 5.1. So, I had thought that 56C would allow HKDF. 
What am I missing?

----------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: "Salz, Rich" <[email-masked]>
Date: Fri, 8 May 2020 21:08:06 +0000

It cites it, but doesn't include it in the 800-56 doc.

---

From: Dan Brown <[email-masked]>
Date: Fri, 8 May 2020 21:28:15 +0000

> From: Salz, Rich <[email-masked]>
>
> >    [DB] But NIST Draft SP 800-56Cr2 cites RFC 5869, which is HKDF, and 
> > says
> HKDF

To be clear, are you saying that RFC 5869 HKDF is not compatible with 
800-56Cr2?

(I had assumed they were compatible, but just used different notation for the 
same idea.)

Looking just now, I see 800-56C refers to 800-108, whose Section 5.2, KDF in 
Feedback Mode looks really close to HKDF in RFC 5869.  I see the same overall 
design, but some different orderings of inputs, which could cause non-interop. 
Is that the case?

---

From: John Bradley <[email-masked]>
Date: Fri, 8 May 2020 17:50:06 -0400

COSE RFC8152 uses RFC5869 HKDF in all of its key aggrement alsgs. eg the
popular alg -25 ECDH-ES + HKDF-256

COSE becoming widely used in many protocols like Fido2/WebAutn.

HKDF not being certifiable by the CMVP would definatly suck for some.

I also mistakenly assumed that it would be certifiable.

John B.

On 5/8/2020 4:21 PM, Salz, Rich wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Yevgeniy Dodis <[email-masked]>
Date: Fri, 8 May 2020 17:52:56 -0400

Dear all.

I just now noticed the call for comment for SP-800-56c. Please note
the state-of-the-art paper
on seedless randomness extraction in the recent CRYPTO'19 paper by
Sandro Coretti, Harish Karthikeyan, Stefano Tessaro and myself:
"Seedless Fruit is the Sweetest: Random Number Generation, Revisited",

https://cs.nyu.edu/~dodis/ps/seedless.pdf

Along its results, it strongly advises AGAINST using CBC-mode, such as
AES-CMAC, for
randomness extraction. It also gives very clean randomness extraction
modules based on
existing functions, such as SHA2 and SHA3, and also analyzes HKDF.

I (and likely my co-authors, cc'ed) will be happy to work with NIST on
making sure they follow state-of-the-art recommendation validated by
the top conferences such as CRYPTO. I admit I did not read the
document in detail, but it looks like it does not include any of the
optimized constructions from our paper, but still includes (at least
theoretically) insecure CMAC mode.

Can somebody recommend a proper course of action if my suspicion is correct?

Yevgeniy

---

From: "Salz, Rich" <[email-masked]>
Date: Sat, 9 May 2020 13:07:35 +0000

Sorry for the confusion I caused.

HKDF is part of SP 800-56C.  NIST says that what TLS 1.3 does isn't quite the same, and therefore will not be covered by 56C. NIST wants to get TLS 1.3 validated for FIPS, and is currently trying to figure out how to do so.  The comment period for 56C closes Friday, and getting the TLS 1.3 KDF accepted into that is one way to get TLS 1.3 into FIPS.

Hope this helps clear things up.

---

From: Watson Ladd <[email-masked]>
Date: Sat, 9 May 2020 11:40:49 -0400

On Sat, May 9, 2020 at 9:08 AM Salz, Rich <rsalz=[email-masked]>
wrote:
> HKDF is part of SP 800-56C.  NIST says that what TLS 1.3 does isn't quite
the same, and therefore will not be covered by 56C. NIST wants to get TLS
1.3 validated for FIPS, and is currently trying to figure out how to do
so.  The comment period for 56C closes Friday, and getting the TLS 1.3 KDF
accepted into that is one way to get TLS 1.3 into FIPS.

Well, now I'm really confused. Can't NIST look at the spec and ensure they
have documents covering all parts of TLS 1.3 for FIPS?

> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

---

From: Sean Turner <[email-masked]>
Date: Sat, 9 May 2020 19:33:48 -0400

Rich,

Check out SP 800-52r2. Section 3.1 includes the following:

servers … should be configured to negotiate TLS 1.3.

and

Agencies shall support TLS 1.3 by January 1, 2024.

“should” and “shall” are defined in RFC 2119. One could make the case that you are already there ;} If not, then I’m going to guess that SP 800-135r1, which includes a bunch of Application-Specific KDFs (e.g., IKEv2, TLS 1.2) needs a rev.

spt

> On May 9, 2020, at 09:07, Salz, Rich <rsalz=[email-masked]> wrote:
>

---

From: "Dang, Quynh H. (Fed)" <[email-masked]>
Date: Mon, 11 May 2020 12:09:36 +0000

Hi Rich, Sean and all,

1) Traditionally, a HKDF-Extract is used to extract entropy from a DH type shared secret. However, the first HKDF-Extract in the key schedule takes a PSK instead of a DH shared secret.

We don't see security problems with this instance in TLS 1.3. NIST requires the PSK to have efficient amount of entropy (to achieve a security strength required by NIST) when it is externally generated. When it is externally generated, one of NIST's approved random bit generation methods in SP 800-90 series must be used.

When the PSK is a resumption key, then its original key exchange and its key derivation function(s) must meet the security strength desired/required for the PSK.

NIST plans to allow/approve the function in SP 800-133r2, Section 6.3, item # 3 on pages 22 and 23: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-133r2-draft.pdf

2) Traditionally, HKDF is extract-then-expand. However, in TLS 1.3, we have extract-then-multiple expands.

We don't see security problems for this new version of HKDF as specified in TLS 1.3.  NIST plans to approve a general method for this approach in SP 800-56C revision 2, section 5.3: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Cr2-draft.pdf

NIST plans to handle the issues above that way to avoid repeating the work when one or both of the same HKDF instances or new variant(s) for one or both of them is/are used in different application(s).

The other KDFs are already compliant with NIST's existing KDFs.

Regards,
Quynh.
Recommendation for Key-Derivation Methods in Key-Establishment Schemes<https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Cr2-draft.pdf>
23 . Draft NIST Special Publication 800-56C 24 . Revision 2 25 Recommendation for Key-Derivation 26 . Methods in Key-Establishment Schemes 27 . 28 . 29 Elaine Barker 30 Lily Chen 31 Computer Security Division 32 . Information Technology Laboratory
nvlpubs.nist.gov

________________________________
From: Cfrg <[email-masked]> on behalf of Salz, Rich <rsalz=[email-masked]>
Sent: Friday, May 8, 2020 4:21 PM
To: [email-masked] <[email-masked]>; [email-masked] <[email-masked]>
Subject: [Cfrg] NIST crypto group and HKDF (and therefore TLS 1.3)

Thank you.
        /r$

_______________________________________________
Cfrg mailing list
[email-masked]
https://gcc02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg&amp;data=02%7C01%7Cquynh.dang%40nist.gov%7C6ba71a06d50f41e6582508d7f38d7d80%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C637245661358887556&amp;sdata=5DEzorMNakxeh%2Bkb4wYJ00QxyRmcXbsDFm7wlVw9iig%3D&amp;reserved=0

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 11 May 2020 13:16:16 -0400

I will forward this to the official comment address as well.

I don't support making HKDF a NIST standard in its current form because
there is a flaw.

Consider the case in which the initial keying material is formed by
concatenating two items, the second of which is a variable length string.

As currently specified, the values for o_key and i_key are the same for a
key k and that same key with a zero byte concatenated. This might not seem
like a big deal but the whole point of defining common building blocks for
crypto is to eliminate all the bear traps we can.

The problem can be eliminated as follows:

1) Generate i_key by padding the key value with byte x before XORing with
the i_mask

2) Generate o_key by padding the key value with byte y (y <> x) before
XORing with the o_mask

This ensures that the values of o_key and i_key will change if zeros are
appended.

This would require us to issue a revised version of HKDF. But I think we
should do just that. Crypto utility functions should be robust under all
known forms of mistreatment. I am probably not the only person who has
multiple salt inputs to a KDF. Fortunately my unit tests caught the issue.

---

From: Hugo Krawczyk <[email-masked]>
Date: Mon, 11 May 2020 16:36:24 -0400

There is no flaw if you use HMAC and HKDF as intended. See details below.

The bottom line advise is: If you are using related (not random) salt
values in HKDF, you are probably using it with  domain separation
functionality. In HKDF, domain separation is enforced via the info field
not the salt. Read the HKDF RFC and paper for background and rationale.

More below.

> crypto is to eliminate all the bear traps we can.

I assume that by o_key and i_key you mean the key xor-ed with opad and
ipad, respectively. Is that right?
It is true that in HMAC, and then in HKDF, you do not distinguish between a
key K shorter than a block and the same key with appended 0s.
This is OK in HMAC because as a MAC or PRF you must use HMAC with random
keys for which the probability to have the above property (choosing two
keys of different lengths, one  being the prefix of the other) is virtually
0.
For HKDF, this issue applies to the salt value. Salt values (read the RFC)
should either be random or set to the all-zero string. Hence no issue there.

You can read the HKDF paper for extensive rationale for these choices.
https://eprint.iacr.org/2010/264

> This ensures that the values of o_key and i_key will change if zeros are

It will not solve the issue if one of the keys is of a block length
Historical anecdote: The original design of HMAC had the concatenation
scheme as you suggest, Adi Shamir suggested changing it to xoring method
that was eventually adopted (see the Acknowledgment section in the HMAC
1996 paper),
https://link.springer.com/content/pdf/10.1007/3-540-68697-5_1.pdf
So you can see that thought was put into these issues.

> multiple salt inputs to a KDF. Fortunately my unit tests caught the issue.

You should not have multiple salt inputs if they are not independently
random.
If you want to use them for "domain separation", use the info field.

---

From: Hugo Krawczyk <[email-masked]>
Date: Mon, 11 May 2020 17:04:37 -0400

Hi Quynh, see a couple of remarks below,

On Mon, May 11, 2020 at 8:10 AM Dang, Quynh H. (Fed) <quynh.dang=
[email-masked]> wrote:

> Hi Rich, Sean and all,
>
> 1) Traditionally, a HKDF-Extract is used to extract entropy from a DH type
> shared secret. However, the first HKDF-Extract in the key schedule takes a
> PSK instead of a DH shared secret.
>

The whole point of HKDF is to define a KDF that can be applied to different
uses and settings for key derivation. A single KDF mechanism that can
address a DH setting as well as a PSK, or  anything else, with
functionalities of PRF, random oracle, randomness extraction, etc., and
with some theoretical basis. Btw, TLS 1.3 is an application where
essentially all these aspects of HKDF show up.

NIST has adopted the view of HKDF in a very general sense via
the standardization of the extract-then-expand approach at the basis of
HKDF . This applies equally to extracting entropy from a DH value, the
output of an RNG, a PSK, etc.

>
> We don't see security problems with this instance in TLS 1.3. NIST
> requires the PSK to have efficient amount of entropy (to achieve a security
> strength required by NIST) when it is externally generated. When it is
> externally generated, one of NIST's approved random bit generation methods
> in SP 800-90 series must be used.
>
> When the PSK is a resumption key, then its original key exchange and its
> key derivation function(s) must meet the security strength desired/required
> for the PSK.
>
> NIST plans to allow/approve the function in SP 800-133r2, Section 6.3,
> item # 3 on pages 22 and 23:
> https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-133r2-draft.pdf
>

The HKDF RFC 5869 says that in the case where the amount of required key
bits, L, is no more than HashLen, one could use PRK directly as the OKM.

In the usage by TLS, you are using the output of extract as a key to a PRF
(implemented as HKDF-expand, essentially HMAC) with multiple, different
inputs (different thanks to the use of the info field) which is perfectly
secure. Also, note that the composition of the extract step in TLS with
each of the subsequent expands can be represented as a full HKDF
application. This was part of the design for cases (maybe  hardware) where
one may have an interface to HKDF but not a separate interface to
the extract and expand steps.

> We don't see security problems for this new version of HKDF as specified
> in TLS 1.3.  NIST plans to approve a general method for this approach in SP
> 800-56C revision 2, section 5.3:
> https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Cr2-draft.pdf
>

Agreed. The above comment summarizes why there should be no security
problems with these mechanisms.

I haven't looked at the revisions. But in previous versions you needed
lawyer skills to go through the language to see that RFC 5869 was indeed
compliant with the NIST recommendation. It would be nice if this time it
would make very explicit that RFC 5869 is compliant with this
Recommendation.

Hugo

>
> NIST plans to handle the issues above that way to avoid repeating the work
> when one or both of the same HKDF instances or new variant(s) for one or
> both of them is/are used in different application(s).
>
> Recommendation for Key-Derivation Methods in Key-Establishment Schemes
> <https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Cr2-draft.pdf>
> 23 . Draft NIST Special Publication 800-56C 24 . Revision 2 25
> Recommendation for Key-Derivation 26 . Methods in Key-Establishment Schemes
> 27 . 28 . 29 Elaine Barker 30 Lily Chen 31 Computer Security Division 32 .
> Information Technology Laboratory
> nvlpubs.nist.gov
>
> ------------------------------
> *From:* Cfrg <[email-masked]> on behalf of Salz, Rich <rsalz=
> [email-masked]>
> *Sent:* Friday, May 8, 2020 4:21 PM
> *To:* [email-masked] <[email-masked]>; [email-masked] <[email-masked]>
> *Subject:* [Cfrg] NIST crypto group and HKDF (and therefore TLS 1.3)
>
> NIST SP 800-56C (Recommendation for Key-Derivation Methods in
> Key-Establishment Schemes) is currently a draft in review. The document is
> at https://csrc.nist.gov/publications/detail/sp/800-56c/rev-2/draft
> Email comments can be sent to [email-masked] with a deadline
> of May 15.  That is not a lot of time.  The NIST crypto group is currently
> unlikely to include HKDF, which means that TLS 1.3 would not be part of
> FIPS. The CMVP folks at NIST understand this, and agree that this would be
> bad; they are looking at adding it, perhaps via an Implementation Guidance
> update.
>
> If you have a view of HKDF (and perhaps TLS 1.3), I strongly encourage you
> to comment at the above address.  Please do not comment here. I know that
> many members of industry and academia have been involved with TLS 1.3, and
> performed security analysis of it. If you are one of those people, *please*
> send email and ask the NIST Crypto Team to reconsider.
>
> Thank you.
>         /r$
>
>
>
> <https://gcc02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg&amp;data=02%7C01%7Cquynh..dang%40nist.gov%7C6ba71a06d50f41e6582508d7f38d7d80%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C637245661358887556&amp;sdata=5DEzorMNakxeh%2Bkb4wYJ00QxyRmcXbsDFm7wlVw9iig%3D&amp;reserved=0>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 12 May 2020 01:49:13 -0400

> There is no flaw if you use HMAC and HKDF as intended. See details below.

One time pads aren't flawed if you use them right. When they become a two
time pad, there is a problem.

My point is that if we are developing schemes that are supposed to be used
as utility building blocks, we need to consider all the ways they might be
used and not just limit ourselves to the ones we expect. That was the
argument made for defining authenticated encryption modes, it holds here as
well.

> not the salt. Read the HKDF RFC and paper for background and rationale.

I am already using the info field for domain separation. I use info to
generate separate keys for encryption, authentication, any IVs etc. by
concatenating the IANA protocol name and the encryption function. So I
don't want to put any more in there.

It is easy enough to fix if you are aware of it. I noticed the issue while
I was implementing HMAC by hand. But the person who is using the function
using a library call (i.e. myself five years from now) might not be aware.

Saying 'read my paper' really isn't an argument. I know the design
rationale. I am saying it is the wrong one for the future. And regardless,
I don't see mention of the issue in section 4.2 of the paper you cite nor
is there mention of the issue in RFC 2104.

If I have to go hunting to find security issues with a standard, that is a
problem in itself.

BTW, the reason it came up with DARE was an attempt to address the problem
of 'encrypting the subject header' and other metadata separately from the
content data. But under the same key. Bearing in mind that we want to be
able to encrypt multiple data items under a single key exchange.

So starting from the result of the key agreement, I add in a per envelope
salt which is typically 128 bits. That allows for erasure of the message by
overwriting the salt value. The main data content is encrypted under a KDF
with the IKM and envelope salt. If additional encrypted data sequences are
required, they are encrypted under the IKM, salt and an additional counter.

Now I can fix my designs, but others won't. Considering the EDS counter to
be an extension to the key led to the unexpected result that the EDS and
content were encrypted with the same key. Now, it is arguably better
considered to be a part of the salt which is where I think the current code
is (have to check). But my general point stands, this should be a utility
function but the Feb 1997 spec does not meet our standards today.

---

From: "Torsten Schütze" <[email-masked]>
Date: Tue, 12 May 2020 13:39:58 +0200

Hi Hugo, hi Quynh,
 
on Monday, 2020-05-11 Hugo Krawzcyk wrote: 
 
> I haven't looked at the revisions. But in previous versions you needed lawyer skills to go through the language to see that RFC 5869 was indeed compliant with the NIST recommendation. It would be nice if this time it would make very explicit that RFC 5869 is compliant with this Recommendation.
 
Indeed. In SP800-56C Rev. 2 draft we have in lines 545, 546: 

"[RFC 5869] specifies a version of the above extraction-then-expansion key-derivation procedure using HMAC for both the extraction and expansion steps."  so one would assume that HKDF according to RFC 5869 is compliant with SP800-56CR2.

However, for key expansion it refers in line 533, 532 to 

"2. Call KDF( K_DK, L, {IV,} FixedInfo ) to obtain DerivedKeyingMaterial or an error indicator (see [SP 800-108] for details)." 

Everything would be fine if we find KDF( K_DK, L, {IV}, FixedInfo) as 

HKDF-Expand(PRK, info, L) -> OKM

The output OKM is calculated as follows:

   N = ceil(L/HashLen)
   T = T(1) | T(2) | T(3) | ... | T(N)
   OKM = first L octets of T

   where:
   T(0) = empty string (zero length)
   T(1) = HMAC-Hash(PRK, T(0) | info | 0x01)
   T(2) = HMAC-Hash(PRK, T(1) | info | 0x02)
   T(3) = HMAC-Hash(PRK, T(2) | info | 0x03)

i.e. the definitions of RFC 5869 in SP800-108. Unfortunately, the closest one could find in SP800-108 is 

5.2 KDF in Feedback Mode

1.  n: = \ceil{L/h}.
2.  If n > 2^{32} -1, then indicate an error and stop.
3.  result(0):= ∅ and K(0):= IV.
4.  For i = 1 to n, do
    a.
        K(i) := PRF (KI, K(i-1) {|| [i]2 }|| Label || 0x00 || Context || [L]2)
    b.
        result(i) := result(i-1) || K(i)
5. Return: K_O := the leftmost L bits of result(n).

With the substitutions PRK = KI, HashLen = h, N = n, T(i) = K(i-1) 0x01, 0x02 = [i]_2, PKM = K_O and info = Label || 0x00 || Context || [L]_2 one is almost there, EXCEPT

- the counter 0x01, 0x02, 0x03 is at the end of the string in HKDF RFC 5869 and right-after the K(i-1), respectively T(i), in SP800-108. At least this gives different results. (This is what already Dan Brown wrote in a recent mail). I don't think this has security implications, but I'm no expert.

- With HKDF, it is only allowed to iterate up to N = 255 as L \le 255 HashLen while in SP800-108 we have n \le 2^{32}-1. 

So, with this interpretation I don't see that HKDF RFC5869 is a concrete instantiation of SP800-56C rev2 draft + SP800-108. At least I couldn't find any official CAVP test vectors for such an HKDF-HMAC-SHA-256 construct. BTW, while we have such test vectors in RFC 5869 for SHA-384 (and SHA-1) there are no such things for SHA-384 or SHA-512, i.e. higher security levels. As a practitioner I would first test my HKDF RFC 5869 implementation if it is allows to iterate above N = 255. BTW, I don't have a good feeling with extracting up to 2^{32}-1 keys from a single IKM.

I would like to hear from NIST if there are any plans to provide CAVP test vectors for HKDF-HMAC-SHA-2 according to RFC 5869. In my opinion, SP800-56C rev2 draft is suboptimal as it refers for a very important component, i.e. key expansion, to another, quite old document.

Torsten

---

From: "Dang, Quynh H. (Fed)" <[email-masked]>
Date: Tue, 12 May 2020 12:04:44 +0000

Hi Torsten,

Thank you for the review. I think the review helps many people to understand the HKDF's spec and its NIST's approval better.

In SP 800-108 (https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-108.pdf, at the end of Section 5. (before 5.1), it says that "  Alternative orders for the input data fields may be used
for different KDFs. " .

And, at the end of the paragraph before that, it says "
One or more of these fixed input data fields may be omitted unless required for
certain purposes as discussed in Section 7.5 and Section 7.6.".

After an extraction step, the output is a pseudorandom key. The KDFs in SP 800-108 are NIST's approved KDFs to derive key(s) from a pseudorandom key.  The purpose of any of these KDFs in SP 800-108 is the same with the purpose of the expansion step. Therefore, they are allowed for being used as expansion steps.

Regards,
Quynh.

________________________________
From: "Torsten Schütze" <[email-masked]>
Sent: Tuesday, May 12, 2020 7:39 AM
To: Hugo Krawczyk <[email-masked]>
Cc: Dang, Quynh H. (Fed) <[email-masked]>; [email-masked] <[email-masked]>; [email-masked] <[email-masked]>; [email-masked] <[email-masked]>
Subject: Re: [Cfrg] NIST crypto group and HKDF (and therefore TLS 1.3)

Hi Hugo, hi Quynh,

   N = ceil(L/HashLen)

   where:

5.2 KDF in Feedback Mode

1.  n: = \ceil{L/h}.

Torsten

---

From: "Torsten Schütze" <[email-masked]>
Date: Tue, 12 May 2020 14:36:01 +0200

Hi Quynh,

thank you for your quick response. I knew that omitting some fields was allowed, but not that permutations are allowed, too. Okay, this makes HKDF RFC 5869 definitely to a NIST SP800-56C rev 2 compliant KDF. But what to do about the CAVP tests or approved test vectors. Couldn't NIST provide for the very often used RFC 5869 HKDF approved test vectors? I coulnd't find any. Only for some older, application specific KDFs. Of course, I can generate them by myself with an independent implementation, but I'm talking about evaluation/approval business here.

Regards 

Torsten

Gesendet: Dienstag, 12. Mai 2020 um 14:04 Uhr
Von: "Dang, Quynh H. (Fed)" <[email-masked]>
An: "Torsten Schütze" <[email-masked]>, "Hugo Krawczyk" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Betreff: Re: [Cfrg] NIST crypto group and HKDF (and therefore TLS 1.3)

Hi Torsten,

 
And, at the end of the paragraph before that, it says "One or more of these fixed input data fields may be omitted unless required for
certain purposes as discussed in Section 7.5 and Section 7.6.".

Regards,
Quynh. 

------------------------------------------------------------

Hi Hugo, hi Quynh,

 

   N = ceil(L/HashLen)

   where:

5.2 KDF in Feedback Mode

1.  n: = \ceil{L/h}.

Torsten

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 12 May 2020 16:02:10 +0000

Good to know, thanks!

Could you clarify, please: does this "permission to permute" apply to the input to the HKDF extractor as well?

SP800-56Cr2 section 5 "Two-Step Key Derivation" (3rd paragraph) requires that "salt" serves as a MAC *key*, and the shared secret Z serves as the "message". I need to reverse these, because HSM devices that do not directly implement HKDF cannot run HMAC in this mode.

If what I'm asking is not allowed - can you please explain why from a *practical* cryptography point of view (and given that the "salt" is neither random nor uniformly distributed)? I.e., what would break or what attacks would become possible?

On 5/12/20, 08:36, "TLS on behalf of "Torsten Schütze"" <[email-masked] on behalf of [email-masked]> wrote:

    Hi Quynh,

    Regards 

    Torsten

    Hi Torsten,

    Regards,
    Quynh. 

    Hi Hugo, hi Quynh,

       N = ceil(L/HashLen)

       where:

    5.2 KDF in Feedback Mode

    1.  n: = \ceil{L/h}.

    Torsten

---

From: Dan Brown <[email-masked]>
Date: Tue, 12 May 2020 16:31:42 +0000

Hi Hugo,

Some curious molehill questions. Please take with a grain of salt.

In short, does HKDF-Extract suffer from related-salt and repeated-IKM?

To elaborate:

Phillip raises a good point below about HMAC suffering from key-extension (by zero bytes).  You are right that this is not a MAC attack, the main intended use of HMAC, but now the scope of HMAC has expanded to non-MAC purposes.   

Surely HMAC has good PRF properties, so non-MAC applications make sense.  For what little it’s worth, I had just presumed that HKDF always used HMAC with the a strong secret key, like a good PRF should.  (I failed to verify this, though.)

But Phillip seems to want to use structured HMAC keys (i.e. not uniformly distributed keys), specifically the salts in HKDF-Extract, I presume.  Under my presumption, this would not be best practice (using structure or related keys).

So, I went to the HKDF RFC, basically expecting to find this clearly disallowed.  Re-reading the RFC, it was unclear to me what kind of salt was allowed. (The eprint might be clearer, but it is longer to find this needle.) Would it (dis)allow the structured salts Phillip described? 

Then, I saw a phrase in the HKDF RFC that salts were unlike IKM, because they could be re-used.  I inferred that IKM was not to be re-used.  If so, related salts should cause no problem for extraction, because a different IKM would always be used.  But might IKM be re-used?  For example, the rare event that TLS client and server both re-use their ECDHE keys.  So, I went to look at TLS 1.3.

In TLS 1.3, HKDF-Extract is used with both structured salts (e.g. 0), and structured IKMs (e.g. 0).  In the end, all is fine, because at least one of the salt or IKM has lots of entropy, and there were no related salts.  (The case HKDF-Extract(0,0) is mentioned in TLS 1.3, but very clearly that this case does not provide security.)  I presume TLS 1.3 designers were adhering to the intended use of HKDF-Extract.  

To summarize, related-salt + repeated-IKM in HKDF-Extract might lead to repeated PRK, right? This could be bad if PRK used in HKDF-Expand to create two identical stream cipher keys.  If two identical authentication keys, perhaps an unexpected replay attack might apply?  Are these a concern?  Is TLS 1.3 fine, mainly because HKDF was used correctly?  Are these related-salts really realistic: would an implementer do this? Do you think better implementer guidance is needed to prevent this type of accident?  

Best regards,

Dan

PS

The HKDF RFC clearly excludes an adversary causing related salts, so that’s good.

I really like both defense in depth and provable security, but I would also like it to be clear that is the main motivation for HKDF in key derivation.  To wit, HMAC itself internally derives two closely-related keys using XOR ipad and XOR opad.   You have proved this turns out fine, despite the relatedness of the two keys, because the robust property of hash function.  My point here, is if we assumed the derived keys are used in robust algorithms, e.g. AES-GCM, could they tolerate simpler ways of deriving keys, i.e. XORing a key with a non-random separation string?  To repeat, I am totally fine to use robust key derivation, like HKDF, but I would want the reason to be clear.  E.g. TLS 1.3 handshake uses HKDF as hedge against possible related-key attacks on the symmetric-key crypto in the record layer, or for better or simpler security proofs (e.g. compared to past key derivation methods).

As many know, hashes were, once upon a time, only used for message digests in signatures. Message-extension in hashes did not result in signature forgery.   But then people naturally wanted to use hashes (as a “utility function” in Phillip’s terms) for a MAC.  But hashes with message extension suffer from MAC forgery. Along came HMAC to the rescue, saving the day, and the rest is history.  (To exaggerate: it is, on a minute scale, repeating;)

From: TLS <[email-masked]> On Behalf Of Phillip Hallam-Baker
Sent: Tuesday, May 12, 2020 1:49 AM
To: Hugo Krawczyk <[email-masked]>
Cc: Dang, Quynh H. (Fed) <quynh.dang=[email-masked]>; [email-masked]; [email-masked]; Salz, Rich <rsalz=[email-masked]>
Subject: Re: [TLS] [Cfrg] NIST crypto group and HKDF (and therefore TLS 1.3)

On Mon, May 11, 2020 at 4:36 PM Hugo Krawczyk <[email-masked] <mailto:[email-masked]> > wrote:

One time pads aren't flawed if you use them right. When they become a two time pad, there is a problem.

My point is that if we are developing schemes that are supposed to be used as utility building blocks, we need to consider all the ways they might be used and not just limit ourselves to the ones we expect. That was the argument made for defining authenticated encryption modes, it holds here as well.

The bottom line advise is: If you are using related (not random) salt values in HKDF, you are probably using it with  domain separation functionality. In HKDF, domain separation is enforced via the info field not the salt. Read the HKDF RFC and paper for background and rationale.

I am already using the info field for domain separation. I use info to generate separate keys for encryption, authentication, any IVs etc. by concatenating the IANA protocol name and the encryption function. So I don't want to put any more in there.

It is easy enough to fix if you are aware of it. I noticed the issue while I was implementing HMAC by hand. But the person who is using the function using a library call (i.e. myself five years from now) might not be aware.

Saying 'read my paper' really isn't an argument. I know the design rationale. I am saying it is the wrong one for the future. And regardless, I don't see mention of the issue in section 4.2 of the paper you cite nor is there mention of the issue in RFC 2104.

If I have to go hunting to find security issues with a standard, that is a problem in itself.

BTW, the reason it came up with DARE was an attempt to address the problem of 'encrypting the subject header' and other metadata separately from the content data. But under the same key. Bearing in mind that we want to be able to encrypt multiple data items under a single key exchange.

So starting from the result of the key agreement, I add in a per envelope salt which is typically 128 bits. That allows for erasure of the message by overwriting the salt value. The main data content is encrypted under a KDF with the IKM and envelope salt. If additional encrypted data sequences are required, they are encrypted under the IKM, salt and an additional counter.

Now I can fix my designs, but others won't. Considering the EDS counter to be an extension to the key led to the unexpected result that the EDS and content were encrypted with the same key. Now, it is arguably better considered to be a part of the salt which is where I think the current code is (have to check). But my general point stands, this should be a utility function but the Feb 1997 spec does not meet our standards today.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 12 May 2020 13:03:49 -0400

On Tue, May 12, 2020 at 12:31 PM Dan Brown <[email-masked]> wrote:

> Phillip raises a good point below about HMAC suffering from key-extension
> (by zero bytes).  You are right that this is not a MAC attack, the main
> intended use of HMAC, but now the scope of HMAC has expanded to non-MAC
> purposes.
>
>
>
> Surely HMAC has good PRF properties, so non-MAC applications make sense.
> For what little it’s worth, I had just presumed that HKDF always used HMAC
> with the a strong secret key, like a good PRF should.  (I failed to verify
> this, though.)
>
>
>
> But Phillip seems to want to use structured HMAC keys (i.e. not uniformly
> distributed keys), specifically the salts in HKDF-Extract, I presume.
> Under my presumption, this would not be best practice (using structure or
> related keys).
>
>
>
> So, I went to the HKDF RFC, basically expecting to find this clearly
> disallowed.  Re-reading the RFC, it was unclear to me what kind of salt was
> allowed. (The eprint might be clearer, but it is longer to find this
> needle.) Would it (dis)allow the structured salts Phillip described?
>

The HMAC RFC is from 1997. While we have revised the spec to add new digest
algorithms, we have never revised the security considerations.

I think we should take the opportunity to level up to our current best
practices rather than relying on the old. Back in 1997 we were still using
DES as the blockcipher but very few folk were talking about the fact that
we should be considering birthday attacks and limiting the amount of
cipherstream generated under a particular key. We do consider that type of
issue today.

The concern I have is not the number of keys generated from a given IKM or
PRK so much as the amount of data those keys are used to encrypt. If I have
a log file with 1 million entries of 120 bytes, am I worse off by
generating 1 million keys from the same IKM or by generating one key and
using different IVs? The second is closer to customary practice but only
because we are considering the KDF as being a completely separate thing
from the block cipher key schedule.

Since I cannot do a key agreement for every log entry, there will be
related keys or repeated keys. The question is which we prefer.

Another application of the same approach is to encrypt a live video stream
and its associated data frame by frame with the intention of retaining
random access, fast forward etc. capabilities. I cannot perform a key
exchange per frame. But I can do a KDF per frame. Regarding the salt input
to the KDF as being a substitute for the IV gives me the performance and
flexibility I need without increasing the amount of data per entry. I just
generate an IV along with my session key.

The whole point of this approach is to construct a mechanism that allows me
to be very sure that every piece of encrypted data is encrypted under a
different key. It is really hard to screw up without it being apparent.

So in summary:

* Consider the NIST certification process to be an opportunity, not a
burden.

* We should revise the RFCs for HMAC and KDF. HMAC in particular needs
proper security considerations.

* We should look at the security of both the individual components and the
composition of the components in a system and require that both be sound as
opposed to allowing either.

* We should propose a simple, backwards compatible means of protecting
against the zero key padding issue on HMAC. One approach is simply
appending a non zero byte to the key. 0x50 is what I plan to use for my
HMAC variant unless someone has a better idea.

---

From: Hugo Krawczyk <[email-masked]>
Date: Tue, 12 May 2020 22:29:28 -0400

> with the a strong secret key, like a good PRF should.  (I failed to verify

If you what you wanted is a PRF, there was no need for HKDF. HMAC is a PRF.
The whole point of HKDF is to transform non-uniform entropy  into strong
(pseudo) random keys. If you had a strong secret key you not need HKDF.

> Under my presumption, this would not be best practice (using structure or

This may be what Philip wants but not what HKDF gives (I too want some
things that even HKDF cannot give me). Not all combinations of keys and
inputs to HMAC produce magic outputs. HKDF was built and analyzed to
identify uses and combinations that go well together for the KDF
functionality. The RFC (and paper) say it clearly: The HMAC key can be
replaced with a random salt (meaning a random but not necessarily secret
value) and if such value is not availalble then the salt (or HMAC key) is
set to 0. If someone wants to use HMAC differently, they are welcome. But
that's not HKDF. They are welcome to analyze their design.

> Then, I saw a phrase in the HKDF RFC that salts were unlike IKM, because
> they could be re-used.  I inferred that IKM was not to be re-used.  If so,
> related salts should cause no problem for extraction, because a different
> IKM would always be used.  But might IKM be re-used?
>

The security of HKDF as an extractor requires IKM values produced by an
application to be fresh and independent . The RFC (section 3.4) and paper
say that clearly.

If you use dependent IKMs then you need to analyze HKDF under random oracle
modeling.  You can use a fixed random oracle setting salt to 0 or a
randomized family with random salts.

For example, the rare event that TLS client and server both re-use their
> ECDHE keys.  So, I went to look at TLS 1.3.
>
>
>
> In TLS 1.3, HKDF-Extract is used with both structured salts (e.g. 0), and
> structured IKMs (e.g. 0).  In the end, all is fine, because at least one of
> the salt or IKM has lots of entropy, and there were no related salts.  (The
> case HKDF-Extract(0,0) is mentioned in TLS 1.3, but very clearly that this
> case does not provide security.)  I presume TLS 1.3 designers were adhering
> to the intended use of HKDF-Extract.
>

Indeed.

>
>
> To summarize, related-salt + repeated-IKM in HKDF-Extract might lead to
> repeated PRK, right?
>
This could be bad if PRK used in HKDF-Expand to create two identical stream
> cipher keys.  If two identical authentication keys, perhaps an unexpected
> replay attack might apply?  Are these a concern?  Is TLS 1.3 fine, mainly
> because HKDF was used correctly?  Are these related-salts really realistic:
> would an implementer do this? Do you think better implementer guidance is
> needed to prevent this type of accident?
>

RFC 5869 gives clear guidance that addresses the issues raised here. One
can expand on it. But if people do not read or follow it then what good it
does? Anyway, I am not opposed to give more guidance of course. But there
is never a way to exhaust what people can think of doing with a
cryptographic function, especially one to which we attach magic powers. For
example, the solution Philip suggested for his problem (appending a fixed
byte) does not fully  solve his problem and leaves others uncovered. For
example, in HKDF, if you choose a salt that is larger than a block size and
then choose a salt that equals the hash of that other salt, you get the
same function even though these were different salts. By saying use random
salt or otherwise set to 0 (and allowing arbitrary inputs through the  info
field) we addressed all these variations and limited other inventive ways
to use the function.

Hugo

> I really like both defense in depth and provable security, but I would
> also like it to be clear that is the main motivation for HKDF in key
> derivation.  To wit, HMAC itself internally derives two closely-related
> keys using XOR ipad and XOR opad.   You have proved this turns out fine,
> despite the relatedness of the two keys, because the robust property of
> hash function.  My point here, is if we assumed the derived keys are used
> in robust algorithms, e.g. AES-GCM, could they tolerate simpler ways of
> deriving keys, i.e. XORing a key with a non-random separation string?  To
> repeat, I am totally fine to use robust key derivation, like HKDF, but I
> would want the reason to be clear.  E.g. TLS 1.3 handshake uses HKDF as
> hedge against possible related-key attacks on the symmetric-key crypto in
> the record layer, or for better or simpler security proofs (e.g. compared
> to past key derivation methods).
>
>
>
> As many know, hashes were, once upon a time, only used for message digests
> in signatures. Message-extension in hashes did not result in signature
> forgery.   But then people naturally wanted to use hashes (as a “utility
> function” in Phillip’s terms) for a MAC.  But hashes with message extension
> suffer from MAC forgery. Along came HMAC to the rescue, saving the day, and
> the rest is history.  (To exaggerate: it is, on a minute scale, repeating;)
>
>
>
>
>
> *From:* TLS <[email-masked]> *On Behalf Of *Phillip Hallam-Baker
> *Sent:* Tuesday, May 12, 2020 1:49 AM
> *To:* Hugo Krawczyk <[email-masked]>
> *Cc:* Dang, Quynh H. (Fed) <quynh.dang=[email-masked]>;
> [email-masked]; [email-masked]; Salz, Rich <rsalz=[email-masked]
> >
> *Subject:* Re: [TLS] [Cfrg] NIST crypto group and HKDF (and therefore TLS
> 1.3)
>
>
>
>
>
>
>
> This transmission (including any attachments) may contain confidential
> information, privileged material (including material protected by the
> solicitor-client or other applicable privileges), or constitute non-public
> information. Any use of this information by anyone other than the intended
> recipient is prohibited. If you have received this transmission in error,
> please immediately reply to the sender and delete this information from
> your system. Use, dissemination, distribution, or reproduction of this
> transmission by unintended recipients is not authorized and may be unlawful.
>

---

From: "Dang, Quynh H. (Fed)" <[email-masked]>
Date: Thu, 14 May 2020 18:19:22 +0000

Hi Torsten,

The HKDF is one of the approved KDFs for being used together with an approved key exchange as specified in 56C.

At this moment, a standalone HKDF is not approved yet.

Draft version 2 of SP 800-133 (Section 6.3, item# 3: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-133r2-draft.pdf )specifies an option for a HKDF's extraction step when the IKM is a shared secret generated from a NIST's approved random bit generator in SP 800-90 series (like external pre-shared key in TLS 1.3) or when the IKM is a pseudorandom key derived from a previous approved key exchange (like a resumption in TLS 1.3).

Recommendation for Cryptographic Key Generation<https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-133r2-draft.pdf>
Draft NIST Special Publication 800-133 . Revision 2. Recommendation for Cryptographic Key Generation. Elaine Barker . Allen Roginsky . Richard Davis . This publication is available free of charge from:
nvlpubs.nist.gov

When/if that extraction step option is officially approved, meaning the current NIST's approved HKDFs in key exchanges in SP 800-56C would become NIST-approved standalone HKDFs, we'll publish their test vectors.

Regards,
Quynh.

________________________________
From: "Torsten Schütze" <[email-masked]>
Sent: Tuesday, May 12, 2020 8:36 AM
To: Dang, Quynh H. (Fed) <[email-masked]>
Cc: Hugo Krawczyk <[email-masked]>; [email-masked] <[email-masked]>; [email-masked] <[email-masked]>; [email-masked] <[email-masked]>
Subject: Aw: Re: [Cfrg] NIST crypto group and HKDF (and therefore TLS 1.3)

Hi Quynh,

Regards

Torsten