Subject: [TLS] Should we use proof-of-possession rather than signatures?

From: Bill Cox <[email-masked]>
Date: Tue, 24 Nov 2015 08:25:53 -0800

Much of the world seems to have switched to Schnorr-signature inspired ECC
signature schemes such as ECDSA-P256 and Ed25519.  These schemes are very
fast, but require two point multiplications to do a Schnorr-style
verification.  A simpler proof-of-possession can be verified with only one
point multiplication.

The server authentication scheme used in QUIC is for the server to prove
possession of the static key when it encrypts the new ephemeral key share.
The trick is to take advantage of the key shares that have already been
computed.  The client has already computed its ephemeral keyshare, and the
server just uses its static keyshare from the server config.  The
CertificateVerify message could be generated by the server computing the
ECDHE shared secret between its static secret and the client's ephemeral
keyshare, and then encrypt of the client random as it's proof.  The client
verifies the proof by decrypting the nonce.  As with Schnorr signatures,
creating the proof takes only one multiply: in this case the server
multiplies the client's keyshare by it's static keyshare secret.  Instead
of having to do two scalar point multiplications, the client only has to
multiply the server's static keyshare by its ephemeral keyshare secret.
The proof is also smaller: 32 bytes vs 72 for ECDSA-P256.

This proof-of-possession is not a digital signature, since it can only be
used to prove to the client that the server possesses the static private
key.  However, I don't see any reason to create a full digital signature.
Is there any?  I just don't like seeing something as fast as QUIC degraded
when we switch to TLS 1.3.  I guestimate this will cost every connection
~1/8th of a millisecond when using ECDSA-P256.  Running "openssl speed
ecdsap256", I get:

Doing 256 bit sign ecdsa's for 10s: 90092 256 bit ECDSA signs in 9.99s
Doing 256 bit verify ecdsa's for 10s: 37154 256 bit ECDSA verify in 9.99s

This is about 0.27ms per verification, and on most client machines, this
will probably be slower.  I think we can nearly double this speed.

In TLS, microseconds count.  This seems like low hanging fruit to me.

Thanks,
Bill

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 24 Nov 2015 09:01:54 -0800

> The proof is also smaller: 32 bytes vs 72 for ECDSA-P256.

This is a sort of complicated question.

In general, servers have signature keys, not static DH keys. QUIC bridges
this by
having the server generate an offline signature over a static DH key, but
TLS explicitly
rejected this as a generic approach because of concerns about the impact of
producing
a long-term delegated credential, especially if generic TLS credentials
could be used to
do so (see the extensive discussion on the list a while back on the mailing
list as well
as [0]). So, the current design requires the server to prove present
possession of the
signing key, not just that it possessed it at some point.

It's correct that demonstrating proof of possession of a long-term DH share
is
somewhat faster than signatures. There are two potential ways to do this
with
TLS while retaining the guarantees above:

1. Issue DH (or probably ECDH) certificates.
2. Have a certificate extension that indicates that the certificate can be
used
    for offline signatures (following a suggestion by Hugo Krawczyk)

The general sense of the WG is that while these are both good ideas, ECC is
now
so fast that they can be pursued separately rather than in the critical
path. If you're
interested in working on that, it would be great to get someone on it, so
please
contact me or the chairs offline :)

> Is there any?

See above. In addition, because the signature covers the entire handshake
transcript, it provides some defense against downgrade in cases where the
weakest common group is weaker than the server's signing key.

-Ekr

[0] See also:
http://www.nds.rub.de/media/nds/veroeffentlichungen/2015/08/21/Tls13QuicAttacks.pdf

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 24 Nov 2015 09:53:48 -0800

Sent from my phone.  Please excuse brevity and typos.

> On Nov 24, 2015, at 09:01, Eric Rescorla <[email-masked]> wrote:
> 
> 
>> Much of the world seems to have switched to Schnorr-signature inspired ECC signature schemes such as ECDSA-P256 and Ed25519.  These schemes are very fast, but require two point multiplications to do a Schnorr-style verification.  A simpler proof-of-possession can be verified with only one point multiplication.
>> 
>> The server authentication scheme used in QUIC is for the server to prove possession of the static key when it encrypts the new ephemeral key share.  The trick is to take advantage of the key shares that have already been computed.  The client has already computed its ephemeral keyshare, and the server just uses its static keyshare from the server config.  The CertificateVerify message could be generated by the server computing the ECDHE shared secret between its static secret and the client's ephemeral keyshare, and then encrypt of the client random as it's proof. 

