Bitcoin Forum
May 07, 2024, 03:23:19 PM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 »  All
  Print  
Author Topic: Re: Dealing with SHA-256 Collisions  (Read 1738 times)
lovenlifelarge (OP)
Hero Member
*****
Offline Offline

Activity: 676
Merit: 501



View Profile
May 13, 2013, 02:44:05 PM
 #1

A mathematician friend of mine pointed out that there are very few if any hash protocols that have survived for 10 years or more. What would Bitcoin's solution be if SHA256 were to be cracked tomorrow?

I'm not sure what the solution would be but doesn't the block chain have a backup so if its ever forked it can just be rolled back with an update?? (This would allow changes to however it was hashed with everyone keeping there coins )

I think a major thing to recognize here is if SHA256 is ever broken all current ASIC's in the wild would become paper weights over night!

Which would be = WOFTAM = Waste Of Fucking Time And Money!

Correct me if i'm wrong!

▄▄▄████████▄▄▄
▄▄███▀▀▀      ▀▀▀███▄▄
▄██▀▀                ▀▀██▄
▄██▀                      ▀██▄
██▀                          ▀██
██▀                            ▀██
██▀    ███████        ███████    ▀██
▄██   ██████████████  ██████████   ██▄
██     ▄▄▄▄▄▄▄▄▄▄▄▄  ▄███████▄▄     ██
██     ▀▀▀▀▀▀▀▀▀▀▀▀  ███████▀▀▀     ██
██         ███████  ███████         ██
██         ▀██████████████▀         ██
▀██         ▀████████████▀         ██▀
██▄         ████████████         ▄██
██▄         ██████████         ▄██
██▄                          ▄██
▀██▄                      ▄██▀
▀██▄▄                ▄▄██▀
▀▀███▄▄▄      ▄▄▄███▀▀
▀▀▀████████▀▀▀
    ███████████████████████
█  ██             ██  █
█████             █████
█  ██             ██  █
█████             █████
█  ██             ██  █
███████████████████████
█  ██             ██  █
█████             █████
█  ██             ██  █
█████             █████
█  ██             ██  █
███████████████████████
█  ██             ██  █
█████             █████
█  ██             ██  █
█████             █████
█  ██             ██  █
███████████████████████
    ████████████████████▄
██                ████▄
██                ██████▄
██                ████████▄
██                ██████████▄
██                ████████████
██                ██        ██
██                ████████████
██                ██        ██
██████████████████████████████
██                          ██
██████████████████████████████
██                          ██
██████████████████████████████
██                          ██
██████████████████████████████
██                          ██
██████████████████████████████
██                          ██
██████████████████████████████
1715095399
Hero Member
*
Offline Offline

Posts: 1715095399

View Profile Personal Message (Offline)

Ignore
1715095399
Reply with quote  #2

1715095399
Report to moderator
The trust scores you see are subjective; they will change depending on who you have in your trust list.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1715095399
Hero Member
*
Offline Offline

Posts: 1715095399

View Profile Personal Message (Offline)

Ignore
1715095399
Reply with quote  #2

1715095399
Report to moderator
1715095399
Hero Member
*
Offline Offline

Posts: 1715095399

View Profile Personal Message (Offline)

Ignore
1715095399
Reply with quote  #2

1715095399
Report to moderator
Gavin Andresen
Legendary
*
qt
Offline Offline

Activity: 1652
Merit: 2216


Chief Scientist


View Profile WWW
May 13, 2013, 02:45:50 PM
 #2

Correct me if i'm wrong!

You are wrong.  If Bitcoin was using (double) MD5 for its proof-of-work hashing algorithm, we'd be just fine.

How often do you get the chance to work on a potentially world-changing project?
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8411



View Profile WWW
May 13, 2013, 02:55:37 PM
 #3

