Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Announcing the first SHA-1 collision

security.googleblog.com

Post reply on HN
Print view View original

251–260 of 524 posts

Re: Announcing the first SHA-1 collision

#251

Post by sp332 »

nickez wrote: post #9
zurn wrote: post #6

Anyone have back of the envelope calculations for the cost of the CPU and GPU time?

On the shattered webpage: This attack required over 9,223,372,036,854,775,808 SHA1 computations. This took the equivalent processing power as 6,500 years of single-CPU computations and 110 years of single-GPU computations.

Hm, according to https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a27... a GTX 1080 can do 8.54 billion SHA-1 hashes per second. That puts it at only 34.2 years to compute 9.22*10^18 hashes.

Re: Announcing the first SHA-1 collision

#252

Post by mate_soos »

I am a bit saddened that Vegard Nossum's work, which they used for encoding SHA-1 to SAT, is only mentioned as a footnote. The github code is at

https://github.com/vegard/sha1-sat

and his Master Thesis, whose quality is approaching a PhD thesis is here:

https://www.duo.uio.no/bitstream/handle/10852/34912/thesis-o...

Note that they also only mention MiniSat as a footnote, which is pretty bad. The relevant paper is at

http://minisat.se/downloads/MiniSat.pdf

All of these are great reads. Highly recommended.

Re: Announcing the first SHA-1 collision

#253

Post by tonfa »

Siecje wrote: post #157

Is Mercurial impacted?

Yes, as it uses a similar hashing scheme as git. https://www.mercurial-scm.org/wiki/FAQ#FAQ.2FTechnicalDetail...

That said the file format was switched pretty early on (2006 I think, less than a year after initial release) to reserve space for 32 bytes instead of 20 for the hash, thus allowing hash migration more easily (sha1 is 20 bytes, sha2 which at the time was the obvious replacement was 32 bytes). https://www.mercurial-scm.org/wiki/RevlogNG

Re: Announcing the first SHA-1 collision

#255

Post by jakob223 »

problems wrote: post #242
m3ta wrote: post #144

To put things into perspective, let the Bitcoin network hashrate (double SHA256 per second) = B and the number of SHA1 hashes calculated in shattered = G. B = 3,116,899,000,000,000,000 G = 9,223,372,036,854,775,808 Every three seconds the Bitcoin mining network brute-forces the same amount of hashes as Google did to perform this attack. Of course, the brute-force approach will always take longer than a strategic appr…

A few considerations though: - Google used GPUs, much of the Bitcoin network relies on fully custom ASICs now and mining without them isn't really profitable anymore - SHA1 hashes can also be computed over twice as fast as SHA256 even on GPUs, so if someone were to go out and build SHA1 ASICs, you could probably do this very, very fast. It's almost certain that intelligence agencies could invest this effort to say, b…

> say, break SHA1 SSL certs

Maybe, and probably, but probably not within the scope of this attack. This attack relies on being able to have a large similar prefix and a lot of control over further internal data; SSL certs are somewhat more constrainted.

Re: Announcing the first SHA-1 collision

#256

Post by AlexandrB »

amichal wrote: post #224

Linked http://shattered.io/ has two PDFs that render differently as examples. They indeed have same SHA-1 and are even the same size. $ls -l sha*.pdf -rw-r--r--@ 1 amichal staff 422435 Feb 23 10:01 shattered-1.pdf -rw-r--r--@ 1 amichal staff 422435 Feb 23 10:14 shattered-2.pdf $shasum -a 1 sha*.pdf 38762cf7f55934b34d179ae6a4c80cadccbb7f0a shattered-1.pdf 38762cf7f55934b34d179ae6a4c80cadccbb7f0a shattered-2.pdf Of cou…

As someone who knows only the very basics of cryptography - would verifying hashes of a file using SHA-1 and a "weak" hash function like MD5 provide any additional protection over just SHA-1? I.e. how much harder would be it be to create a collision in both SHA-1 and MD5 than in just SHA-1?

My common sense intuition is that it would be a lot harder, but I'm guessing theoretically/mathematically it's only a little bit harder given how easy collisions in MD5 are?

Re: Announcing the first SHA-1 collision

#257

Post by Ajedi32 »

Natanael_L wrote: post #191
Ajedi32 wrote: post #156

Earlier quoted context omitted.

Edit: Nevermind, I misinterpreted something in the report. Collisions between malicious and non-malicious documents are indeed most likely feasible. Original comment: While theoretically possible, I don't really see that particular attack as being an actual, practical problem anytime soon. In order for that to work not only would you have to find _a_ collision, but you'd have to find one with the additional constrain…

No, that's not the big problem. Every collision of this kind so far just requires a random looking section, and allows another section to be whatever you want. You can just swap out one file for malware.

Ah, sorry. I got confused by this section on shattered.it, which seemed to be saying that merely requiring a certain level of entropy in the resulting documents would be enough to mitigate the attack:

> Are TLS/SSL certificates at risk? [...] it is required that certificate authorities insert at least 20 bits of randomness inside the serial number field. If properly implemented this helps preventing a practical exploitation.

After giving it a bit more thought though, I realize now though that this mitigation actually works by preventing the attacker from fully controlling the hash of the first, non-malicious document.

Re: Announcing the first SHA-1 collision

#258

Post by JshWright »

ikeboy wrote: post #140

Someone just made about $2500 See https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013... and https://bitcoinchain.com/block_explorer/address/37k7toV1Nv4D...

That would offset a very, very tiny fraction of the cost of 56,940,000 CPU hours and 963,600 GPU hours.

Re: Announcing the first SHA-1 collision

#259

Post by anilgulecha »

kinkrtyavimoodh wrote: post #245
anilgulecha wrote: post #204

Earlier quoted context omitted.

No, each commit (or merge) is simply the SHA1 of the diff-patch. Thus adding the second file does create a diff, since the contents are not the same.

No, a commit is not the SHA-1 of the diff. The fundamental object model of Git does not store diffs, it stores the actual state of the source tree as represented by a commit. For instance, here's a commit file [1]— $ git cat-file -p fdf4fc3 tree d8329fc1cc938780ffdd9f94e0d364e0ea74f579 author Scott Chacon 1243040974 -0700 committer Scott Chacon 1243040974 -0700 first commit A commit object just points to the tree obj…

Correct -- I was being terse: the commit is a function of the changes going in (and metadata like time, authorship).

Details: https://gist.github.com/masak/2415865

Re: Announcing the first SHA-1 collision

#260

Post by jakob223 »

Natanael_L wrote: post #191
Ajedi32 wrote: post #156

Earlier quoted context omitted.

Edit: Nevermind, I misinterpreted something in the report. Collisions between malicious and non-malicious documents are indeed most likely feasible. Original comment: While theoretically possible, I don't really see that particular attack as being an actual, practical problem anytime soon. In order for that to work not only would you have to find _a_ collision, but you'd have to find one with the additional constrain…

No, that's not the big problem. Every collision of this kind so far just requires a random looking section, and allows another section to be whatever you want. You can just swap out one file for malware.

This attack requires both to be, in some sense, "random looking". i.e. you can't generate a collision for an arbitrary first text.
Post reply on HN