Subject: RE: [TLS] PRF in TLS 1.2

From: "Blumenthal, Uri" <[email-masked]>
Date: Tue, 26 Sep 2006 19:19:27 -0400

>> "If it ain't broke, don't fix it"?
>
>I would phrase it as "make the most minimal change possible"

:-)

>> Will using SHA-1 only result in a weaker PRF than the TLS 1.1 PRF,
>> which uses both MD5 and SHA-1?
>
>This would be a good question to direct at Dan Simon or Hugo Krawczyk.
>My intuition is that because the secret is split between the two
>hashes in the current PRF, this PRF would be arguably stronger
>than the current PRF if MD5 is badly compromised. In any case,
>this is a general question of whether we want two hashes
>rather than a detailed one abt construction.

A PRF based on one decent hash will be stronger.
Better than PRF based on two (especially including one that's broken).

>> Is it required that the PRF use label and seed only in the form
>> of their concatenation label + seed?
>
>No, I don't think so

It wouldn't be a good idea to force PRF into such use pattern.

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

---

From: "Kyle Hamilton" <[email-masked]>
Date: Tue, 26 Sep 2006 21:35:03 -0700

My thought is that even if one of the hash algorithms is badly broken,
the fact that more than one hash is being used means that a 'hedge'
exists against that possibility.

MD5 may be able to be broken.  SHA1 may be able to be broken.
However, their outputs both rely on the original input for their
value, such that 1 bit of entropy in the input leads basically to 1
bit of entropy in the output.

As well, I haven't heard of anyone being able to create a bitstring
that will go through both hashes to form an identical bit pattern from
both of them.  So, even if MD5 is broken (such that a valid message
can be created for message injection/session hijack), the fact that
another cipher suite is also in use arguably provides at least as much
security as using that cipher suite alone, and hypothetically more.
(I cannot attest to theory.)  Especially if the outputs are XORed
together -- if SHA1 cannot be predicted but MD5 can, there's still the
entire output space of 160 bits to go through.  If SHA1 can be
predicted but MD5 cannot, then there's still 128 bits of output space
to go through.  (Believing that (SHA1 & MD5) has the same amount of
entropy as (sizeof(SHA1) + sizeof(MD5)) is a fallacy; it has the
amount of entropy that the largest unpredictable one gives.)

-Kyle H

-- 

-Kyle H

---

From: [email-masked] (Peter Gutmann)
Date: Wed, 27 Sep 2006 19:33:33 +1200

>amount of entropy that the largest unpredictable one gives.)

I agree with everything in the above text.  This is a completely
unnecessary change, it gratuitously breaks compatibility with the
existing PRF, it provides no extra security (that anyone knows of), and
by eliminating the current belt-and-suspenders design, it may even reduce
the overall security.  If new research appears showing that (a) there's
a problem in the current design and (b) a new, demonstrably more secure
design, then let's switch.  But changing the design simply because we
haven't changed anything else for awhile and we need to meet some 
quota for new text in the next draft (or whatever's motivating the
current change) is not only pointless, it's counterproductive.

Peter.

---

From: David Hopwood <[email-masked]>
Date: Wed, 27 Sep 2006 12:59:09 +0100

Peter Gutmann wrote:
>>However, their outputs both rely on the original input