This is insecure. You need to MAC the whole handshake, especially the server ephemeral.

>> The client verifies the proof by decrypting the nonce.  As with Schnorr signatures, creating the proof takes only one multiply: in this case the server multiplies the client's keyshare by it's static keyshare secret.  Instead of having to do two scalar point multiplications, the client only has to multiply the server's static keyshare by its ephemeral keyshare secret.  The proof is also smaller: 32 bytes vs 72 for ECDSA-P256.

The size advantage of proof of possession is significant if the server actually has a DH cert, one for the same group as the client's ephemeral. 

> In general, servers have signature keys, not static DH keys. QUIC bridges this by
> having the server generate an offline signature over a static DH key, but TLS explicitly
> rejected this as a generic approach because of concerns about the impact of producing
> a long-term delegated credential, especially if generic TLS credentials could be used to
> do so (see the extensive discussion on the list a while back on the mailing list as well
> as [0]). So, the current design requires the server to prove present possession of the
> It's correct that demonstrating proof of possession of a long-term DH share is
> somewhat faster than signatures. There are two potential ways to do this with

Correct-ish. For example, the current implementation of ed448 takes 463k skylake cycles (new cpu, top of the chart, I'm on a phone, sorry) to compute ecdh, which would need to happen twice. But it takes 162kcy to sign and 509k to verify, for a total of 671k vs 926k.  Signing favors the server while double DH favors the client; there are good reasons to go in either direction in this.

Presumably the two server scalar multiplications could be combined with dual Shamir's trick, at which point double DH would be slightly faster than sigs, but I don't have an implementation of that lying around.  There is also a different calculation if the client has precomputed a table from the server's static key, but nobody does that and I'd guess the results are similar anyway.

Proof of possession is a bigger win if you go with MQV.

> 2. Have a certificate extension that indicates that the certificate can be used
> The general sense of the WG is that while these are both good ideas, ECC is now
> so fast that they can be pursued separately rather than in the critical path. If you're
> interested in working on that, it would be great to get someone on it, so please

I agree that the speed and size savings are not necessarily worth the complexity. If we were rolling a new protocol from scratch they probably would be though. 

>  
>> This proof-of-possession is not a digital signature, since it can only be used to prove to the client that the server possesses the static private key.  However, I don't see any reason to create a full digital signature.  Is there any? 
> 

Agreed.  It's also clearer how to combine this with postquantum key exchange, though proof of possession should be fine if you're also using DHE.

Cheers,
-- Mike

> -Ekr
> 
> [0] See also: http://www.nds.rub.de/media/nds/veroeffentlichungen/2015/08/21/Tls13QuicAttacks.pdf
>  
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 24 Nov 2015 10:06:41 -0800

On Tue, Nov 24, 2015 at 9:53 AM, Mike Hamburg <[email-masked]> wrote:

> Correct-ish. For example, the current implementation of ed448 takes 463k
> skylake cycles (new cpu, top of the chart, I'm on a phone, sorry) to
> compute ecdh, which would need to happen twice. But it takes 162kcy to sign
> and 509k to verify, for a total of 671k vs 926k.  Signing favors the server
> while double DH favors the client; there are good reasons to go in either
> direction in this.
>

In general, I tend to want to favor the server, I think :)

> I agree that the speed and size savings are not necessarily worth the
> complexity. If we were rolling a new protocol from scratch they probably
> would be though.
>

It's worth noting that it's not just a matter of an existing protocol but
also of an
existing authentication infrastructure (i.e., widespread RSA and ECDSA
signing
certs.)

Thanks,
-Ekr

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 24 Nov 2015 12:04:54 -0800

> On Nov 24, 2015, at 10:06 AM, Eric Rescorla <[email-masked]> wrote:
> 
> 
> 
> On Tue, Nov 24, 2015 at 9:53 AM, Mike Hamburg <[email-masked] <mailto:[email-masked]>> wrote:
> 
>> 

Actually, I did a quick test and the signatures still look faster when optimized.  The hitch is that the dual scalarmul algorithm must be side-channel protected, which is pretty expensive.  I did a quick implementation this morning with libdecaf on Haswell.  I’m sure it could be done better, but here’s a rough bench, not counting point encode and decode.

For Ed448, a protected fixed-base scalarmul (for signing) takes 109kcy and an unprotected verification double-scalarmul takes 517kcy, but a protected dual-scalarmul takes 690kcy which is more than both together.

For Ed25519, these take 164kcy, 40kcy and 236kcy respectively; again the dual scalarmul is slower.

Note that these numbers are for some internal testing version, so they’re not as optimized as the SUPERCOP numbers, but also that they don’t include point encode and decode.

So yeah, you’d need ECMQV to get a speed boost from this, or you’d need to care more about the client computation and bandwidth than the server computation.

Cheers,
— Mike

---

From: Hugo Krawczyk <[email-masked]>
Date: Tue, 24 Nov 2015 15:27:34 -0500

On Tue, Nov 24, 2015 at 12:53 PM, Mike Hamburg <[email-masked]> wrote:

>> Much of the world seems to have switched to Schnorr-signature inspired
>> ECC signature schemes such as ECDSA-P256 and Ed25519.  These schemes are
>> very fast, but require two point multiplications to do a Schnorr-style
>> keyshare, and then encrypt of the client random as it's proof.
>>
>
> The client verifies the proof by decrypting the nonce.  As with Schnorr
>> signatures, creating the proof takes only one multiply: in this case the
>> server multiplies the client's keyshare by it's static keyshare secret.
>> Instead of having to do two scalar point multiplications, the client only
>> has to multiply the server's static keyshare by its ephemeral keyshare
>> secret.  The proof is also smaller: 32 bytes vs 72 for ECDSA-P256.
>>
>
> The size advantage of proof of possession is significant if the server
> actually has a DH cert, one for the same group as the client's ephemeral.
>
> Presumably the two server scalar multiplications could be combined with
> dual Shamir's trick, at which point double DH would be slightly faster than
> sigs, but I don't have an implementation of that lying around.  There is
> also a different calculation if the client has precomputed a table from the
> server's static key, but nobody does that and I'd guess the results are
> similar anyway.
>

​The all-DH-based solution, with DH certificates, does not add complexity
but rather simplifies the protocol and analysis, and opens the option of
more efficient protocols (e.g. MQV-like ones). But the world does not seem
ready to depart from the beloved signature certificates.

​Hugo​

​

> Agreed.  It's also clearer how to combine this with postquantum key
> exchange, though proof of possession should be fine if you're also using
> DHE.
>
> Cheers,
> -- Mike
>
> -Ekr
>
> [0] See also:

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 24 Nov 2015 13:25:57 -0800

> On Nov 24, 2015, at 12:27 PM, Hugo Krawczyk <[email-masked]> wrote:
> On Tue, Nov 24, 2015 at 12:53 PM, Mike Hamburg <[email-masked] <mailto:[email-masked]>> wrote:
> 
> ​The all-DH-based solution, with DH certificates, does not add complexity but rather simplifies the protocol and analysis, and opens the option of more efficient protocols (e.g. MQV-like ones). But the world does not seem ready to depart from the beloved signature certificates.
> 
> ​Hugo​

I agree for new protocols, but the proposal for TLS isn’t all-DH.  It’s allowing both all-DH and DHE+sign.  That’s more complex than just allowing DHE+sign.  But I suppose the difference in TLS as proposed is really just putting a DH+MAC in CertificateVerify instead of a signature, which isn’t a complicated difference.

Sorry to be negative.  I really do like all-DH for simplicity, compactness and speed, especially if IP-encumbered algorithms are available.  I’m not against its inclusion in TLS if others think it’s worth the complexity of adding another option.  But I’m grumpy because this thread started with an insecure proposal justified using incorrect numbers.

— Mike

---

From: Bill Cox <[email-masked]>
Date: Tue, 24 Nov 2015 14:31:00 -0800

On Tue, Nov 24, 2015 at 1:25 PM, Michael Hamburg <[email-masked]> wrote:

> I agree for new protocols, but the proposal for TLS isn’t all-DH.  It’s
> allowing both all-DH and DHE+sign.  That’s more complex than just allowing
> DHE+sign.  But I suppose the difference in TLS as proposed is really just
> putting a DH+MAC in CertificateVerify instead of a signature, which isn’t a
> complicated difference.
>
> Sorry to be negative.  I really do like all-DH for simplicity, compactness
> and speed, especially if IP-encumbered algorithms are available.  I’m not
> against its inclusion in TLS if others think it’s worth the complexity of
> adding another option.  But I’m grumpy because this thread started with an
> insecure proposal justified using incorrect numbers.
>

I need to remember not to skip details when writing to this group :)  Yes,
encrypting a handshake digest is the right thing to do, not the client
random.  I normally leave out this detail in discussions to simplify making
my point.  I'll see if I can correct some numbers below.  Also, that was an
awesome attack in the paper linked to above.  Clearly, this is tricky
territory to make changes securely!

