Subject: Re: [Cfrg] TLS PRF security proof?

From: Dan Brown <[email-masked]>
Date: Wed, 9 Jul 2014 12:58:30 +0000

‎TLS has been asking for CFRG input on curves, so maybe TLS is now more open to a suggestion like HKDF for future updates.

Furthermore, the latest TLS 1.3 draft makes a point of lacking a security analysis: thus my question to this list. (Not to the TLS list, because of the research nature of the question. )

I'll ask the converse question: besides provable security, what advantage would HKDF have over TLS PRF? Eg, does HKDF fare better than TLS PRF under some disastrous HMAC failure? In other words, if proofs cover the sufficient conditions, what about the necessary conditions? Does the HKDF RFC answer all this already?

Best regards, 

-- Dan
‎
  Original Message  
From: Peter Gutmann
Sent: Wednesday, July 9, 2014 1:58 AM
To: [email-masked]
Subject: Re: [Cfrg] TLS PRF security proof?

Dan Brown <[email-masked]> writes:

>Would it be useful if CFRG were to publish a recommended PRF?

Already done, just use HKDF, RFC 5869. The problem isn't publishing it, it's
getting it adopted, so far each and every standards group has seen fit to
invent their own incompatible PRF/KDF, and I'm not sure what size gun you'd
need to hold to everyone's head to get them to agree to standardise on HKDF
(or anything els for that matter).

Peter.

_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: Andy Lutomirski <[email-masked]>
Date: Wed, 9 Jul 2014 08:18:13 -0700

> I'll ask the converse question: besides provable security, what advantage would HKDF have over TLS PRF? Eg, does HKDF fare better than TLS PRF under some disastrous HMAC failure? In other words, if…

I can't speak for the TLS WG, but from my own perspective, I have
three problems with HDKF:

1. HKDF is parametrized by a hash.  What hash should people use?
(Hence my suggestion of using combiners -- changing the PRF in an
existing protocol is a real PITA and might not even be possible
without introducing security holes.)

2. The RFC didn't make the security properties clear to me.  For
example, protocols should stick nonces into the salt.  Oh, wait, they
shouldn't stick nonces into the salt without care.  Can I use multiple
"info" values to safely extract key material and publish it?

3. (Only relevant to hashes using MD construction) My understanding of
HMAC is that it's secure against generic attacks on MD hashes if the
key is secret and unpredictable.  HKDF doesn't necessarily use a
secret, unpredictable key for HMAC.  Is HKDF-SHA-1 insecure as a
result?  What about HKDF-SHA-512 against an adversary with unlimited
precomputation power?

--Andy

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 9 Jul 2014 08:28:22 -0700

> 1. HKDF is parametrized by a hash.  What hash should people use?

Any one that has no known weakening of preimage resistance. That is: nearly any of them.

> without introducing security holes.)

Adding more choices makes interoperability less likely. In real-world protocols, excellent interoperability with almost-perfect security is *much* better than good interoperability with perfect security.

> shouldn't stick nonces into the salt without care.  

Can you justify that second sentence with anything from RFC 5869? In fact, it says the opposite:

   Ideally, the salt value is a random (or pseudorandom) string of the
   length HashLen.  Yet, even a salt value of less quality (shorter in
   size or with limited entropy) may still make a significant
   contribution to the security of the output keying material; designers
   of applications are therefore encouraged to provide salt values to
   HKDF if such values can be obtained by the application.

> Can I use multiple

Yes. Can you point at something in the RFC that indicates any different?

> result?  What about HKDF-SHA-512 against an adversary with unlimited

For the discussion at hand, the key is secret and unpredictable.

--Paul Hoffman

---

From: Andy Lutomirski <[email-masked]>
Date: Wed, 9 Jul 2014 08:33:27 -0700

>    HKDF if such values can be obtained by the application.

Quoting from RFC 5869, section 3.4:

   Independence is also an important aspect of the salt value provided
   to a KDF.  While there is no need to keep the salt secret, and the
   same salt value can be used with multiple IKM values, it is assumed
   that salt values are independent of the input keying material.  In
   particular, an application needs to make sure that salt values are
   not chosen or manipulated by an attacker.  As an example, consider
   the case (as in IKE) where the salt is derived from nonces supplied
   by the parties in a key exchange protocol.  Before the protocol can
   use such salt to derive keys, it needs to make sure that these nonces
   are authenticated as coming from the legitimate parties rather than
   selected by the attacker (in IKE, for example this authentication is
   an integral part of the authenticated Diffie-Hellman exchange).

