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

Michael StJohns <msj@nthpermutation.com> Sun, 26 April 2015 18:59 UTC

Return-Path: <msj@nthpermutation.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 074201B2AAA for <tls@ietfa.amsl.com>; Sun, 26 Apr 2015 11:59:04 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.601
X-Spam-Level: *
X-Spam-Status: No, score=1.601 tagged_above=-999 required=5 tests=[BAYES_50=0.8, HTML_MESSAGE=0.001, J_CHICKENPOX_12=0.6, J_CHICKENPOX_36=0.6, MIME_8BIT_HEADER=0.3, RCVD_IN_DNSWL_LOW=-0.7] 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 GHqAw_l51RoK for <tls@ietfa.amsl.com>; Sun, 26 Apr 2015 11:59:01 -0700 (PDT)
Received: from mail-vn0-f41.google.com (mail-vn0-f41.google.com [209.85.216.41]) (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 2834D1B2C8D for <tls@ietf.org>; Sun, 26 Apr 2015 11:59:01 -0700 (PDT)
Received: by vnbf1 with SMTP id f1so9470332vnb.5 for <tls@ietf.org>; Sun, 26 Apr 2015 11:59:00 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:message-id:date:from:user-agent:mime-version:to :subject:references:in-reply-to:content-type; bh=TuJzslATjBjJxXdORswzJYmHuyrxVitXqcPgCEgF/gc=; b=bHv2lw9Il+sn4qSsuKFFmrTIcH5qiUmR9k8uv2qhxHJMka5Zv1Z8JCLpjrollP5nCn gRtNuCrtf8G0FLLWqbFVn86ZOBOGQAZ8DBF7Zs4NXfC1vOK+QFSPvB5Pk7BcrHRDZ8lq 8DJ4plrNGH/OyGjbQiQuThtXeMLhH+1SWNf7dmHlsH0J/8Nrze+eNGw2tYArpkSB0Cjy r4UHqS4WIk/HKnypE0jVMrVOLhBUWkXmQKvxOZfo7X1Kl89jSeIxGghHlRCG0RilyNhh 5dy2ZSozn7ftgH0ePq3YR1NXqfxNGuhAMxQiMx7e68X0vU06hVWvSyyoZJsJrPvemQdp HkQQ==
X-Gm-Message-State: ALoCoQmSsVFSt0xKoA9b4AR+8uet9Ohnsq3L1nJbO2qGWcIC7/QBQN3DpEsDKBjGG94EA+HQupK2
X-Received: by 10.52.176.103 with SMTP id ch7mr19592275vdc.68.1430074740156; Sun, 26 Apr 2015 11:59:00 -0700 (PDT)
Received: from ?IPv6:2601:a:2a00:84:cae:d6cf:19b5:13bc? ([2601:a:2a00:84:cae:d6cf:19b5:13bc]) by mx.google.com with ESMTPSA id fi9sm19737259vdb.27.2015.04.26.11.58.59 for <tls@ietf.org> (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 26 Apr 2015 11:58:59 -0700 (PDT)
Message-ID: <553D3572.6040408@nthpermutation.com>
Date: Sun, 26 Apr 2015 14:58:58 -0400
From: Michael StJohns <msj@nthpermutation.com>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
MIME-Version: 1.0
To: tls@ietf.org
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>
In-Reply-To: <CADi0yUPTixoesXkgd=HYe_+ua_+=_UfcDBSndCgdh1usTzNpzQ@mail.gmail.com>
Content-Type: multipart/alternative; boundary="------------050805020400080402020009"
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/wau8onM0JZAMrZbFlCEHzrH_JiI>
Subject: Re: [TLS] =?windows-1252?q?confirming_the_room=92s_consensus=3A_adopt?= =?windows-1252?q?_HKDF_PRF_for_TLS_1=2E3?=
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 18:59:04 -0000

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.

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.



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

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.

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



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

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 list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls