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

[Hugo Krawczyk <[e-mail]>]

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

> 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.)
>

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.


>
> 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).
>

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.


>
> 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?
>

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


>
> 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 <[e-mail]> *On Behalf Of *Phillip Hallam-Baker
> *Sent:* Tuesday, May 12, 2020 1:49 AM
> *To:* Hugo Krawczyk <[e-mail]>
> *Cc:* Dang, Quynh H. (Fed) <quynh.dang=[e-mail]>;
> [e-mail]; [e-mail]; Salz, Rich <rsalz=[e-mail]
> >
> *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 <[e-mail]>
> wrote:
>
> 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.
>
>
>
> 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.
>
>
>
>
>
>
>
>
> ------------------------------
> 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.
>