Subject: [TLS] Kill Finished (and other tricks for hardware)

From: Watson Ladd <[email-masked]>
Date: Thu, 17 Apr 2014 18:03:31 -0700

Dear all,

Recently Michael St. Thomas pointed out the PRF is painful in
hardware. It's painful in software if you do monadic tricks to ensure
keys are only encrypted with and never sent over the wire or process
isolation to ensure that they are never read. So I'll make a radical
proposal, and it will get pared down to something acceptable over
time.

So I propose the following changes: Client IV starts at 0 and proceeds
through the even numbers, Server IV from 1 and proceeds through the
odd numbers.

Finished dies. Instead we hash the entire handshake, certs and all
into the master secret. This has the side effect of making life for
cryptographers a lot nicer. I've not figured out resumption quite yet:
maybe this is a problem there. I've also probably missed some other
outputs that need munging or replacements.

This way the PRF is only used to generate keys, so it can be marked at
such. There aren't any security implications: we've replaced finished
with the master secret hashing, so the only way to get two identical
master secrets is from identical exchanges.

Sincerely,
Watson Ladd

---

From: Nico Williams <[email-masked]>
Date: Thu, 17 Apr 2014 20:10:24 -0500

This would require updating the tls-unique channel binding (which the
resumption bug doesn't: just fix resumption).

Also, are you proposing to have no message which demonstrates
possession of the shared master secret immediately after being able to
compute it?

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Thu, 17 Apr 2014 18:35:51 -0700

> resumption bug doesn't: just fix resumption).

You have a master key: do another extraction from it. I don't see this
as unsolvable.

> possession of the shared master secret immediately after being able to

Yes. Key confirmations are useful in extremely limited circumstances.
Furthermore, this fixes the issue with 1-RTT proposals where a
modified handshake might not get detected until data was sent on a
downgraded channel.

Sincerely,
Watson Ladd

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

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 17 Apr 2014 19:13:04 -0700

> proposal, and it will get pared down to something acceptable over

Interesting suggestion. I have some questions/thoughts below.

> through the even numbers, Server IV from 1 and proceeds through the

Can you elaborate more on what you have in mind here? In the current
GCM mode, the per-packet nonce is formed from a fixed "IV" generated
by the PRF (as described by Mike) and a per-packet value which is
carried in the packet. What structure were you thinking of here?

Also, what's the advantage of partitioning the IV space like this if you
use separate keys in each direction?

> outputs that need munging or replacements.

How would this interact with wanting to encrypt parts of the handshake,
e.g., the client's certificate? I.e., we need to generate keys which we
can use to encrypt the certificate, but these must be generated prior to
the certificate being transmitted. Were you thinking we would have two
sets of keys? We wouldn't hash them into the keys? Something else?

-Ekr

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

---

From: Nico Williams <[email-masked]>
Date: Thu, 17 Apr 2014 21:23:35 -0500

> You have a master key: do another extraction from it. I don't see this

I was pointing out a fact.  Clearly it's solvable.

> Yes. Key confirmations are useful in extremely limited circumstances.

Are key confirmations cargo cult?  It depends:

If one is doing channel binding then a channel binding confirmation
-which might look much the same as key confirmation- is needed.  The
reason is that the point of CB is to leave encryption to the
lower-layer channel, but only if there was no MITM there.

If one is not doing channel binding then I believe no key confirmation
is needed.

The Kerberos AP exchange is a clear case of this.  When no CB is used
what does one gain from key confirmation in Kerberos?  Nothing, IMO.
If you trust your KDC and the cryptosystem then really, who cares if
you're feeding ciphertext to a party that lacks the key to decrypt it
with?

But in the Kerberos GSS mechanism the AP-REP message serves as the
channel binding confirmation message, so if one is doing CB then
clearly one also wants that AP-REP.

> modified handshake might not get detected until data was sent on a

Only by removing the thing that the modification of which would have
been detected.  The "issue" remains in some sense, or it was never
really an issue.  Let's focus on whether and when we need key
confirmation.

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Thu, 17 Apr 2014 20:38:12 -0700

> carried in the packet. What structure were you thinking of here?

Nonces as incrementing integers. Each side tracks the other's nonce,
or you can put them on the wire if you want.

> use separate keys in each direction?

None. I forgot we did this.
> sets of keys? We wouldn't hash them into the keys? Something else?

So I wasn't thinking in terms of anything more than a 1-RTT handshake.
If you want to encrypt portions of the handshake, I would hash the
ciphertext in. I wasn't going to reuse anything from the key
generation of those keys.

Sincerely,
Watson Ladd

---

From: Michael D'Errico <[email-masked]>
Date: Thu, 17 Apr 2014 22:59:34 -0700

Watson Ladd wrote:
> 
> So I propose the following changes:...
> 

The Finished messages are equivalent to "Can you hear me now?" spoken
over the encrypted link, with an affirmative reply in both directions.
Without them, you just start talking and hope that the other side can
hear you.

The only way for a sender to know there's a problem is to receive an
alert (which can't be decrypted) and/or a dropped connection.  If the
other side is also sending application_data, then a failed decryption
will indicate a problem.

This is a much weaker failure indication than checking the Finished
messages, so I'd prefer to keep them.  Can you think of an alternate
construction for the Finished message that doesn't use the PRF?

Mike

---

From: Michael StJohns <[email-masked]>
Date: Fri, 18 Apr 2014 10:44:59 -0400

Edited and comments in line.

On 4/18/2014 1:59 AM, Michael D'Errico wrote:
>> Finished dies.  .........

The simplest thing here is to use the negotiated PRF algorithm 
(SecurityParameters.prf_algorithm, not the TLS PRF wrapper around that 
algorithm) directly, but key it with a different key than the master 
secret that would also be derived from the pre-master secret.

_____________________________________________________

draft-stjohns-tls-tls13-crypto-infra has the complete details on what 
I'm proposing along with the above.  It recommends doing a straight MAC 
over the handshake data, but I realized last night that that might not 
(will not?) be possible as you may not (will not?) have the derived key 
you're going to need for this until later in the processing.  You'd have 
to keep a copy of the negotiation messages around until you acquired the 
other side's random data (e.g. on the client side until you heard 
ServerHello).  So having some sort of summary function is going to be 
necessary.    We know how to do this for hash-based (e.g. HMAC) MACs 
(use the underlying hash directly), but would have to define something 
for a block-cipher (e.g. CMAC) MAC to do the summary function - probably 
using the CMAC with a zero key.

So something like:

if MAC is a CMAC then
      verify_data = MAC (handshake_key, MAC (0, 
handshake_messages))[0..verify_data_length-1];
else
     verify_data = MAC (handshake_key, HASH 
(handshake_messages))[0..verify_data_length-1];

Mike

---

From: Watson Ladd <[email-masked]>
Date: Fri, 18 Apr 2014 07:58:17 -0700

Dear all:
I screwed up my reply and Nicos argued it needed to be sent to the list.

> lower-layer channel, but only if there was no MITM there.

Is channel binding really necessary in TLS? I agree key extractors
are, but I think the cases where TLS is layered on encrypted channels
are pretty rare. Of course if TCPcrypt becomes more common this will
change. But I don't see how to do a key confirmation and 1-RTT in the
same handshake: we may end up with options, and then have to be very,
very careful in hashing the handshake. Chalk this up to me neglecting
a usecase.

> If one is not doing channel binding then I believe no key confirmation

That's correct: You can't get PFS but only weak PFS. However, weak PFS
is good enough. No two message protocol can achieve PFS.

> really an issue.  Let's focus on whether and when we need key

I was completely confused. You can have

C->S: here's my key
S->C: here's my exchange and half of the confirmation
C->S: confirmation and my data.
S->C: response

a 1-RTT handshake in which the Finished message actually protects the handshake.

Sincerely,
Watson Ladd

---

From: Watson Ladd <[email-masked]>
Date: Fri, 18 Apr 2014 08:15:47 -0700

On Fri, Apr 18, 2014 at 7:44 AM, Michael StJohns <[email-masked]> wrote:
> algorithm) directly, but key it with a different key than the master secret
> that would also be derived from the pre-master secret.