I think a major thing to recognize here is if SHA256 is ever broken all current ASIC's in the wild would become paper weights over night!
In addition to the point Gavin made— there is no reason for the POW and the rest of the protocol has to be using the same hash function.  We don't have the same security requirements in the POW as we do elsewhere. So its also perfectly conceivable to me that if there were concerns about the sha2 family everything else could change while the POW stayed SHA2-256.
oakpacific
Hero Member
*****
Offline Offline

Activity: 784
Merit: 1000


View Profile
May 13, 2013, 03:42:47 PM
 #4

And for address hashing I think we can just switch to SHA256(SHA256(PubKey)+PubKey), right?

https://tlsnotary.org/ Fraud proofing decentralized fiat-Bitcoin trading.
Dabs
Legendary
*
Offline Offline

Activity: 3416
Merit: 1912


The Concierge of Crypto


View Profile
May 13, 2013, 09:46:07 PM
 #5

What does the double hashing do that single hashing doesn't do? I ask because, how does a double hash affect those "games" that use hashes to determine winners?

While we're at it, why not a triple hash?

jdbtracker
Hero Member
*****
Offline Offline

Activity: 727
Merit: 500


Minimum Effort/Maximum effect


View Profile
May 13, 2013, 10:25:01 PM
 #6

The double hash could be useful to stop someone using a rainbow table or md5 dictionary preventing them from doing a collision attack, all they have left is to brute force it directly.

The latest wisdom suggests, that you use double hashing with a salt
Basically, you generate large salt (length 128b or more), and store in database Nth iteration (where N is several hundreds) of repetitive hashing salt with password.
Code php:
//Generating new salt and hash for new password
function set_password($password,$user_id){
$salt='';
for($x=0;$x<64;$x++){
   $salt.=chr(rand(0,255)); //generating salt of length 512b
}
$hashed_password='';
for($x=0;$x<512;$x++){
   $hashed_password=hash('sha512',$password . $hashed_password . $salt,true);
}
$hashed_password_to_store=hash('sha512',$hashed_password . $salt,true);
store_password($salt,$hashed_password_to_store,$user_id);//function that connects to DB and does inserting.
}

Code php:
//Generating new salt and hash for new password
function set_password($password,$user_id){
$salt='';
for($x=0;$x<64;$x++){
   $salt.=chr(rand(0,255)); //generating salt of length 512b
}
$hashed_password='';
for($x=0;$x<512;$x++){
   $hashed_password=hash('sha512',$password . $hashed_password . $salt,true);
}
/* here comes the addition */
$additional_number_of_iterations = ord($hashed_password[0]); //here we get a number from 0 to 255
for($x=0;$x<$additional_number_of_iterations;$x++){
   $hashed_password=hash('sha512',$password . $hashed_password . $salt,true);
}
$hashed_password_to_store=hash('sha512',$hashed_password . $salt,true); //password is not added here,
//for Hardened Stateless Cookies schema to work, see below.
store_password($salt,$hashed_password_to_store,$user_id);//function that connects to DB and does inserting.
}


and the address too is randomly generated!  Grin,

Bitcoin doesn't mess around, it pwnes hackers for breakfast

but yeah, if someone did break it... how does the system transfer to sha512 or SHA3?

If you think my efforts are worth something; I'll keep on keeping on.
I don't believe in IQ, only in Determination.
TierNolan
Legendary
*
Offline Offline

Activity: 1232
Merit: 1083


View Profile
May 13, 2013, 10:27:14 PM
 #7

While we're at it, why not a triple hash?

If you do 100 hashes and then check the target, then the target would be 100 times "easier" (i.e. highers).  It still balances, you do 100X as much work per hash, but the target is 100 times easier.

There is no extra effort for miners.

However, verifying the block chain is now 100 times as hard, since each header needs 100X as much effort to check.  The benefit is that it is much harder to break.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
jl2012
Legendary
*
Offline Offline

Activity: 1792
Merit: 1097


View Profile
May 14, 2013, 03:54:27 AM
 #8

Correct me if i'm wrong!

You are wrong.  If Bitcoin was using (double) MD5 for its proof-of-work hashing algorithm, we'd be just fine.

