Distributed rainbow table network? (MD5 coin)

[fbueller]

I was wondering what bitcoin would be like if it used MD5, and that got me to thinking about a distributed rainbow tables, where miners are hashing plain-text sent over the p2p network as messages, and also doing a proof of work similar to bitcoins as well.

People submitting plain-text to be hashed and stored could attach a fee, and should be default, so miners can work on other peoples hashes, and earn something in that way. Fees wouldn't necessarily be required, so miners could compute their own garbage once it hasn't been worked on before perhaps? Spam messages are tolerated an extent, since MD5 is fast, and miners can hash these for the public good anyway.

Similar networks could be deployed for all hashing algorithms, to get the clock ticking on their demise, and eventually it may highlight issues in the algorithm, and hopefully even result in a collision. There would be an ever present reminder for developers to stay away from weak hash functions, and use adequate salts for passwords, if something like this was working away in the background.

Just daydreaming, what do you think of something like this?

I wonder if all of bitcoins invalid block hashes were stored, would a collision have been found in SHA256 yet?

[TimS]

I wonder if all of bitcoins invalid block hashes were stored, would a collision have been found in SHA256 yet?

With extremely high probability, no. The network hash rate recently passed 100 PH/s. If we had been mining at 100 PH/s for 1 year, we would've done about 10^21.5 hashes (actual total number is probably lower than this, but will exceed it soon enough). There's a table on the Wikipedia article about the Birthday attack, which shows that for a 256-bit hash (assuming no known weaknesses), you'd need over 10^38 hashes to have a >1% chance of a collision.
So at 100 PH/s, we'd need to hash for around 10^16.5, or 31 quadrillion years. Even with increasing computer speed, I don't think we practically have to worry about a collision...unless maybe we find a way to harness the mass-energy of entire suns and galaxies, all for the purpose of finding a SHA256 collision.

[jl2012]

I wonder if all of bitcoins invalid block hashes were stored, would a collision have been found in SHA256 yet?

Not this again, please

[TimS]

Not this again, please
[image]

What if we found a way to harness the entire mass-energy of the Sun, not just the portion burned through by its natural fusion? Because that would certainly give you enough energy to count to 2^256. I'm using data from http://en.wikipedia.org/wiki/Orders_of_magnitude_(energy) that the minimum energy to change state at the lowest temperature yet achieved (100 picokelvins) is ~10^-33 J, and the mass-energy of the sun is ~10^47 J. 10^47 / 10^-33 ~= 2^266, so you might be able to count close to 1000 times 2^256 with the mass-energy of the sun. If you take the milky way with its dark matter/energy, you're looking at ~2^306 information changes.

In fact, since addresses are "only" 160 bits, you "only" need ~10^15 J (~400 gigawatt-hours; the world uses more electricity each hour) to enact 2^160 information changes at 100 picokelvins. Granted, RIPEMD160(SHA256(priv * G)) is much harder than 1 information change, but maybe not "burn out the sun trying" hard.

Don't get me wrong: I know that we'll not get even close to this being an issue for a very long time. But I think that image is highly inaccurate about how secure Bitcoin is. It takes best-case scenarios in some things (energy change, 1 flip = 1 hash), nearsighted ones in others (only one sun, can only get energy by letting it burn naturally), and completely ignores that 2^160 is the weak point of the current system, not 2^256. It's also very light on the science behind its claims.

[fbueller]

I appreciate that a collision in SHA256 is unlikely, I was actually hoping for a response to the rest of the post, not the one line mentioning collision in SHA256.

[TimS]

I was wondering what bitcoin would be like if it used MD5, and that got me to thinking about a distributed rainbow tables, where miners are hashing plain-text sent over the p2p network as messages, and also doing a proof of work similar to bitcoins as well.

People submitting plain-text to be hashed and stored could attach a fee, and should be default, so miners can work on other peoples hashes, and earn something in that way. Fees wouldn't necessarily be required, so miners could compute their own garbage once it hasn't been worked on before perhaps? Spam messages are tolerated an extent, since MD5 is fast, and miners can hash these for the public good anyway.

Similar networks could be deployed for all hashing algorithms, to get the clock ticking on their demise, and eventually it may highlight issues in the algorithm, and hopefully even result in a collision. There would be an ever present reminder for developers to stay away from weak hash functions, and use adequate salts for passwords, if something like this was working away in the background.

Doing one MD5 hash is far easier than creating a transaction and paying a fee to have someone else do it for you. The only way I can even see this being remotely plausible is if you made the tasks fairly difficult, e.g. by specifying a pattern that contains thousands/millions of things to be hashed.

People complain about the blockchain size of Bitcoin, a paltry ~20GB. Rainbow tables can easily reach 200GB or 2000GB. Rainbow tables that are distributed and where people are rewarded for doing low-interest hashes would grow fast. I for one wouldn't want to buy many TBs in order to have an MD5 lookup table/coin.