Re: [openpgp] proof-of-work fingerprints [was: Re: Fingerprint requireme

@#($*@#(!! 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(_at_)hallambaker(_dot_)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(_at_)hallambaker(_dot_)com
phill(_at_)hallambaker(_dot_)com.MB2GK-6DUF5-YGYYL-JNY5E-RWSHZ.onion
phill(_at_)hallambaker(_dot_)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(_at_)hallambaker(_dot_)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(_at_)hallambaker(_dot_)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(_at_)fifthhorseman(_dot_)net> wrote:
> > On Tue 2016-04-12 13:01:14 -0400, Werner Koch <wk(_at_)gnupg(_dot_)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(_at_)ietf(_dot_)org
> > https://www.ietf.org/mailman/listinfo/openpgp
_______________________________________________
openpgp mailing list
openpgp(_at_)ietf(_dot_)org
https://www.ietf.org/mailman/listinfo/openpgp