(half the original input, but that's enough.)

>>for their
> the overall security.

I also agree. Note that for the foreseeable future, because implementations
would support versions with both new and old PRFs, the attacker has a choice
which one to try and break. So even if, for the sake of argument, there were
a security problem with the old PRF, changing it still would not increase
security; it can only potentially decrease it.

(Note that if you can break the PRF, you can also break any protection
against version rollback -- not that that protection was particularly robust
to start with.)

> If new research appears showing that (a) there's

Hear, hear.

-- 
David Hopwood <[email-masked]>

---

From: "Pasi Eronen" <[email-masked]>
Date: Thu, 28 Sep 2006 18:19:29 +0300

Peter Gutmann wrote:
> This is a completely unnecessary change, it gratuitously breaks
> compatibility with the existing PRF, it provides no extra security
> (that anyone knows of), and by eliminating the current
> belt-and-suspenders design, it may even reduce the overall security.
> If new research appears showing that (a) there's a problem in the
> current design and (b) a new, demonstrably more secure design, then
> let's switch.  But changing the design simply because we haven't
> changed anything else for awhile and we need to meet some quota for
> new text in the next draft (or whatever's motivating the current
> change) is not only pointless, it's counterproductive.

Our WG charter explicitly warns about "gratuitous changes", and
I guess you're worried that this is such a change? But I'd like 
to understand better your dislike of Eric's proposal...

Would you prefer that the default PRF (for ciphersuites that
don't specify anything else, including all current ciphersuites)
would be the current TLS 1.0/1.1 PRF? 

But still allow new cipher suites to define other PRFs, as long 
as they use the same "API" (arbitrary-length secret, label and 
seed in, sufficiently-long byte string out)?

Best regards,
Pasi

---

From: <[email-masked]>
Date: Thu, 28 Sep 2006 18:40:34 +0300

David Hopwood wrote:
> I also agree. Note that for the foreseeable future, because
> implementations would support versions with both new and old PRFs,
> the attacker has a choice which one to try and break. So even if,
> for the sake of argument, there were a security problem with the old
> PRF, changing it still would not increase security; it can only
> potentially decrease it.

This is a problem in many transitions; however, our WG charter
explicitly lists removing dependency on MD5 and SHA-1 as our primary
goal. So, at least it must be somehow possible to configure two TLS 1.2
endpoints in a mode that doesn't use MD5 or SHA-1 at all.

This is not a configuration you'd want to use for your web browser 
or server in 2006 (or even 2010 probably), but hopefully eventually. 
We are starting to get rid of SSL2 and 40-bit ciphersuites, after all.

There are quite many ways of how we could achieve that functionality
in TLS 1.2 though; how would you modify Eric's proposal to avoid
the problems you mention?

> (Note that if you can break the PRF, you can also break any
> protection against version rollback -- not that that protection was
> particularly robust to start with.)

Wouldn't breaking the rollback protection require breaking the PRF
essentially in real-time? 

Best regards,
Pasi

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 28 Sep 2006 08:55:23 -0700

> exists against that possibility.

Sure, that was absolutely the original rationale.

> MD5 may be able to be broken.  SHA1 may be able to be broken.

But this is where it goes off track. Because of the close relationship
between MD5 and SHA-1 and the empirical correlation between attacks on
SHA-1, which appear to also imply attacks on MD5, it's not at all
clear that MD5 provides any redundancy at all here, and arguably makes
things worse than with SHA-1 alone. In particular, the fact that the
secret is split between MD5 and SHA-1 rather than fed into both of
them is a source of a potential problem. As a thought experiment,
consider a TLS PRF variant in which we replace MD5 with the identity
function. At this point the PRF reduces to SHA-1 with half of the
input space. This issue is made even more complicated by the fact
that for the DH cipher suites the input space isn't unstructured
and the PRF is used to whiten it.

In any case, there are several issues here:

1. Should we change the default TLS PRF to use some algorithm(s)
   other than MD5/SHA-1? If so, what should be the structure of
   that PRF? This is motivated by concerns about the continuing 
   security of MD5 and SHA-1.

2. Should we be able to substitute hash functions in the TLS PRF?
   This is motivated by concerns about our ability to assess the
   security of any digest as a fixed part of the protocol.

3. Should we have negotiable PRFs? This is motivated primarily by
   the desire to support GOST and the NIST 800-56A KDF.

The current draft embodies (and the WG discussion in Montreal) 
seemed to be mostly positive on all three of these changes.
Which of these are you objecting to?

-Ekr

---

From: David Hopwood <[email-masked]>
Date: Thu, 28 Sep 2006 17:00:47 +0100

> seed in, sufficiently-long byte string out)?

I don't see what the motivation is for changing the PRF at all.

Sure, it's an inelegant construction, but that's not important.

If you have multiple PRFs, you would have to prove that *all* the
PRFs are secure in order for ciphersuite negotation to be secure, so
security can't be the motivation.

So what is the motivation?

---

From: David Hopwood <[email-masked]>
Date: Thu, 28 Sep 2006 17:03:22 +0100

Eric Rescorla wrote:
> them is a source of a potential problem.

No it isn't, because each half of the secret by itself has sufficient
entropy, as far as we understand the security arguments for all of the
currently defined ciphersuites.

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 28 Sep 2006 09:13:26 -0700

> currently defined ciphersuites.

I haven't seen a convincing argument for this when the PMS is
a Diffie-Hellman ZZ.

-Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 28 Sep 2006 09:26:18 -0700

> So what is the motivation?

Your argument rather oversimplifies the situation.

1. In order to have secure negotiation, all the PRFs that both
   sides support have to be secure against a specific kind of
   active attack.

2. There are concerns about the future security of PRFs based
   on MD5 and SHA-1 against a variety of future attacks, which
   may or may not enable attacking the PRF in real time.

3. If such attacks do emerge and the only PRF we have is 
   the current one, then you're looking at a multi-year
   standardization and deployment cycle to fix the problem.

4. If such attacks do emerge and TLS 1.2 already has an 
   adjustable PRF with support for (e.g., SHA-256), then 
   the cut-over to a secure mode is a simple matter of 
   telling people to turn off SHA-1 and MD5 at which point
   they will be able to negotiate cipher suites securely.

So, I don't agree with you that the "security can't be the
motivation".

-Ekr

---

From: David Hopwood <[email-masked]>
Date: Thu, 28 Sep 2006 18:22:40 +0100

> I haven't seen a convincing argument for this when the PMS is

<http://www.di.ens.fr/~pointche/Documents/Papers/2006_icalp.pdf>

  In this paper we introduce very simple deterministic randomness
  extractors for Diffie-Hellman distributions. More specifically we
  show that the k most significant bits or the k least significant bits
  of a random element in a subgroup of Z*_p are indistinguishable from
  a random bit-string of the same length. This allows us to show that
  under the Decisional Diffie-Hellman assumption we can deterministically
  derive a uniformly random bit-string from a Diffie-Hellman exchange in
  the standard model. Then, we show that it can be used in key exchange
  or encryption scheme to avoid the leftover hash lemma and universal
  hash functions.

This also seems relevant, although I haven't read it:

<http://www.springerlink.com/content/f042yn47t16cxq59/>

  We generalize and extend results obtained by Boneh and Venkatesan
  in 1996 and by González Vasco and Shparlinski in 2000 on the hardness
  of computing bits of the Diffie-Hellman key, given the public values.
  Specifically, while these results could only exclude (essentially)
  error-free predictions, we here exclude any non-negligible advantage,
  though for larger fractions of the bits. We can also demonstrate a
  trade-off between the tolerated error rate and the number of
  unpredictable bits.
  Moreover, by changing computational model, we show that even a very
  small proportion of the most significant bits of the Diffie-Hellman
  secret key cannot be retrieved from the public information by means
  of a Las Vegas type algorithm, unless the corresponding scheme is
  weak itself.

---

From: "Kyle Hamilton" <[email-masked]>
Date: Thu, 28 Sep 2006 10:45:46 -0700

I do agree, by the way, with the need to make other PRFs available.  I
was merely referencing the "default" PRF.  For
backwards-compatibility, I would like to see the current secret-split
to MD5 and SHA1 work, until support is withdrawn in TLS1.3 or TLS2.0.

For forwards compatibility, I would like to see multiple PRFs be a
negotiatable option (meaning, right now we have MD5+SHA1; I'd like to
see the ability to negotiate SHA256+GOST, as an example), as an option
which may be mandated later.  There's also the semantics of multiple
PRFs to be taken into account... "half of the data goes to one, half
to the other" appears to be a fairly dangerous paradigm.  This leaves
us with two choices... TLS1.1 semantics, or "feed all data in to both
PRFs" semantics.

Thanks for your time.

-Kyle H

---

From: Daniel Brown <[email-masked]>
Date: Thu, 28 Sep 2006 16:56:54 -0400

David Hopwood <[email-masked]> wrote on 09/28/2006 

>   or encryption scheme to avoid the leftover hash lemma and universal

As for pseudorandomness: for the upper bits your paper says that p has to 
be sufficiently close to a power of two.  Is this a requirement for TLS 
1.2?

As for entropy: If p is a 1024 prime, and g has order less than 512 bits 
long, then its likely that there exists a function that f that such that 
f(MSB(g^z)) = LSB(g^z).  (Please ignore if TLS 1.2 requires g to have 
order 1023 bits long.)  In other words, one half has zero entropy relative 
to the other.  In all likelihood, it is computationally infeasible to find 
such a function.  In other words, each half has computational entropy 
independent of the other.  I don't know if this computational assumption 
(about the hardness of computing f(.)) follows from any standard 
assumptions, such as hardness of the decisional DH problem.

- Dan Brown

---

From: Bodo Moeller <[email-masked]>
Date: Fri, 29 Sep 2006 09:46:53 +0200

> be sufficiently close to a power of two.  Is this a requirement for TLS 

No.  More problematic is the requirement of this paper that the
subgroup order be >> sqrt(p), which means the paper cannot be applied
to Schnorr/DSA-style groups (order-q subgroup of (Z/pZ)* where
q is on the order of 2^(2k), where k is the intended "security
level", and where the bitlength of p is much larger).  For TLS,
the DH group could be anything -- we might have a Schnorr/DSA-style
group, or a group (Z/pZ)* where p is a safe prime (p = 2q + 1,
q prime).

However, while the Fouque/Pointcheval/Stern/Zimmer paper has rather
strong requirements, it needs these to arrive at an extraordinarily
strong conclusion: Under appropriate conditions (which unfortunately
are not mentioned in the abstract ...), there is not even a need to
use any hash function since the appropriate substrings of the binary
representation of the DH result can directly be used as keys.  This is
much stronger a consequence than would be needed for our purposes.

> assumptions, such as hardness of the decisional DH problem.

This looks quite good, and we don't even need a strict result here
either.  Even assuming that one half of the DH result *could* be
computed from the other, we don't have any problem in practice since
we never reveal any half of the DH result: the PRF result is obtained
by XORing a hash result based on one half with a hash result based on
the other half, so unless there is any kind of weird interdependence
between the separate hash functions, we have nothing to fear.

---

From: <[email-masked]>
Date: Fri, 29 Sep 2006 12:40:22 +0300

> Sure, it's an inelegant construction, but that's not important.

Is your concern about just changing the "default" PRF, or are
you also opposed to introducing new PRFs for new ciphersuites?

(The latter seems to be implied by our WG charter.)

> So what is the motivation?

Not *all* PRFs; only those ones that are enabled. The hope is that
some day, we can switch off the current MD5/SHA1 PRF, just like
we're now disabling SSL2 (and in some limited environments, not 
general web browsing, you could do that pretty soon).

Best regards,
Pasi

---

From: "Kyle Hamilton" <[email-masked]>
Date: Fri, 29 Sep 2006 05:49:00 -0700

> (The latter seems to be implied by our WG charter.)

Changing the default PRF would change the current ciphersuites in an
incompatible fashion, and thus would create implementation problems.
Allowing for a different PRF to be defined in a ciphersuite is the
goal; the larger problem is "how do we know what ciphersuite [and thus
PRF] we need to use?"... since MD5 and SHA1 are not FIPS-accepted and
being phased out, respectively, they can't be used down the roat in
any fashion, including handshaking, by FIPS-validated modules.

