Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I need an untrusted client to generate a random public/private keypair (in particular, an Ed25519 keypair, which can be generated really fast), but I'm only allowed to see the public key. The randomness is important because the public key is used in attack-sensitive ways such that being able to influence it more than a few bits is a security risk.

I had the following idea:

  1. Create a nonce and send it to the client.
  2. Let the client create a public/private keypair such that hash(public_key + nonce) starts with at least n zero bits and send it back.
  3. If the client returns a public/private keypair after t seconds, reject it.

Is this a correct scheme to ensure randomness of the keypair, given an appropriately chosen n and t?

share|improve this question
2  
"being able to influence it more than a few bits is a security risk" seems like a really weird requirement. –  CodesInChaos Feb 3 '13 at 17:18
    
@CodesInChaos: the public key is used as a node id in the Kademlia DHT, being able to choose it allows for attacks like the Eclipse attack. –  nightcracker Feb 3 '13 at 17:27
1  
But a DHT usually has no authoritative server, so who would enforce the time limit or generate the nonce? –  CodesInChaos Feb 3 '13 at 17:29
    
@CodesInChaos: the authoritative server :) –  nightcracker Feb 3 '13 at 18:09
add comment

1 Answer 1

up vote 7 down vote accepted

An alternative:

  1. Client generates preliminary keypair $(t, T)$ with $T=tB$
  2. Clients sends $T$ to server
  3. Server sends a random scalar $n$ back(alternatively choose $n = \mathrm{HMAC}(k, T)$ with secret key $k$), and assigns the public key $A = T + nB$ to the client
  4. Client uses $a = t+n$ as private and $A$ as public key.

That way the server decides the public key, without knowing the associated private key. If the server shouldn't be able to influence the public key either, you can use a commitment scheme that allows mutually distrusting parties to generate a random number.


Your proof-of-work approach doesn't really work since there isn't a good value for the timeout. For typical hash proofs, an attacker can easily have several thousand times the computational power of a defender. GPUs, FPGAs, using cloud computing to rent lots of power for a short time, etc.

share|improve this answer
    
The server is allowed to influence the public key. –  nightcracker Feb 3 '13 at 17:28
    
I'm new to elliptic curve cryptography, how would the sum A and the sum a be calculated? A general answer is nice, but if you could comment on it using the terminology/functions used in the SUPERCOP implementation (also available from my github) that would be nice. –  nightcracker Feb 3 '13 at 18:23
1  
summing A would be called a group addition, summing s a scalar addition. –  CodesInChaos Feb 3 '13 at 18:43
    
I managed to implement it, thanks a ton! This property of Ed25519 is really cool. –  nightcracker Feb 3 '13 at 19:58
1  
You can use the same technique with other elliptic curves, or even finite fields. For example Bitcoin Vanitygen uses it so that the party who uses a lot of computational power to find the meaningful address doesn't need to know the private key. –  CodesInChaos Feb 4 '13 at 11:06
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.