Re: [openpgp] proof-of-work fingerprints [was: Re: Fingerprint requirements for OpenPGP]
Phillip Hallam-Baker <phill@hallambaker.com> Sat, 16 April 2016 16:58 UTC
Return-Path: <hallam@gmail.com>
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 5412C12DF0D for <openpgp@ietfa.amsl.com>; Sat, 16 Apr 2016 09:58:03 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.4
X-Spam-Level:
X-Spam-Status: No, score=-2.4 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FREEMAIL_FORGED_FROMDOMAIN=0.199, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 qkXimWv4Itzk for <openpgp@ietfa.amsl.com>; Sat, 16 Apr 2016 09:58:00 -0700 (PDT)
Received: from mail-lf0-x22e.google.com (mail-lf0-x22e.google.com [IPv6:2a00:1450:4010:c07::22e]) (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 8D75112DECE for <openpgp@ietf.org>; Sat, 16 Apr 2016 09:57:59 -0700 (PDT)
Received: by mail-lf0-x22e.google.com with SMTP id j11so176431737lfb.1 for <openpgp@ietf.org>; Sat, 16 Apr 2016 09:57:59 -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; bh=vBDaXBpDK19LIJLbBbdwIwB7UbM8RzYvq3muENIwUUQ=; b=wzyuewcVt4t6NCKY8PAiT+KrnrijO5GyTAeQ30fSe5NnV1R5jJpPFwbr3i9zEBY/hn j+ED5sH+krJyyZuMLXfmmasNZjAAJ/R1tfdBYmWfjG1/G3+8LdTTAtxf9Bb8jB5Sqjug bx78whFbkt8Ms61t0f5XA7UOddcZyd9KoFFGFjgpoLyaOosDyKqOut7Pd+DayKdHMUer CevRz1+HugtFjmVLWteqDquZOoBDYbVAWwpLoTQyYcgQ98VhkzXO0KpPB2RkYGvQsKr6 d2t24PpEgN3mcbvGYB2RW7paEsZO2bJPrftJCyeqXjvgMARtYNccSzsm1eSTywhNCc8r 0Qjw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:sender:in-reply-to:references:date :message-id:subject:from:to:cc; bh=vBDaXBpDK19LIJLbBbdwIwB7UbM8RzYvq3muENIwUUQ=; b=PNje69q2shyzyxiL+j/yOKnC7DAXbmVNVCo44JUJipHYQJ+LpXE7bmUzDOB4nsQ5v9 8zmsMTWUWgMefnKf5PP3kW/r4jEf1eeOVPmIwy5Lnkex87oK/A3FFu4oxe0WB1wJgWtq 2M31CvUUt5lZqP3GAEYd5qJLdgYbHbT3bYw2pBM+619NB1Bac2fwM3pvE1lr2gK7mXOG IbqtcSHXvRfqCscPaBUMYnNV5uPZyJo9xmFQqFFz0yNlgAr8empzrAn7mLZXSxqGDqBC Ne6nEIjiZDWtZKmS/5amr9LTdJ33ZV38fFRmP1uAnbXnJcXCmrf3OBSQtjJMNuS3K+RL T2Pw==
X-Gm-Message-State: AOPr4FVViMi2/o920q0xFCpc50UfNZz4DpedYRiL0z/5X/apFCzprvnomqTF2wpZ5jgG+MX47t5X7iqXMe8PSw==
MIME-Version: 1.0
X-Received: by 10.25.209.73 with SMTP id i70mr2021851lfg.67.1460825877620; Sat, 16 Apr 2016 09:57:57 -0700 (PDT)
Sender: hallam@gmail.com
Received: by 10.112.3.102 with HTTP; Sat, 16 Apr 2016 09:57:57 -0700 (PDT)
In-Reply-To: <CAMm+Lwi95bv_QG751=exgDpH3UpP2-oAeS++5gqi-sxjMqANKw@mail.gmail.com>
References: <87vb3nslqh.fsf@alice.fifthhorseman.net> <87potug3s5.fsf@wheatstone.g10code.de> <87potuadxq.fsf@alice.fifthhorseman.net> <CAMm+Lwi95bv_QG751=exgDpH3UpP2-oAeS++5gqi-sxjMqANKw@mail.gmail.com>
Date: Sat, 16 Apr 2016 12:57:57 -0400
X-Google-Sender-Auth: TZwXYdJpwH87rY0Qawo851UsLqs
Message-ID: <CAMm+LwgSJd8Wn8P=wsSA+jO_A3_Fdj-tRV0K3LARSFX+-gLg_g@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
To: Daniel Kahn Gillmor <dkg@fifthhorseman.net>
Content-Type: text/plain; charset="UTF-8"
Archived-At: <http://mailarchive.ietf.org/arch/msg/openpgp/PK8lMXYDpgN6e6JZDZWWBKGcO4Q>
Cc: Werner Koch <wk@gnupg.org>, IETF OpenPGP <openpgp@ietf.org>
Subject: Re: [openpgp] proof-of-work fingerprints [was: Re: 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: Sat, 16 Apr 2016 16:58:03 -0000
@#($*@#(!! Gmail sent the other one too soon. On truncation, there are some game we can play. Lets say that we start off with a 256 bit hash. Now I am only using SHA-2-512 and SHA-3-512 because I want to have as many rounds as possible even if I am going to discard bits I distinguish between the following 1) The hash output size (512 bits for UDF) 2) The fingerprint size (250 bits for UDF) 3) The presentation size (varies from 25 bits to 250 bits in 25 bit increments) So the has output is 512 random bits which give the following fingerprint: MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ-SV75J-C4OZQ-5GIN2-GQ7FQ-EEHFI This may be presented as phill-6DUF5@hallambaker MB2GK-6DUF5-YGYYL-JNY5E MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ ... MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ-SV75J-C4OZQ-5GIN2-GQ7FQ-EEHFI Depending on the context. Now note here that I am assuming that users will be using subkeys and so in most contexts, a PGP fingerprint is of a key that under best practice is only ever used to sign other keys. The only case where it is not is when someone has already identified the signing key and is looking for the correct sub key for a specific operation. At the moment, a general overhaul of the OpenPGP key distribution system is out of scope. But it is my view that we should consider the possibilities for a new key distribution infrastructure when we design a new fingerprint scheme. Our choices here will open or close future options. In particular, I am assuming that there will be a convergence of the OpenPGP, SSH and S/MIME key distribution mechanisms (all suck today) and that this convergence will result in the emergence of a new infrastructure that looks somewhat like 'BaL's MIT key server plus blockchain'. This is what I am currently building in the Mesh. The idea is that the Mesh is a hash chain notarized, append-only log that can be written to from multiple input streams (portals) and finalizes every hour or so. So if you have that type of backing infrastructure, you can take a short presentation of a fingerprint, 'MB2GK-6DUF5-YGYYL-JNY5E' and consult the Mesh to receive back a record that gives you the corresponding public key record and the full length fingerprint. This allows me to make fingerprints really short since all that is necessary is to distinguish them in context. phill-6DUF5@hallambaker only needs a 25 bit fingerprint presentation because it is only necessary to distinguish the key from any prior keys for phill@hallambaker.com that have been checked in previously. [Yes, this uses the second block of the fingerprint. That is because the first block ends up filled with control information] This approach is similar to the 'last four digits' of your credit card number which is rather hilariously used as an abstract for the whole card number. It is hilarious because the first six digits are the bank identification number and there is one digit of checksum. Many small banks have less than 100,000 accounts and so they only actually use the last 6 digit fields. In our context, the approach is secure because people won't be creating a thousand fingerprints for their own use and expecting them to work. There are two considerations for fingerprint size 1) How many data items do we want to hash? 2) What is the work factor we want to set for breaking any one of them? When we are talking about OpenPGP fingerprints, I think the first number is about 2^40 the global population is roughly 8 billion (2^33) and a hundred trust roots per user seems enough for a lifetime. For work factor, the very lowest lower bound would be 2^85 right now which gives us a total work factor of 2^125 as the very lowest fingerprint size to be considered 'safe'. Using the 'work hardening' approach described in the earlier message, we can create a 100 bit signature that has a work factor of 2^125. Which is short enough to fit on a business card. There are many contexts where I would not want to do work hardening though. Particularly in an enterprise network where I am creating keys for individual devices. The considerations for sub keys are rather simpler as there we only need to consider how many keys the parent has signed. Lets say the sub key distinguisher is E34TG, we might represent that in a config file as follows: MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ/E34TG Now all this is quite a bit more complex than OpenPGP alone needs or you are going to accept right now. But it is mechanism that delivers a lot of power and convenience if it can be applied to all a user's cryptographic applications. Wouldn't it be nice if you could cut and paste your single Mesh master key fingerprint into a PGP application, an SSH application and an S/MIME application and have them all 'just work'? Another game that can be played with master keys is the one I outlined in the Arcing BOF and I am writing up a paper on. A key fingerprint is a root of trust. It is convenient to be able to embed roots of trust into other identifiers. Over the past few years I have played with the following embedding schemes: MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ?phill@hallambaker.com phill@hallambaker.com.MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ.onion phill@hallambaker.com.MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ The last is my preferred approach. It would be pretty easy to configure a DNS client to consider any TLD of 19 characters or more to be a fingerprint of a root of trust that governs the interpretation of the rest. The client begins by resolving MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ using whatever infrastructure exists for that task (lets call it the Mesh because we have already used nets and webs and mesh was the only one left I could think of). So the root of trust signs some record that says something like: {"DNSSEC" : "MLFXX-KIDDN-BSWG2-3FMQQ-GE5LU-EBXG6", "TLS" : "MKRUG-S4ZAN-FZSAY-LMONX-SAZTB" } These are two trust roots that can be used to interpret the address "phill@hallambaker.com". The first is the ICANN DNSSEC root, the second is a local intermediate PKIX cert for the TLS. [It isn't necessary to identify a new trust root for OpenPGP of course because that key would simply be signed in OpenPGP] Yes, there are a lot of options. But creating a lot of options does not mean that we have to have a lot of complexity. Right now, the UDF draft is an 8 pager, most of which is boilerplate: https://tools.ietf.org/html/draft-hallambaker-udf-03 I will drop in the description of the work hardening. It is simply a new algorithm type. The only impact this has on the OpenPGP use is that instead of the fingerprint being Fingerprint = H (OpenPGPFormat (Key)) It is instead: Fingerprint = VersionID + H ( "application/open-pgp-key" + H (OpenPGPFormat (Key))) Making that one change (i.e. adopting my draft) makes the fingerprint format the cornerstone of integration of OpenPGP, SSH and more into a single interoperable cryptographic infrastructure. On Sat, Apr 16, 2016 at 11:56 AM, Phillip Hallam-Baker <phill@hallambaker.com> wrote: > This is almost the scheme I am looking at. The main practical > difference is that I don't see the need to be quite so granular. If > people are going to use proof of work, then I would start off with a > threshold designed to take about an hour of processing on contemporary > machines, for the sake of argument, say that is 24 bits. Then I would > allow for prefixes of 24, 34, 40 bits. > > This approach can be encoded using a leading 1s approach. So each > increase in work saves 7 bits. > > The increase in work may look dramatic, but it really isn't because I > expect people would throw parallel machines at the problem. Also note > moving from RSA to ECC saves a huge chunk of keygen time. So any > compression scheme is having to deal with a vast difference in > computing demands and capabilities. > > The wonderful thing about exponents is that they tend to quickly > balance any mismatch in such things. > > > The other trick I think is very useful is to use truncated > fingerprints as keyIds. Lets say that we start with a SHA-51 > > > > > > On Tue, Apr 12, 2016 at 2:18 PM, Daniel Kahn Gillmor > <dkg@fifthhorseman.net> wrote: >> On Tue 2016-04-12 13:01:14 -0400, Werner Koch <wk@gnupg.org> wrote: >>> According to Peter, this means SHA-256. There may be no proof-of-work >>> to for creating a key and thus a structured fingerprint. (Sometimes you >>> have to create a lot of one-off keys.) >> >> The one proposal i've heard that keeps things somewhat simple but still >> allows the possibility of an increased cost to an adversary intent on a >> preimage attack is related to floating point implementations, and was >> suggested by PHB. I try to describe my understanding of the scheme >> below, but writing it all down makes me think that "somewhat simple" >> might be overselling it; there are quite a few complications. >> >> Here goes: >> >> * Start from a design of a fingerprint of X bits, using a truncation of >> digest of size Z (where Z > X). for example, a 200-bit fingerprint >> from sha-256. this would typically mean an adversary has to do about >> 2^200 sha-256 operations to find a match. (this is an impossibly >> high bar if we're talking about brute force, but if we assume that >> most cryptanalysis of SHA-256 allows an attacker to shave off some >> sizeable work factor, it represents the "safety margin" against >> unknown cryptanalysis of this type) >> >> * Instead, make the fingerprint X+N bits, where the first N bits >> indicate the number of leading zeros of the digest. Now if i do a >> bit of work to generate keys with, say, 10 leading zeros, an attacker >> will probably need to do about 2^10 more digests to find a match. >> >> So if we're doing a 200-bit truncation of sha-256, and we have an 8-bit >> count of leading zeros, and the digest produced is (in hex -- i'm not >> making an argument about choice of textual representation here, just >> showing in hex for discussion): >> >> 001a1bb6c7e907d06dafe4687e579fce76b37e4e93b7605022da52e6ccc26fd2 >> >> then it would result in a fingerprint of (again in hex for discussion): >> >> 0ba1bb6c7e907d06dafe4687e579fce76b37e4e93b7605022da5 >> >> That is: 11 (0x0b) bits of zeros, followed by a 1 bit, followed by >> a1bb6c7e907d06dafe4687e579fce76b37e4e93b7605022da5 >> >> More precisely, under this scheme, fingerprint generation looks like: >> >> scan1(x) : the position of the left-most 1 bit in bitstring x >> A[n:m] : bits n through m-1 of bitstring A >> enc(n,b) : a bitstring of length b encoding n as an unsigned int >> dgst(x) : a fixed-length bitstring digest of bitstring x (e.g. sha-256) >> X : number of explicitly-represented bits >> N : size of bitfield for counting leading zeros >> || : bitstring concatenation >> >> def fpr(z): >> h = dgst(z) >> k = scan1(z) >> return enc(k,N) || h[z+1:z+1+X] >> >> * note that first bit that is set to 1 is omitted from the >> representation (it's present by implication). This isn't just a hack >> to squeeze one more bit of entropy out of the fingerprint, it's >> arguably necessary to ensure that there is exactly one fingerprint >> that corresponds to any given digest. Otherwise, i can represent a >> fingerprint with 3 leading zero bits as: >> >> <3> 1100101... >> >> or: >> >> <2> 01100101... >> >> or: >> >> <1> 001100101... >> >> or: >> >> <0> 0001100101... >> >> The other alternative is to require that the leading bit after the >> zero-run prefix is always 1 (unless the zero-run prefix is maxed >> out?), which would mean that certain fingerprints are simply invalid >> (we'd want tools to reject them?) >> >> * note also that for some choices of dgst and N it would mean there >> could be some keys that are un-fingerprintable. For example, if we >> chose dgst = sha-256 and N = 5, then any key that has a sha-256 >> digest with a leading run of more than 31 zeros might be >> unrepresentable. >> >> With all these caveats, i confess the much-simpler construction "200-bit >> truncation of sha-256" looks pretty appealing :) >> >> --dkg >> >> _______________________________________________ >> openpgp mailing list >> openpgp@ietf.org >> https://www.ietf.org/mailman/listinfo/openpgp
- [openpgp] Fingerprint requirements for OpenPGP Daniel Kahn Gillmor
- Re: [openpgp] Fingerprint requirements for OpenPGP Vincent Breitmoser
- Re: [openpgp] Fingerprint requirements for OpenPGP Joseph Lorenzo Hall
- Re: [openpgp] Fingerprint requirements for OpenPGP Vincent Breitmoser
- Re: [openpgp] Fingerprint requirements for OpenPGP Daniel Kahn Gillmor
- Re: [openpgp] Fingerprint requirements for OpenPGP Derek Atkins
- Re: [openpgp] Fingerprint requirements for OpenPGP Daniel Kahn Gillmor
- Re: [openpgp] Fingerprint requirements for OpenPGP Derek Atkins
- Re: [openpgp] Fingerprint requirements for OpenPGP Daniel Kahn Gillmor
- Re: [openpgp] Fingerprint requirements for OpenPGP Salz, Rich
- Re: [openpgp] Fingerprint requirements for OpenPGP Daniel Kahn Gillmor
- Re: [openpgp] Fingerprint requirements for OpenPGP Werner Koch
- Re: [openpgp] Fingerprint requirements for OpenPGP Werner Koch
- Re: [openpgp] Fingerprint requirements for OpenPGP KellerFuchs
- Re: [openpgp] Fingerprint requirements for OpenPGP Derek Atkins
- Re: [openpgp] Fingerprint requirements for OpenPGP Jon Callas
- [openpgp] proof-of-work fingerprints [was: Re: Fi… Daniel Kahn Gillmor
- Re: [openpgp] Fingerprint requirements for OpenPGP Daniel Kahn Gillmor
- Re: [openpgp] Fingerprint requirements for OpenPGP Werner Koch
- Re: [openpgp] Fingerprint requirements for OpenPGP Bill Frantz
- Re: [openpgp] Fingerprint requirements for OpenPGP Werner Koch
- Re: [openpgp] Fingerprint requirements for OpenPGP Derek Atkins
- Re: [openpgp] Fingerprint requirements for OpenPGP Derek Atkins
- Re: [openpgp] Fingerprint requirements for OpenPGP Derek Atkins
- Re: [openpgp] Fingerprint requirements for OpenPGP Derek Atkins
- Re: [openpgp] Fingerprint requirements for OpenPGP Joseph Lorenzo Hall
- Re: [openpgp] Fingerprint requirements for OpenPGP Werner Koch
- Re: [openpgp] Fingerprint requirements for OpenPGP Werner Koch
- Re: [openpgp] Fingerprint requirements for OpenPGP Vincent Breitmoser
- Re: [openpgp] Fingerprint requirements for OpenPGP Joseph Lorenzo Hall
- Re: [openpgp] Fingerprint requirements for OpenPGP Derek Atkins
- Re: [openpgp] Fingerprint requirements for OpenPGP Derek Atkins
- Re: [openpgp] Fingerprint requirements for OpenPGP Joseph Lorenzo Hall
- Re: [openpgp] Fingerprint requirements for OpenPGP Phillip Hallam-Baker
- Re: [openpgp] proof-of-work fingerprints [was: Re… Phillip Hallam-Baker
- Re: [openpgp] proof-of-work fingerprints [was: Re… Phillip Hallam-Baker