# Elliptic curve cryptography related key attacks [closed]

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.

Symbolically, with root private key $a$, public key $A$, 'fixed number' $b$, hash function $H(\cdot)$, we could construct a new private key as:

$a' = a + H(b)$,

which gives the corresponding public key as:

$A' = A + H(b) \cdot G$, where $G$ is the generator of the elliptic curve group in question.

There was some discussion about the properties $H(i)$ should have, with the responder being unsure if $H(i)=i$, or any $H$ at all, results in a secure system. 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 $A + H(\mbox{contents})\cdot G$ and the private key $a + H(\mbox{contents})$

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(\mbox{contents})$: they can set an arbitrary number of bits by exhaustive search, incrementing 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 contents 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?

• 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
• 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

• Cryptoeconomic security: People will not try and game your scheme if you can ensure that the value of gaming your scheme is less than the cost of doing so. In your example, if you use the blockhash within the protocol, an adversary controlling the blockhash may withhold the block they have successfully mined, in order to give themselves a better than average chance at winning your game. With this knowledge, you can find the lower bound on how motivated and powerful an adversary attacking your scheme must be by defining a security parameter $n$ such that: $$\mbox{value gained by winning your game} < n * \mbox{bitcoin block reward}.$$
For your question of whether creating signatures with 'related keys' is secure, this is something I'm currently working on formally proving. With the hash function modeled as a random oracle, I believe we have the result that one can produce: $$a' = a + H(S),$$ and hence spend funds associated with an account if and only if they know the $A$ such that: $$A' = A + H(S) \cdot G,$$ with $G$ the generator of the elliptic curve group in question. However, this is dependent on your opinion of hash functions as random oracles. $H(i) = i$ would definitely not be sufficient, and $S$ is assumed to be secret.
EDIT: If $H(S)$ is not secret, there will be a de-anonymising attack on all transactions associated with your account, but people will not be able to forge transactions from you, or spend the bitcoin from that account, as they will not have the root private key $a$ necessary to form the private key. They will simply be able to scan the blockchain and group the accounts associated with you. This is how view keys and spending keys in anonymous cryptocurrencies such as Monero work.