SHA256 Collision Attack

[Gabi]

I'm still waiting for that collision 

[1713947007]

1713947007

[1713947007]

1713947007

[A_CardeN]

I know 7.

[Garr255]

I know 7.

Pfft... I found upwards of 70 this week alone...

[A_CardeN]

I know 7.

Pfft... I found upwards of 70 this week alone...

To be honest, I don't even know what a sha256 collision attack is LOL

But it does not sound good.

[Fuzzy]

surely OP will deliver...

[Kazimir]

I know 7.

Post one, and 1000 bitcoins will come your way, sir!

[Kazimir]

To be honest, I don't even know what a sha256 collision attack is LOL

Collision = two different pieces of data (as in sequences of bytes) that have the same sha256 checksum.

Collision attack = an attempt at abusing a collision to make a fake transaction appear valid (because even though the data is forged, its checksum still matches).

There exists an infinite amount of such collisions (since there is an infinite number of possible byte sequences, yet only 2²⁵⁶ different sha256 hashes) but it's gonna be pretty darn difficult to actually find one. And that's quite an understatement (see the rough calculation posted earlier).

But it does not sound good.

No worries, it's not a problem whatsoever. First of all cause nobody will be able to find one in the foreseeable future, second because even if somebody accidentally runs into a collision, this is absolutely no threat to Bitcoin by any stretch of the imagination.

Only if someone "breaks" sha256, that is finding a practical way to deliberately generate a piece of data that results in a given sha256, we'd be effed. But as unlikely it is that somebody will even find just a random accidental single collision (and I'm really talking incredibly, astronomically, EXTREMELY unlikely here), it is still many, MANY orders of magnitude more unlikely that someone will actually break sha256.
 
Oh and by the way, if someone does break sha256, you can't trust online banking and credit card systems anymore either.

[JompinDox]

Don't know about Collision attacks, but I've been able to find a 11-character vanity address (the name of my band) easily, while vanitygen claimed it would take millions of years...

this is the address: 1ELECeJompinDox61L73eAUyaWpe3Q5HZB

Am I just lucky?

[casascius]

Don't know about Collision attacks, but I've been able to find a 11-character vanity address (the name of my band) easily, while vanitygen claimed it would take millions of years...

this is the address: 1ELECeJompinDox61L73eAUyaWpe3Q5HZB

Am I just lucky?

To successfully prove you found a vanity address, you must actually send some funds from the address, or sign a message with its private key.  Can you do that?  Otherwise all you have is proof you found a 32-bit collision on the checksum, which anyone can do quickly.  Otherwise, claiming something incredible like this as your 1st post is going to draw skepticism.

Assuming you can spend from the address, there is also the theoretical possibility that you vanitygen'd a bunch of 9-character semi-pronounceable string, picked one that looked the best (especially upper-and-lower-case-wise), and then said "that's my name!", incorporating the two digits "61" into the claim that those were exactly what you were looking for.  I mean, you did just create the account minutes before posting.

[gamebak]

The principle is simple
For every f(x) = sha256 hash there exists an f'(x) = same 256 hash

I think this was the theory in the back why a hash collision is possible for any of the existing hashes.

[BoardGameCoin]

The principle is simple
For every f(x) = sha256 hash there exists an f'(x) = same 256 hash

I think this was the theory in the back why a hash collision is possible for any of the existing hashes.

I believe this is wrong. There is nothing guaranteeing that there is not a unique image somewhere in the sha256 domain (byte sequences). Also, to state what I think you mean is that

for all x::[byte] there exists x'::[byte] such that

