SHA256 Collision Attack

[Kazimir]

Do the bets made in this thread apply to me
if I can successfully prove my claim?

No, well at least not my part

My bounty was on a pure sha256 collision. That is: two different sequences of bytes (not necessarily of the same length) which have the same sha256 hash.

A vanity address is something entirely different (although a 11+ digit vanity address is impressive if you indeed have the corresponding private key).

I'll add another 1000 BTC is you can generate a collision for a specific sha256 hash
Let's say, for example, if you can generate data (a sequence of bytes) which has this sha256 hash: 7bf3c0394237866352e95d84c91648bc141ab32f64e1b56ac198bb618571846d

Being totally broke (I was devastated by a $350,000 loss last year, but that's another story)

Damn man, sounds shitty

[AbsoluteZero]

It must be a very secret band as there are no Google results found for "Jompin Dox"

[flatfly]

It must be a very secret band as there are no Google results found for "Jompin Dox"

+1!  I call bluff...  But I still just donated a few bitcents to that mystery address, in case you're the real deal

[JompinDox]

Unfortunately I'm in no position to prove this yet, as I don't know how to 'sign a message'
and have no BTC to spend...

You now have 0.0638 BTC from me... assuming you have the private key to that address.  Send it anywhere, and your claim that you own the address is proven correct.

Hi, I've just made a test send.
I guess this proves that I do own the key to that address.

[Kazimir]

So, any news on this?

I just noticed an article by Bruce Schneier, where he states that we might start seeing the first successful SHA-1 attacks in 6-9 years from now.

Now remember, SHA-1 is just 160-bit. The SHA-2 variant used in Bitcoin is 256-bit, that's almost a hundred million billion trillion (!!) more possibilities. Somehow I doubt the stories about SHA256 collisions that some people were claiming here

[pieppiep]

I don't have the time right now to read it, but somehow I think the attack isn't related to the 160-bit but more to the algoritm.
So if a flaw is found in SHA-1 with 160-bit, and you make a SHA-1b with 320-bit, a collision can be found in somewhat the same time.

[Kazimir]

I don't have the time right now to read it, but somehow I think the attack isn't related to the 160-bit but more to the algoritm.

Well, fortunately, the SHA-2 algorithm (which also includes SHA-256) is completely different than SHA-1.

So if a flaw is found in SHA-1 with 160-bit, and you make a SHA-1b with 320-bit, a collision can be found in somewhat the same time.

I doubt it - the described possible future attack abuses some weak properties of SHA-1, to reduce the number of brute force attempts from 2⁸⁰ to 2⁵².
If you do the same with a 320-bit hash, you're still dealing with 2¹³² (reduced from 2¹⁶⁰) attempts or maybe 2¹⁰⁴ in best case scenario (if the weak properties extend to additional SHA rounds in the 320-bit version).

Well, 2¹⁰⁴ is still a HECK of a lot more than 2⁸⁰
Once we can do 2⁸⁰ in one day (which we can't, not even in 6-9 years cause the described scenario only deals with the reduced 2⁵² case), the 2¹⁰⁴ would still take 45.000 years. Good luck with that sir

[Bitznbitz]

Give it to a 3yr old kid, if anyone can break it, they can.

[alberthendriks]

Are these bounties still on? If so, could you post expiry dates and/or expiry events?

[pieppiep]

My 10 BTC is expired, it's already spent
But you can probably get a lot more than the few thousand bitcoins you get here.
Also, a normal SHA-256 isn't that interesting for bitcoin. For bitcoin you need SHA-256d which is SHA-256(SHA-256())

[nimda]

My 10 BTC is expired, it's already spent
But you can probably get a lot more than the few thousand bitcoins you get here.
Also, a normal SHA-256 isn't that interesting for bitcoin. For bitcoin you need SHA-256d which is SHA-256(SHA-256())

An arbitrary collision on SHA-256 gives a collision on SHA-256d.

[alberthendriks]

I'm still attacking SHA-2 (256). Of course I know it's not going to work out, but it's a nice and learnful hobby.

Sometimes while hobbying, I run into stupid questions. Like this one:
Wikipedia claims that the best preimage attack on SHA-2 is actually reduced (41 rounds) in time 2^(253.5).
It seems trivial to have a full 2^256 attack (so where do I go wrong?) if SHA is really a bit pseudorandom. Input to SHA is 447 (free) bits; output is 256 (fixed) bits. I make some propagators to rule out trivially conflicting bit assignments. I make 191 non-locally-conflicting random bit-assignments (propagating after each assignment). I have 256 free bits left. Since there are 256 free bits and the output is also 256 bits, I expect to have 1.0 solution left. I search for it with brute-force.

[b!z]

I'm still attacking SHA-2 (256). Of course I know it's not going to work out, but it's a nice and learnful hobby.

Sometimes while hobbying, I run into stupid questions. Like this one:
Wikipedia claims that the best preimage attack on SHA-2 is actually reduced (41 rounds) in time 2^(253.5).
It seems trivial to have a full 2^256 attack (so where do I go wrong?) if SHA is really a bit pseudorandom. Input to SHA is 447 (free) bits; output is 256 (fixed) bits. I make some propagators to rule out trivially conflicting bit assignments. I make 191 non-locally-conflicting random bit-assignments (propagating after each assignment). I have 256 free bits left. Since there are 256 free bits and the output is also 256 bits, I expect to have 1.0 solution left. I search for it with brute-force.

good luck cracking sha 256. it probably won't ever work.

[alberthendriks]

Yes I know, but it gives such a great feeling to find dependencies within sets of bits that were possibly unintended.