Subject: [TLS] rm Hello.random w/ (EC)DHE [was OPTLS: Signature-less TLS 1.3]

From: Dan Brown <[email-masked]>
Date: Mon, 10 Nov 2014 17:58:12 +0000

When using (EC)DHE (inc. OPTLS below), the TLS random nonces (ClientHello.random and ServerHello.random) seem redundant (unless one re-uses ephemeral secret keys (but then maybe a counter or secure time would be almost as good a nonce as a random in this case), or perhaps for some other reason I’m missing), and perhaps even a point of fragility (e.g. if a common generator for nonces and keys is weak, or corrupted). So, does it make sense to remove these Hello.randoms, when using (EC)DHE, or to replace them with something milder, like Hello.time, Hello.counter, or just Hello.nonce?

Best regards,

Dan

From: TLS [mailto:[email-masked]] On Behalf Of Hugo Krawczyk
Sent: Friday, October 31, 2014 8:54 PM
To: [email-masked]
Cc: Hoeteck Wee
Subject: [TLS] OPTLS: Signature-less TLS 1.3

During the TLS interim meeting of last week (Oct 22 2014) I suggested that TLS
1.3 should abandon signature-based authentication (other than for certificates)
and be based solely on a combination of ephemeral Diffie-Hellman for PFS and
static Diffie-Hellman for authentication. This has multiple benefits including
major performance gain (by replacing the per-handshake RSA signature by the
server with a much cheaper elliptic curve exponentiation), compatibility with
the mechanisms required for forward secrecy, natural accommodation of a 0-RTT
option, and a simple extension without signatures for client authentication.

Below I present a schematic representation of the proposed protocol referred
to as OPTLS where OPT stands for OPTimized and/or for One-Point-Three.  
The presentation is sketchy and omits the exact procedure for key derivation.
The latter is a crucial component for the security of the protocol, but 
before getting into these details we want to get a sense of whether the WG is
interested in this approach. In the meantime, Hoeteck Wee and myself are 
working on the details of the protocol and the security proof.

We describe a setting with optional 0-RTT and server-only authentication.
Client authentication can be added as a further option or as an extension
(similar to the current 1.3 proposal) - see below.

NOTATION AND TERMINOLOGY:

[K] symbols represent pointers to key material whose exact derivation is not
included here except for specifying the basic DH values from which the key is
derived (actual derivation will include further information similar to the
extended hash mechanisms or SessionHash proposal considered for 1.3). 
Asterisks represent optional fields that the WG can decide to leave as optional,
mandatory, or simply remove without changing the core cryptographic security of
the protocol. All references to encryption mean "authenticated encryption"
using the encrypt-then-mac paradigm (or any other secure AEAD mechanism).  

KeyShare's represent ephemeral Diffie-Hellman values exchanged by the parties.
All the public key and Diffie-Hellman operations are assumed to happen over a
cyclic group with generator g of order q (typically implemented by an elliptic
curve group). We use multiplicative notation where ^ denotes exponentiation as
in g^x, g^{xy} (here xy denotes multiplication of the scalars x and y), etc.
Omitted from the current high level description is a mechanism for testing group
membership of DH values or cofactor exponentiation (the specific mechanism
depends on the group type and is typically very efficient for elliptic curves).

SERVER PUBLIC KEY AND CERTIFICATE:

The server has a long term private-public key pair denoted by (s,g^s) where 
s is uniform random in [0..q-1] (we refer to s and g^s as "static keys"). 
We assume that the server has a certificate that includes the server's public
key g^s and a CA-signed binding of this key to the server's identity.
We discuss the implementation of such certificates below.

PROTOCOL OPTLS:

ClientHello
ClientKeyShare 
ClientData* [K0]       -------->
                                           ServerHello   
                                           ServerKeyShare  
                                           ServerCertificate* [K1]
                                           ServerFinished [K2]
                       <--------           ServerData* [K2]