This still has the key-dependent encryption issue. If we fix the key
generation, the finished messages can be constants.
If we need to use finished messages related to keys, then for
technical reasons verification gets hard.

I'm not an expert on this matter: I only had it explained to me at
DIAC '13 by someone. I don't know how the miTLS paper deals with it,
or if new methods can avoid it. There are key-confirmation messages
that do not have this issue.

It does fix your hardware issue though.
> draft-stjohns-tls-tls13-crypto-infra has the complete details on what I'm
> proposing along with the above.  It recommends doing a straight MAC over the
> handshake data, but I realized last night that that might not (will not?) be
> possible as you may not (will not?) have the derived key you're going to
> need for this until later in the processing.  You'd have to keep a copy of
> the negotiation messages around until you acquired the other side's random
> data (e.g. on the client side until you heard ServerHello).  So having some
> sort of summary function is going to be necessary.    We know how to do this
> for hash-based (e.g. HMAC) MACs (use the underlying hash directly), but
> would have to define something for a block-cipher (e.g. CMAC) MAC to do the
> summary function - probably using the CMAC with a zero key.

There is a problem here: CMAC is a MAC, not a hash. In particular, I
can make collisions in CMAC(0, message) trivially, by letting m_1' be
the decryption of m_2+m_2'.

Sincerely,
Watson Ladd

