hashed user IDs redux [was: Re: Creating a key bearing no user ID]

[Robert J. Hansen]

On 1/26/12 11:22 AM, Peter Lebbing wrote:
> If I'm not going to give it verbally, why not just give the key
> fingerprint?

Yes.

I've not hidden my opinion that I think this is an exercise in quixotry,
but still, never let it be said I wasn't willing to make some
contribution to an idea.  Let's not talk about implementation details:
right now we don't have a good enough handle on the problem to talk
about how to solve it.  So let's see if we can't use a 'Problem',
'Goal', 'Requirements' and 'Constraints' model to focus the conversation
a little bit.

PROBLEM:
  * Some people want to make it possible to opt out of their email
    addresses being harvestable on the keyservers.

GOAL:
  * Give users an optional way to make their user IDs resistant to
    harvesting.

REQUIREMENTS:
  * The solution must work within the OpenPGP framework without
    requiring any extensions.
  * The solution must work with SKS without requiring any extensions.
  * The User ID must be searchable (otherwise the solution is trivial,
    create a User ID with a name but no email address).  If a user
    searches the keyserver for exactly a given email address, matching
    certificates must be returned.

CONSTRAINTS:
  * Key enumeration.  There are only roughly 10 million login names
    five characters or less.  Searching those 10 million login names
    over the top 100 email domains amounts to about a billion queries.
    Split over a botnet of 100,000 elements, each bot would have to
    make 10,000 queries.  Even if each query took one second (an
    unreasonable number: it would substantially impact OpenPGP adoption
    because people would be furious over the slow speed of lookups),
    that means a spammer network could break any such blinded hashing
    scheme in about three hours.
  * Utility.  One way to make a blinded hashing scheme enumeration-
    resistant is to put a large amount of random data in there.
    However, searching for 'zz78gH1Y==@hotmail.com' is of comparable
    complexity to searching for a certificate ID.  The system must
    work for all reasonable User IDs, rather than requiring User IDs
    to be unreasonable.


... Looking over this, I don't think that what MFPA wants is possible.
I just don't.  The key enumeration issue and the ease of getting past
it, *even if we require each search to take one second to execute*, is
the gorilla in the center of the room that's threatening to pound to a
pulp anyone who seriously tries to take on this problem.

If we discard the "must conform to OpenPGP" and "must be compatible with
SKS" requirements, then maybe we could make it work.  But as is, if I
was asked to evaluate this research project, I would call it extreme
risk for minimal reward.

"Risk", in an engineering management context, usually means "risk of
failure and wasting all the resources invested."  The risk level seems
extreme.

Even if you succeed, how many people will join up?  How many people will
revoke their old User IDs and create new ones?  Few, I think, which
makes this minimal-reward.  Even if you succeed, you'll impact only a
very small fraction of OpenPGP users.