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

[Hugo Krawczyk <[e-mail]>]

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

>
>
> Sent from my phone.  Please excuse brevity and typos.
>
> On Nov 24, 2015, at 09:01, Eric Rescorla <[e-mail]> wrote:
>
>
> On Tue, Nov 24, 2015 at 8:25 AM, Bill Cox <[e-mail]> 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.
>
> 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:
>
>
> 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.
>
> 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 :)
>
>
> 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.
>

​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​


​


>
>
>
>> 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?
>>
>
> 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.
>
>
> 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
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tls
>
>
> _______________________________________________
> TLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tls
>
>