Announcing the first SHA-1 collision • Hacker News Board

Re: Announcing the first SHA-1 collision

#161

Post by agentgt » Thu, Feb 23, 2017, 2:36 PM UTC

anilgulecha wrote: post #33

Big things affected: * DHT/torrent hashes - A group of malicious peers could serve malware for a given hash. * Git - A commit may be replaced by another without affecting the following commits. * PGP/GPG -- Any old keys still in use. (New keys do not use SHA1.) * Distribution software checksum. SHA1 is the most common digest provided (even MD5 for many). Edit: Yes, I understand this is a collision attack. But yes, it…

> * PGP/GPG -- Any old keys still in use. (New keys do not use SHA1.)

> * Distribution software checksum. SHA1 is the most common digest provided (even MD5 for many).

Software distribution seems to be the greatest threat (e.g. a Maven repository or Debian repository).

It still seems like an enormous amount of work. You would have to go after a package with an old PGP key and then I guess go spoof a mirror (most of these guys already use SSL so that is a problem). There are probably easier and far more cost effective attack vectors.

Re: Announcing the first SHA-1 collision

#162

Post by inetknght » Thu, Feb 23, 2017, 2:37 PM UTC

yAnonymous wrote: post #136

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…

>This will mess up torrent sharing websites in a hurry. I doubt it. Should this ever become a problem, it would be trivial to change the hashing algorithm. Not worth the effort.

How do you propose to ensure backwards compatibility with the millions of torrents already produced?

Re: Announcing the first SHA-1 collision

#163

Post by stordoff » Thu, Feb 23, 2017, 2:39 PM UTC

prefect42 wrote: post #58

milge wrote: post #29

Earlier quoted context omitted.

Probably peanuts to any 3 letter government agency.

71 device years, on an p2.16xlarge instance, I think the NSA could certainly come up with something way moar better in a shorter timeframe, assuming they haven't already done so.

> The time needed for a homogeneous cluster to produce the collision would then have been of 114 K20-years, 95 K40-years or 71 K80-years

If I'm reading that correctly, 852 (71 * 12) K80 cards gets that down to a month, which sounds well within the reach of NSA et al.

Even getting it down to a day (71 * 12 * 30=25,560 cards) seems feasible. Assuming $10k per card ($5k launch price + doubled to account for supporting hardware), the upfront investment is around $0.25 billion, a figure that sounds plausible given, e.g., that the Utah data centre is budgeted at around $2 billion.

Edit: formatting fix. Also, this is of course assuming custom hardware designed for a specific hash function isn't employed.

Re: Announcing the first SHA-1 collision

#164

Post by sah2ed » Thu, Feb 23, 2017, 2:39 PM UTC

> "Today, 10 years after of SHA-1 was first introduced, ..."

That part from the original article seems to be missing something?

Re: Announcing the first SHA-1 collision

#165

Post by anilgulecha » Thu, Feb 23, 2017, 2:39 PM UTC

koolba wrote: post #81

anilgulecha wrote: post #77

Earlier quoted context omitted.

The initial torrent metadata is pulled from nothing but the first hash. This is the point where the rest of the data forks.. someone gets the movie, another gets the .exe.

That's not an issue with the torrent. That would be with the magnet link format. Also, and more importantly, this isn't a preimage attack so replacing an existing torrent's SHA-1 hash with a malicious one isn't computational possible.

Magnet URI hash is SHA1.

A hash collision can still be used as an attack if you create 2 torrents with the same hash and then distribute.

Re: Announcing the first SHA-1 collision

#166

Post by Aissen » Thu, Feb 23, 2017, 2:39 PM UTC

I love the fact that there is a tool for detecting any collision using this algorithm: https://github.com/cr-marcstevens/sha1collisiondetection

and it's super effective: The possibility of false positives can be neglected as the probability is smaller than 2^-90.

It's also interesting that this attack is from the same author that detected that Flame (the nation-state virus) was signed using an unknown collision algorithm on MD5 (cited in the shattered paper introduction).

Re: Announcing the first SHA-1 collision

#167

Post by MayeulC » Thu, Feb 23, 2017, 2:40 PM UTC

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.

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 recall that md5 operates on 512 bit chuncks (padded if necessary), and takes the result to seed the next computation. So, with md5 (if I recall correctly, still), the attack could work if each part of the torrent was a multiple of 512 bits, Merkel or not, and regardless of the base. Of course, you cannot change the whole torrent in that case, as it would be prohibitively expensive. And you still have to keep the same file size.

I would love to hear a bit more on the topic from someone more knowledgeable about hashes and torrents.

Re: Announcing the first SHA-1 collision

#168

Post by pacaro » Thu, Feb 23, 2017, 2:41 PM UTC

tejohnso wrote: post #40

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?

Linus' answer: http://marc.info/?l=git&m=115678778717621&w=2 tl;dr it's a non-issue

No.

Linus' answer is correct, as far as it goes, but the threats he considers are only a subset of the real problems.

Laying aside the fact that this attack isn't the one you need to attack a hit repo, and recognizing that the theoretical weakness of SHA-1 (that has been known since (IIRC) before the conception of git) has now become a practical weakness

If an attacker can forge an arbitrary part of a git tree, then if they can poison an upstream repo (we are presuming a motivated attacker given the costs involved), then they can undetectably compromise anyone downstream that clones the repo.

Linus describes in 2006 a trust model where you don't trust remote repos more than your local repo. This isn't how git is used by most users today

Re: Announcing the first SHA-1 collision

#169

Post by Aissen » Thu, Feb 23, 2017, 2:41 PM UTC

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.

Then this smallest piece must also change the file type to an executable, and contain a meaningful payload.

Re: Announcing the first SHA-1 collision

#170

Post by dcosson » Thu, Feb 23, 2017, 2:42 PM UTC

svantana wrote: post #151

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…

Interesting premise, some objections: 1) wouldn't search time be proportional to file size for hashes? These guys worked on 400kb pdf's, while most popular torrent content is in the GB range 2) Wouldn't this only work for users that got the entire file from you? fileA and fileB may have the same hash, but some random portions from each will have a different hash.

You could replace a single chunk with your malware. Then it could be any size and the rest of the chunks could be the legit content. I don't know much about video codecs, but this assumes there's some way to break out of the playback and run your malicious code. Maybe a buffer overflow, or maybe if your malware is the first chunk of the file you could get it to run first somehow before the video?

Or even better, torrents of apps sometimes come with an executable that you run to crack the DRM (so I hear). You could swap that out undetected, and you can probably also convince people they have to run it with sudo.