Subject: [TLS] Open Issue: verify_data processing

From: Eric Rescorla <[email-masked]>
Date: Tue, 17 Oct 2006 12:45:20 -0700

Stipulating for the moment that we intend to replace the PRF,
we're left with the issue of how to compute the verify_data.
Currently, the verify_data is computed as:    

           PRF(master_secret, finished_label, MD5(handshake_messages) +
           SHA-1(handshake_messages)) [0..11];

If you're not using MD5 for your PRF, it doesn't make sense to use
it here either. This leaves us with two possibilities:

1. PRF the handshake_messages directly.
2. Hash them first.

The argument for hashing them first is that it avoids having
to store them (2-5k) for the entire handshake. It also will
accomodate PRFs which won't take unlimited size data.

The argument against is that it puts the security of the 
handshake on an unkeyed hash rather than a MAC (since 
you only need to mount a 2nd preimage attack on the hash
and then you have 2nd preimage on MAC(K,hash).).

My preference here would be to move to PRF(messages) and
if new PRFs can't cope with that then they can specify
a hash reduction of their own. Recall that the PRF needs
to be able to deal with fairly large data anyway since
the PMS + randoms could easily be 300+ bytes...

Comments? 

-Ekr

P.S. Please don't use this thread to say you don't want to
replace the PRF at all. The only question here is what we
do if *do* replace the PRF.

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

---

From: Wan-Teh Chang <[email-masked]>
Date: Tue, 17 Oct 2006 14:55:55 -0700

> and then you have 2nd preimage on MAC(K,hash).).

You can use this argument against RSA, DSA, and ECDSA
signatures, too.

My preference is to hash the handshake_messages first.
The issue isn't that new PRFs can't cope with large data.
The issue is the new burden on TLS implementations to buffer
data of an indefinite length. Also consider the memory usage
of a busy TLS server that has a lot of handshakes in progress.

Wan-Teh

---

From: Vipul Gupta <[email-masked]>
Date: Tue, 17 Oct 2006 19:56:48 -0700

On Oct 17, 2006, at 2:55 PM, Wan-Teh Chang wrote:

