3
$\begingroup$

Earlier today I was answering a question on the ethereum SE site that analyzed the potential for more than one private key on curve secp256k1 (which maps to a distinct public key) to control the same ethereum address which are derived by hashing the public-key with Keccak256 as a byte array, and whether the rightmost 160-bits of the two resulting distinct hash digest could collide and thus two different private keys control the same address.

In other words, what would be the possibility that any two Keccak-derived hash digests had the same right-most 160 trailing bits (small-endian side)?

And secondly, does that possibility change (and to what degree) if both pre-images can only be valid secp256k1 public-keys of which there are roughly ${2^{256}}$ of them or more precisely n as per this curve's parameters, where n is equal to 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141.

Again, ethereum addresses are simply the last 40-hex characters of a 64-hex (256 bit) Keccak Hash of the secp256k1 public-key derived from the users private key (assumed to be less than n).

If the digest space is $2^{256}$, and there exist even 2 digests that share the same trailing 160-bits, what are the chances that the pre-images to those 2 digests are valid 512-bit public-keys? And moreover, that those private-keys were actually derived by a private key known to the user (and not just a random 512-bit string that was brute-forced).

Given the multiple layers of conditions (compared being able to try any arbitrary pre-image regardless of length etc..), I was thinking that it could be possible (by chance perhaps) that no two private keys will derive the same ethereum address, even if there exists more than one Keccak256 hash-digest that partially collides in terms of the last 160 bits.

Although if there is a non-negligible amount of such 160-trailing-bit collisions, perhaps the chances actually exist for one ethereum address to be controlled by two different public keys? (even if not feasible to find them).

Note: My estimate/guess is that one would have to brute-force search at least $2^{160}$ valid private keys on the elliptic curve, including steps to derive the public key and resulting Keccak256 hash digest, to try to find even one such partial collision of the last 160-bits.

Can such a scenario even be computed or is there no way to know?

$\endgroup$
2
  • $\begingroup$ With 160 hash bits in the address (for a strong hash) it's a 1/2^160 risk of accidental collision for 2 arbitary addresses, and 2^(160/2) = 2^80 work to create a deliberate collision between 2 of your own generated addresses (birthday paradox attack). For a strong hash, each individual bit is supposed to be independent and indistinguishable from random, under a computational security definition, thus the simple math above. The structure of the input data should not result in visible bias in the hash output. $\endgroup$
    – Natanael
    Aug 22, 2019 at 8:18
  • $\begingroup$ And by the pigeonhole principle, when the address hashes are smaller than the public keys there are always multiple valid public keys for each hash. For ECC, in most curves every possible input string of the right size is a valid public or private key (with some exceptions). $\endgroup$
    – Natanael
    Aug 22, 2019 at 8:20

1 Answer 1

4
$\begingroup$

There are about $2^{256}$ distinct inputs, secp256k1 private keys, and about $2^{160}$ distinct outputs, Ethereum addresses.

By the pigeonhole principle, there is at least one address which is shared by many private keys. In principle, there could be $2^{160} - 1$ addresses each with exactly one private key, and another address with $2^{256} - (2^{160} - 1)$ different private keys. But that is essentially guaranteed not to be the case in practice.

The map from secp256k1 private keys to Ethereum addresses can reasonably be modeled as a uniform random function. In this model, the expected number of secp256k1 private keys shared by a single hash is about $2^{96} = 2^{256}\!/2^{160}$.

What can you do with this apparently staggering number of colliding private keys?

  • Suppose the world has generated $n$ private keys and published their addresses. The probability that there is a pair of private keys $k \ne k'$ sharing a common address $H(k) = H(k')$ is about $n^2\!/2^{160}$ by the birthday paradox[1].

    If the world has generated a trillion keys, or about $2^{40}$, this probability is below $1/2^{80}$. In other words, you are essentially guaranteed it hasn't happened.

  • Suppose you want to find some pair of private keys $k \ne k'$ sharing a common address $H(k) = H(k')$. The cheapest known method is the van Oorschot–Wiener parallel collision search machine[2], whose expected cost is $\sqrt{2^{160}} = 2^{80}$; of course, if parallelized $p$ ways, it runs in time $2^{80}\!/p$.

    This cost is spent by the Bitcoin network in about a day. But what would you do with this pair of keys? You could give one of the keys to someone and do something nefarious with the other key, but…if you can already choose someone's key, it's hard to imagine what nefarious things you could do with a colliding key that you couldn't already do with the original in the first place.

  • Suppose you have a specific address $h = H(k)$ for a key $k$ that you don't know, and you want to find a key $k'$ that matches $h$. You are essentially guaranteed that $k' \ne k$, but that doesn't matter—$k$ can spend the money of $k'$ and vice versa. Perhaps you actually have $t$ different addresses, $h_1 = H(k_1)$, $h_2 = H(k_2)$, …, $h_t = H(k_t)$, and you will be happy if you find one matching $k'_i$. The cheapest known method is an adaptation of Oechslin's rainbow tables[3] to a $p$-way parallel machine[4], which costs $2^{160}\!/t$ as long as $t < p^2$, and runs in time $2^{160}\!/pt$.

    Even if you had a quadrillion target keys (about $2^{50}$), which you don't, and you had a $2^{100}$-way parallel computer, which you don't, it would still cost $2^{110}$ to power that computer to find the first matching private key, which you won't.


P.S. Public keys may be encoded with 512 bits but there are only about $2^{256}$ of them—specifically, there are exactly as many distinct public keys as there are distinct private keys.

$\endgroup$
2
  • $\begingroup$ Interesting, it looks like bitcoin addresses have the same address-space dilemma: bitcoin.stackexchange.com/a/31/89688 Are you saying that an address could be cracked, by finding a private key that mapped to that same address (even if it wasn't the underlying users same key) in 2^110 operations? I think a few days ago the bitcoin network broke 82 trillion hashes per second, which is about 2^63 hashes per day ( which is still very very far from 2^110). $\endgroup$ Aug 23, 2019 at 7:25
  • $\begingroup$ You would have to have a computer of size $2^{100}$ in order to make it this cheap, and you would have to have $2^{50}$ keys to target for it to be this efficient. That's a lot of silicon, and I'm pretty sure even the now-venerable Bitcoin blockchain doesn't have anywhere near $2^{50}$ bits in it, let alone $2^{50}$ keys. A century of Bitcoin mining at about 1 MB every 10 min would produce only about 5 TB of data. Even if every byte were (magically) a key, for $5\cdot 10^{12} \approx 2^{42}$ keys, the best cost estimate would be $2^{118}$, which you definitely can't afford. $\endgroup$ Aug 23, 2019 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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