Re: [openpgp] Followup on fingerprints
Phillip Hallam-Baker <phill@hallambaker.com> Mon, 03 August 2015 20:22 UTC
Return-Path: <hallam@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 9A9AC1B30F1 for <openpgp@ietfa.amsl.com>; Mon, 3 Aug 2015 13:22:18 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.277
X-Spam-Level:
X-Spam-Status: No, score=-1.277 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FM_FORGED_GMAIL=0.622, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_PASS=-0.001] autolearn=no
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 qcIqMztX7k9l for <openpgp@ietfa.amsl.com>; Mon, 3 Aug 2015 13:22:17 -0700 (PDT)
Received: from mail-lb0-x22a.google.com (mail-lb0-x22a.google.com [IPv6:2a00:1450:4010:c04::22a]) (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 DE9A31B30EA for <openpgp@ietf.org>; Mon, 3 Aug 2015 13:22:16 -0700 (PDT)
Received: by lbbyj8 with SMTP id yj8so83914026lbb.0 for <openpgp@ietf.org>; Mon, 03 Aug 2015 13:22:15 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=yjQDWkBtXJgg0JvT9caHF562yzGA8QjkZtZxq+y1reI=; b=B+xPRNsfuZAeHZHtaLEKZhGy/2w6b/cDkxIezzWFiVD/ReuM4EeFBnIyiFxL4teRTn w9hWoK+erpBTYE0caagZ9EfBHZ1+o92AW/PCPdqi62SyRpvRBArjD+ZElRNS/V0ExybZ 88EZbxBplGZvKGL+dXw1E5ZIckMeUzSFKiSBwf3Uhpb1tqokb2QIVBKLZVlMVLwUdE3o 4AF7aL/+eixyZUO2CCkW2mszLv0a23EHfpmiwrwByTUP5eJCfNVamrGdZHSwNcnOJCgn sjKQi9EgDLL2Yej3TfpYJRcn1SomGhnaY1s2B023+7N57M6pywmUzgLpa1MlHxNy7ggg o+xg==
MIME-Version: 1.0
X-Received: by 10.112.185.100 with SMTP id fb4mr18875975lbc.79.1438633335353; Mon, 03 Aug 2015 13:22:15 -0700 (PDT)
Sender: hallam@gmail.com
Received: by 10.112.203.163 with HTTP; Mon, 3 Aug 2015 13:22:15 -0700 (PDT)
In-Reply-To: <9c2c8c5df67c83925d7e3c21fe943483.squirrel@mail2.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> <CAAS2fgR6LYck+km5Ze6S9z65ZgsR61d8md2CqojDaceZ0OrZrw@mail.gmail.com> <9c2c8c5df67c83925d7e3c21fe943483.squirrel@mail2.ihtfp.org>
Date: Mon, 03 Aug 2015 16:22:15 -0400
X-Google-Sender-Auth: 0ULiRz3Uln1-5DSW1XrTz48sjD4
Message-ID: <CAMm+LwjJ3mdawz92obKRz3NRhbc4veJFgW-u9gvO6sudem=ABg@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
To: Derek Atkins <derek@ihtfp.com>
Content-Type: multipart/alternative; boundary="001a11c3ca22ea78eb051c6dec54"
Archived-At: <http://mailarchive.ietf.org/arch/msg/openpgp/bKa-atbLuOI2kn6YE_Wc3vjw1LM>
Cc: Gregory Maxwell <gmaxwell@gmail.com>, IETF OpenPGP <openpgp@ietf.org>, Daniel Kahn Gillmor <dkg@fifthhorseman.net>
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 20:22:18 -0000
On Mon, Aug 3, 2015 at 1:20 PM, Derek Atkins <derek@ihtfp.com> wrote: > > On Mon, August 3, 2015 12:59 pm, Gregory Maxwell wrote: > > 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. > > Luckily my computations (which you unfortunately cut out) were based on 30 > million attempts per second, so my results (the attack taking over a year) > is still correct! Indeed, your numbers are still 3x slower than my > computation estimates. Your original assertion was broken. I don't think it very likely that someone is going to spend more than a machine year to generate a vanity key unless they can get someone else to pay for the time. A hundred machine years for creating a key collision attack is completely viable. Also when we are talking about PGP Key fingerprint, the fingerprint is over the key binding and not just the key and so it is malleable. I can well imagine someone making use of all that Bitcoin hardware for some mischief. Hence a reason to go for SHA-2-512. Again, this is only a security consideration that has to be noted.
- [openpgp] Followup on fingerprints Phillip Hallam-Baker
- Re: [openpgp] Followup on fingerprints Werner Koch
- Re: [openpgp] Followup on fingerprints Phillip Hallam-Baker
- Re: [openpgp] Followup on fingerprints Werner Koch
- Re: [openpgp] Followup on fingerprints Vincent Breitmoser
- Re: [openpgp] Followup on fingerprints Daniel Kahn Gillmor
- Re: [openpgp] Followup on fingerprints Daniel Kahn Gillmor
- Re: [openpgp] Followup on fingerprints Werner Koch
- Re: [openpgp] Followup on fingerprints Phillip Hallam-Baker
- Re: [openpgp] Followup on fingerprints Phillip Hallam-Baker
- Re: [openpgp] Followup on fingerprints Wyllys Ingersoll
- Re: [openpgp] Followup on fingerprints Phillip Hallam-Baker
- Re: [openpgp] Followup on fingerprints Daniel Kahn Gillmor
- Re: [openpgp] Followup on fingerprints Vincent Breitmoser
- Re: [openpgp] Followup on fingerprints Derek Atkins
- Re: [openpgp] Followup on fingerprints Phillip Hallam-Baker
- Re: [openpgp] Followup on fingerprints Vincent Breitmoser
- Re: [openpgp] Followup on fingerprints ianG
- Re: [openpgp] Followup on fingerprints Gregory Maxwell
- Re: [openpgp] Followup on fingerprints Phillip Hallam-Baker
- Re: [openpgp] Followup on fingerprints Derek Atkins
- Re: [openpgp] Followup on fingerprints Gregory Maxwell
- Re: [openpgp] Followup on fingerprints Derek Atkins
- Re: [openpgp] Followup on fingerprints Peter Pentchev
- Re: [openpgp] Followup on fingerprints Derek Atkins
- Re: [openpgp] Followup on fingerprints Phillip Hallam-Baker
- Re: [openpgp] Followup on fingerprints Vincent Breitmoser
- Re: [openpgp] Followup on fingerprints Vincent Breitmoser
- Re: [openpgp] Followup on fingerprints Phillip Hallam-Baker
- Re: [openpgp] Followup on fingerprints Werner Koch
- Re: [openpgp] Followup on fingerprints Nicholas Cole
- Re: [openpgp] Followup on fingerprints Derek Atkins
- Re: [openpgp] Followup on fingerprints Derek Atkins
- Re: [openpgp] Followup on fingerprints Phillip Hallam-Baker
- Re: [openpgp] Followup on fingerprints Derek Atkins
- Re: [openpgp] Followup on fingerprints Vincent Breitmoser
- Re: [openpgp] Followup on fingerprints Daniel Kahn Gillmor
- Re: [openpgp] Followup on fingerprints Daniel Kahn Gillmor
- Re: [openpgp] Followup on fingerprints Derek Atkins
- Re: [openpgp] Followup on fingerprints ianG
- Re: [openpgp] Followup on fingerprints Vincent Breitmoser
- Re: [openpgp] Followup on fingerprints Nicholas Cole
- Re: [openpgp] Followup on fingerprints Werner Koch
- Re: [openpgp] Followup on fingerprints Phillip Hallam-Baker
- Re: [openpgp] Followup on fingerprints Daniel Kahn Gillmor
- Re: [openpgp] Followup on fingerprints Phillip Hallam-Baker
- Re: [openpgp] Followup on fingerprints ianG
- Re: [openpgp] Followup on fingerprints Vincent Breitmoser
- Re: [openpgp] Followup on fingerprints Bill Frantz
- Re: [openpgp] Followup on fingerprints ianG
- Re: [openpgp] Followup on fingerprints Bill Frantz