ClientFinished* [K2]   -------->

            Protected Application Data [K3]
                       <------->

1-RTT CASE:

The basic 1-RTT case omits the ClientData* field. It includes a ClientKeyShare
g^x and a ServerKeyShare g^y and an optional (encrypted) server certificate. 
If the certificate is sent (it can be omitted if the client has indicated that
it knows the server key as in the case in the 0-RTT scenario) and is encrypted,
the encryption key K1 is derived from g^{xy}.

Key K2 is an encryption key derived from both g^{xs} and g^{xy}. It is used to
authenticate-encrypt the ServerFinished and ClientFinished messages (which
include a hash of the previous traffic) and to encrypt data from the server if
such data is piggybacked to the second message.

Key K3 is the "application key" used to derive key material for protection of
application data.  This key material will include (directional) Authenticated
Encryption keys and, possibly, keys for derivation of further re-key material.
K3 is computed from  both g^{xs} and g^{xy} similarly to K2, but its derivation
will be different than K2, e.g., using a separating key expansion technique.

SUPPORT FOR 0-RTT: 

The above protocol is compatible with a 0-RTT protocol such as QUIC. In this
case, the client is assumed to have information about the server's public key
and other security parameters. The server is assumed to have some mechanism in
place for detecting replay (e.g., via timestamps, stored client nonces, etc.).
The resulting protocol is as described above where the ClientData field is sent
encrypted under key K0 derived from g^{xs}.  
The rest of the protocol is identical to the above.  
Note: In this case, ServerCertificate is not sent as the client had to know
the server's public key before the first message (one can imagine a setting
where the server may send a different certificate in the second message - if
desired, this can be accommodated too as an option or extension).

CLIENT AUTHENTICATION: 

Client authentication can be supported via an option or extension. It would
include a client certificate for a static DH key g^c sent in the third message 
(the certificate can be encrypted under key K2 to provide client's identity
protection). In this case, the key for computing the ClientFinished message and
the application key K3 would be derived from a combination of the values g^xy,
g^xs, g^yc (and possibly also g^{cs}). 

NOTES:

Note on Finished messages: The above spec sets ServerFinished as mandatory and
ClientFinished as optional. The latter option is needed for a 1-RTT protocol.
In principle, both Finished messages could be omitted and still obtain security
via implicit authentication (assuming the inputs to key derivation are chosen
appropriately). But given the advantages of ServerFinished for providing
explicit authentication, key confirmation, and active forward secrecy (see
below), it seems advisable to always include it. Including ClientFinished
provides key confirmation from client and also explicit client authentication
when client certificate is included. ClientFinished also provides Universal
Composable (UC) security (this is a result of the Canetti-Krawczyk proof that 
CK security implies UC security when a client confirmation step is included).  

Note on certificates: Since in current practice servers hold certificates for
RSA signature keys rather than for static DH keys, the certificate field in the
above protocol will be implemented by a pair consisting of (i) the server's RSA
signature certificate and (ii) the server's signature using this RSA key on the
server's static public DH key g^s. The latter signature by the server is
performed only when a new static DH key is created (how often this happens and
how many such keys are created is completely up to the server - it has the
advantage that these keys can be changed often to increase security against
leaked keys). This use of RSA also enjoys the high efficiency of RSA
verification for the client.  
The handling of Client certificates would be similar.

Note on forward security (a.k.a. as PFS for Perfect Forward Security): 
PFS is provided by the (mandatory) use of ephemeral Diffie-Hellman keys.
The meaning of PFS is that an attacker that finds the (long-term) static
private keys of the parties cannot compromise past session keys. Without the
ServerFinished message the above protocol ensures forward secrecy against
passive attackers (i.e., for sessions where the attacker did not choose g^y).
With ServerFinished, PFS holds also against active attackers.  A similar
consideration applies to ClientFinished.

