search

jewel / clearskies

Open source btsync clone
1.41k stars 50 forks source link

Do not use SHA-256 hashing #36

Closed GitMoDu closed 10 years ago

GitMoDu commented 10 years ago

Because of bitcoin miners, we now have dedicated devices that can hash SHA-256 in the order of Terahash/s. Since this rate is rising fast, SHA-256 will soon be obsolete.

I don't know enough to suggest any algorithm with confidance, but I'd also avoid s-crypt as dedicated devices for that algorithm are coming this year. S-crypt-n should be fine, however.

larroy commented 10 years ago

+1

larroy commented 10 years ago

jewel, please comment on this.

krupan commented 10 years ago

relevant: http://bitcoin.stackexchange.com/questions/17132/is-bitcoin-mining-itself-compromising-the-security-of-sha256

jewel commented 10 years ago

Thanks for the issue, @GitMoDu.

I recently removed password-related uses of SHA256, where a brute force attack on a password with little entropy would be possible.

The only remaining use where we need cryptographicly sound SHA256 is in the "directory" extension, where we are computing the SHA256 of files. A malicious read-only user could substitute their own versions of files and try and have other read-only peers read them if they can find a file with the same SHA256 checksum as an existing file.

I don't believe that the prevalence of cheap SHA256 hardware acceleration weakens the SHA256 for this use case. I can't find my notes for this, but I believe that even if the hashrate for the bitcoin network keeps doubling at the same rate, it won't be a problem for a several decades.

If someone can find a credible source that says otherwise, we can switch to a SHA-3 variant. If I get a chance I'll redo the math. In the meanwhile, I'll leave this issue open.

GitMoDu commented 10 years ago

A malicious read-only user, could try to wreck the files by selecting a small enough file so that he can try to hash a new signed file with different data/garbage. With a low size file, the hashing can be done very fast (no disk I/O to slow things down) and increases the chances of finding a collision, which translates into a read-only client writing. Please correct me if I've understood something wrong.

The hashrate for the bitcoin network is not much the point, what's important is the availability of SHA256 machines with increasingly high hashrates, much more than double per year: 2012 top was 25 Gh/s, 2014 is 1 Th/s!

This might be a rather small and innocuous attack vector, but if we can plug it from the start, I'd rest easier.

Thoughts?

krupan commented 10 years ago

"...increases the chances of finding a collision..." Increases the chances from some small probability to some larger but still tiny probability. The stackexchange question I referenced earlier states that you'd have to try 10^38 hashes to find a collision. If you harnessed all the bitcoin miners to get that 10^12 h/s hash rate (by somehow convincing them that cracking clearskies would be a more profitable use of their hardware?), it would still take 10^26 seconds to do all 10^38 hashes. 10^26 seconds is about 3x10^18 years, or in other words, 3 quintillion years. I think using SHA-256 is probably fine.

jewel commented 10 years ago

@GitMoDu, file size is irrelevant, since you can save the state of the SHA hash machine and just keep trying to change the last few bytes.

The reason why I don't think this is an issue is that 2^256 is unbelievably big. In order to find a collision, you'd have to try, on average, 2^255 different combinations in order to get a match. At 1 terahash/second, it would take 1.835*10^57 years.

All cryptography has a limited shelf life, of course. There's no point in trying to find something that will be safe to use forever, as long as it's safe for a few decades.

onionjake commented 10 years ago

It is also important to note when the hashing algorithm would be vulnerable to an attack. Jewel has already identified that you would need to have a read-only share with someone you did not trust (possible). They would need to then compute a file that has the same hash as an existing file (very very hard, i.e. impossible). This 'corrupt' file could then be shared to new peers that happen to download that file from that single peer. Even if they managed to do that, the original read-write share would never download this corrupted file from this read-only peer.

Also, as soon as you modify that file, all copies would be blown away and the attacker would have to start over.

GitMoDu commented 10 years ago

Thank you all, for all your replies. I think I've cleared my doubts about this issue.