How safe is bitcoin with regard to a random address generation attack? [duplicate]

Question

This question already has an answer here:

• Is it possible to brute force bitcoin address creation in order to steal money? 11 answers

Imagine an attacker implementing something like the following pseudocode on the fastest ASIC farm money can buy:

attack(blockchain, my_address)
    addresses = generate_tree_of_all_nonempty_addresses(blockchain)
    while true:
        private_key = generate_random_private_key()
        public_key = generate_public_key(private_key)
        address = ripemd160(sha256(public_key))
        if is_matched(address, addresses):
            steal_bitcoins(private_key, public_key, address, my_address)

Given that RIPEMD-160 reduces addresses to a size of 160 bits (in binary form), and that there are (IIRC) over a million non-empty addresses out there, does it really still take an impractically long time to find collisions? I should be able to do the math myself, but I know some of you are better at that kind of thing than I am...

Or to put that another way, is it possible that the decision to hash public keys the way bitcoin does, might in the future turn out to be unwise given the heightened risk of collisions compared to simply using the full ECDSA public key length?

Answer 1

Ok, I'm spoiling the fun of you working it out yourself, but I had too much fun working it out myself to not post.

In order to have as many target addresses as possible, let's suppose every satoshi that will ever exist (21e6 * 100e6 = 2.1e15 or 2.1 quadrillion) were in a different address. And let's suppose someone developed an ASIC that, at the same rate as today's ASICs compute SHA256D, could generate a private key, compute the corresponding public key and address, and check it against all 2.1 quadrillion of those targets. (This is absurd - generating an ECDSA public key is many orders of magnitude more complex than an SHA256 hash.) Suppose they deployed this ASIC on the same scale as today's entire Bitcoin mining network.

The current Bitcoin difficulty is about 4e10, meaning the network as a whole is computing 4e10 * 2^32 = 1.7e20 hashes per second. So let's say our imaginary attacker's network is generating 1.7e20 private keys per second. Each private key has a probability of 2.1e15 / 2^160 = 1.4e-33 of matching one of the target addresses. So the attacker finds a match at a rate of 1.7e20 * 1.4e-33 = 2.4e-13 per second. On average, it takes 1/2.4e-13 = 4.0e12 seconds, or roughly 130,000 years, to find one match.

So this highly dedicated attacker, who is spending millions (if not billions) of dollars on ASICs and electricity, will be able to steal an average of one satoshi every 130,000 years.

One really has to come to terms with how mind-bogglingly fast an exponential function grows. 160 bits seems like a very small amount of data, but 2^160 is an incredibly huge number.

Answer 2

This question has received some great quotes by David Schwartz and others at: https://bitcointalk.org/index.php?topic=24268.0

The total address space is 2^160

To put that in perspective, there are only 2^63 grains of sand on all of the beaches of the Earth (http://www.hawaii.edu/suremath/jsand.html)

---

There are just under 2^256 private keys, just under 2^256 public keys, and 2^160 addresses. There are some addresses that have more than one corresponding public key and thus more than one corresponding private key.

---

The most sensible way to attempt the attack (which is still insane) is to generate random private keys, calculate the corresponding addresses, and then see if that address has a non-zero balance. I believe there are 2^160 possible addresses. So even if there are 1,000,000,000 addresses with non-zero balances, your odds of getting a non-zero balance on a single key are 1 in 2^128.

So brute-forcing a single bitcoin address with a non-zero balance (assuming there are a billion of them, which is generous), is as hard as, say, brute-forcing a given 128-bit AES key.

---

With an average of 300,000,000 bitcoin addresses being consumed (used once only) every day the 2^160 address space is going to serve its purpose for say another 2^131 days. The memory of us will forever live inside what will then be called the ancient blockchain.