Re: k-deterministic public-private key generation

Lenny G. wrote:
>"K-deterministic public keys," which are
>public/private key pairs generated by using a keyword 'K' as the only
>input to the psuedo-random number generator that is used by the key
>generator. [...] A peer
>searching for a keyword 'K' also generates the key pair 'Ku(K)/Kr(K)',
>and sends H(Ku(K)) as the query. The publisher responds by sending
>matching content results, and "intermediaries can verify that the
>response is properly signed by a public key that hashes to the query
>hash, but are unable to decrypt the response or learn the 'K' that was
>used to generate the public key without guessing."

This would be fine if the keyword was generated uniformly at random from
a space large enough to prevent guessing K. However, if K has fairly low
entropy, then this sounds like it has serious problems. An attacker who
sees H(Ku(K)) could find K by dictionary search, and once you know K you
know the private key Kr(K). The attack effort can be amortized: one could
build a lookup table mapping hash digest H(Ku(K)) --> keyword K, for many
likely values of K, and then attacking any single query requires only a
hashtable lookup.

I don't know enough about how this is used as part of the search, but it
doesn't sound like it is adding much, if keywords are guessable.

>It seems like if you
>know something about the nature of the set of likely queries that might
>be issued by peers, you might have a fairly decent way to see what is
>going on. For example, if I were a record label and wanted to monitor
>for people searching for/sharing music by my label, I'd just compute
>the hashes of k-deterministic keys from appropriate keywords (artist
>name(s), album names, track names), insert some intermediaries, and
>when I see a match, pay close attention to the initiators and
>responders. Any reason why this wouldn't work?

That sounds right to me.

>More interestingly, is there any way to go from Ku to K?

Not if K has sufficient entropy and is distributed uniformly (or from
a distribution that the pseudorandom generator is secure for).

>Assymetric key generation isn't usually one-way, is it?

Actually, it is. If given the public key Ku, you were able to recover the
random coins used during key generation (K), then given the public key Ku
you would be able to recover the private key Kr. For any secure asymmetric
scheme, the latter is supposed to be infeasible.

>My /real/ question is related: is there anything wrong with generating
>Ku/Kr from the hash of a user-chosen password (assuming, of course,
>that the password is not a dictionary word or otherwise weakly chosen)
>in the same manner as described for k-deterministic key pairs?

Yes, what's wrong is that your assumption is unlikely to hold in the real
world. Passwords rarely have enough entropy to resist offline dictionary
search, and this scheme is subject to offline password search attacks. In
theory it would work fine if passwords could be assumed to be high entropy.
Received on Sat Oct 15 04:38:04 2005