[Cfrg] Client-side signature verification costs (was Re: Not the same thread -> was Re: Rerun: Elliptic Curves - preferred curves around 256bit work factor (ends on March 3rd))

Brian Smith <brian@briansmith.org> Wed, 25 February 2015 20:46 UTC

MIME-Version: 1.0
Date: Wed, 25 Feb 2015 12:46:01 -0800
Message-ID: <CAFewVt55bEQk_htCzqy3n=Epsr9pQLRM+QabNgDg7BHg8C3AAg@mail.gmail.com>
From: Brian Smith <brian@briansmith.org>
To: Phillip Hallam-Baker <phill@hallambaker.com>
Content-Type: text/plain; charset="UTF-8"
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/qAavKSAr73LNIJ7XGEhdv4R_FZc>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: [Cfrg] Client-side signature verification costs (was Re: Not the same thread -> was Re: Rerun: Elliptic Curves - preferred curves around 256bit work factor (ends on March 3rd))
Precedence: list

Phillip Hallam-Baker <phill@hallambaker.com> wrote:
> For the client side, if we have one intermediate and one EE cert:
>
> RSA2040: One encrypt, two verifies, 93usec
> EC 521: One DH, two verifies, 753 usec.
>
> OK so performance is possibly an issue on the client. But only if we are on
> a constrained device or the client is making a huge number of key
> negotiations. And why would you want to do that on a constrained device.

Here are the signatures that the client is likely to need to verify:

1. The signature of the ECDH parameters by the server's end-entity certificate.

2. The signature of end-entity certificate by the intermediate CA certificate.

3, 4, 5. Three signatures of Certificate Transparency proofs.

6. The signature of the (stapled) OCSP response for the end-entity
certificate by the intermediate's OCSP signing certificate.

7[a]. The signature of the OCSP signing certificate by the
intermediate CA certificate.

8[a]. The signature of the intermediate CA certificate by the root.

9[b]. The signature of the OCSP response for the intermediate CA
certificate by the root's OCSP signing certificate.

10[a][b]. The signature of the root's OCSP signing certificate.by the root

[a] It is likely that the client can pre-calculate the verification of
signatures for common intermediate CA certificates and OCSP signing
certificates. Such precalculation could save up to three
verifications.

[b] Assuming mutli-stapling for OCSP ever catches on.

Therefore, we're looking at up to 10 signature verification in a
single handshake.

According to the numbers above, 7.3ms would be spent on a 3.6GHz
Haswell system for 10 signatures. However, we have to consider
systems, in particular low-end smartphones that are much slower. These
phones are also limited in how many of the signatures can be done in
parallel. And, several batches of up to 10 signatures may be necessary
just to start displaying a web page.

My own certificate verification code can do the signature
verifications in parallel, precomputes signatures of common
intermediate and OCSP signing certificates, and caches signature
verification results. But, most certificate verification libraries do
not make any of these performance optimizations. And, in practice
we're often not able to to parallelize signature verification on
phones because they have small numbers of cores and those cores are
often busy doing other things.

Consequently, I think a better question for client-side performance
would be "How fast can we verify 3 separate batches of 10 signatures
on two 1Ghz NEON-capable ARM cores?"

This should steer us in the direction of batch verification,
smaller/faster curves, as few different curves as possible (so that
batching works), signature formats that facilitate batching.

Cheers,
Brian

[Cfrg] Client-side signature verification costs (… Brian Smith