I think latency is more important than CPU overhead or whether the latency
happens at the client or server.  Since servers have well managed
computation capability, it may be best to favor server-side latency, where
it can be managed and minimized, vs client latency which can vary much more.

Just looking at TLS 1.3 1-RTT mode handshake (0-RTT does not use
CertificateVerify), the latency looks like this:

- First flight from client to server: 0 overhead, since ephemeral keyshare
can be precomputed
- First flight from server to client: 1 shared key derivation, in parallel
with signing
- Second flight from client to server: 1 shared key derivation in parallel
with verification

At least for Ed25519 and ECDSA-P256, signing is faster than shared key
derivation, which is faster than signature verification.  So, the latency
is 1 shared key derivation + 1 signature verification.  The median values
for Skylake using curve25519/Ed25519 are, in cycles:

keyshare computation: 150690
shared secret derivation: 143338
signing: 48990
verify signature: 161488

If we take full advantage of parallelism, the latency is 304,862 cycles.
If instead we used ECC DH everywhere, it would be 2 keyshare computations =
286676 cycles.  There would only be about a 6% improvement, which is hard
to get excited about.  Also, on some other curves it could be slower,
rather than faster.

AFAIK, OpenSSL and most other TLS libraries do not use multiple threads,
and will not take advantage of the available parallelism to reduce
latency.  At first glance, it looks like there is significant opportunity
here, but I know the coders involved in this code base are among the best
in the world.  There is zero chance they decided to avoid pthreads without
some pretty good reasons (cross-platform compatibility?).  I bet the
ephemeral keyshares are also not precomputed.