Client certificates in the first message: We note that in cases where client
certificates can be sent in the clear in the first message of the protocol, one
can provide PFS and mutual authentication in a 1-RTT at essentially the same
cost of an unauthenticated DH exchange (i.e., a cost of little more than two
exponentiations). In such a setting one can also obtain mutual authentication in
a 0-RTT protocol (with forward secrecy with respect to the client's key).  
These options, however, require HMQV-like mechanisms and may raise IP issues (this
can be investigated further if the WG is interested).

---

From: Martin Thomson <[email-masked]>
Date: Mon, 10 Nov 2014 11:04:54 -0800

On 10 November 2014 09:58, Dan Brown <[email-masked]> wrote:
> When using (EC)DHE (inc. OPTLS below), the TLS random nonces
> (ClientHello.random and ServerHello.random) seem redundant (unless one
> re-uses ephemeral secret keys (but then maybe a counter or secure time would
> be almost as good a nonce as a random in this case), or perhaps for some
> other reason I’m missing), and perhaps even a point of fragility (e.g. if a
> common generator for nonces and keys is weak, or corrupted). So, does it
> make sense to remove these Hello.randoms, when using (EC)DHE, or to replace
> them with something milder, like Hello.time, Hello.counter, or just
> Hello.nonce?

Aren't they still highly relevant in the resumption cases?  In which
case, a new source of entropy ensures that two sessions resumed from
the same base don't have synchronized keys.

---

From: Geoffrey Keating <[email-masked]>
Date: 10 Nov 2014 11:05:51 -0800

Dan Brown <[email-masked]> writes:

> (ClientHello.random and ServerHello.random) seem redundant (unless
> one re-uses ephemeral secret keys (but then maybe a counter or
> secure time would be almost as good a nonce as a random in this
> case), or perhaps for some other reason I’m missing), and perhaps
> even a point of fragility (e.g. if a common generator for nonces and
> keys is weak, or corrupted). So, does it make sense to remove these
> Hello.randoms, when using (EC)DHE, or to replace them with something
> milder, like Hello.time, Hello.counter, or just Hello.nonce?

The client's nonce is its way of ensuring that the server has
generated a fresh signature on the server's DHE parameters.  However
you could achieve the same thing by having the server sign both its
and the client's DHE parameters, effectively treating them as a nonce.

Another thing the nonces do is ensure that even if the DHE exchange is
controlled by one side, the master secret (and therefore the
connection identification) is still different between different
connections from the client.  To preserve this you would need to
ensure all the DHE parameters are valid.  This is necessary to prevent
a triple handshake style of attack.

---

From: Nico Williams <[email-masked]>
Date: Mon, 10 Nov 2014 13:24:04 -0600

On Mon, Nov 10, 2014 at 05:58:12PM +0000, Dan Brown wrote:
> re-uses ephemeral secret keys (but then maybe a counter or secure time
> would be almost as good a nonce as a random in this case), or perhaps
> for some other reason I’m missing), and perhaps even a point of
> fragility (e.g. if a common generator for nonces and keys is weak, or
> corrupted). So, does it make sense to remove these Hello.randoms, when
> using (EC)DHE, or to replace them with something milder, like
> Hello.time, Hello.counter, or just Hello.nonce?

The main problem with the hello randoms today is that they are big.
This is what made Dual_EC deadly for TLS.  Besides, large nonces also
create a large covert channel.

Larger nonces make sense for plain PSK, static DH, and session
resumption.

For RSA key transport I don't see the point of larger nonces.

For (EC)DHE small nonces help the briefly reused server-side ephemeral
private key case, which is nice to have.

64-bit nonces should suffice for the key exchanges that need larger
nonces, no?

32-bit nonces should suffice for the key exchanges that need smaller or
no nonces.

The client should send a nonce of size matching the largest needed by
any of the ciphersuites it offers.

The server should send a nonce whose size is given by the selected
ciphersuite.

If variable size nonces are a problem (e.g., fingreprinting), then send
large nonces but set unneeded bits to one of a small set of suitable
constant patterns.

Nico
--