Re: [openpgp] Fingerprint requirements for OpenPGP

Joseph Lorenzo Hall <joe@cdt.org> Wed, 13 April 2016 23:42 UTC

Return-Path: <jhall@cdt.org>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D9C5B12DA74 for <openpgp@ietfa.amsl.com>; Wed, 13 Apr 2016 16:42:04 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Level:
X-Spam-Status: No, score=-2.699 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cdt.org
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 oih9UMXQNOMa for <openpgp@ietfa.amsl.com>; Wed, 13 Apr 2016 16:42:03 -0700 (PDT)
Received: from mail-vk0-x235.google.com (mail-vk0-x235.google.com [IPv6:2607:f8b0:400c:c05::235]) (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 6406712D9D5 for <openpgp@ietf.org>; Wed, 13 Apr 2016 16:42:03 -0700 (PDT)
Received: by mail-vk0-x235.google.com with SMTP id k1so90599055vkb.0 for <openpgp@ietf.org>; Wed, 13 Apr 2016 16:42:03 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cdt.org; s=google; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc; bh=sETRUc0CCSkp8U0wXBsK5YxUzO60xB/sokf46JqY1fk=; b=da0T4Z6eV4OkoGVnO0C7BMAST039l+woHdaV0PczW6DAPOzXXCg5mRifg9ieq6qH2q 7gTpOrO3V9CkiLlRDKXSUSq7GKtxiWCX2crKVIcRADPrx8s/02iikjtiXZMzbV3hOnZ5 bJB4D656hYo3w8XSgtK2yxfI5Ipjyz2lAUsqM=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc; bh=sETRUc0CCSkp8U0wXBsK5YxUzO60xB/sokf46JqY1fk=; b=LQLkahRR6bD6+KMu1aZdMa9jISPOvyY0xbWqy7f1yMtZ/KAM9DpjYJ7NeabI+BpEv2 7kMWNSU9P9RpY5u5lAEYtSqM15OvfnTR5c69j00F0mtxq2nQ8jKbWnVzwHp5LTCitrK2 EN4tSvbcXD5WAlmSN2FVIwDQj9TwVYXG7UxRKMW4vXN3A+05rvU0XLe6X1jp7zLzmZjh xJ6UXPXDfYuMZBdkPIYQ01pmCcYmwOuPsLTtaiHrELnW2j0Ohk5rRePZ7VuSzvchPOGv FwJTt3B2RwihMvpJBxaWgJxAO7yCMkqitPNZrTv+Auj83SeT/yj5mBkqEeQYzHIQvmru ujow==
X-Gm-Message-State: AOPr4FWSft5ne8yqFC6fBVyg3BksXl2C8ErtPzG1GrIY7V/CWj2XMc4ybmAFyrDTUgU7ArWqAGUlBbSys9K5qJuL
MIME-Version: 1.0
X-Received: by 10.159.33.183 with SMTP id 52mr5335753uac.114.1460590922311; Wed, 13 Apr 2016 16:42:02 -0700 (PDT)
Received: by 10.103.94.3 with HTTP; Wed, 13 Apr 2016 16:42:02 -0700 (PDT)
In-Reply-To: <20160413170751.GA4283@littlepip.fritz.box>
References: <87vb3nslqh.fsf@alice.fifthhorseman.net> <20160412083409.GA16775@littlepip.fritz.box> <87egaarj74.fsf@alice.fifthhorseman.net> <20160412172246.GE9034@hashbang.sh> <20160413170751.GA4283@littlepip.fritz.box>
Date: Wed, 13 Apr 2016 19:42:02 -0400
Message-ID: <CABtrr-XD704FBjWCBWOUizYUPyai+hOfHFvPdH=+JdOHySxXmQ@mail.gmail.com>
From: Joseph Lorenzo Hall <joe@cdt.org>
To: Vincent Breitmoser <look@my.amazin.horse>
Content-Type: multipart/alternative; boundary="001a113acfc21650bc0530665370"
Archived-At: <http://mailarchive.ietf.org/arch/msg/openpgp/QugKtoKB7nipXf-9sOi8bxHEdF0>
Cc: IETF OpenPGP <openpgp@ietf.org>, KellerFuchs <KellerFuchs@hashbang.sh>, Daniel Kahn Gillmor <dkg@fifthhorseman.net>
Subject: Re: [openpgp] Fingerprint requirements for OpenPGP
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.17
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: Wed, 13 Apr 2016 23:42:05 -0000

that is pretty damn convincing to me, thanks

On Wednesday, April 13, 2016, Vincent Breitmoser <look@my.amazin.horse>
wrote:

> >   usually considered “broken” by cryptographers
>
> This is not the general case cryptographers talk about, but a specific
> use case with a very specific set of requirements.
>
> >   so it seems OK to be somewhat cautious here and require collisions
> >   to be hard.
>
> If we could get it for free, maybe. But collision resistance is a factor
> two in bitsize, which is not only not free, but pretty darn costly.
>
> Just to get a feeling for the numbers, let's do some good old
> pessimistic math:
>
> We take a 128 bit fingerprint. We say the attacker wants to attack a
> pool of 65000 keys, so 2^16. That leaves 112 bits of fingerprint to
> attack. We also assume that an attacker can test as fast as they can
> generate sha-256 hashes, and give no penalties for key generation,
> multi-target attack, collisions or stuff like that.
>
> Top of the line hashing ASICs are at about 5 terahashes per second. But
> let's just say our attacker has 10 terahashes/s (2^43) per device for
> ease of math. Then let's say our attacker has one *billion* of those
> devices (2^30), which is a ridunculous number to have.
>
> In this scenario, our attacker needs 2^(128-16-43-30) = 2^39 seconds to
> find a single preimage, which is 17432 years.
>
> From a different angle, for one Joule of energy (= 1 watt-second) you
> can very optimistically get about 5T (2^42) sha256 hashes for one Joule
> of energy. For 2^112 hashes, that's 2^(112-42) = 2^70 Joule of energy,
> or 2^19 terawatt-hours of energy. For comparison, the total world energy
> consumption is around 2^17TWh per year, so that's something like four
> years of energy (not even only power) used by people in the world.
>
>  - V
>


-- 
Joseph Lorenzo Hall
Chief Technologist, Center for Democracy & Technology [https://www.cdt.org]
e: joe@cdt.org, p: 202.407.8825, pgp: https://josephhall.org/gpg-key
Fingerprint: 3CA2 8D7B 9F6D DBD3 4B10  1607 5F86 6987 40A9 A871