> Yes. Can you point at something in the RFC that indicates any different?

No, but it wasn't clear to me that this property was guaranteed.

> For the discussion at hand, the key is secret and unpredictable.

I believe this, but I'd like to imagine that we've reached the point
where we don't need weird hacks (i.e. HMAC) and overcomplicated
analysis to work around the generic weaknesses of old hashes.  Oh,
well -- this is more of an aesthetic issue than a security issue.

--Andy

---

From: Andy Lutomirski <[email-masked]>
Date: Wed, 9 Jul 2014 10:50:37 -0700

>    an integral part of the authenticated Diffie-Hellman exchange).

I should note that this text in 3.4 smells funny to me even taken
alone.  Making sure that the nonces come from legitimate parties does
*not* imply that they are independent of the IKM in any sense of the
word "independent" that I understand.

I, and presumably protocol designers everywhere, would much prefer
language that tells me "this primitive provides this security
guarantee if this condition is met" where the condition is clearly
specified.

This is not to say that HKDF is not a perfectly good KDF, but I find
the RFC 5869 language unconvincing.

--Andy

---

From: Watson Ladd <[email-masked]>
Date: Wed, 9 Jul 2014 18:52:49 -0700

> the RFC 5869 language unconvincing.

The reason the salt argument exists is because of a technicality in
the existence of entropy extractors:
they don't exist. Therefore, you need to make a randomized definition,
which requires a random string
independent of the other arguments.