> general web browsing, you could do that pretty soon).

I disable SSLv2 in my general web browsing regardless.  If the server
doesn't support higher protocol revisions, I certainly don't want to
put my credit card information into it. :)

Cheers,

-Kyle H

---

From: EKR <[email-masked]>
Date: Fri, 29 Sep 2006 06:56:56 -0700

> incompatible fashion, and thus would create implementation problems.

I don't agree with this. The version number will indicate the change
and the implementations will adjust. We know this doesn't create major
implementation problems becauswe we've done it already, in the
SSLv3-TLS 1.0 changeover.

-Ekr

---

From: Daniel Brown <[email-masked]>
Date: Fri, 29 Sep 2006 11:22:44 -0400

> between the separate hash functions, we have nothing to fear.

I was only trying to address certain assertions being made about the 
security rationale for the TLS PRF.  Although I'm not aware of any attacks 
on the old TLS design, I fear that I understand too little the attacks on 
MD5/SHA1 to feel confident as others that preimage resistance is not going 
to be weakened, at least in the next 5 years.  That's why I would like to 
see a formal justification for the TLS PRF design, or alternative PRF 
designs.

Is there any definitive write-up (say peer-reviewed) of why the TLS PRF is 
secure?  There seems to be an eternal debate between those who think 
splitting the secret in half and XOR separate PRFs on each other has 
security greater than, or at least as good as, the sum (or maximum) of its 
parts, whereas other who think the security less than, or at most as good 
as, the minimum of its parts.  I'm not sure myself, but I would feel 
better if I see could an formal paper explaning it one way or another.

