Subject: [TLS] OPTLS: Signature-less TLS 1.3

From: Hugo Krawczyk <[email-masked]>
Date: Sat, 1 Nov 2014 02:54:08 +0200

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: Eric Rescorla <[email-masked]>
Date: Fri, 31 Oct 2014 18:44:35 -0700

Hugo,

Thanks for writing this up. I'm still digesting this, but I had a few
questions.

1. In the interim, I believe you suggested MAC of the transcript under
g^{xs} to authenticate g^y. This is fairly analogous to CertificateVerify,
except using a MAC rather than a signature. In the current design, you
instead generate a combined key from g^{xs] and g^{xy}. Are there
advantages to this design or is it just a matter of style?

2. I'm thinking about how to adapt this to PSK+PFS modes (i.e.,
where you want the PSK for authentication but you want to do
a DHE exchange for PFS). In the design you propose, it seems
like the analogous thing to do would be to treat the PSK like
g^{xy}? Does this interact at all with whether to mix the keys
or use a MAC?

3. WRT client auth, I think we've generally decided that the client's
certificate ought to be encrypted. Given that, I wonder if it would be
easier
for the client to just do a digital signature over the transcript and/or
an authenticator derived from the secret. Generally, the additional
cost of the RSA signature isn't a huge problem for most clients and
those which do should be able to quickly move to EC-based keys.

Thanks,
-Ekr

On Fri, Oct 31, 2014 at 5:54 PM, Hugo Krawczyk <[email-masked]>
wrote:

> All the public key and Diffie-Hellman operations are assumed to happen
> over a
> curve group). We use multiplicative notation where ^ denotes
> exponentiation as
> Key K2 is an encryption key derived from both g^{xs} and g^{xy}. It is
> used to
> include a hash of the previous traffic) and to encrypt data from the
> server if
> and other security parameters. The server is assumed to have some
> mechanism in
> protection). In this case, the key for computing the ClientFinished
> message and
> 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
> certificates can be sent in the clear in the first message of the
> protocol, one
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>
>

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 31 Oct 2014 18:59:05 -0700

P.S. At first glance this kind of design seems to have some really nice
properties and wouldn't be too hard to modify the draft (and
implementations)
to support. I'm looking forward to hearing what the WG thinks.

Best,
-Ekr

On Fri, Oct 31, 2014 at 6:44 PM, Eric Rescorla <[email-masked]> wrote:

>> During the TLS interim meeting of last week (Oct 22 2014) I suggested
>> that TLS
>> before getting into these details we want to get a sense of whether the
>> WG is
>> included here except for specifying the basic DH values from which the
>> key is
>> Omitted from the current high level description is a mechanism for
>> testing group
>> Key K3 is the "application key" used to derive key material for
>> protection of
>> The resulting protocol is as described above where the ClientData field
>> is sent
>> Note on Finished messages: The above spec sets ServerFinished as
>> mandatory and
>> performed only when a new static DH key is created (how often this
>> happens and

---

From: Watson Ladd <[email-masked]>
Date: Fri, 31 Oct 2014 22:15:38 -0700

Dear Hugo,

There are some issues I can see:

-Servers already supporting ECDSA certificates seem to not win. If I'm
understanding correctly, a server does three exponentiations, one of
which can be optimized by ephemeral reuse, when using ECDSA+ECDHE. The
servers that win are the ones with RSA certs. The only way to win vs
ECDSA is if DH only permits faster exponentiation, which it does, and
removing the ancillary junk in ECDSA.  However, here we have two
variable base exponentiations after ephemeral reuse, as opposed to one
fixed, one variable, so there is a loss in performance on the same
group, made up for by removing inversions modulo the group order.

-I'm interested to see how different this is from ntor.[0] (To my eyes
it is very similar, which may make proving easier. OTOH, the 0-RTT and
1-RTT options require care). Similarly, Michael Backes and coauthors
have proposed Ace[1], which does similar tricks to HMQV to reduce
server side cost, and provides a key exchange with some similar
properties.

-Estimations of the cost of group computations require care: while
those in the original email are correct, the estimates for shared-base
and multibase have to take into account the existence of ladders. A
seeming optimization might force the use of a slower representation.
In genus 1 this is no longer an issue.

-We've already had controversy on the list about removing
renegotiation as a mechanism for client authentication. While I would
really like to see a symmetric client authentication method, the fact
that some people want to change the client authentication state in the
middle of the connection limits the kinds of options we have. (I don't
know what exactly the requirements are or how they limit the options,
but I remember this being raised in an earlier proposal for removing
renegotiation)

None of these issues look like showstoppers to me. I think the
benefits of this proposal, particularly with regards to 0-RTT and
1-RTT exchanges where there is a solid proposal as opposed to none at
all, significantly outweigh the minor disadvantages. It opens the door
to massive performance increases by removing a dependency on signing,
and the consequent annoyances. And lastly, it will hopefully have a
proof that is understandable by humans with reasonable assumptions.

Sincerely,
Watson Ladd
-----

[0] http://cacr.uwaterloo.ca/techreports/2011/cacr2011-11.pdf
[1] https://www.infsec.cs.uni-saarland.de/~mohammadi/paper/owake.pdf

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