IETF Logo Mail Archive

Re: [openpgp] Followup on fingerprints

Gregory Maxwell <gmaxwell@gmail.com> Mon, 03 August 2015 16:59 UTC

Return-Path: <gmaxwell@gmail.com>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 1ADD71AC414 for <openpgp@ietfa.amsl.com>; Mon, 3 Aug 2015 09:59:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.7
X-Spam-Level:
X-Spam-Status: No, score=0.7 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, 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 TQLm8C5O7v6a for <openpgp@ietfa.amsl.com>; Mon, 3 Aug 2015 09:59:11 -0700 (PDT)
Received: from mail-io0-x232.google.com (mail-io0-x232.google.com [IPv6:2607:f8b0:4001:c06::232]) (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 D1DCB1A03E3 for <openpgp@ietf.org>; Mon, 3 Aug 2015 09:59:11 -0700 (PDT)
Received: by ioeg141 with SMTP id g141so151146056ioe.3 for <openpgp@ietf.org>; Mon, 03 Aug 2015 09:59:11 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=iKMF0trxSK2NvdmaZCp/PcYriDXWQPwKcOs2RGuiG74=; b=uKCs92T7a0M0Bc2uI0QPG4QGqOrdrO9396h+7uP13UyETDVLSaICYiFWL8QpoOXhUh 2PlwTV1TfEiy18WUwPgmxDWSjRtFuC1z+Sj1LjXUOVR6R5/ZDzmqcwpLeyaMP/XGCd/9 O8wY8aFu9ThC0FVLMmlxuDn+eWTcpdYFACgJAwUN6UVV2rZotUndhFKJBFojcS1OVx0q lnkdNXXm6nsh9prlqex+WWEiLXlWkGyW/2R1308y6ZH86feLldfSECiIteAGiABTf4Nx n4u4IouErRBAG1yCdHcg+/Xxq/JkPztjiDK022PGk87t8zVBUqHx2MhURZazniA84Zyv mlrQ==
MIME-Version: 1.0
X-Received: by 10.107.137.42 with SMTP id l42mr22065115iod.150.1438621151227; Mon, 03 Aug 2015 09:59:11 -0700 (PDT)
Received: by 10.107.14.136 with HTTP; Mon, 3 Aug 2015 09:59:11 -0700 (PDT)
In-Reply-To: <sjmwpxc1kbv.fsf@securerf.ihtfp.org>
References: <CAMm+LwgTcn8CY+Zk-f9gzXQtMJezG97T+kx2=C7PR5g7zFer_A@mail.gmail.com> <87twsn2wcz.fsf@vigenere.g10code.de> <CAMm+LwgRJX-SvydmpUAJMmN3yysi4zzGSpO2yY4JAMhD-9xLgQ@mail.gmail.com> <87zj2ecmv8.fsf@alice.fifthhorseman.net> <CAMm+LwgKmcTes=V7uS3MjCQixWCo-i7PY=VE7eCHSqt3Ho3OSg@mail.gmail.com> <87a8udd4u6.fsf@alice.fifthhorseman.net> <sjm61503182.fsf@securerf.ihtfp.org> <CAMm+LwgEVySpfL-iN2uzX-4tu7R+isDkHE9D8uAeLTxxd4VxqQ@mail.gmail.com> <sjmwpxc1kbv.fsf@securerf.ihtfp.org>
Date: Mon, 03 Aug 2015 16:59:11 +0000
Message-ID: <CAAS2fgR6LYck+km5Ze6S9z65ZgsR61d8md2CqojDaceZ0OrZrw@mail.gmail.com>
From: Gregory Maxwell <gmaxwell@gmail.com>
To: Derek Atkins <derek@ihtfp.com>
Content-Type: text/plain; charset="UTF-8"
Archived-At: <http://mailarchive.ietf.org/arch/msg/openpgp/u1QpY79YQWQA3PJo3OucKZRAlNI>
Cc: Phillip Hallam-Baker <phill@hallambaker.com>, Daniel Kahn Gillmor <dkg@fifthhorseman.net>, IETF OpenPGP <openpgp@ietf.org>
Subject: Re: [openpgp] Followup on fingerprints
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <openpgp.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/openpgp>, <mailto:openpgp-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/openpgp/>
List-Post: <mailto:openpgp@ietf.org>
List-Help: <mailto:openpgp-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/openpgp>, <mailto:openpgp-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 03 Aug 2015 16:59:13 -0000

On Mon, Aug 3, 2015 at 3:08 PM, Derek Atkins <derek@ihtfp.com> wrote:
> Remember, the fingerprint is over the public key, so you still have to
> actually perform the ECC g^x operation for each trial.

Take care to not confuse what you would do with what an attacker _must_ do.

For each new key to generate the attacker can perform only a single
addition of G or a doubling (whichever is faster for the curve in
question), then a conversion to affine (which is nearly free--
marginally, ~one field multiply-- if done in a batch).

E.g. You compute,
P_0 = xG
P_1 = P_0 + G  (x_1 = x_0 + 1)
P_2 = P_1 + G  (x_2 = x_1 + 1)
...

There are even faster techniques available for some curves.

If software for this doesn't run in the rough ballpark of a million
per second on a current gen laptop/desktop or 10 million/sec on a GPU
even on a fairly generic curve, it's probably completely naieve.

v2.23.0 | Report a Bug | By Email