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

201–210 of 524 posts

Re: Announcing the first SHA-1 collision

#201

Post by 0x0 »

hannob wrote: post #194
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…

Git stores the files as so-called blob objects, they're prefixed with a simple header. So even if sha1(file1)==sha1(file2), your git will still get different hashes, because it's doing sha1(prefix+file1), sha1(prefix+file2). You'd need a file that collides with this prefix. This is certainly possible, but not sure if it may mean you need to pay for that several thousand cpu/gpu cluster google used to make it feasible…

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

Re: Announcing the first SHA-1 collision

#202

Post by vorticalbox »

mabbo wrote: post #74

One practical attack using this: create a torrent of some highly desirable content- the latest hot TV show in high def or whatever. Make two copies, one that is malware free, another that isn't. Release the clean one and let it spread for a day or two. Then join the torrent, but spread the malware-hosting version. Checksums would all check out, other users would be reporting that it's the real thing, but now you've g…

It's would more profitable to just develop undetectable malware and spread that from the start.

Re: Announcing the first SHA-1 collision

#204

Post by anilgulecha »

0x0 wrote: post #193
anilgulecha wrote: post #185

Earlier quoted context omitted.

That's not the attack on git -- it's the commit ID. You can have two patches that have the same commit. Apply one now, and in the future replace it with the second one, without affecting any other commits IDs afterwards.

But I thought files in git were also identified by the sha1 of their contents? Why isn't there a conflict/de-duplication happening when committing one file over the other? I must be misunderstanding something, but I thought the commit points to a hash of a tree (file list) which has a list of blobs (file referenced by their sha1 sum), how does it know which of the two pdf file blobs to pick out of the blob store?

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.

Re: Announcing the first SHA-1 collision

#205

Post by drzaiusapelord »

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…

Well, certainly there's a lot of work that can be done by a computer network that spans what? 500+k computers all pegging their many cpu/gpu/asic processors at 100% 24/7. The bitcoin network, if seen as one processing unit, is history's most powerful computer. Of course it can punch out difficult work quickly. That doesn't mean your average Russian hacker can.

Of course this cuts both ways, we'll probably be seeing ASIC's designed just for this work that'll vastly cut down how much time is required to make these collisions.

Also, I find it impressive SHA-1 lasted 10 years. Think about all our advances in that time from both a hardware and cryptographic perspective. A decade of life in the cryptospace should be seen as a win, not a loss. I'm not sure why we thought these things would last forever. If anything, the cryptospace is faster moving now than ever. The concept of a decades long standard like we had with DES or AES is probably never going to happen again.

Re: Announcing the first SHA-1 collision

#206

Post by Pigo »

Ajedi32 wrote: post #156
mabbo wrote: post #74

One practical attack using this: create a torrent of some highly desirable content- the latest hot TV show in high def or whatever. Make two copies, one that is malware free, another that isn't. Release the clean one and let it spread for a day or two. Then join the torrent, but spread the malware-hosting version. Checksums would all check out, other users would be reporting that it's the real thing, but now you've g…

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…

I really don't see why anyone would go through all this trouble when you can still just put Star_Wars_XIII.exe out there and get 10k downloads.

Re: Announcing the first SHA-1 collision

#207

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?

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

Re: Announcing the first SHA-1 collision

#208

Post by Bartweiss »

espadrine wrote: post #110
mabbo wrote: post #74

One practical attack using this: create a torrent of some highly desirable content- the latest hot TV show in high def or whatever. Make two copies, one that is malware free, another that isn't. Release the clean one and let it spread for a day or two. Then join the torrent, but spread the malware-hosting version. Checksums would all check out, other users would be reporting that it's the real thing, but now you've g…

> the latest hot TV show in high def or whatever Since it takes 6,500 CPU years and 110 GPU years, it won't quite be the latest show, unless you have really deep pockets. There are way less costly ways to make money illegally using simpler vulnerabilities or by being a pay-to-use DDoS provider.

Realistically, the closest low-cost attack is to just upload a malware-laden torrent of the latest TV show and not even pretend. It won't get seeded as widely, but you can do the same thing again next week.

Re: Announcing the first SHA-1 collision

#209

Post by OJFord »

giovannibajo1 wrote: post #20
koolba wrote: post #11

What's the impact to something like git that makes extensive use of SHA-1? In their example they've created two PDFs with the same SHA-1. Could I replace the blob in a git repo with the "bad" version of a file if it matches the SHA-1?

This is not a pre-image attack, so you can't create a file that matches an existing SHA1. It's a collision attack, so you can create two files whose SHA1 is the same. So what I could potentially do (given a multi-million dollar budget) is create from scratch two git repositories with different content, whose HEAD is the same. This would allow me to serve different repositories to different users. What is currently st…

> What is currently still not feasible is to create a custom git repository whose HEAD matches that of the Linux kernel.

Hang on, that doesn't matter though, does it?

I was under the impression that git's SHAs were to be treated as repo-wise unique; not universally. There must non-adversarial 'collisions' across repositories already, surely?

I thought this attack potentially allows creating two commits in the same repo with the same hash - although it may only be possible for these to be root commits.

Re: Announcing the first SHA-1 collision

#210

Post by the8472 »

MayeulC wrote: post #167
sp332 wrote: post #129

Earlier quoted context omitted.

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.

I don't know enough specifics about sha-1 or bit torrent, but it would seem to me that it depends on the data that is chosen for the base ("leaves") of the tree: if it just consists in taking the hashes, concatenating them, and move higher until you only have one hash, then yes. However, if the data itself is concatenated for the first step, that might not be the case (depending on the sha-1 algorithm). I seem to rec…

The process is fairly simple. Files are concatenated and that blob is then chunked into multiple-of-16KiB-sized pieces. Each piece is hashed. The hashes are concatenated and embedded as string in the torrent file. Then a specific subdictionary of the torrent file including the piece hashes, filenames and the length of the data is hashed to yield the infohash.

Magnets only convey the infohash. .torrent files convey the whole metadata, including the pieces hash string.

Post reply on HN