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

[Phillip Hallam-Baker <[e-mail]>]

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
<[e-mail]> wrote:
> 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
>
> _______________________________________________
> openpgp mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/openpgp