---

From: Henrick Hellström <[email-masked]>
Date: Fri, 18 Apr 2014 17:16:55 +0200

> construction for the Finished message that doesn't use the PRF?

Indeed. The client (being the last peer of the connection to send a 
random handshake message, and being in a position to pick the 
pre_master_secret) will have a quadratically improved chance of picking 
a specific master_secret.

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 18 Apr 2014 18:36:31 +0300

> very careful in hashing the handshake. Chalk this up to me neglecting

AFAIK, This isn't about binding TLS to something underneath, but about
binding something over TLS into the TLS.

Naively, one would expect signing a value from TLS-extractor to provode
channel binding.

Currently this does not hold because:
- Non-FS key exchanges.
- FS key exchanges not binding DH public keys into master secret
  (allows MITM to play games resulting same MS on both sides).

And yes, if there is TCPCrypt running, that's whole another ballgame.

-Ilari

---

From: Michael StJohns <[email-masked]>
Date: Fri, 18 Apr 2014 12:10:49 -0400

> master secrets is from identical exchanges.

Not quite.  You missed that IVs are generated using the PRF and that's 
another problem.

My PRF proposal is to change the PRF to a counter based PRF

prf_step (i, secret, label, context, total_length) =
      MAC (secret, i + label + 0x00 + context + total_length); // i and 
total_length are uint32 big endian

prf_data (secret, label, context, total_length) =
      CONCAT (i = 1 to CEIL(total_length/blocksize), prf_step (i, 
secret, label, context, total_length))[0..total_length-1];

For deriving keys, you use the above construct and a master secret. For 
using this for the production of random public data (e.g. IVs), you use 
a '0' key of the appropriate length.  The externalized functions are the 
KDF function (which passes in a key) and the DRBG (deterministic random 
bit generator) (which doesn't pass in a key), but the underlying 
implementation is common.  The PRF function is never externalized.

The above construct is the same as defined in NIST SP800-108 (no, not 
dual EC...) and is similar to KDF and DRBG constructs used with X9.63, 
ECDH etc

Mike

---

From: Andy Lutomirski <[email-masked]>
Date: Fri, 18 Apr 2014 11:56:25 -0700

> If one is not doing channel binding then I believe no key confirmation

Playing the devil's advocate:

Suppose I'm using client certificates and I have a server that takes
some action as soon as an authenticated client connects.  Without some
kind of key confirmation, this stops being secure.

Fixing it may be as simple as having the client send an empty record
after the handshake.

I don't see this being a problem in the other direction.  Without key
confirmation, a MITM could trick a client into thinking it connected to
the server, and the client wouldn't notice until it sent some data and
never gets any response.  But even with key confirmation, a MITM can do
more or less the same thing, just by severing the connection after the
handshake.

--Andy

---

From: Michael D'Errico <[email-masked]>
Date: Fri, 18 Apr 2014 12:09:52 -0700

Watson Ladd wrote:
> If we fix the key generation, the finished messages can be constants.

IANAC but using a long-enough "magic number" for Finished seems fine
if the handshake hash is moved to the key generator.

But how long should that magic number be?  Currently we use 12 bytes,
but should it be 16 or maybe even 32 bytes (when negotiating 256-bits
of security)?  Can it be a simple string of zeros?

Mike

---

From: Martin Thomson <[email-masked]>
Date: Fri, 18 Apr 2014 13:21:05 -0700

> of security)?  Can it be a simple string of zeros?

Why would it need to be anything at all?  As long as you can identify
the message as a Finished unambiguously, that should suffice.
HandshakeType is one byte.