I know of a paper by Kaliski and Jonsson,  "On the Security of RSA 
Encryption in TLS", which gives a security proof assuming that one of the 
PRFs is a random oracle (regardless of whether the other is insecure, e.g. 
invertible).  That's a good start, but now that both SHA-1 and MD5 are 
showing cracks, in so far as collisions can be found faster than in random 
oracles, it would be better to give some other kind of argument not 
depending on random oracles.  By the way, I have not read their in detail 
enough to know if their argument applies to DH suites too.

For some ECDH suites, particularly 409-bit binary fields, the premaster 
secret has a fixed LSB.  While this does not have a big impact after going 
through a 1-way function, I wonder if splitting the PMS exposes this bias 
more than necessary.  In any case, 384+ bit curves are nominally intended 
to provide 192+ bits of security. I don't see how the TLS PRF can provide 
more 160 bits of security, unless one is wildly optimistic about the 
design of TLS PRF:  that it provides security equal to the sum of its 
parts (not just the maximum), i.e. 128 + 160 = 288.  If this additive 
property were true, then it would be quite easy to build one-way 
functions, which seems too good to be true.  Perhaps the objective of TLS 
PRF is something weaker than being 1-way?

Thanks,

Dan

---

From: Bodo Moeller <[email-masked]>
Date: Fri, 29 Sep 2006 18:36:47 +0200

