producing GnuPG keys as proof of work

[Mirimir]

On 10/02/2014 12:28 PM, Daniel Kahn Gillmor wrote:
> On 10/02/2014 02:02 PM, Mirimir wrote:
>> Would it be feasible to use gpg in batch mode to generate numerous keys,
>> selecting for a particular key ID, or perhaps a longer part of the
>> fingerprint? I'm aware of shortcuts for creating keys with arbitrary key
>> IDs, but they produce keys with atypical key lengths etc. Based on
>> limited experience, I suspect that entropy would be the limiting
>> resource. Is that correct?
> 
> No, this is not a good idea.  Searching for a particular OpenPGP keyid
> or substring of a fingerprint is functionally equivalent to searching
> for a substring of any other SHA1 digest.
> 
> gpg's delay in generating a key is due to trying to generate keys with
> specific characteristics, drawn from suitably robust entropy.  It's not
> possible in the general case to observe from the generated public part
> of the key (much less the fingerprint) whether those constraints were
> respected or not, so someone wanting to fake the proof of work could
> simply ignore the gpg constraints, use a weaker (or nonexistent) entropy
> source, and rapidly generate public keys that a naive (or
> resource-constrained) observer couldn't distinguish from a real key.
> This effectively cheats the proof-of-work scheme.

Thank you. I didn't realize that distinguishing real from fake was hard.

> If you want proof-of-work, there are many better-evaluated mechanisms
> available than using OpenPGP fingerprints.

I haven't found a challenge-based proof-of-work mechanism. Suggestions
or hints would be very helpful.

> 
> 	--dkg
>