The "obvious" way to get a salt is to do a coinflip protocol, then use
that as the salt. (That is, commit, commit, reveal,
reveal, and xor the revealed strings). This produces a random string,
independent (well, no... the attacker could abandon
the protocol round rather than continue it if they don't like it) of
other values. (To fix this you condition on successful protocol
runs, and do some math)

In the ROM none of this matters, but interestingly the eprint paper
gives a natural protocol secure in the ROM, but insecure
because a natural choice of hash function admits a length extension attack.

Without the salt argument the result is simply H(stuff), which is
supposed to be fine for any reasonable choice of H.

Sincerely,
Watson Ladd

---

From: Andy Lutomirski <[email-masked]>
Date: Wed, 9 Jul 2014 19:50:38 -0700

> other values. (To fix this you condition on successful protocol

Would it be good enough to do:

A -> B: commit
B -> A: nonce
A -> B: reveal

Not that any protocol designer is likely to do this, but it's less
unpalatable than adding the extra round.

And does using a salt as suggested in the RFC actually reduce provable security?

> because a natural choice of hash function admits a length extension attack.

Does that mean that HKDF-SHA-bits is not secure in the ROM?

> supposed to be fine for any reasonable choice of H.

If stuff is (party A data | party B data) and party A gets to choose
all of its data offline, then this isn't so appealing for common
choices of H.

--Andy

---

From: Watson Ladd <[email-masked]>
Date: Wed, 9 Jul 2014 20:05:36 -0700

> And does using a salt as suggested in the RFC actually reduce provable security?

No, not using a salt forces stronger assumptions on the hash function.
In some cases these assumptions
are so strong they are not satisfied by any hash function: in that
case you prove the protocol secure in the ROM.

Doing anything in the standard model, with standard assumptions, is
hard. In practice the ROM is good enough for protocols.

Honestly, I would be shocked if HKDF turned out to not get the job
done in any reasonable protocol.

> Does that mean that HKDF-SHA-bits is not secure in the ROM?

A protocol where H(stuff) is revealed, and H(stuff | junk) is used as
a key, falls apart for hashes admitting length extension,
(like every MD style hash) but is secure in the ROM. SHAxxx is not a
random oracle! No deterministic function ever can be
a random oracle, but SHAxxx is particularly easy to distinguish as it
has a length extension property.

> all of its data offline, then this isn't so appealing for common

Why not? Is there a weakness of SHA256 I'm unaware of? If you need
signatures, you need collision resistant hash functions.
All uses of SHA1 and MD5 need to be ended ASAP: Microsoft has already
begun this process.

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Andy Lutomirski <[email-masked]>
Date: Wed, 9 Jul 2014 20:16:19 -0700

> All uses of SHA1 and MD5 need to be ended ASAP: Microsoft has already

Suppose that party A is malicious and they can find "party A data 1"
and "party A data 2" that collide.  I can imagine protocols in which
this violates one of the assumptions of the protocol.

If you allow party A to spend an extremely long time precomputing
something *before starting the protocol*, I'd like the protocol to
remain reasonably secure.  Hashes with unnecessarily small internal
state violate this.

Admittedly, it's supposed to be impractical to find even a single
collision for SHA-256, etc, but it seems unfortunate to have this type
of weakness in new protocols, hence my request for a better PRF.

FWIW, H(padded_length(stuff) | stuff | stuff) would fix this, I think.
Maybe this is a pointless consideration.

--Andy

---

From: Jakob Breier <[email-masked]>
Date: Thu, 10 Jul 2014 13:16:42 +0200

Hi,

> remain reasonably secure.  Hashes with unnecessarily small internal

If internal state size is your problem you can always use Sha512 or 
Sha3-512 for an intended collision resistance of 256bit.

But I find your argument much more compelling in the context of 
deteriorating hash functions, like MD5. Of course you wouldn't use MD5 
for new protocols, nonetheless it provides a nice case study for how the 
Sha2 and Sha3 family might break down with future cryptanalysis. 
Specifically while MD5 is no longer collision resistant, it is still 
preimage resistant and target collision resistant / UOWHF (in the sense 
that the random value is prefixed to the message).

On 09.07.2014 17:28, Paul Hoffman wrote:
> On Jul 9, 2014, at 8:18 AM, Andy Lutomirski<[email-masked]>  wrote:
>

Which brings me back to RFC 5869 in the use case of PRFs for protocols 
like TLS. If you want to assure your handshake was not tampered with, 
for example in a downgrade attack, and then put the whole handshake into 
the PRF/KDF (in addition to the Diffi-Hellman result or some other 
secret) you will at least need collision resistance of the KDF. HKDF was 
not analyzed under this setting (as far as I can tell from Definition 7 
of the accompanying paper) and the explanations in the RFC do not help 
you decide with which hash functions it is secure then.

It would be nice to only rely on target collision resistance and 
preimage resistance instead of full collision resistance of the hash 
function, and for right choices of the salt this would be possible for 
HKDF, too. For example if after the handshake an additional random from 
each of the parties is exchanged and the concatenation is used as the 
salt. I don't see how it would be feasible without at least one further 
message transfer, though, so it it's likely not worth the additional costs.

Regards,
Jakob Breier

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 10 Jul 2014 18:09:39 -0400

​Let me provide some clarifications regarding this discussion.

If I understand correctly, Dan Brown's original posting referred to the TLS
PRF and its use of a feedback mode. Later postings started discussing HKDF
which uses this feedback mode but only as a component of a more general
functionality, namely, key derivation.

The crucial difference between KDFs and PRFs is that the latter are used to
expand a strong cryptographic key into several keys while KDFs assume that
you start with keying material of "sufficient entropy" but not contained in
the form of a short uniform (or pseudo-random) key. Thus, HKDF works in two
stages: a first stage that "extracts" a strong cryptographic key from the
input entropy and a second stage where this key is expanded into more
(cryptographically strong) keys using a PRF.

HKDF is defined in RFC 5869 which contains limited design and use rationale
but which is backed by a detailed article explaining such rationale:
http://eprint.iacr.org/2010/264.

The intention of the paper was to be written so that it contains the formal
treatment a mathematical cryptographer expects but also have intuitive
English discussions for the less formalist reader (actually, most of the
math background for the paper belongs to prior work). So I would encourage
people interested in the discussion in this thread to take a look at the
paper; it should answer some of the questions raised here such as the role
of salt, source independence, etc.).

In particular, the paper contains a short section on the rationale of using
feedback mode for the PRF part and its advantage over counter mode
(answering one of the points raised by Dan Brown). Indeed, I argue that
while counter mode is more natural it is also more vulnerable to future
weaknesses (*). It is also worth noting that HKDF adds an increasing
counter to the feedback iterations that is not part of the TLS definition
and was added to defend against (theoretical) hash cycles. I would
recommend that any revision of TLS that changes its key derivation adopts
HKDF as defined in RFC 5869.

A general comment to address some of the more specific issues raised in
this discussion: The basic design goal of HKDF is to serve as a
multi-purpose design. One that works in all key derivation scenarios (from
whitening the output of a physical RNG to extracting randomness from pools
of entropy to deriving keys in key exchange protocol) and with different
assumptions on the underlying cryptographic hash functions. In particular,
confining the use of idealized assumptions (e.g., random oracle) or even
collision resistance to the minimum necessary. The important point is that
you get the benefits of the design without having to customize it on a
per-use basis.

Hugo

(*) This PRF mode of operation (introduced in the early design of IKEv1,
from which it found its way to TLS via SSLv3) was "inspired" by the early
weaknesses of MD5 (Dobbertin work). I thought at the time that we better
design safegueards to protect against future weaknesses of our beloved
functions. I believe we should stick to that principle.

---

From: Watson Ladd <[email-masked]>
Date: Fri, 11 Jul 2014 07:48:09 -0700

On Thu, Jul 10, 2014 at 4:16 AM, Jakob Breier
<[email-masked]> wrote:
> If internal state size is your problem you can always use Sha512 or Sha3-512
> for an intended collision resistance of 256bit.
>
> deteriorating hash functions, like MD5. Of course you wouldn't use MD5 for
> new protocols, nonetheless it provides a nice case study for how the Sha2
> and Sha3 family might break down with future cryptanalysis. Specifically
> while MD5 is no longer collision resistant, it is still preimage resistant
> and target collision resistant / UOWHF (in the sense that the random value
> is prefixed to the message).
>
>
> Which brings me back to RFC 5869 in the use case of PRFs for protocols like
> TLS. If you want to assure your handshake was not tampered with, for example
> in a downgrade attack, and then put the whole handshake into the PRF/KDF (in
> addition to the Diffi-Hellman result or some other secret) you will at least
> need collision resistance of the KDF. HKDF was not analyzed under this
> setting (as far as I can tell from Definition 7 of the accompanying paper)
> and the explanations in the RFC do not help you decide with which hash
> functions it is secure then.

See "Dr. Strangelove, or how I learned to stop worrying and love the ROM".

The extract-hash-expand composition works. but it requires a source of
randomness (possibly public)
independent from  the data exchanged if you want it to work with
assumptions that aren't extremely hard.
Getting such data is impossible: you need to do a subtle calculation
of the gap between independence and
non-independence induced by the source in the security proof. It's a
very tricky thing to get right.

However, the protocol failures we've seen in the past were easily
discoverable in the ROM: they don't rely
on subtleties of hash functions. Furthermore, signatures == collision
independent hash functions. (I know the
<-, but maybe -> is more complicated: it might be just conjectural. At
least with ECDSA this is ==).

Real-world hash functions are stronger than most of our assumptions
about them, and weaker than the assumptions
that we can get away with in practice.

>
> It would be nice to only rely on target collision resistance and preimage
> resistance instead of full collision resistance of the hash function, and
> for right choices of the salt this would be possible for HKDF, too. For
> example if after the handshake an additional random from each of the parties
> is exchanged and the concatenation is used as the salt. I don't see how it
> would be feasible without at least one further message transfer, though, so
> it it's likely not worth the additional costs.

That one isn't independent of the rest of the protocol... Independance
is really hard.

The problem is that in the standard model life is very complicated:
it's not clear to me that just using HKDF is enough.
(In fact it isn't: you need additional analysis). We can't even make
secure protocols in the ROM in the IETF: while it would
be amusing to watch the TLS WG try to make a secure key agreement
protocol, it's probably a waste of time compared to
getting things right in the ROM.

Sincerely,
Watson Ladd

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 11 Jul 2014 13:56:58 -0400

Having a source of independent public randomness (a.k.a. salt) it less rare
than you seem to believe and it has benefits even if you use a beloved
random oracle (see the Photuris real-world example in page 28 of
http://eprint.iacr.org/2010/264).

Some examples of applications where salt is readily available:

- Any KE with explicit authentication (via signatures or public key
encryption like IKE) can use as salt the nonces exchanged between the
parties  (and chosen independently of other randomness used in the
protocol). It requires explicit authentication since you need to
authenticate these nonces to ensure they are not chosen by an attacker.
Since nonces are part of most KE protocols you get the salt for free.

- A DH-based public-key encryption scheme (i.e ElGamal) can publish a salt
string (certified together with the public key) for extracting a strong
encryption key from DH values.

- A physical RNG can use fixed salt to whiten possible biases of the
generator.

On the subject of trusting analysis based on random oracle. A protocol with
a formal proof in the random oracle model is much better than one without a
proof at all. And one with a proof in the standard (non-RO) model is better
than one in the ROM. I would not suggest, in general, paying a significant
performance cost to avoid ROs but if you have two schemes with comparable
performance one with RO and one without, I would favor the latter.

The case of HKDF is even simpler: you don't need to choose between two
schemes. The *same* scheme supports non-ROM cases when possible, supports
salt when available, and supports ROM (with and without salt) when
necessary.

On Fri, Jul 11, 2014 at 10:48 AM, Watson Ladd <[email-masked]> wrote:

> Sha3-512
> for
> like