sha256(x) == sha256(x') and x != x'

But my contention is that it's not known whether thats true for all 'x'. It's certainly true that

there exists x::[byte] and x'::[byte] such that

sha256(x) == sha256(x') and x != x'

[JompinDox]

Don't know about Collision attacks, but I've been able to find a 11-character vanity address (the name of my band) easily, while vanitygen claimed it would take millions of years...

this is the address: 1ELECeJompinDox61L73eAUyaWpe3Q5HZB

Am I just lucky?

To successfully prove you found a vanity address, you must actually send some funds from the address, or sign a message with its private key.  Can you do that?  Otherwise all you have is proof you found a 32-bit collision on the checksum, which anyone can do quickly.  Otherwise, claiming something incredible like this as your 1st post is going to draw skepticism.

Assuming you can spend from the address, there is also the theoretical possibility that you vanitygen'd a bunch of 9-character semi-pronounceable string, picked one that looked the best (especially upper-and-lower-case-wise), and then said "that's my name!", incorporating the two digits "61" into the claim that those were exactly what you were looking for.  I mean, you did just create the account minutes before posting.

OK, you don't believe...  
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...

I do have some questions.

How easy would it be to "vanitygen a bunch of 9-character semi-pronounceable string and pick one that looks best"?

Or has anyone else been able to vanitygen a 11+ character address (with proper capitalization)? Probably with some sort of super computer?

What is the longest vanity address to date?


PS: Of course I just created this forum account, because I thought it was worth replying to this thread.

[gamebak]

The principle is simple
For every f(x) = sha256 hash there exists an f'(x) = same 256 hash

I think this was the theory in the back why a hash collision is possible for any of the existing hashes.

I believe this is wrong. There is nothing guaranteeing that there is not a unique image somewhere in the sha256 domain (byte sequences). Also, to state what I think you mean is that

for all x::[byte] there exists x'::[byte] such that

sha256(x) == sha256(x') and x != x'

But my contention is that it's not known whether thats true for all 'x'. It's certainly true that

there exists x::[byte] and x'::[byte] such that

sha256(x) == sha256(x') and x != x'

Yes mate, thanks for clearing the fact for everyone else.
Yeah it's true, i am not sure if this is possible for every sha256(x). I will have to check some documents as well.

[casascius]

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.

[pieppiep]

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.

Following, http://blockchain.info/address/1ELECeJompinDox61L73eAUyaWpe3Q5HZB

How easy would it be to "vanitygen a bunch of 9-character semi-pronounceable string and pick one that looks best"?

The base58 part contains out of the characters "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
vowels : 3 uppercase, 5 lowercase. (AEUaeiou)
consonants : 21 uppercase, 20 lowercase.
numbers : 9

If you want it like JompinDox, 3x (consonant vowel consonant) with the first and seventh characters uppercase, your chance will be
21/58 * 5/58 * 20/58 * 20/58 * 5/58 * 20/58 * 21/58 * 5/58 * 20/58 = (5^3 * 20^4 * 21^2) / (58^9) = 8820000000 / 7427658739644928 = 1.1874535851954921019166981507839e-6
1 / 1.1874535851954921019166981507839e-6 = 842138 tries.

But IIRC the bitcoin address is a 1 followed by 33 characters of the base58 string.
So you have 25 places it can occur, making it 842138 / 25 = 33685.52 tries.

(about the last part I'm not 100% sure, but I know for sure it gives you a better chance so lowering your tries needed)

[JompinDox]

I do have a question first.

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

Casascius himself stated that my claim was "incredible".

However, I didn't actually break SHA256 or anything, so how much
you're willing to bet on my claim that I did find that address
and own the key to it is up to you.

Being totally broke (I was devastated by a $350,000 loss last year,
but that's another story), I'm naturally very curious about that.

[pieppiep]

I don't know about the others, but you can have my 10BTC if you can show a sha256 collision.
But the bitcoin address is something else, I don't bet about that (yet?).

It is possible you have the keypair for the address with you name in it, but I don't know how you made it. It still is possible for you to have choosen your name because of that address.
However, if you really think you can generate a specific address, I can make a new address and put some bitcoins on it. Then I tell you the address and you generate the keypair and have the bitcoins.
But if it is possible to do that, why not just choose some used addresses and use the coins on it.

[JompinDox]

I don't know about the others, but you can have my 10BTC if you can show a sha256 collision.
But the bitcoin address is something else, I don't bet about that (yet?).

It is possible you have the keypair for the address with you name in it, but I don't know how you made it. It still is possible for you to have choosen your name because of that address.
However, if you really think you can generate a specific address, I can make a new address and put some bitcoins on it. Then I tell you the address and you generate the keypair and have the bitcoins.
But if it is possible to do that, why not just choose some used addresses and use the coins on it.

Lol of course I'm not able to do that I don't have that kind of superpower... Or it would mean the end of Bitcoin...

[flatfly]

Interesting... Watching this too

I've never been able to find a vanity address longer than 5 characters with my prehistoric laptop...

[JompinDox]

I've also just found these:

 16L48ssoSeG1worstVpsENv1rewVsw7nMa

 1GpacsJetrebeLcV15FSmw3vjLmPsineCp

Don't know if that's impressive or not