[openpgp] proof-of-work fingerprints [was: Re: Fingerprint requirements for OpenPGP]

[Daniel Kahn Gillmor <[e-mail]>]

On Tue 2016-04-12 13:01:14 -0400, Werner Koch <[e-mail]> 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