Subject: [TLS] Avoiding Trial Decryption (for 0-RTT)

From: Karthik Bhargavan <[email-masked]>
Date: Sat, 2 Apr 2016 19:53:16 +0200

TLS 1.3 0-RTT introduces an “optimistic” mode where the client 
encrypts data that the server can then accept or reject.

In the case when the server rejects 0-RTT, the server is left in a somewhat
ugly state where it will receive, in sequence:
(a) encrypted 0-RTT handshake data (that it needs to throw away)
(b) encrypted 0-RTT application data (that it needs to throw away)
(c) encrypted 1-RTT handshake data (that it needs to process)

Since we have removed content types from the record headers
of encrypted messages, these 3 flights of messages look the same.
So, the current draft requires the server to “trial decrypt” each message
with the 1-RTT Handshake keys, in order to detect where (c) begins, and 
to discard packets that do not decrypt correctly. 

The situation can be even worse. Suppose the client sends a ClientHello
and 0-RTT data, the server responds with a HelloRetryRequest, and
now the client sends a new ClientHello and new 0-RTT data.
In this case, we have (a), (b), (a), (b), (c); that is, the server needs
to skip 4 flights of messages by trial decryption before getting to the 1-RTT handshake data.

This seems inefficient and inelegant, and it may open up a new attack
vector where an attacker may sent many messages and get the 
server to decrypt them under the same key (and same IV, etc). 
In other modes of TLS, a single decryption failure would close
the connection, so this mode of attack is new and we may need to take care.

Here is a proposal that would avoid trial decryption.
When the client sends 0-RTT application data, it currently
ends this flight of messages with an encrypted end_of_early data warning alert.
How about: if the server rejects trial decryption, the client
must then send an *unencrypted* end_of_early_data warning alert before
continuing with 1-RTT handshake data.
The server could then easily discard all records until it sees this warning alert.

The main disadvantage of this approach seems to be that it reveals to the adversary
the point at which the 0-RTT application data ends (if this is sensitive information.)
However, note that if the length of 0-RTT data was sensitive, an attacker
could probably already obtain it by delaying the server flight.

Does anyone see other practical or security disadvantages to using this alert?

Best regards,
Karthik

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 3 Apr 2016 14:43:51 +0300

> the 1-RTT handshake data.

And with DTLS, one can get even more wonderful cases from all sorts of
datagram reordering. Including things like 1st round encrypted 0-RTT data
being interpretted as 2nd round encrypted 0-RTT data (it won't decrypt).

Oh, and also 0-RTT data being received after handshake has already
finished.

Well, in rejection case in (stream) TLS, you get ClientHello with its
different content type in the middle. But that won't help with the last
handshake.

> The server could then easily discard all records until it sees this warning alert.

Only works on (stream) TLS, but in DTLS this can presumably be deduced from
epoch numbers.

> could probably already obtain it by delaying the server flight.

Also, the length could probably be obtained passively from message sizes, unless
the implementation is very careful with padding (with high overhead).

-Ilari

---

From: "Kaduk, Ben" <[email-masked]>
Date: Mon, 4 Apr 2016 14:44:50 +0000

>Does anyone see other practical or security disadvantages to using this alert?

I tried to think of ways that a misbehaving client (or attacker) could cause a server relying on the unencrypted alert to consume resources and sit around waiting for a long time, but it seems like the unencrypted alert is strictly better than trial decryption in that regard (since the server doesn't have to burn CPU on decryption).  So, it seems that revealing the length of the 0-RTT data is the main disadvantage, but as Ilari notes, there are likely to be other channels that would leak that boundary in many cases.

Using the unencrypted alert does also provide a clear indication that the client/server failed to exchange 0-RTT data; for a PSK mode with a cache of 0-RTT sessions this could provide a window into the validity periods used by the two parties or as a signal that a finite-sized cache is full and ejecting old entries.  Perhaps an attacker could use that signal to determine the rate of some other sort of attack that requires getting a session evicted from the cache, but the need for such a signal seems pretty hypothetical, given that an attacker can already claim to be as many different clients as it wants.

-Ben