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

231–240 of 524 posts

Re: Announcing the first SHA-1 collision

#231

Post by runeks »

sp332 wrote: post #129
runeks wrote: post #115

Earlier quoted context omitted.

Not only that, BitTorrent also uses a Merkle tree of the torrent data split into pieces (e.g. 1 MB per piece), meaning you need to compute thousands of colliding hashes, with the added restriction that the data must be exactly the piece length. The torrent ID is the Merkle root hash, which is a hash of all the piece-hashes hashed together in a tree structure: https://i.stack.imgur.com/JVdvj.png

If you find a collision for the smallest piece, you don't need to find collisions for any higher nodes on the Merkle tree because you'll just be hashing the same values as the legit version.

Good point. It should be possible to create a video file that fills ups exactly the first n pieces, such that the last piece contains only the ambiguous data.

Re: Announcing the first SHA-1 collision

#233

Post by eneveu »

0x0 wrote: post #180

I'm trying to play with this in git. Added the first file, committed, and then overwrote the file with the second file and committed again. But even when cloning this repository into another directory, I'm still getting different files between commit 1 and 2. What does it take to trick git into thinking the files are the same? I half expected "git status" to say "no changes" after overwriting the first (committed) pd…

It's semi-relevant to your question, but if you want to learn more about Git internals, I recommend the last chapter of the "Pro Git" book, which is free:

https://git-scm.com/book/en/v2/Git-Internals-Plumbing-and-Po...

Re: Announcing the first SHA-1 collision

#234

Post by hatsunearu »

comboy wrote: post #154
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…

I wonder if SHA1 was used instead of SHA256 for Bitcoin mining, how much optimization these SHA1 discoveries would bring to the mining process (since it's more like partial brute forcing rather than finding collisions) i.e. what would be the percentage difference in the difficulty because of them - on the long run, since it takes some time to implement those things as ASICs.

>since it takes some time to implement those things as ASICs.

not really. it's just a few man-years to develop a kickass hdl and a lot of money and you're good to go. all bitcoin did was create a massive market for sha1 asics. i wonder if those asics can be used to reduce the 110 gpu-years down to a few asic-years?

Re: Announcing the first SHA-1 collision

#236

Post by amichal »

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…

The differing bytes are interesting

http://imgur.com/a/wI4xb

Re: Announcing the first SHA-1 collision

#237

Post by sktrdie »

Natanael_L wrote: post #198
sktrdie wrote: post #149

Earlier quoted context omitted.

But you can't control the data in the malware. It will be garbage.

They controlled the visual appearance of the different PDF files in the example. Why couldn't you inject malware instead?

Are you sure this isn't only possible because of the PDF file format? http://shattered.it/static/pdf_format.png

Hence shouldn't be possible for general malware.

Re: Announcing the first SHA-1 collision

#238

Post by consp »

simias wrote: post #219
0x0 wrote: post #201

Earlier quoted context omitted.

Why wouldn't the header be the same? The files have the same size and same name here? Does it have anything to do with zlib compression (I'd imagine the two files compress differently since they are actually different?)

Even if you use exactly the same headers it means that at the moment the SHA1 algorithm encounters the specially crafted data that creates the collision it's in a different state than with the "naked" files, so the collision (very probably) won't happen. Adding more content at the end of the file would work though, since at this point the SHA1 state machine would be in the same state on both sides. You can test that…

True, but the attack already builds upon modifying the state machine to get the same end result, creating data to allow for a specific prefix (e.g. always getting the desired intermediary state) should also be doable in some form of this attack.

Re: Announcing the first SHA-1 collision

#239

Post by compuguy »

ktta wrote: post #7

Here's a good blog about how SHA-1 works: http://www.metamorphosite.com/one-way-hash-encryption-sha1-d... . The biggest risk I see with this is how torrents are affected: https://en.wikipedia.org/wiki/Torrent_poisoning There's also a problem with git, but I don't see it being that as susceptible as torrents: http://stackoverflow.com/a/34599081/6448137

What about l2tp/ipsec? It can use sha-1.

Re: Announcing the first SHA-1 collision

#240

Post by saalweachter »

sktrdie wrote: post #207
Natanael_L wrote: post #198

Earlier quoted context omitted.

They controlled the visual appearance of the different PDF files in the example. Why couldn't you inject malware instead?

Because controlling the visual appearance would change the data of the PDF, hence change the underlying hash.

Non-coding regions.

Not every part of a file codes for its apparent output. Comments, symbol names, whitespace, color tables... for most file formats, there are countless variations of the bytes on disk which produce outputs which are visually indistinguishable.

The trick is to identify this space in a way that lets you efficiently iterate through it until you find a version which matches the target hash.

Post reply on HN