Topic: Re: Dealing with SHA-256 Collisions (Read 1775 times)

Definitely in our future, Bitcoin clones popping up everywhere! That is a more pressing concern than worrying that the encryption will be broken in the next 40 years.

I don't mind some of them, like CureCoin or ScienceCoin, those sound like interesting proposals with serious bandwidth problems if they try to use Bitcoin's system... I like them.

Bank coin, hmmm does that mean they call the stakes and our collective evolution of Bitcoin will be grinded to a halt?
This is BankCoin! This is how it is! do as we say not as we do!


Binary concatenation seems quite effective, definitely limits the problem of duplicate hashes, but what about the bandwidth needed? would it increase the size of transactions? Is the limit 500kb/block right now?

Instead of the double hashing that Bitcoin currently uses, i.e. sha256(sha256(x)), I would have preferred a nested double hash, i.e. sha256(sha256(x)+x) where '+' means binary concatenation. For one, this avoids entropy reduction. Which normal double hashing does not - the 1st way can (and most likely will) have less effective entropy than the 2nd.

Or ever better, the recursive hashing depth could increase with every N blocks. So after a specific (considerably large) number of blocks, the hashing method would become: sha256(sha256(sha256(x)+x)+x), etc.

Anyway, even with the current simplistic double hashing, if sha256 ever gets broken (not to be expected in the forseeable future), Bitcoin is still safe for a *long* time and we have plenty of opportunity to switch to sha512 or sha3 (keccak).

I'll take that for yes. Not need to include you worries.
Anyway if I wanted to worry bitcoin have enough serious economic problems so I don't need technical ones

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.

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

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?

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.

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?

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

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.

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.

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

Indeed, but thats not sufficient to produce a collision with any existing MD5 attacks.

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

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

How about having 2 valid blocks with same 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.

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!  ,

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?

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?

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