How about having 2 valid blocks with same hash?

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3 (Bitcoin ONLY)
LRDGENPLYrcTRssGoZrsCT1hngaH3BVkM4 (LTC)
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
oakpacific
Hero Member
*****
Offline Offline

Activity: 784
Merit: 1000


View Profile
May 14, 2013, 04:27:47 AM
 #9

Correct me if i'm wrong!

You are wrong.  If Bitcoin was using (double) MD5 for its proof-of-work hashing algorithm, we'd be just fine.

How about having 2 valid blocks with same hash?

How can you? The blcokheader, other than the nonce, has deterministic data in it, no?

https://tlsnotary.org/ Fraud proofing decentralized fiat-Bitcoin trading.
jl2012
Legendary
*
Offline Offline

Activity: 1792
Merit: 1097


View Profile
May 14, 2013, 06:29:50 AM
 #10

Correct me if i'm wrong!

You are wrong.  If Bitcoin was using (double) MD5 for its proof-of-work hashing algorithm, we'd be just fine.

How about having 2 valid blocks with same hash?

How can you? The blcokheader, other than the nonce, has deterministic data in it, no?

Arbitrary data could also be added to coinbase or transaction scripts.

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3 (Bitcoin ONLY)
LRDGENPLYrcTRssGoZrsCT1hngaH3BVkM4 (LTC)
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8411



View Profile WWW
May 14, 2013, 06:30:35 AM
 #11

Arbitrary data could also be added to coinbase or transaction scripts.
Indeed, but thats not sufficient to produce a collision with any existing MD5 attacks.
oakpacific
Hero Member
*****
Offline Offline

Activity: 784
Merit: 1000


View Profile
May 14, 2013, 07:12:22 AM
 #12

Hmmm, so what's the "SHA-256 became completely broken" everyone, including Satoshi was talking about in the post OP referred to really meant?

https://tlsnotary.org/ Fraud proofing decentralized fiat-Bitcoin trading.
jdbtracker
Hero Member
*****
Offline Offline

Activity: 727
Merit: 500


Minimum Effort/Maximum effect


View Profile
May 14, 2013, 08:44:03 AM
 #13

Quantum Computers that do calculations in Qubits are not too far away; they have now been able to do calculations using 84 Qubits!! Holy!

In 2009, researchers at Yale University created the first rudimentary solid-state quantum processor. The two-qubit superconducting chip was able to run elementary algorithms. Each of the two artificial atoms (or qubits) were made up of a billion aluminum atoms but they acted like a single one that could occupy two different energy states.

http://spectrum.ieee.org/nanoclast/computing/hardware/largest-quantum-computer-calculation-to-datebut-is-it-too-little-too-late

In Brian Wang's interview with D-Wave’s Rose, there's a discussion of the company’s new 512-qubit chip that should be, according to their calculations, 1000 times faster than the 128-qubit chips that D-Wave is currently working with

the best is from a group in Australia that has made a real 1 atom qubit.

In September 2012, Australian researchers at the University of New South Wales said the world's first quantum computer was just 5 to 10 years away, after announcing a global breakthrough enabling manufacture of its memory building blocks. A research team led by Australian engineers created the first working "quantum bit" based on a single atom in silicon, invoking the same technological platform that forms the building blocks of modern day computers, laptops and phones

http://www.gizmag.com/d-wave-quantum-computer-supercomputer-ranking/27476/

Even if their claims are bs, someone should be looking into this, it's only a matter of time before they begin mass producing these, bringing the price down: how many of these will it take to break the SHA256 encryption? 512?

http://www.dvice.com/archives/2012/04/quantum-simulat.php

They're up to 7 real qubits so far... obviously D-Waves computer is not a true Quantum computer, but that level of hashing power is enormous it could crack the SHA256 in no-time.

If you think my efforts are worth something; I'll keep on keeping on.
I don't believe in IQ, only in Determination.
oakpacific
Hero Member
*****
Offline Offline

Activity: 784
Merit: 1000


