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.

This question is an extension of Families of public/private keys in elliptic curve cryptography

As described above, bitcoin "type 2" deterministic wallets use a root private/public key pair, where subsequent keys take advantage of the fact that in elliptic curve cryptography the public key for a private key + a fixed number, happens to be another public key plus the same number times a point. There was some discussion about what properties the $H(i)$ function had to have, with the responder being unsure if $H(i)=i$ is secure, or for that matter, any $H$ at all. This issue has been discussed in the bitcoin community as well, with the consensus being that if $H$ is a pseudorandom function, the idea is secure. Theory aside, this is exactly how a number of production "type 2" deterministic wallets work, and they haven't been hacked yet.

Building on that sandy foundation, I'd like to extend the idea even farther. Specifically, I'm creating a wager service, where I'd like users to be able to submit their wagers by sending bitcoins to specially encoded addresses. My thought was to use $H(\mbox{bet details} | \mbox{return address})$ with $|$ representing concatenation and $H$ a pseudorandom function. Thus the final public key for the address becomes $\mbox{pub_key_root} + H()\cdot \mbox{point}$ and the private key $\mbox{priv_key_root} + H()$

If the bet details are restricted to a small search space, and the return addresses restricted to addresses seen on the bitcoin network in the last $n$ blocks, simple brute force checking of every transaction to see if it is part of the system is quite feasible.

Note that I do not care if someone can determine if a given public key is related to another; the system will be completely public and all public keys will be determinable by anyone. In fact, for this application this property is an advantage for reasons of transparency.

The problem is, this gives the attacker a lot of control over the value $H()$: they can set an arbitrary number of bits by brute forcing a hash collision. (changing the return address as required) If the service then spends the payments it is forced to use related private keys chosen by the attacker. To me, this smells bad, but if ECC is genuinely secure against related keys, it's not a problem.

Now I will say, a countermeasure would be to include in the calculation of $H()$ the block hashes of $n$ consecutive bitcoin blocks seen after the receiving address was last in the block chain. This assumes that no attacker has the hashing power to choose the hashes of $n$ consecutive blocks; a particularly strong statement as even to generate one block you are heavily constrained by the requirement to create a partial collision; $n=1$ may be sufficiently secure. However this extension would complicate the user interface and slow down the wagers which I'd like to avoid if possible. The attacker would still have control over the bet details as well.

Quite simply: Is my proposed scheme secure, and why?

share|improve this question
    
Actually, regarding the countermeasure at the end, it occurs to me that anything beyond $n=1$ adds no value, as you still have the problem that if you can control the last data going into the hash, you simply pick it appropriately for the result you want. –  user2006 Apr 24 '12 at 8:23
1  
What exactly is your question here? –  Paŭlo Ebermann Apr 24 '12 at 20:09
    
Sorry, I wasn't being clear. Quite simply, is my proposed scheme secure, and why? Ideally someone could point me to a statement that yes, creating signatures with such related keys is secure, or no it isn't. –  user2006 Apr 25 '12 at 2:28

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.