The case for moving from a 160 bit to a 256 bit Bitcoin address

[gmaxwell]

Also, It looks like the new 256 bit hash format is part of the current segwit proposal, correct?

Yes, Segwit script v0 P2WSH (the p2sh for segwit) uses 256bit SHA2; both boosting the security to 128 bits, and removing ripemd160 from the potential locations of weakness.

There is a 160 bit supported, but only for single key checksig only. Basically so that the very common single key case that gains little from the 256bit hash isn't any longer than non-segwit.

[addrstore.com]

The author, there is no need to go to the 256-bit address. 160 bits is enough to ensure the security of the address.

The problem is completely contrived.

In order to get a collision with a probability of 1.77636E-15 (and this probability is negligible, there is a higher chance of winning the lottery) there must be a blockchain in which 2 ^ 56 addresses will be used, each address being 20 bytes (160 bit). In total, the blockchain with such an amount of addresses will occupy not less than 2 ^ 56 * 20 = 1441151 TB (this is the lowest estimate), by the way, at the moment, the blockchain is only 126 GB.

[BurtW]

The author, there is no need to go to the 256-bit address. 160 bits is enough to ensure the security of the address.

The problem is completely contrived.

In order to get a collision with a probability of 1.77636E-15 (and this probability is negligible, there is a higher chance of winning the lottery) there must be a blockchain in which 2 ^ 56 addresses will be used, each address being 20 bytes (160 bit). In total, the blockchain with such an amount of addresses will occupy not less than 2 ^ 56 * 20 = 1441151 TB (this is the lowest estimate), by the way, at the moment, the blockchain is only 126 GB.

When you read the thread did you see this post:

There are only 2,100,000,000,000,000 satoshis.

Therefore the maximum number of Bitcoins addresses that can contain value at any one time is only about 2⁵¹ and that assumes only one satoshi per address.

At the time the block chain contains 2⁵⁵ transactions it would be somewhere between a petabyte and an exabyte in size.  So a full node would need a multi petabyte drive to store the entire block chain.

Your estimate for block chain size is interesting.  I will ponder that.  Thanks.

[DannyHamilton]

The author, there is no need to go to the 256-bit address. 160 bits is enough to ensure the security of the address.

The problem is completely contrived.

In order to get a collision with a probability of 1.77636E-15 (and this probability is negligible, there is a higher chance of winning the lottery) there must be a blockchain in which 2 ^ 56 addresses will be used, each address being 20 bytes (160 bit). In total, the blockchain with such an amount of addresses will occupy not less than 2 ^ 56 * 20 = 1441151 TB (this is the lowest estimate), by the way, at the moment, the blockchain is only 126 GB.

Did you even think about reading the thread before wasting your time writing your post?

There is a bigger concern with 160 bit P2SH addresses than a collision with an address in the blockchain.  The concern is that an attacker can create two separate addresses that BOTH DO NOT exist in the blockchain, but which collide with each other.  With 160 bit addresses, there is a reasonably good chance that an attacker could do so within 2^80 attempts.

While 2^80 is a big number and probably more than you're going to do with your CPU today, it isn't big enough to be considered "secure".

As for the storage requirements:

- snip -
A cost optimized solver will make some time/memory tradeoff and usually end up using a couple times more computation . . . in exchange for little to no storage.  (google floyds cycle finding algorithim)

And yes, thats the risk-- that your counterparties degree of freedom in choosing part of the contract will let them find an alternative contract with only collision like work, rather than with second-preimage like work.
- snip -

[addrstore.com]

With 160 bit addresses, there is a reasonably good chance that an attacker could do so within 2^80 attempts.

What good chance are you talking about?

You can take specific numbers and count.

