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