> better if I see could an formal paper explaning it one way or another.

No, there is no such paper.  Furthermore, while it appears that using
the TLS PRF is reasonable for the currently existing ciphersuites, its
rather bizarre design imposes non-obvious design rules on new key
exchange mechanisms for TLS (they must take into account the premaster
secret splitting), so it certainly is desireable to replace the PRF
eventually.  RFC 4492, the TLS ECC specification, acknowledges that
the current TLS PRF may be replaced by a new PRF:

   ([...]                                       As of TLS 1.0 [2] and
   1.1 [3], this means that the MD5- and SHA-1-based TLS PRF serves as a
   KDF; it is conceivable that future TLS versions or new TLS extensions
   introduced in the future may vary this computation.)

> more than necessary.

Actually, for ECDH we have more to worry about fixed MSBs than fixed
LSBs.  E.g. for the 409-bit field (with about 406 or 407 bits of
entropy in the ECDH result for NIST K-409 and NIST B-409,
respectively), it is a 52-octet string that is split into two parts of
26*8 = 208 bits each.  The first (MD5) portion starts with seven bits
that are fixed to zero, and accordingly the second (SHA-1) portion
gets more than half of the total entropy.

(If there's an odd number of octets in the ECDH-result x coordinate,
then the TLS PRF has the medium octet shared between the MD5 and SHA-1
inputs, so in that case we don't waste too much entropy on MD5 either.)

>                       In any case, 384+ bit curves are nominally intended 

The additive property certainly is not true to this extent, at least
not in the sense of 1-way-ness.  But then indeed we don't actually
need a 1-way function here.  And we don't really need more than
160 bits of security against non-quantum adversaries -- and even with
160-bit entropy truncation, 256-bit AES would remain better than
128-bit AES.  It is quite reasonable to assume that more than 160
entropy bits will survive the TLS PRF, even if we assume that MD5 is
otherwise just included as a simple mask to prevent more elaborate
attacks against the SHA-1 component of the TLS PRF.

In short, one way to think of the TLS PRF is as a PRF designed to
offer at least 160 bits of security (when fed with appropriate inputs,
such as DH or ECDH results) with potentially significantly more
against various attacks that might be effective against a variant
based on a single hash function only.

I don't really expect to see any formal proofs that the TLS PRF does
better than 160 bits, but still its design appears to prevent
straightforward attacks that could be performed in on the order of
2^160 steps, or in on the order of 2^80 steps on a quantum computer.

Certainly the TLS PRF should be replaced eventually.  It just should
not be replaced too often.  If we switch to a PRF based on a single
hash function from the "SHA-2" family (SHA-224, SHA-256, SHA-384, and
SHA-512), will that be good enough?  Or should we rather wait a while
to see what is coming out of the current research, such as the
NIST's hash-function analogue of the AES selection process?

Bodo