---

From: Michael D'Errico <[email-masked]>
Date: Fri, 18 Apr 2014 13:26:53 -0700

Martin Thomson wrote:
>> But how long should that magic number be? ....
> 

Oh, I see, as long as you can decrypt the record layer, you know it's
working.

Mike

---

From: Martin Thomson <[email-masked]>
Date: Fri, 18 Apr 2014 13:29:22 -0700

> Oh, I see, as long as you can decrypt the record layer, you know it's

Yep, either that or the record layer is busted :)

---

From: Henrick Hellström <[email-masked]>
Date: Sun, 20 Apr 2014 10:47:26 +0200

On 2014-04-18 17:39, Watson Ladd wrote:
> On Fri, Apr 18, 2014 at 8:16 AM, Henrick Hellström <[email-masked]> wrote:
>> Indeed. The client (being the last peer of the connection to send a random
>> handshake message, and being in a position to pick the pre_master_secret)
>> will have a quadratically improved chance of picking a specific
>> master_secret

Please note that this relevant in the context of removing the Finished 
messages and including the handshake hash in the KDF step, because of 
the following questions:

   #1. How easy is it for an attacker to pick one specific master_secret 
as the output of a handshake?
   #2. How easy is it for an attacker to pick any master_secret, that 
happens to produce the correct finished messages and a partially chosen 
key block (e.g. with only one write key chosen) when the handshake hash 
is not included in the KDF step?
   #3. How easy is it for an attacker to pick any master_secret, that 
happens to produce a partially chosen key block (e.g. with only one 
write key chosen) when the handshake hash is included in the KDF step?

(I am not elaborating on exactly what kind of practical attacks would 
become possible if the attacker picks a partially correct master_secret. 
It suffice to say that it doesn't seem to be something that should be 
easy to do.)

It seems reasonable to assume that case #1 and case #2 are equivalent, 
i.e. since the PRF is invoked three times with the same key material 
(master_secret) and different labels and seeds, picking a partially 
correct master_secret is not easier than picking the exactly correct 
master_secret.

However, if the PRF is only invoked once with the master_secret as key 
material and the handshake hash as seed, it is not self-evident that 
case #3 is as hard as case #1. In particular, #3 might be significantly 
easier for some PRF algorithms than other.

Generally speaking, though, irregardless of the security properties of 
the PRF, the case of collision attacks ought to be considered.

Suppose an attacker is trying to get two different connections to have 
the same client_write_encryption key. With a 128 bit security cipher 
suite, this key will be 128 bits, and getting a collision in 128 bits 
only require an 2^64 effort, even if the PRF is completely perfect.

> Care to expand on this? For noncontributory exchanges you may be
> correct, but ECDHE is contributory.

I am comparing the chances the server has to choose the master_secret, 
to the chances the client has.
   - When the server_key_exchange is sent, the server doesn't know what 
the client will send, so the server has no better chance than random to 
pick the master_secret.
   - When the client_key_exchange is generated, the client will in 
principle be able to predict the master_secret before sending the 
client_key_exchange message.

In particular, if e.g. ECDHE-P256 is used, then presuming the TLS PRF 
preserves entropy up to at least 256 bits, the server will have on 
average a one in 2^255 chance of picking the "right" master_secret, 
because the server is gambling on what 256 bit ephemeral private key the 
client will pick. The client will however be able to pick the pre_master 
secret with a 2*2^128 effort (based solely on the DLP strength of EC-P256).

Now, for the same reason, if someone proposes a cipher suite that 
significantly weakens the PRF/KDF (e.g. by basing it solely on AES 
without ensuring the function is one way), eliminating the finished 
messages will potentially enable a man-in-the-middle to have 
significantly better chance than 1 on 2^256 to pick a master secret that 
is "almost" right and at least results in a chosen client_write_key.

---

From: Michael Procter <[email-masked]>
Date: Sun, 20 Apr 2014 15:12:52 +0100

> HandshakeType is one byte.

Does a single byte Finished message mean that a MiTM attacker that
modifies, say, the ClientHello, has a 1 in 256 chance that the
server's Finished message will be decoded correctly by the client?
Clearly the whole session isn't going to work well after this, but the
client is likely to emit a bunch of ciphertext before either end
realises the problem.

Regards,

Michael

---

