Subject: [TLS] Signed messages should be prefixed with a NUL-terminated context string.

From: Adam Langley <[email-masked]>
Date: Mon, 24 Nov 2014 22:55:29 -0800

I generally recommend that, whenever signing a message, a
NUL-terminated, ASCII context string is prepended to the message to
ensure that the verifier isn't confused about the context.
(NUL-terminated, ASCII strings have the property that none is a prefix
of any other.)

I think that TLS 1.3 provides a good demonstration of why:

Mavrogiannopoulos, Vercauteren, Velichkov and Preneel[1] showed a
near-miss in the design of TLS <= 1.2 due to a lack of context in
ServerKeyExchange messages resulting in an ambiguity about whether a
specific message was DHE or ECDHE.

TLS 1.3 has the server return a CertificateVerify message[2] that
signs the handshake so far, similar to TLS <= 1.2's message of the
same name. However, consider a client that implements any version of
TLS and a server that implements TLS 1.3:

An attacker watches for the ClientHello from the client. Assume, as is
quite common now, that the client generates its client_random with 32
random bytes (i.e. there's no timestamp). With probability 2^-32, the
client_random will start with 0x0100 and bytes 4 and 5 will be 0x03
and 0x04.

The attacker now connects to the TLS 1.3 server and sends a
ClientHello such that the prefix of the message (including handshake
message type and length) is equal to the victim client's client_random
value. (Most of the bytes can be put into the attacker's client_random
value and the restriction on the victim client's message ensures that
the handshake type, length and protocol version are taken care of.)

With the rest of the ClientHello, the attacker is free to make the TLS
1.3 handshake look like a TLS 1.2 ServerKeyExchange message. An
obvious choice is to stuff a dummy server_random into the session ID
and specify a small p and g such that a discrete-log is easy, then
consume the rest of the handshake with a huge Y. (The length of the
TLS 1.3 handshake from the server is predictable.)

Some clients might check that Y < p but, if they do the obvious thing,
then the TLS 1.3 server's signature over the handshake can be used as
a TLS 1.2 ServerKeyExchange signature and the client compromised.

I may have missed something and, even if not, the restrictions on the
client's client_random value make it an expensive attack to pull off.
But it's still another near-miss.

Thus I suggest that signed messages in TLS 1.3 be prefixed with
context strings. For example, "TLS 1.3 CertificateVerify message from
server\x00" in this case.

However, since TLS <= 1.2 provides an attacker the ability to get a
signature for a message with a 32-byte, chosen prefix via the
ServerKeyExchange, I additionally suggest that the context string
start with 48-64 bytes of "PADTLS" repeated, in order to clear that
prefix and cover part or all of the server_random.

(And that signature oracle in TLS <= 1.2 provides another reason,
should any be needed, not to run a CA:TRUE certificate on a server.)

[1] https://www.cosic.esat.kuleuven.be/publications/article-2216.pdf
[2] https://tlswg.github.io/tls13-spec/#rfc.section.7.4.7
[3] https://tools.ietf.org/html/rfc5246#section-7.4.1.2
[4] https://tools.ietf.org/html/rfc5246#section-7.4.3

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 25 Nov 2014 13:39:57 +0100

----- Original Message -----
> I think that TLS 1.3 provides a good demonstration of why:
[...]
> TLS and a server that implements TLS 1.3:

Thanks for bringing that up, as it is an interesting issue. I read the changes
to TLS 1.3, and the current approach in TLS 1.3. as I understand is to use the 
following construction for both client and server certificate verify.
      struct {
           digitally-signed struct {
               opaque handshake_messages[handshake_messages_length];
           }
      } CertificateVerify;

That would mean that CertificateVerify is compatible between a server and client,
and I believe this was the thing the designers of SSL 3.0 wanted to avoid when
they made different signature formats for each message.

To add to your attack for that construction, an attack in early crypto
protocols was a client using the server signed response to authenticate using the 
server's own key (Unfortunately I don't remember where this was first described).
While in TLS 1.3 the hash contents will be different at the point both messages 
are sent, and the attack doesn't directly apply, I think the fact that the format 
of two different signatures matches cleanly is a reason for concern.

I am for using any kind of distinguisher to make these messages context dependent.

regards,
Nikos

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 25 Nov 2014 08:40:48 -0800

This seems like a good idea. Thanks for raising it.

If you want to make a PR, I will merge it in.

-Ekr

On Mon, Nov 24, 2014 at 10:55 PM, Adam Langley <[email-masked]>
wrote:

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

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Wed, 26 Nov 2014 02:40:12 -0500 (EST)

----- Original Message -----
> This seems like a good idea. Thanks for raising it.

An additional issue of switching to the new CertificateVerify
format for client and server, is that privilege separation for
authentication is not possible any more.

On a previous mail I was asking for that feature to be extended for the 
server as well:
http://www.ietf.org/mail-archive/web/tls/current/msg13398.html

Was the removal of that protocol feature intentional?

If not I'd suggest the following format for the signatures:
      struct {
           digitally-signed struct {
               opaque client_random[32];
               opaque server_random[32];
               opaque handshake_messages[handshake_messages_length];
           }
      } CertificateVerify;

regards,
Nikos

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 26 Nov 2014 06:09:38 -0800

> Was the removal of that protocol feature intentional?

Not really. I was aiming for unifying the structures.

>                opaque handshake_messages[handshake_messages_length];

I've filed https://github.com/tlswg/tls13-spec/issues/97 so this doesn't get
lost.

If someone wants to contribute a PR so that we can have something
concrete to look at that would be even better.

Best
-Ekr