Without multiple threads, the 1-RTT handshake takes 2 keyshare computations
+ 2 shared key derivations + 1 sign + 1 verify = 798534 cycles.  With ECC
DH based proof-of-possession, it would be 2 keyshare computations + 4
shared key derivations = 874732 cycles, worse than with the current signing
scheme.

>From the paper, it sounds like using delegated keys currently has some
unanticipated security problems, at least in the near term while we
continue to accept incorrectly padded RSA based certs.  Would Hugo's
suggestions for extending certificates address weaknesses due to delegated
keys, and allow DH keyshares to be used for proof-of-possession, and
possibly MQV?  If so, it sounds like a valuable upgrade.

Thanks,
Bill

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 24 Nov 2015 14:42:08 -0800

> possibly MQV?  If so, it sounds like a valuable upgrade.

The underlying concern is misuse of *existing* server's signing keys to
produce essentially
permanent delegations. So, as Hugo observed, requiring a certificate
extension (or DH
certificates) removes this case. As I mentioned in my earlier message, we
discussed this
extensively at a number of meetings and came to the WG consensus that it
would
be good if someone wrote a separate draft documenting one or both of these
mechanisms,
but that it shouldn't be on the critical path for TLS 1.3. Volunteers
wanted!

-Ekr

---

From: Bill Cox <[email-masked]>
Date: Tue, 24 Nov 2015 16:34:36 -0800

On Tue, Nov 24, 2015 at 2:42 PM, Eric Rescorla <[email-masked]> wrote:

> As I mentioned in my earlier message, we discussed this

Well, I'm currently over-committed and owe a patch for EMS resumption, and
initial integration of Blake2, and I'm behind at work because I got caught
with my pants down by the security implications of 0-RTT connections.
However, I'd be happy to add it to my list and help if I can :)

Bill