View Profile
May 14, 2013, 08:51:53 AM
 #14

Quantum Computers that do calculations in Qubits are not too far away; they have now been able to do calculations using 84 Qubits!! Holy!

In 2009, researchers at Yale University created the first rudimentary solid-state quantum processor. The two-qubit superconducting chip was able to run elementary algorithms. Each of the two artificial atoms (or qubits) were made up of a billion aluminum atoms but they acted like a single one that could occupy two different energy states.

http://spectrum.ieee.org/nanoclast/computing/hardware/largest-quantum-computer-calculation-to-datebut-is-it-too-little-too-late

In Brian Wang's interview with D-Wave’s Rose, there's a discussion of the company’s new 512-qubit chip that should be, according to their calculations, 1000 times faster than the 128-qubit chips that D-Wave is currently working with

the best is from a group in Australia that has made a real 1 atom qubit.

In September 2012, Australian researchers at the University of New South Wales said the world's first quantum computer was just 5 to 10 years away, after announcing a global breakthrough enabling manufacture of its memory building blocks. A research team led by Australian engineers created the first working "quantum bit" based on a single atom in silicon, invoking the same technological platform that forms the building blocks of modern day computers, laptops and phones

http://www.gizmag.com/d-wave-quantum-computer-supercomputer-ranking/27476/

Even if their claims are bs, someone should be looking into this, it's only a matter of time before they begin mass producing these, bringing the price down: how many of these will it take to break the SHA256 encryption? 512?

http://www.dvice.com/archives/2012/04/quantum-simulat.php

They're up to 7 real qubits so far... obviously D-Waves computer is not a true Quantum computer, but that level of hashing power is enormous it could crack the SHA256 in no-time.

First, they are nowhere near being capable of cracking ECDSA or RSA, the most direct proof is they are not factoring any number larger than 21.

Second, even if a QC is created, the best they can pull off is a 51% attack, which can be done by any government right now with classical computers.

https://tlsnotary.org/ Fraud proofing decentralized fiat-Bitcoin trading.
CIYAM
Legendary
*
Offline Offline

Activity: 1890
Merit: 1078


Ian Knowles - CIYAM Lead Developer


View Profile WWW
May 14, 2013, 08:57:43 AM
 #15

It doesn't seem to make much sense to talk about "cracking" a hash algorithm (it isn't an encryption or signature algo after all) but certainly a weakness in MD5 did make it possible to create different "strings" that would return the same hash (also known as "birthdays").

As each block has to include the previous blocks hash in its own "string" (plus other information including the timestamp and nonce) it doesn't make much sense that even if such a weakness was found in SHA256 that it would matter (unlike the rather more serious situation of using such hashes for say a CA cert).

Also even if ECDSA were to be "cracked" (i.e. making it easy to determine the private key from a public key) that would only be a problem if you re-use addresses (a good reason why you are advised not to).

With CIYAM anyone can create 100% generated C++ web applications in literally minutes.

GPG Public Key | 1ciyam3htJit1feGa26p2wQ4aw6KFTejU
aaaxn
Sr. Member
****
Offline Offline

Activity: 359
Merit: 250



View Profile
May 14, 2013, 09:46:18 AM
Last edit: May 14, 2013, 10:01:01 AM by aaaxn
 #16

What if someone could make valid next block which hash is exactly same as previous one? Wouldn't he be able to make chain of hundreds of this same block and still make valid blockchain?


                                                                              █
                              █████████                  ██████ 
                      ███████████████████████████   
              ███████████████████████████████   
            ████████████████████████████████   
        █████████████████████████████████     
    ████████████████████████████████████   
    ████████          █████████          █████████   
  ████████                ██████              ████████   
█████████                █████                ████████   
███████████                █                ███████████ 
██████████████                      ██████████████ 
█████████████████            ████████████████ 
███████████████                  ███████████████ 
█████████████                          █████████████ 
███████████              ███                ██████████ 
█████████                █████                ████████   
  ████████              ███████              ███████     
    █████████        █████████          ████████     
      █████████████████████████████████       
        ██████████████████████████████           
            ███████████████████████████             
              ████████████████████████                 
                  ████████████████████                     
