Re: [openpgp] Mining protection in fingerprint schemes

Jon Callas <jon@callas.org> Fri, 08 April 2016 18:32 UTC

Return-Path: <jon@callas.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 409C512D5A6 for <openpgp@ietfa.amsl.com>; Fri, 8 Apr 2016 11:32:37 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] 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 Rp09CWQO7X7j for <openpgp@ietfa.amsl.com>; Fri, 8 Apr 2016 11:32:35 -0700 (PDT)
Received: from mail.merrymeet.com (merrymeet.com [173.164.244.100]) by ietfa.amsl.com (Postfix) with ESMTP id 2E0EE12D59D for <openpgp@ietf.org>; Fri, 8 Apr 2016 11:32:35 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by mail.merrymeet.com (Postfix) with ESMTP id DB8DE946C698; Fri, 8 Apr 2016 11:32:34 -0700 (PDT)
X-Virus-Scanned: amavisd-new at merrymeet.com
Received: from mail.merrymeet.com ([127.0.0.1]) by localhost (merrymeet.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id SuluegEmTHtW; Fri, 8 Apr 2016 11:32:33 -0700 (PDT)
Received: from keys.merrymeet.com (keys.merrymeet.com [173.164.244.97]) by mail.merrymeet.com (Postfix) with ESMTPSA id D6778946C67C; Fri, 8 Apr 2016 11:32:32 -0700 (PDT)
Received: from [10.0.23.7] ([173.164.244.98]) by keys.merrymeet.com (PGP Universal service); Fri, 08 Apr 2016 11:32:33 -0700
X-PGP-Universal: processed; by keys.merrymeet.com on Fri, 08 Apr 2016 11:32:33 -0700
Mime-Version: 1.0 (Mac OS X Mail 9.3 \(3124\))
From: Jon Callas <jon@callas.org>
In-Reply-To: <E9A5B4B3-0EEC-4E86-8CEC-6680A24BE44F@gmail.com>
Date: Fri, 08 Apr 2016 11:32:32 -0700
Message-Id: <0D7A75AB-74C6-40E9-87C5-BA6F05FCDBF7@callas.org>
References: <4C08CDDD-4C06-41AD-9797-7DD6F08ECD06@gmail.com> <2AA5B912-0AE6-4722-8BC7-66E37559C0B1@callas.org> <D17B23A3-633F-4E4E-BC14-69ED6060F357@gmail.com> <6E221A61-7AB2-4E0B-B64D-60F210A0131F@callas.org> <E9A5B4B3-0EEC-4E86-8CEC-6680A24BE44F@gmail.com>
To: Bryan Ford <brynosaurus@gmail.com>
X-Mailer: Apple Mail (2.3124)
Content-Type: multipart/alternative; boundary="Apple-Mail=_24807E06-8D49-4CE8-983C-EE03A1C272B4"
Archived-At: <http://mailarchive.ietf.org/arch/msg/openpgp/GGtlxIkuubUSSLH-t4v4vruvZ8I>
Cc: openpgp@ietf.org, Jon Callas <jon@callas.org>
Subject: Re: [openpgp] Mining protection in fingerprint schemes
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: Fri, 08 Apr 2016 18:32:37 -0000

> On Apr 7, 2016, at 6:12 PM, Bryan Ford <brynosaurus@gmail.com> wrote:
> 
> * PGP - S/MIME Signed by an unverified key: 04/07/2016 at 06:12:06 PM
> 
>> On Apr 7, 2016, at 8:36 PM, Jon Callas <jon@callas.org <mailto:jon@callas.org>> wrote:
>>> On Apr 7, 2016, at 7:55 AM, Bryan Ford <brynosaurus@gmail.com <mailto:brynosaurus@gmail.com>> wrote:
>>> The whole idea of providing some form of “mining-resistance” in a fingerprint scheme is to enable the key-owner to invest some effort at key-creation time, to ensure that any attacker who wants to try to mine for a key with a similar-looking fingerprint will have to invest a *lot* more time and effort, not just a little.
>>> 
>>> Does this make sense?
>> 
>> I believe I understand you.
>> 
>> You're complexifying key creation for a hypothetical, movie-plot attack.
> 
> This attitude, that IETF-standardized protocols should not attempt to address known or foreseeable weaknesses unless there are documented cases of those specific attacks happening in the wild *right now*, is one key reason Internet security is in such a horrific state.  When protocol designs only ever attempt to address attacks that have already been documented in the wild - and calling all other attacks “movie-plot” scenarios - by definition you’re always playing catch-up and attackers will always be ahead.  The pervasiveness of this attitude, while understandable, makes me sad.

The first rule of security is that you can't protect against all threats. This is why you do things like threat modeling.

I'm really sorry you're sad, but you said "although I don’t know if it’s actually happened in practice" -- which means that it's a hypothetical attack.

But now, below, you're saying it's not. Look, if you were in error and now know documented cases, when you didn't yesterday, that's cool. We can always revise.


> 
> In the case of fingerprint-mining, we actually do have documented evidence of that occurring, the most obvious and well-known being Facebook’s vanity .onion address.  The fact that Facebook was not maliciously attacking anyone else - in effect they were only “attacking” their own brand-name by mining for a public-key whose .onion address would look like it - does not change the fact that their action demonstrated that both the capability and the incentives exist in the real-world to mine for fingerprints that look similar to something-or-other.  If it so happened that the “real” Facebook was mounting this attack against its own brand, the next time it might be a fake Facebook imposter mounting the same attack against Facebook by creating a similar-looking vanity name and hoping users will fall for it.  The issue is not who or what the fingerprint-miner is trying to make their mined fingerprint look like; the issue is that such attacks are clearly practical.
> 
> Documented fingerprint-mining attacks have occurred in other domains too: for example, not too long ago I remember that it was found that the Ripple ledger was vulnerable to “Transaction ID” fingerprint-mining attacks that were actually being exploited, in which an attacker mined for low-numbered transaction IDs which would cause their transactions to get processed first and provide arbitrage opportunities.  Obviously the fingerprint-mining was for a fairly different purpose in this case, but still it’s another documented example of the same general class of weakness: i.e., an attacker mining for a hash-based fingerprint that looks kinda like something that will help him get what he wants in some way.


Let me go on a small rant of my own.

There is a problem in OpenPGP that it is notoriously too hard to use. 

I use OpenPGP through a PGP Universal server, but I also use S/MIME. S/MIME is in my mailer darned easy to use! Heck, your email itself was signed with S/MIME, not OpenPGP.

If you make key creation harder, people will create fewer keys.

If you make database lookup from fingerprint to key harder (or more costly) that makes it harder and more costly.

What's the *benefit* we derive from this added complexity and time? 

Moreover, can this problem be solved in a higher-level system?

We need to have a quick way to turn a cryptographic key into a fixed lookup (database key). The naive solution is a hash of that key, with or without something else.

If we turn the "fingerprint" into something complex, then we need to have a new thing that does what the old fingerprint does -- a quick transformation of key into lookup. What should that be?

Let me give a proposal of a generic scheme:

One of the ideas we had a long time ago was that the "fingerprint" actually has two fields in it. A tag and a value. I'm still fond myself of the fingerprint that is 

<algorithm-id>:<algorithm-value>

but I'm not wedded to the syntax. I like the idea; I don't care about the syntax.

If that gets adopted, then we *could* have a high-compute fingerprint and encourage people to put them on their business cards.

Does that help?

	Jon