Re: [openpgp] Fingerprint requirements for OpenPGP

Daniel Kahn Gillmor <dkg@fifthhorseman.net> Tue, 12 April 2016 18:38 UTC

Return-Path: <dkg@fifthhorseman.net>
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 8C9FD12DAF3 for <openpgp@ietfa.amsl.com>; Tue, 12 Apr 2016 11:38:08 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] autolearn=ham autolearn_force=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 O8h-pe8rFSPu for <openpgp@ietfa.amsl.com>; Tue, 12 Apr 2016 11:38:07 -0700 (PDT)
Received: from che.mayfirst.org (che.mayfirst.org [162.247.75.118]) by ietfa.amsl.com (Postfix) with ESMTP id 10D5212DA7B for <openpgp@ietf.org>; Tue, 12 Apr 2016 11:38:07 -0700 (PDT)
Received: from fifthhorseman.net (unknown [38.109.115.130]) by che.mayfirst.org (Postfix) with ESMTPSA id CCE08F991; Tue, 12 Apr 2016 14:38:05 -0400 (EDT)
Received: by fifthhorseman.net (Postfix, from userid 1000) id 768D1200B0; Tue, 12 Apr 2016 14:38:05 -0400 (EDT)
From: Daniel Kahn Gillmor <dkg@fifthhorseman.net>
To: KellerFuchs <KellerFuchs@hashbang.sh>
In-Reply-To: <20160412172246.GE9034@hashbang.sh>
References: <87vb3nslqh.fsf@alice.fifthhorseman.net> <20160412083409.GA16775@littlepip.fritz.box> <87egaarj74.fsf@alice.fifthhorseman.net> <20160412172246.GE9034@hashbang.sh>
User-Agent: Notmuch/0.21+128~g620f892 (http://notmuchmail.org) Emacs/24.5.1 (x86_64-pc-linux-gnu)
Date: Tue, 12 Apr 2016 14:38:05 -0400
Message-ID: <87mvoyad0y.fsf@alice.fifthhorseman.net>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: 8bit
Archived-At: <http://mailarchive.ietf.org/arch/msg/openpgp/bFBm9oYHclrcrmCnCrffte4MBRs>
Cc: IETF OpenPGP <openpgp@ietf.org>, Vincent Breitmoser <look@my.amazin.horse>
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: Tue, 12 Apr 2016 18:38:08 -0000

On Tue 2016-04-12 13:22:46 -0400, KellerFuchs <KellerFuchs@hashbang.sh> wrote:
> I think it is sane here to require collision resistence, because that's what
>   multi-target preimages devolves to: an attacker might not want to target
>   one specific key, but one amongst a large set of key (says, the developers
>   of a popular software, or perhaps any “widely signed” key in the WoT).
>
> In that case, the attacker gets a non-trivial speedup, and as the set of
>   targets grows larger, the hardness of the problem devolves into that of
>   finding a collision.

The size of the set of possible targets is relevant here, though, right?
if the pool of available targets is 2^16, you're not going to get more
than a 2^16 speedup by targeting them.  Even if we had a separate key
for every IPv4 address, that'd only be a 32-bit reduction in work
factor.

by comparison, a pre-image brute force costs 2^(2X) when a collision
attack costs 2^X due to the "birthday paradox".

We're talking about fingerprints in the range of 2^160 (the OpenPGPv4
fingerprint) and 2^256 (probably the upper bound of what we can expect
humans to be able to deal with).

so you'd need a pool of keys to attack on the order of 2^80 or 2^128 to
get a comparable speedup.

> Moreover, colision resistence implies second-preimage resistence, and hash
>   functions are usually considered “broken” by cryptographers once there is
>   an attack for colisions, so it seems OK to be somewhat cautious here and
>   require collisions to be hard.

I think we're in quite a bit of trouble if we actually need both
collision resistance and any sort of plausible human-accessibility for
high-entropy strings.

          --dkg