CorionX


















Powered by,
CIYAM
Legendary
*
Offline Offline

Activity: 1890
Merit: 1078


Ian Knowles - CIYAM Lead Developer


View Profile WWW
May 14, 2013, 09:54:40 AM
 #17

As mentioned the previous hash needs to be included - the likelihood of SHA256( x ) being identical to SHA256( SHA256( x ) ) (in reality each hash actually being two hashes) is so close to zero as to be only be likely to occur sometime after firm evidence for the existence of the tooth fairy is published in Science magazine.

Smiley

With CIYAM anyone can create 100% generated C++ web applications in literally minutes.

GPG Public Key | 1ciyam3htJit1feGa26p2wQ4aw6KFTejU
oakpacific
Hero Member
*****
Offline Offline

Activity: 784
Merit: 1000


View Profile
May 14, 2013, 10:02:14 AM
 #18

As mentioned the previous hash needs to be included - the likelihood of SHA256( x ) being identical to SHA256( SHA256( x ) ) (in reality each hash actually being two hashes) is so close to zero as to be only be likely to occur sometime after firm evidence for the existence of the tooth fairy is published in Science magazine.

Smiley


But as you mentioned before, it could be better if we do SHA256(XOR(SHA256(PubKey),PubKey)) for the address hashing, perhaps we may likely stay largely safe even if practical QC is invented and both the ECDSA and SHA256 are exploited and no patch is immediately available, should we be able to do so?

https://tlsnotary.org/ Fraud proofing decentralized fiat-Bitcoin trading.
aaaxn
Sr. Member
****
Offline Offline

Activity: 359
Merit: 250



View Profile
May 14, 2013, 10:03:29 AM
 #19

As mentioned the previous hash needs to be included - the likelihood of SHA256( x ) being identical to SHA256( SHA256( x ) ) (in reality each hash actually being two hashes) is so close to zero as to be only be likely to occur sometime after firm evidence for the existence of the tooth fairy is published in Science magazine.

Smiley

Well, my question wasn't about likelihood of this happening, but whether such block would allow one to construct valid blockchain of arbitrary length.


                                                                              █
                              █████████                  ██████ 
                      ███████████████████████████   
              ███████████████████████████████   
            ████████████████████████████████   
        █████████████████████████████████     
    ████████████████████████████████████   
    ████████          █████████          █████████   
  ████████                ██████              ████████   
█████████                █████                ████████   
███████████                █                ███████████ 
██████████████                      ██████████████ 
█████████████████            ████████████████ 
███████████████                  ███████████████ 
█████████████                          █████████████ 
███████████              ███                ██████████ 
█████████                █████                ████████   
  ████████              ███████              ███████     
    █████████        █████████          ████████     
      █████████████████████████████████       
        ██████████████████████████████           
            ███████████████████████████             
              ████████████████████████                 
                  ████████████████████                     
CorionX


















Powered by,
CIYAM
Legendary
*
Offline Offline

Activity: 1890
Merit: 1078


Ian Knowles - CIYAM Lead Developer


View Profile WWW
May 14, 2013, 10:07:03 AM
 #20

Well, my question wasn't about likelihood of this happening, but whether such block would allow one to construct valid blockchain of arbitrary length.

True - but the likelihood is *why* the answer is not relevant (i.e. in "fairyland" we can have such a blockchain but in the real world we cannot).

Seriously if you want to *worry* about something then worry that the banks invent Bankcoin (which may or may not just be a bitcoin clone) and spend say 1 billion USD promoting it (nothing to them) wiping out all value for BTC after governments all decide that its usage should be banned.

With CIYAM anyone can create 100% generated C++ web applications in literally minutes.

GPG Public Key | 1ciyam3htJit1feGa26p2wQ4aw6KFTejU
Pages: [1] 2 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!