Re: [TLS] confirming the room’s consensus: adopt HKDF PRF for TLS 1.3

Hugo Krawczyk <hugo@ee.technion.ac.il> Sun, 26 April 2015 20:21 UTC

Return-Path: <hugokraw@gmail.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 403531A8AA6 for <tls@ietfa.amsl.com>; Sun, 26 Apr 2015 13:21:26 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.823
X-Spam-Level:
X-Spam-Status: No, score=0.823 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FM_FORGED_GMAIL=0.622, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, J_CHICKENPOX_12=0.6, J_CHICKENPOX_36=0.6, J_CHICKENPOX_57=0.6, MIME_8BIT_HEADER=0.3, SPF_PASS=-0.001] autolearn=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 7W6POs4xg1qj for <tls@ietfa.amsl.com>; Sun, 26 Apr 2015 13:21:22 -0700 (PDT)
Received: from mail-lb0-x22a.google.com (mail-lb0-x22a.google.com [IPv6:2a00:1450:4010:c04::22a]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id F3F891A8851 for <tls@ietf.org>; Sun, 26 Apr 2015 13:21:21 -0700 (PDT)
Received: by lbcga7 with SMTP id ga7so68737549lbc.1 for <tls@ietf.org>; Sun, 26 Apr 2015 13:21:20 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; bh=povnA4BhJ+XCjNr+hkkv4j9txeZQmK7yEgEDgagV4jc=; b=nQKCDvp7qzoAaP5+zdNUyWMxKChtpLzGND0cFXyv0zfKxu7MOyyzMheGTMXazjjmCb msaQjIuV9Y7StBjmH1rCNAB2jJGLAM7IIfL9usnK0WpmJDIeCpAK+HU7GaTj6FAIwhLz Cx9CvFJKSfzm7CyN/j35ZtD27Ph012d4isK/2EgYejaBgSeBUWS6EYKCSE3/hg4wd0GC ZG3EPwGDz03lDlV2LcsDVMeeEH1P67HWcQwxwaJQ/QCZJFT3XL8E60QIZAPtrcoNb7QF GaGtqXW7qT1JoIAKzfy/hjCrzh2TXrFAsAMpkmipMDzDdD4Xc41IIzL1wMVBQa8YkbOT py/w==
X-Received: by 10.152.43.110 with SMTP id v14mr6488515lal.4.1430079680395; Sun, 26 Apr 2015 13:21:20 -0700 (PDT)
MIME-Version: 1.0
Sender: hugokraw@gmail.com
Received: by 10.25.78.66 with HTTP; Sun, 26 Apr 2015 13:20:49 -0700 (PDT)
In-Reply-To: <553D3572.6040408@nthpermutation.com>
References: <4A5C6D8F-6A28-4374-AF1F-3B202738FB1D@ieca.com> <551DDD4E.5070509@nthpermutation.com> <F7F3EB83-FEA2-477C-8810-38C49B71C977@ieca.com> <551E290D.7020207@nthpermutation.com> <55381768.8010402@nthpermutation.com> <CACsn0cm5A50dP4JDKq9R0XdB83hyzPPLQHAMnUcXFb+DCSwV7g@mail.gmail.com> <55392B08.6020304@nthpermutation.com> <CADi0yUPTixoesXkgd=HYe_+ua_+=_UfcDBSndCgdh1usTzNpzQ@mail.gmail.com> <553D3572.6040408@nthpermutation.com>
From: Hugo Krawczyk <hugo@ee.technion.ac.il>
Date: Sun, 26 Apr 2015 16:20:49 -0400
X-Google-Sender-Auth: 6tn98oFwit3ZA_1MFw5ICZVV9j0
Message-ID: <CADi0yUOnsD0Sasq7dRTbRpUm9jTg-uf+vjkkpMCxxsKXH0kqMw@mail.gmail.com>
To: Michael StJohns <msj@nthpermutation.com>
Content-Type: multipart/alternative; boundary="001a11c3515259be700514a65fc7"
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/cVtwlgD-fTtS0UKoc-JhAwPjreo>
Cc: "tls@ietf.org" <tls@ietf.org>
Subject: Re: [TLS] confirming the room’s consensus: adopt HKDF PRF for TLS 1.3
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sun, 26 Apr 2015 20:21:26 -0000

On Sun, Apr 26, 2015 at 2:58 PM, Michael StJohns <msj@nthpermutation.com>
wrote:

>  Inline below.
>
>
> On 4/24/2015 5:31 PM, Hugo Krawczyk wrote:
>
>
> Here are a few clarifications regarding HKDF and its use in TLS 1.3 in
> response
> to recent emails (including those under the "HSM-friendly Key Computation"
> thread). I will not touch on anything specific to HSM or PKCS11 since I
> know
> little about these and the recent exchange on these issues has not helped
> me
> understanding these things any better (but rather confuse me more).
>
> Let me start with the issue of whether we should be using the HKDF-Extract
> and
> HKDF-Expand separately or only use HKDF as a single function (which
> internally
> operates HKDF-Extract and HKDF-Expand). There is an obvious advantage for
> the
> latter approach (single function) as it deals with HKDF as a black box.
> But there are also advantages to calling these two components separately,
> and
> TLS 1.3 provides some good examples for that. First, HKDF is built to
> output as
> many keys as needed from a single HKDF operation, but in TLS we are
> deriving
> multiple keys from the same keying material through separate applications
> of the
> expand part. In such a case it is more natural to apply extract once and
> apply
> expand several times (with different info fields!). For example, Master
> Secret
> is derived using a single Extract operation but it is then used in three
> different Expand operations for deriving other keys (application traffic
> keys,
> export master secret, and resumption master secret). Second, when one
> starts with
> a strong key then the Extract step can be skipped making it convenient to
> be
> able to call Expand directly. Third, it is convenient to call Expand
> directly as
> a PRF for computing the Finished message. Lastly, and not least, it makes
> the
> key derivation logic more explicit which helps conveying the rationale of
> each
> operation and helps those analyzing the protocol (now and in the future).
>
>
> What you're doing as far as I can tell is optimizing implementation at the
> cost of requiring special interfaces.
>
> One of the ways we've gotten to the point where TLS key material can't
> actually be kept secret in an HSM is by generalizing the concept of a PRF
> into a KDF and a MAC.    What we need to do is have a MAC function and a
> KDF function and understand what the inputs to those are.
>
> TLS1.2 uses the Master secret as a key for both the MAC and KDF functions
> and that needs to change.  Those can't be the same key - and hence your
> comment about using the same master secret for different derives becomes
> problematic especially if one of the outputs is to an exporter.
>

​The same Master Secret is used to derive multiple keys but these are
derived with unique label+context input.​
​
​Different derivations *never* use the same label+context.​



> Internally, an HSM MAY choose to retain the output of the extract phase as
> cached material (and in fact taking the master secret, doing the impedance
> match of the extract phase and replacing the master secret with the
> reduction still pointed to the master secret handle may be what a
> particular implementation does).  But that's an implementation discussion,
> not a KDF input/output discussion.
>

​Is this discussion geared to define the KDF mechanism for TLS 1.3?
If so, can you say what exactly you are proposing to do?
​


>
>
>
>
> My recommendation is to keep the Extract and Expand separation for the
> moment,
> in particular due to the last point, so we can see more clearly the logic
> while
> still setting the missing details of the protocol. When the whole picture
> is
> clear we can revisit this point.
>
> On other issues:
>
> - This should be obvious but worth repeating: All calls to HKDF-Expand
> MUST use
>   a non-empty info field binding the derived key(s) to a unique context
> (in the
>   case of TLS this is usually a label and a cumulative session-hash).
>
>
> All calls to HKDF *should* use a non-empty label and context field, but
> that's tied more to the specific use than anything else.
>

​Agreed. All calls to HKDF that produce cryptographic keys for use in the
protocol MUST use a non-empty label and context field and that's what we
do.
​


> This isn't something that needs to be enforced by the security module as
> the crypto will cause different streams to be generated with different
> labels and contexts.
>
> Except for the problem of the Length term.   Same label and context but
> with different output lengths will have the same prefixed key stream.
>

​I am completely lost on this length issue. Can you give me a concrete
example where TLS 1.3 derives different keys with same label and context
but with different output lengths? As said, in TLS 1.3 each label and
context is used exactly once. I must be missing something in your argument
but I just can't figure what's that.
​


>
> - It was suggested that the length of derived keys should be part of the
> input
>   to key expansion. If desired, this length can be entered through the info
>   field of HKDF but I would be very careful not to derive two different
> keys
>   where the only difference in the 'info' values is the key length. If the
> two
>   keys happen to be of the same length one would end up with two keys that
> are
>   identical.
>
>
> The term you use in your paper and the RFC is
>
> T(N) = HMAC-Hash(PRK, T(N-1) | info | N) where N is expressed as a single
> octet in the concatenation operation.
>
> You can include the length term in info, but it won't be enforced by the
> HSM and depending on the format of the INFO field could actually be spoofed
> as this is all user supplied info that isn't known to be related to the
> actual desired output length.
>

 Adding the length is not a solution to spoofing attacks- it will not
differentiate between keys of the same length.
You cannot compensate via the KDF for unauthorized access to the HSM. If
the HSM doesn't enforce an access policy, it is the HSM problem, not
something to solve via the KDF or via TLS 1.3 spec.
​


>
> Instead HKDF should be updated to:
>
> T(N) = HMAC-Hash (PRK, T(N-1) | info | N | L) where L is the number of
> bits of desired key stream expressed as a UINT32 in NBO *is* enforceable by
> the HSM as it is a known field (size and position).
>
> NIST SP800-56C (which was standardized after the RFC and references your
> paper) describes the equivalent of your extract phase and then refers to
> SP800-108 and allows any of those to be used in the expansion phase.  ALL
> of the possible alternatives - counter, feed back (and the evil double
> pipeline) include the length term in the per-block expansion.
>
> E.g.  the feedback expansion uses:
>
> K(i) := PRF (KI, K(i-1) {|| [i]2 }|| Label || 0x00 || Context || [L]2)
>
> Where PRF is equivalent to your HMAC-HASH,  KI is the PRK, [i]2 is the
> same as N, "Label || 0x00 || context" is equivalent to info and L[2] is the
> length of the desired output.
>
> HKDF is equivalent to NISTSP800-56C with an expansion phase of NIST
> SP800-108, section 5.2 where the length of i is a single octet, where the
> ordering of the terms is slightly different and where the L term is
> omitted.
>
> The inclusion of L as a mandatory term in the expansion means that any
> change in L changes the entire key stream.  That is NOT the case with HKDF
> as defined in the RFC.
>
> See section 7.5 of
> ​​
> SP800-108 for a discussion of key separation especially paragraph (2) and
> why this is important.
>
> ​I agree with section 7.5 and HKDF, and its use in TLS 1.3, fully complies
with it. There is no mandatory use of length as input. It is certainly
allowed but not mandated. And when allowing it, it is accommodated via the
equivalent of the 'info' ​

​field:

*"different input data strings (e.g. Label || 0x00 || Context || [L]2)
shall be used for different executions".*Length is an example and not even
listed in the explicit examples at the top of page 19.
​

>  - One of the emails raises the issue of using random salt, as
> recommended by RFC
>   5869. Note that the RFC recommendation also indicates that the salt value
>   should be something that is authenticated during the protocol, or
> otherwise it
>   can be selected by the adversary. This authentication needs to happen
>   independently of the key being derived using this salt. For example, one
>   should be careful not to incur in a circular logic, e.g. deriving a key
>   mackey=HKDF(salt, info) and then using mackey to authenticate the salt by
>   computing MAC(mackey, salt). This is why the proposed TLS 1.3 key
> derivation
>   scheme does not use nonces as salt.
>
>
> I believe that is the correct approach.
>
>
> - Someone said: "In an ideal world we would all use the same KDFs rather
> than
>   inventing a new one for each protocol."
>
> That was me.  But what I said was that we should use standard KDFs, not
> reinvent new ones.
>

>  This was exactly the goal of HKDF,
>   namely, provide a single KDF that can serve different protocols,
> requirements
>   and settings. The interested reader can consult my Crypto 2010 paper
>   https://eprint.iacr.org/2010/264
>   for a very detailed treatment of key derivation in general and HKDF in
>   particular,and why this one design fits many different uses. TLS 1.3 is a
>   perfect demonstration of the versatility of HKDF as it is used as a
> random
>   oracle, randomness extractor and PRF, depending on the key material being
>   derived. See the next item for an example.
>
>
> Given SP800-108 and SP800-56C were published before your paper  and the
> RFC and have pretty much identical math (except as I noted), why shouldn't
> we use those cites instead of the RFC?  E.g. is there any cryptographic
> improvement in RFC5869 vs the other two?
>

​SP 800-108 is a framework and set of recommendations, not a specific,
unique KDF function. HKDF follows this framework and NIST found this
sufficiently important to document this in a separate document SP 800-56C
(which explicitly includes HKDF as an instantiation)​
​.​



>
>
> - Another issue raised in recent email exchange is the way to merge the
>   semi-static value g^xs (where s is the semi-static server's private key
> and x
>   the ephemeral client's private key) with the ephemeral value g^xy.
>   This is done by first extracting a key from g^xs as
> PRK1=HKDF-extract(0,g^xs)
>   and then extracting PRK2=HKDF-extract(PRK1,g^xy).
>   Here is the logic: PRK1 is extracted from g^xs using HKDF(0,...) as a
> random
>   oracle as needed in the proof of security. Then PRK2 is derived with
> salt=PRK2
>   for the following reason. If g^xs is not exposed (the typical case) then
> this
>   HKDF use only requires treating HKDF(PRK1,...) as a PRF (essentially the
> less
>   demanding property from HKDF).  If g^xs is revealed by compromise of the
>   server's semi static private key s (after the conclusion of the
> handshake, as
>   in the forward-secrecy setting), then PRK1 is actually an authenticated
> random
>   and non-secret salt so you use HKDF as a randomness extractor.
>   In other words, each use of HKDF uses the minimal cryptographic
> assumption one
>   can have depending on the context of derivation.
>
> - Finally, there has been a long discussion related to the derivation of
> both
>   secret and non-secret material (the latter for IVs). I can't say how this
>   works with HSMs, PKCS11 or other standards, but from the cryptographic
> point
>   of view doing this "mixed" derivation of secret and non-secret values is
> not a
>   problem as long as HMAC is not broken as a PRF.
>
>
> Umm....  I don't actually understand what you said here.
>

​We are definitely having difficulties understanding each other. I'm trying
my best.

Hugo

​


>
> The issue is that you can't use the same key for different purposes if you
> want to enforce key security.  Even though the underlying construct for a
> KDF is an HMAC function, if you can ensure - in an enforceable manner -
> that a master secret can only be used for key expansion and an integrity
> key is only used for a MAC function (including the HMAC over data) and that
> pseudo-random data does not depend on either of these keys (i.e. they are
> cryptographic isolated) then you can build an HSM that can actually do its
> job.  There are other related issues (e.g. the outputs of a KDF getting
> tagged with appropriate key types, lengths and exportability).
>
> All that means is that you want three different functions: KDF (key
> expansion), MAC (finished message signature)  and RBG (IV/Nonce
> production), and that you enforce the type of inputs to them.  The
> underlying cryptographic constructs can be the same or similar, but we need
> to stop conflating them as needing to be identical.
>
> Mike
>
>
> Hugo
>
>
>
> _______________________________________________
> TLS mailing listTLS@ietf.orghttps://www.ietf.org/mailman/listinfo/tls
>
>
>
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
>
>