Bitcoin Forum
December 09, 2016, 09:39:17 PM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: « 1 [2] 3 »  All
  Print  
Author Topic: SHA256 Collision Attack  (Read 10464 times)
Kazimir
Legendary
*
Offline Offline

Activity: 1036



View Profile
June 24, 2012, 11:37:29 AM
 #21

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 Wink
Any news on this? Smiley

In theory, there's no difference between theory and practice. In practice, there is.
Insert coin(s): 1KazimirL9MNcnFnoosGrEkmMsbYLxPPob
1481319557
Hero Member
*
Offline Offline

Posts: 1481319557

View Profile Personal Message (Offline)

Ignore
1481319557
Reply with quote  #2

1481319557
Report to moderator
1481319557
Hero Member
*
Offline Offline

Posts: 1481319557

View Profile Personal Message (Offline)

Ignore
1481319557
Reply with quote  #2

1481319557
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481319557
Hero Member
*
Offline Offline

Posts: 1481319557

View Profile Personal Message (Offline)

Ignore
1481319557
Reply with quote  #2

1481319557
Report to moderator
1481319557
Hero Member
*
Offline Offline

Posts: 1481319557

View Profile Personal Message (Offline)

Ignore
1481319557
Reply with quote  #2

1481319557
Report to moderator
1481319557
Hero Member
*
Offline Offline

Posts: 1481319557

View Profile Personal Message (Offline)

Ignore
1481319557
Reply with quote  #2

1481319557
Report to moderator
Gabi
Legendary
*
Offline Offline

Activity: 1050


View Profile
June 24, 2012, 12:28:16 PM
 #22

I'm still waiting for that collision  Roll Eyes
fanquake
Donator
Sr. Member
*
Offline Offline

Activity: 266


View Profile
June 24, 2012, 01:19:33 PM
 #23

I'm still waiting for that collision  Roll Eyes

I think will be waiting a while.
A_CardeN
Jr. Member
*
Offline Offline

Activity: 42


View Profile
June 24, 2012, 07:54:12 PM
 #24

I know 7.

try again
Garr255
Legendary
*
Offline Offline

Activity: 952


What's a GPU?


View Profile
June 24, 2012, 08:06:49 PM
 #25

I know 7.

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

“First they ignore you, then they laugh at you, then they fight you, then you win.”  -- Mahatma Gandhi

Average time between signing on to bitcointalk: Two weeks. Please don't expect responses any faster than that!
A_CardeN
Jr. Member
*
Offline Offline

Activity: 42


View Profile
June 24, 2012, 08:10:08 PM
 #26

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.

try again
Fuzzy
Hero Member
*****
Offline Offline

Activity: 560



View Profile
June 24, 2012, 08:13:29 PM
 #27

surely OP will deliver...
Kazimir
Legendary
*
Offline Offline

Activity: 1036



View Profile
June 24, 2012, 10:18:41 PM
 #28

I know 7.
Post one, and 1000 bitcoins will come your way, sir!

In theory, there's no difference between theory and practice. In practice, there is.
Insert coin(s): 1KazimirL9MNcnFnoosGrEkmMsbYLxPPob
Kazimir
Legendary
*
Offline Offline

Activity: 1036



View Profile
June 24, 2012, 10:32:26 PM
 #29

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 2256 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).

Quote
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.

In theory, there's no difference between theory and practice. In practice, there is.
Insert coin(s): 1KazimirL9MNcnFnoosGrEkmMsbYLxPPob
JompinDox
Member
**
Offline Offline

Activity: 107


View Profile
June 28, 2012, 06:59:29 PM
 #30

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?

Tips? 1ELECeJompinDox61L73eAUyaWpe3Q5HZB
Down with socks!
casascius
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1344


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
June 28, 2012, 07:02:25 PM
 #31

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.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper wallets instead.
gamebak
Member
**
Offline Offline

Activity: 103


View Profile
June 28, 2012, 07:09:04 PM
 #32

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
Sr. Member
****
Offline Offline

Activity: 283



View Profile
June 28, 2012, 07:16:46 PM
 #33

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'

I'm selling great Minion Games like The Manhattan Project, Kingdom of Solomon and Venture Forth at 4% off retail starting June 2012. PM me or go to my thread in the Marketplace if you're interested.

For Settlers/Dominion/Carcassone etc., I do email gift cards on Amazon for a 5% fee. PM if you're interested.
JompinDox
Member
**
Offline Offline

Activity: 107


View Profile
June 28, 2012, 07:24:03 PM
 #34

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... Sad

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.

Tips? 1ELECeJompinDox61L73eAUyaWpe3Q5HZB
Down with socks!
gamebak
Member
**
Offline Offline

Activity: 103


View Profile
June 28, 2012, 07:40:47 PM
 #35

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
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1344


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
June 28, 2012, 07:43:41 PM
 #36

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... Sad

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.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper wallets instead.
pieppiep
Sr. Member
****
Offline Offline

Activity: 402



View Profile
June 28, 2012, 09:07:57 PM
 #37

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... Sad

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
Member
**
Offline Offline

Activity: 107


View Profile
June 29, 2012, 07:18:08 AM
 #38

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.

Tips? 1ELECeJompinDox61L73eAUyaWpe3Q5HZB
Down with socks!
pieppiep
Sr. Member
****
Offline Offline

Activity: 402



View Profile
June 29, 2012, 07:30:40 AM
 #39

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
Member
**
Offline Offline

Activity: 107


View Profile
June 29, 2012, 07:34:35 AM
 #40

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 Smiley I don't have that kind of superpower... Or it would mean the end of Bitcoin...

Tips? 1ELECeJompinDox61L73eAUyaWpe3Q5HZB
Down with socks!
Pages: « 1 [2] 3 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!