SHA256 Collision Attack

[SHA256Collision]

<redacted>

[hamdi]

i know one collision

[Kazimir]

i know one collision

I'm willing to bet 1000 BTC that you don't.

[Fuzzy]

i know one collision

I'm willing to bet 1000 BTC that you don't.

Me to.

Me thre.

[mistfpga]

i know one collision

I'm willing to bet 1000 BTC that you don't.

Me to.

Me thre.

so let me get this straight, I give you two inputs that after going through the sha256 alg they produce the same output? and i get 3k btc?

this is a joke right?

[Gabi]

No it isn't

Find a collision, c'mon 

[pieppiep]

Collisions in sha256 are possible, but at the moment only in 2^256 operations or 2^128 operations if you have enough memory for a birthday attack.
I'm sure some day a faster way to find collisions will be found, just like happened with md5.
But I'm also willing to bet another 10 BTC (I'm just not as rich as others) it won't happen this year.

[Kazimir]

so let me get this straight, I give you two inputs

(just to emphasize the obvious: two different inputs - not just different in notation, but different in terms of the binary data they represent)

that after going through the sha256 alg they produce the same output? and i get 3k btc?

No, 6k.

1k from me, 2k from Fordy, and 3k from Fuzzy

[Gabi]

C'mon mistfpga we are waiting. Where is that collision? 

[wareen]

so let me get this straight, I give you two inputs that after going through the sha256 alg they produce the same output? and i get 3k btc?

this is a joke right?

No, that's collision resistance of cryptographically secure hash functions

If I were you, I wouldn't settle for 6k BTC if you've actually broken SHA256

[Kazimir]

No, that's collision resistance of cryptographically secure hash functions

If I were you, I wouldn't settle for 6k BTC if you've actually broken SHA256

Note that finding 1 collision (which nobody ever managed to pull off so far, but could happen by chance although extremely unlikely) is by no means breaking sha256.

Breaking sha256 = finding a method that, for any given sha256 hash (or a significant portion of all possible sha256 hashes), can generate data (within reasonable time) which has the given sha256 hash.

[pieppiep]

No, that's collision resistance of cryptographically secure hash functions

If I were you, I wouldn't settle for 6k BTC if you've actually broken SHA256

Note that finding 1 collision (which nobody ever managed to pull off so far, but could happen by chance although extremely unlikely) is by no means breaking sha256.

Breaking sha256 = finding a method that, for any given sha256 hash (or a significant portion of all possible sha256 hashes), can generate data (within reasonable time) which has the given sha256 hash.

Add one little thing, it must be faster than brute force

[Kazimir]

I'll post the research paper once more, soon. 6K if it can be used to compute hashes faster, was it?

"Faster" as in "within reasonable time". Not as in: reducing the number of expected attempts from 2²⁵⁵ to 2²⁴³ or something, cause that's still way beyond reasonable and wouldn't make sha256 significantly less secure.

Allow me to throw in some numbers. If we were to use brute force only, without any trickery or sha256-specific attacks, there are 2²⁵⁶ possible hashes and by average we'd have to do 2²⁵⁶/2 = 2²⁵⁵ ≈5.8×10⁷⁶ attempts to find a collision. When using, say, this $15,295 mining rig which does 25.2 GigaHash/s, it would take ±2.3×10⁶⁶ seconds ≈7.3×10⁵⁸ years. For your reference: the current age of the universe is estimated at a mere 1.37×10¹⁰ years

So, even if you could speed up the computation of hashes by a trillion times (which would be quite an impressive achievement) it would take you 5328467153284670278835433757793583104 times the age of the universe to find a hit.

Let's put it otherwise: can you post a single collision (two different pieces of data having the same sha256 hash) somewhere later this month? Good luck sir

[Dabs]

Even better, is the practical application of finding a collision. That is, get the private key of a public key that has a lot of bitcoins in it. Then cash out. This will be advertised all over the media as a hack or a theft, and everyone will know about it.

Or, mine a block every 10 minutes (don't make it every minute or else people will get suspicious.) and keep the rewards. This will go unnoticed for a few days or a few weeks, depends on several other factors. So you can get BTC 5k every day or something like that.

Or, get the private keys of several public keys, do some salami slicing (get 0.01 BTC from every address). Then cash out. This will be broadcast all over the media eventually, after someone figures out what's happening, but it can take awhile, or people will not notice they just lost 0.01 BTC and not pay attention. This is feasible only if you have actually broken SHA256 and can get several targeted collisions on several bitcoin addresses.

[Soultaker]

Dabs: SHA-256 isn't used to sign transactions. You can't use it to steal money directly. You could exploit weaknesses by forking the blockchain, or, more practical, just earn a lot of BitCoins by mining at a not-too-suspicious rate. Even then, you need something better than just the ability to find a random collision.

[Dabs]

doh. I confused SHA256 with the ECDSA keypair. But what I meant applies to whoever breaks whatever algorithm. Just mine bitcoins. You'd get 5000 a day easy if you broke SHA.

[pieppiep]

5000 is a little to much I think, only 24*6*50 = 7200 / day are mined, so 5000 is almost 70% of total.
If you just mine 5% it is 360 BTC, somewhere like $1800 a day, it is much harder to notice so the chance of someone finding out is much less likely.

[drakahn]

If you break SHA the best thing to do would be to quietly let gavin know and wait for bitcoin to be fixed with an announcement that you broke it and were responsible for no one being ripped off because you only let gavin know, and the BTC "thankyou" payments will start rolling in

[Dabs]

360 BTC is probably also all you could possibly mine unless you really really broke SHA.

The best thing is indeed to tell Gavin. The next best thing is tell him after a few days (and say you were testing it.)

[Kazimir]

Let's put it otherwise: can you post a single collision (two different pieces of data having the same sha256 hash) somewhere later this month? Good luck sir

Any news on this?