> Eric Rescorla wrote:
>> The argument against is that it puts the security of the handshake  
>> on an unkeyed hash rather than a MAC (since you only need to mount  
>> a 2nd preimage attack on the hash

   I would also prefer hashing. Our research team has successfully
created a TLS stack for tiny, wireless sensor devices like the
Berkeley "motes" with only 4KB of RAM (see
http://research.sun.com/spotlight/2004-12-20_vgupta.html
http://research.sun.com/projects/crypto/guptav_sizzle_pmc.pdf).
If the spec were modified to require storing the handshake messages
in full, then TLS (and derivatives like DTLS) would pretty much
be ruled out for this emerging class of devices.

vipul

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 18 Oct 2006 13:23:40 +0200

> be ruled out for this emerging class of devices.

One idea would be to make it possible to negotiate whether to hash the
handshake messages or not.

Perhaps by having the ciphersuite implies that a particular PRF is
used with or without hashing.

Personally, I would prefer to use the entire handshake messages as
input to the PRF, but I agree that you have a compelling argument to
hash them.

/Simon

---

From: <[email-masked]>
Date: Wed, 18 Oct 2006 18:14:54 +0300

> be ruled out for this emerging class of devices.

Is it obvious that hashing the messages requires less memory? Much of
the information in the handshake messages is either static, or has to
be kept around anyway -- and running hashes requires state, too.

For example, consider a TLS server that has just sent ServerHelloDone,
and has negotiated an RSA-based ciphersuite. At this point, the only
pieces of information from the handshake messages the server can
safely discard are:

- ClientHello.compression_methods (usually 2 bytes)
- ClientHello.cipher_suites (hmm.. 22 bytes with 10 ciphersuites?)
- ClientHello.session_id (just 1 byte if not resuming)
- Any unrecognized extensions in ClientHello (usually none)

All the rest has to be kept around anyway (at this point); and I'm
assuming the server certificate is static, so it's kept around 
anyway (once, not separately for each TLS session).

In other words: at this particular point-of-time, hashing would allow
discarding ~25 bytes of information, at the cost of storing the hash
context -- which in e.g. OpenSSL is 96 bytes for SHA-1 and 216 bytes 
for SHA-512. 

If we're using RSA ciphersuites and a PRF that requires only one pass
over the data, the client can start calculating verify_data as soon as
ServerHello has been received, so it's not obvious that first
calculating
a hash and then running PRF over the hash would actually save anything. 

Best regards,
Pasi

---

From: "Ben Laurie" <[email-masked]>
Date: Wed, 18 Oct 2006 18:10:32 +0100

> and then you have 2nd preimage on MAC(K,hash).).

A pedantic quibble here: this makes the assumption that a hash can
always be calculated by chaining partial inputs, which is not a
required property of hashes, just one we're used to having.

---

From: David Hopwood <[email-masked]>
Date: Wed, 18 Oct 2006 23:43:19 +0100

> handshake messages or not.

Please, no. Not only does this unnecessarily complicate the protocol and
its security analysis, it gives an attacker more options as to what to
attack.

(In general, adding negotiated alternatives as to how the handshake is
*verified* is a bad idea. Just decide on one of the possibilities; that
will almost never be worse than negotiation from a security point of view.)

-- 
David Hopwood <[email-masked]>

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Wed, 18 Oct 2006 18:52:24 -0400

> required property of hashes, just one we're used to having.
Indeed.  In fact, the desirability of this property has been raised at
some of the NIST hash function workshops -- some people think we will not
be able to preserve it in a future secure hash function.

		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

---

From: Martin Rex <[email-masked]>
Date: Thu, 19 Oct 2006 02:33:48 +0200 (MET DST)

> be kept around anyway -- and running hashes requires state, too.

The memory requirements are significantly higher if the protocol
stack needs to keep all of the handshake messages around, and
a lot more code is required resulting in more bugs.

How much of the information from small&friendly handshake
message are retained with the session state is entirely irrelevant
here.  Some of the values may not be stored in the original form,
i.e. some implementations will store some protocol values as
byte values, others will store it as integers of varying sizes
(which may reverse the order of LSB/MSB in memory), and it
would result in extremely bloated and error-prone code if an
implementation tried to compute the hash over the handshake
messages from unparsed session state information.

There were proposals to allow additional handshake messages,
the client hello can carry an extension which the server does not
need to recognize, but which goes into the hanshake message hash.
Then there is a cert request message with a list of trusted CAs
which may be fairly long, and cert messages may actually contain
fairly long certificate chains, not only one single certificate.

Personally, I found the original scheme much more appealing
(smaller memory footprint, smaller code), where
the protocol stack did NOT need to keep the handshake messages
around.

Is there a real-world security benefit (not a pure academic one)
justifying such a burden-some change?

-Martin

---

From: Martin Rex <[email-masked]>
Date: Thu, 19 Oct 2006 03:08:04 +0200 (MET DST)

> be able to preserve it in a future secure hash function.

It will be interesting to see how they're going to sell such
hash functions to current consumers of PKI-based software.

PKCS#7/CMS as well as Web services security (xmlsig) applies digital
signatures to quite large blobs of data today.  Some of that data
does not fit into memory already today, and one definitely does
not want such a requirement on a busy server.

So any hash function without that property is likely not going
to be suitable for a drop-in replacement of installed base
PKI-based software.

-Martin

---

From: "Ben Laurie" <[email-masked]>
Date: Thu, 19 Oct 2006 03:28:15 +0100

> to be suitable for a drop-in replacement of installed base

So, a throwaway observation is that you can always derive a chained
hash function from an unchained one, by hashing fixed-size blocks then
hashing the hashes. Whether this preserves the properties needed I
suspect depends on the hash function and the block size.