From: Michael Procter <[email-masked]>
Date: Sun, 20 Apr 2014 17:09:52 +0100

I've been reminded off-list about the write_mac key!  Whilst my
comment is basically true in terms of not verifying the encryption
key, it is wrong in that for the Finished byte to be authenticated
correctly, the same write_mac key will need to be derived at both
ends.

---

From: Michael StJohns <[email-masked]>
Date: Sun, 20 Apr 2014 15:54:16 -0400

> Oh, I see, as long as you can decrypt the record layer, you know it's

There's a question here as to whether or not there's an attack that's 
enabled by changing things in the handshake that don't affect the 
production of the key material.  E.g. addition or subtraction of offered 
or accepted extensions for example.

In some ways, the right answer might be to do a finished signature not 
over the messages, but over the content of SecurityParameters - with 
assumption that the SecurityParameters pseudo-structure is extended to 
provide enough information about offers and acceptances.

Mike

---

From: Watson Ladd <[email-masked]>
Date: Sun, 20 Apr 2014 13:21:48 -0700

On Sun, Apr 20, 2014 at 12:54 PM, Michael StJohns
<[email-masked]> wrote:
> enabled by changing things in the handshake that don't affect the production
> of the key material.  E.g. addition or subtraction of offered or accepted
> extensions for example.

There absolutely is in TLS 1.2 and lower. Remove a supported curves
extension and you cause a fallback to non-PFS ciphersuite. Maybe that
is "affecting the production of the key material", but it's only
noticeable in the ClientHello. Also, remove secure_renegotation and
life can get interesting again.

>
> In some ways, the right answer might be to do a finished signature not over
> the messages, but over the content of SecurityParameters - with assumption
> that the SecurityParameters pseudo-structure is extended to provide enough
> information about offers and acceptances.

Why bother when we have the transcript which gives us exactly that?
What you propose can work, but if we mess it up it won't be pretty.
Furthermore, if an extension isn't actually authenticated that's a
rather big semantic gap. Suppose ALPN wasn't authenticated, and the
same string could have two different meanings under two different
protocols. The right answer is never to remove properties TLS provides
today.

Sincerely,
Watson Ladd

---

From: Martin Thomson <[email-masked]>
Date: Mon, 21 Apr 2014 11:54:02 -0700

On 20 April 2014 13:21, Watson Ladd <[email-masked]> wrote:
> Suppose ALPN wasn't authenticated, and the

I certainly have a use case that depends on ALPN being protected by
the handshake.  And I think that Watson's more generally right here.
The basic guarantee is that the entire handshake is covered, either by
Finished (as in TLS 1.2 and earlier), or by using it as input to the
PRF (as Watson has proposed).

---

From: Michael StJohns <[email-masked]>
Date: Tue, 29 Apr 2014 14:18:24 -0400

Meant to finish up on this.

> Why bother when we have the transcript which gives us exactly that?

Because, you have to start the transcript before you know which summary 
function you're going to negotiate - e.g. which PRF for the 
cryptosuite.  That gives you some issues with respect to negotiation of 
the PRF (and as we've been talking about an issue doing this for block 
cipher based PRFs)

A signature over the transcript of all messages is really about signing 
the final snapshot state the results from those messages. In an ideal 
world, SecurityParameters would hold all of that state.   AFAIK, 
SecurityParameters currently appears to hold all of the state except 
that generated from extension negotiation. Adding that in would allow a 
single HMAC signature over the SecurityParameters pseudo structure to 
replace the current HASH the messages then HMAC approach used to provide 
the Finished message tag.

As I suggested elsewhere - it really should be possible to build a 
lightweight TLS1.3 system based on PSK and using only the AES block 
encrypt function.  (Or other block encrypt function for other domains).  
To enable this, we either need to get the summary function 
(HASH(handshake_messages)) out of the middle, OR come up with a pretty 
standard block-cipher based hashing mechanism.

The problem with the latter approach is that I'm unable to find a 
"standard" (e.g. issued by IEEE, NIST, X9 etc) block cipher hash 
construct.  There are plenty of academic papers, but nothing that meets 
the "BCP" (Best Commercial Practice) smell test.

> protocols. The right answer is never to remove properties TLS provides

The right answer is to understand what properties you actually get and 
make sure they're providing what you want and need (c.f. heartbeat for a 
counter example).   Even crypto specifications say that it's ok to do 
things in different ways as long as you get the same answers.