[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

Return-Path: <brian@briansmith.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A48881A886A for <cfrg@ietfa.amsl.com>; Wed, 25 Feb 2015 12:46:06 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.979
X-Spam-Level:
X-Spam-Status: No, score=-1.979 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id VBzXXv5-naIl for <cfrg@ietfa.amsl.com>; Wed, 25 Feb 2015 12:46:02 -0800 (PST)
Received: from mail-ob0-f180.google.com (mail-ob0-f180.google.com [209.85.214.180]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 8BA5D1A8854 for <cfrg@irtf.org>; Wed, 25 Feb 2015 12:46:02 -0800 (PST)
Received: by mail-ob0-f180.google.com with SMTP id vb8so6532898obc.11 for <cfrg@irtf.org>; Wed, 25 Feb 2015 12:46:02 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:date:message-id:subject:from:to:cc :content-type; bh=0ciFfkkr94UT4r9n/DbvlPyqDD+bYdOfYR/DfJ3ujMk=; b=faAyBlf5S28pxvBnaWnlzEeHjIpSft4zV0UFSdPEUH/MbQftCG6VB2jCF2kbGEDeWQ uRSxlvMv3KIUfjUn9OYmvuzGBIBkS9AnpMOuTyo5AGFPQWxXUi6puLzN+ffODwfAyaJZ 9ByXG2z8kqVv3ALp2iRnW7C25/0qzmtVKFco0Jx5XKMr2CeMeB1feTuhNHEerlkFFvZg 321Dc6jqKgopagTFQIpV1a6Z6ilZ4VWlHzKsvatAXPQIdjADUqEaROzacZe+XRcxTDOn pUql98mTzaxkoECiQB6Ra29GOA53sj5BBH+YJPnrfOygTfXpbAkg+3P40m9tTsJ/Yjp4 V0pg==
X-Gm-Message-State: ALoCoQnVHN42uc2FsKFEQP/5fDqQWq3C6GOi+dRzWH9FlA1erml5surdviV6K14LqeZrqKMayjK8
MIME-Version: 1.0
X-Received: by 10.202.59.131 with SMTP id i125mr3286061oia.125.1424897161814; Wed, 25 Feb 2015 12:46:01 -0800 (PST)
Received: by 10.76.80.230 with HTTP; Wed, 25 Feb 2015 12:46:01 -0800 (PST)
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))
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 25 Feb 2015 20:46:06 -0000

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