Re: [openpgp] Followup on fingerprints

Derek Atkins <derek@ihtfp.com> Mon, 03 August 2015 15:08 UTC

Return-Path: <derek@ihtfp.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 309531A907A for <openpgp@ietfa.amsl.com>; Mon, 3 Aug 2015 08:08:20 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.311
X-Spam-Level: *
X-Spam-Status: No, score=1.311 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HELO_MISMATCH_ORG=0.611] 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 Ihbp2dUsMnXD for <openpgp@ietfa.amsl.com>; Mon, 3 Aug 2015 08:08:16 -0700 (PDT)
Received: from mail2.ihtfp.org (MAIL2.IHTFP.ORG [204.107.200.7]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 648381A907E for <openpgp@ietf.org>; Mon, 3 Aug 2015 08:08:14 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by mail2.ihtfp.org (Postfix) with ESMTP id D6819E2035; Mon, 3 Aug 2015 11:08:12 -0400 (EDT)
Received: from mail2.ihtfp.org ([127.0.0.1]) by localhost (mail2.ihtfp.org [127.0.0.1]) (amavisd-maia, port 10024) with ESMTP id 06549-09; Mon, 3 Aug 2015 11:08:05 -0400 (EDT)
Received: from securerf.ihtfp.org (unknown [IPv6:fe80::ea2a:eaff:fe7d:235]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "mocana.ihtfp.org", Issuer "IHTFP Consulting Certification Authority" (verified OK)) by mail2.ihtfp.org (Postfix) with ESMTPS id 6D5AEE2034; Mon, 3 Aug 2015 11:08:05 -0400 (EDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ihtfp.com; s=default; t=1438614485; bh=nBCKDeyPDBzBGG/HZDgdH8u/udIZpZVjQkjlZAe2C2g=; h=From:To:Cc:Subject:References:Date:In-Reply-To; b=SVlsiPPvyOaX2YjV1PNDnS9Jouv9kOzENmQ4sQnNxqPZAeheSjdMHNDlYHxFnd6bw C2A/gKqZP2vr0alEwNSl/BZUyyzPCSgeHBflifORFnwQoRanNejfAkRk0bBe05CR+e F4Idy+IWLXYLfXxb+Hm0nYSMm5Ct37SvUopPAues=
Received: (from warlord@localhost) by securerf.ihtfp.org (8.14.8/8.14.8/Submit) id t73F84cc018970; Mon, 3 Aug 2015 11:08:04 -0400
From: Derek Atkins <derek@ihtfp.com>
To: Phillip Hallam-Baker <phill@hallambaker.com>
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>
Date: Mon, 03 Aug 2015 11:08:04 -0400
In-Reply-To: <CAMm+LwgEVySpfL-iN2uzX-4tu7R+isDkHE9D8uAeLTxxd4VxqQ@mail.gmail.com> (Phillip Hallam-Baker's message of "Fri, 31 Jul 2015 14:31:11 -0400")
Message-ID: <sjmwpxc1kbv.fsf@securerf.ihtfp.org>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
X-Virus-Scanned: Maia Mailguard 1.0.2a
Archived-At: <http://mailarchive.ietf.org/arch/msg/openpgp/mP9T94oix7Aau2YhbF_EU1ciYlo>
Cc: IETF OpenPGP <openpgp@ietf.org>, Derek Atkins <derek@ihtfp.com>, 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 15:08:20 -0000

Phillip Hallam-Baker <phill@hallambaker.com> writes:

> On Fri, Jul 31, 2015 at 9:28 AM, Derek Atkins <derek@ihtfp.com> wrote:
>
>     Daniel Kahn Gillmor <dkg@fifthhorseman.net> writes:
>    
>     >> At this point, any attempt to hold Mallet accountable is going to have
>     to
>     >> rely on a human examining the logs and working out that Mallet must have
>     >> generated the malicious pair of keys. There is going to be no way to
>     unwind
>     >> the thing automatically.
>    
>     Why?  M1 and M2 are completely different fingerprints, unless you're
>     assuming that the x's are the same.  If the x's are the same that means
>     that Mallet has performed a 2^50 level attack to get 100 bits to match!
>     How long and how much energy does Mallet have to do this?  It's
>     certainly not something s/he is going to do over a long weekend!
>
> Not with RSA keys. With ECC keys, different matter entirely.

Even if you could do 30,000,000 ECC key generations per second (I think
my laptop can do about 3,000-10,000 -- I'm not sure how to measure that
beyond running an openssl speed test), and also assuming the SHA hash to
compute the fingerprint is "free", to do 2^50 keygen + sha computations
would still take 37,529,996 seconds or 434 days, which is over a year!
Remember, the fingerprint is over the public key, so you still have to
actually perform the ECC g^x operation for each trial.

So no, this is not something Mallet is going to be able to do over a
weekend without expending a LOT of effort and cost.  I guess if they had
access to a few hundred really beefy machines (and the electricity to
power them) they might be able to accomplish this feat.  So sure, maybe
a large corporation or gov't agency could perform this kind of Mallet
attack, but generally not some teenager sitting in their basement.

Maybe in a decade or two this will be feasible to a singleton.

This of course is still based on your (rather forced) 100-bit truncated
hash concept.  If applications use the full 160-bit fingerprint (or more
if we migrate up to a larger hash) then a 2^80 attack would still be out
of reach.

-derek
-- 
       Derek Atkins                 617-623-3745
       derek@ihtfp.com             www.ihtfp.com
       Computer and Internet Security Consultant