In order to get collision with a 40% chance on a set of 2 ^ 80 addresses, you need a memory size of 2.4 * 10 ^ 25 bytes. And even applying algorithms that use a trade-off between memory and calculation time - it will still be a huge size. All the Internet for the time of its existence is estimated only in 10 ^ 24 bytes (https://www.livescience.com/54094-how-big-is-the-internet.html), i.e. You will need a memory capacity like 200 modern Internet, I'm not talking about computing power, which will also be needed. Hence, we can conclude that in practice we will not be able to find a collision at the current time and for the next 15-20 years it will be impossible.

Quantum computers will appear faster because of which it will be necessary to change all modern cryptography and hashing methods..

[dinofelis]

With 160 bit addresses, there is a reasonably good chance that an attacker could do so within 2^80 attempts.

What good chance are you talking about?

You can take specific numbers and count.

Well, you are making the case for 80 bits security level.  Bitcoin set out to have a 128 bit security level.  Once that principle is adopted (for good or bad reasons), it is good to stick to it.  If you don't, you have inconsistent security requirements, and inconsistent burdens.  Some calculational and storage burden would be due to people sticking with 128 bit security level, while other parts would only give you 80 bits security level and punch holes in the burden that was paid for elsewhere.  I can agree with you that maybe one should have put bitcoin's security at only 80 bits level.  That would have shortened quite a lot of things (room on chain, processing capacity, network capacity etc....). But Satoshi put it at 128 bits level (that's why the ECDS keys are 256 bit length).  Once you go for that, you have to keep it uniform, or you have inconsistent safety and burden.

[aliashraf]

2^80 is a lot of work, but it isn't enough to be considered secure by current standards.

Actually it is more than enough:
If all the parties of the bitcoin network with the current hash power of (almost) 2^62 H/s reach a consensus and decide to just find one single 160 bit collided pair of keys, they have to devote their total power for the next 1000+ years or so  to do the job. (Note: we have to run 2 hash functions in each test).

Which 'current standards' are you mentioning in this context?

I think there is a point that has been missed out: Any security consideration should be taken in response to the extent of the possible threats which are always proportional to the incentives.

In this specific case it is mathematically possible for a hypothetical very powerful attacker to spend trillions of dollars and a significant amount of time to collide with a 160 bit random (absolutely random) address and disrupt a single contract: my lesson? never put trillions dollars worth of assets on a single contract on top of the bitcoin blockchain, or make sure there is not a single sensitive dependency to the 160 bit hashed key addresses in the policy .

[gmaxwell]

2^80 is a lot of work, but it isn't enough to be considered secure by current standards.

Actually it is more than enough:
If all the parties of the bitcoin network with the current hash power of (almost) 2^62 H/s reach a consensus and decide to just find one single 160 bit collided pair of keys, they have to devote their total power for the next 1000+ years or so  to do the job. (Note: we have to run 2 hash functions in each test).

Check your math. 2^62 hashes per second does 2^80 work in 2^18 seconds.   That is three days.

you need a memory size of 2.4 * 10 ^ 25 bytes. And even applying algorithms that use a trade-off between memory and calculation time - it will still be a huge size.

No it won't.  Collisions can be found an an effectively storageless manner with a small constant factor slowdown, I gave google terms upthread.

You're suffering from the same ignorance that caused the collision design flaw in "xthin" where they were claiming that collisions of a 64-bit hash were infeasible to compute due to storage requirements. (which I eventually eventually grew tired of correcting and started responding to all the messages with 64-bit sha2 collisions.)

[aliashraf]

2^80 is a lot of work, but it isn't enough to be considered secure by current standards.

Actually it is more than enough:
If all the parties of the bitcoin network with the current hash power of (almost) 2^62 H/s reach a consensus and decide to just find one single 160 bit collided pair of keys, they have to devote their total power for the next 1000+ years or so  to do the job. (Note: we have to run 2 hash functions in each test).

Check your math. 2^62 hashes per second does 2^80 work in 2^18 seconds.   That is three days.

OK. My bad. But the main argument remains valid: It takes a definitely huge amount of resources and time to collide with 168 key hashed addresses and for the near future the cost of such an attack can not be justified while bitcoin block chain is a monetary infrastructure and the attacker MUST justify his/her costs.

I insist you and other guys pay more attention here: We are not discussing security as a general problem. It is not about sensitive data related to nuclear missiles or family scandals, data with infinite or undecidable values. Our context is securing contracts on top of the Blockchain.

As of 160 bit hashed address key problem, the hypothetical attack can compromise a contract on the Blockchain, but nobody puts such a huge amount of money on a single contract. He/she should not do this and Bitcoin is not and have not to be adequate for such a contract.

[gmaxwell]

Yes, 2^80 is still a lot of work-- which is why I didn't just do it to make an example in a response.

But it is not an infeasible amount of work: 2^80 work by Bitcoin is paid for by less than three days of mining income-- $14,580,000-ish.

But who are you to decide that the maximum value of of a Bitcoin exchange should be limited to under (say) $15M?  Personally, I'm gunning for the day where a single Bitcoin is worth that much. (otherwise, I dunno how I'm going to finance both a space elevator and the invention of human immortality)-- and what about next year?   With 2^80 work perfectly achievable though expensive now  where will that cost be next year and the year after?  We saw with P2SH that it takes _years_ to adopt a new address type in Bitcoin.  "By 2025 a children's speak and spell could crack it"  (perhaps not, but the point remains)

Being weak in this way is just fodder for conspiracy theories and arguments that Bitcoin will lose its value in the future. This sort of weakness makes life harder for application developers since there are more corner cases which they cannot dismiss as categorically infeasible. Between these, security against near future decreases in computational costs, and security for large values-- 12 bytes of additional public key size is a pretty low price to pay.

[Pieter Wuille]

In order to get collision with a 40% chance on a set of 2 ^ 80 addresses, you need a memory size of 2.4 * 10 ^ 25 bytes. And even applying algorithms that use a trade-off between memory and calculation time - it will still be a huge size.

That's not correct. Floyd's cycle-finding algorithm can be used to find colliding script hashes with O(1) memory, for just a factor 3 slowdown.

[DannyHamilton]

- snip -

- snip -

- snip -

Wow, what a flashback of familiar people.

Burt, Greg, and Pieter all in the same thread?  Feels like I'm back in late 2011, or early 2012.

Bitcointalk hasn't been this educational and interesting in ages.

[aliashraf]

Yes, 2^80 is still a lot of work-- which is why I didn't just do it to make an example in a response.

But who are you to decide ...

I Ignore the language  

... that  the maximum value of of a Bitcoin exchange should be limited to under (say) $15M?  

It is  not about 'exchange' ...
With all due respects, you are exaggerating too much.

I think you haven't caught the real reason that 256 bit addresses are important.  Any N-bit address has only N/2 bits of security against collision, right?

Wrong! They are n/2 secure against a birthday attack in applications sensitive to birthday attack! This is it, nothing more. No generalizations please.

I appreciate your _discovery_ about vulnerabilities in bitcoin's 2-of-2 contracts and alike.

It is definitely a good hint but it has nothing to do with 'exchange' as a general concept.

Thanks to your (and other guys') posts here, one should definitively conclude that, people can 'exchange' trillions of dollars in a single bitcoin transaction and remain safe and secure but they can _not_ put multimillion dollar assets  on 2-of-2 contracts in a 'naive' way.

By 'naive' I mean giving HIS right to an anonymous counter-party without using work around procedures like multiple communications proportional to the value of asset under contract.

Your points implying that people do not understand or do not follow hints, is not acceptable in this context, as we are not discussing simple low stake daily trades. Ignorant people never sign a multi million dollar contract without consultation and following the most secure procedures. In such a trade they will deliberately go through exhaustive communications that can escalate attack costs enough to de-incentivize it.

So I come to my final conclusion: Everything is OK with the current 160 bit hashed addresses and nothing will be compromised in the real world, never ever.

As I understand, you are bolding this vulnerability to justify SW once more, this time as a bonus for dealing with an attack that never gonna happen. Am I right?

[addrstore.com]

you need a memory size of 2.4 * 10 ^ 25 bytes. And even applying algorithms that use a trade-off between memory and calculation time - it will still be a huge size.

No it won't.  Collisions can be found an an effectively storageless manner with a small constant factor slowdown, I gave google terms upthread.

You're suffering from the same ignorance that caused the collision design flaw in "xthin" where they were claiming that collisions of a 64-bit hash were infeasible to compute due to storage requirements. (which I eventually eventually grew tired of correcting and started responding to all the messages with 64-bit sha2 collisions.)

You want to say that performing a hash according to the scheme:

Hash1 = RIPEMD160(SHA256(Data1))
Hash2 = RIPEMD160(SHA256(Data2))

You can find such Data1 and Data2, in which the first 64 bits in hash1 and hash2 will be the same without using the birthdays attack and bruteforce? And you will not spend much memory?

Can I see the algorithm (GitHub) and proof of work? I want to try it myself. How much time will it take to calculate this?

[addrstore.com]

In order to get collision with a 40% chance on a set of 2 ^ 80 addresses, you need a memory size of 2.4 * 10 ^ 25 bytes. And even applying algorithms that use a trade-off between memory and calculation time - it will still be a huge size.

That's not correct. Floyd's cycle-finding algorithm can be used to find colliding script hashes with O(1) memory, for just a factor 3 slowdown.

If I understand correctly on Wikipedia, this is a pointer algorithm, it uses O(1) memory, but the data structure itself, for which pointers will be created how much will it occupy?

[TierNolan]

If I understand correctly on Wikipedia, this is a pointer algorithm, it uses O(1) memory, but the data structure itself, for which pointers will be created how much will it occupy?

You don't store it at all.

You start with some seed for x[0] and then compute x[1] and x[2] and so on.

x[n + 1] = Hash(x[n])

After around 2⁸⁰ steps, x[n] collides with one of the previous values.  This creates a loop.

Code:

*   A -> B -> C -> D -> E .
*             ^            \
*             |             v
*             J             F
*              \           /
*               I <- H <- G

So, compute H = x[2⁸⁰] and then start from x[0] again.  If you hit H before you get to 2⁸⁰, then you know you have a loop.  Continue until you hit H a second time and that gives you the length of the loop.

Once you have the length of the loop and the location(s) of H, you can compute where merge point is.  In the diagram that is the positions of J and B.  Run a third time, and store J and B, you now how 2 values which hash to the same value.

To steal money, you actually need to have 2 types of hash.  The fair and fraudulent one.

Based on LSB of x[n]

EVEN: x[n + 1] = Hash(multisig with [Alice's public key & x[n] as Eve's public key])
ODD: x[n + 1] = Hash(checksig with [Eve's public key] + DROP(x[n]))

In the multisig, Eve doesn't even need to have the private key.  She isn't planning to use that version anyway.

Assume capitals are "fair" and lower case is "fraud", the diagram would change to

Code:

*   a -> B -> c -> D -> e .
*             ^            \
*             |             v
*             J             f
*              \           /
*               I <- H <- g

In this case, B and J are both fair.  So the collision is useless.

Eve would try again with another seed.  She needs to get one fair and one fraud.

There is a 50% chance she gets a mix, so on average she will need 2 seeds.

[addrstore.com]

Thanks. A beautiful and detailed answer. Now I agree that for p2sh addresses there really is a need to use a longer hash.

[TierNolan]

Thanks. A beautiful and detailed answer. Now I agree that for p2sh addresses there really is a need to use a longer hash.

20 bytes is enough for someone who is creating their own address from a private key and doesn't involve someone else.  You get 160 bit security in that case (which is higher than the 128 bit security from the signature algorithm).

One size fits all means that people don't accidentally use the wrong hash size in the cases where there is a weakness.  It also reduces code complexity.