It&#x27;s not used as a security feature in Git (though SHA-1 is designed as a cryptographically secure hash) but Git commit singing does use SHA-1 b&#x2F;c GPG.

Let me know if you want to help- Ive just forked a couple repos and started writing out some notes

Funny, just yesterday I thought about what would be necessary to change and deploy this. Apparently the SHA1 hash wasn&#x27;t designed as a security feature, but I would not be surprised if it is being abused as one today.

So good timing to have just started working on a sha3 version of git I guess...

So... you are saying I couldn&#x27;t do this on my Macbook&#x27;s Core i7?

Hm, according to <a href="https:&#x2F;&#x2F;gist.github.com&#x2F;epixoip&#x2F;a83d38f412b4737e99bbef804a270c40" rel="nofollow">https:&#x2F;&#x2F;gist.github.com&#x2F;epixoip&#x2F;a83d38f412b4737e99bbef804a27...</a> 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.

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.

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

<a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=13713603" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=13713603</a>

EDIT: My original comment was wrong. Git commit signing apparently only signs the commit hash itself, so it&#x27;s only as trustworthy as the integrity of the hash. However, see also other comments which point out that this isn&#x27;t a pre-image attack; you can&#x27;t find a collision for a given thing (in this case, the linux kernel); rather, you can generate from scratch two pieces of data which happen to collide. Still, this is worrying.ORIGINALLY (INCORRECT): Git commit hashes were at least never intended as a form of authentication. That&#x27;s why git has commit signing. That said, they list GPG signatures as one of the things affected by SHA1 brokenness, so maybe even that&#x27;s not enough? I don&#x27;t know enough about how git commit signing or GPG works to tell.

Accidental collisions are still unlikely, it loses SHA1&#x27;s &quot;security&quot; properties though. <a href="http:&#x2F;&#x2F;www.monotone.ca&#x2F;docs&#x2F;Hash-Integrity.html#Hash-Integrity" rel="nofollow">http:&#x2F;&#x2F;www.monotone.ca&#x2F;docs&#x2F;Hash-Integrity.html#Hash-Integri...</a> goes in some detail for a different (older) DSCM, but same issue.

What about git?This makes it technically possible to get a backdoored linux repo with the same commit hash.EDIT: this is wrong, it&#x27;s not a second pre-image attack only a collision attack. That is, you can create 2 git repositories with the same commit hash, but not a git repo that matches an already existing repo. In other words, you can create 2 things with the same hash, but can&#x27;t control what that hash actually is.You might be able to fashion 2 commits to the linux repo with the same hash but a different modification though.

Bittorrent is not a static&#x2F;unchanged old protocol. It has constantly evolved to keep up with any attacks that could be mounted on it&#x27;s distributed nature.I&#x27;m sure a BEP will also come up, and speedtracked on the back of this news.

&gt;torrentsGood, if something stronger and better comes out it&#x27;ll still be a win.

Malware infecting a few hundred beefy-gpu PCs isn&#x27;t implausible.

&quot;That said, attacks only get better&quot;In the case of MD5 collision research, initially it took a cluster of PS4 months to find one. But a few years later a laptop can find a collision instantaneously. So yeah, expect rapid improvement of SHA1 collision feasibility.

I don&#x27;t think we&#x27;re likely to see it used for torrent poisoning if it takes 110 GPUs 1 year to compute a collision - the electricity costs for such a rig would be enormous. 110 GPUs * about 300 W each = about 290 thousand kilowatt hours to break. Electricity costs of at least 10s of thousands of dollars. For a single torrent. You better be damn confident that those torrenters are going to go buy your product and that they won&#x27;t just go to the next torrent down the list.That said, attacks only get better, so it could happen at some point in the future and it&#x27;s probably worth switching the hash function used sooner rather than later.

What about l2tp&#x2F;ipsec? It can use sha-1.

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

Great question... Can anyone answer this? Seems ripe for exploitation.

Previous brute forcing efforts [1] have fiddled with commit and author timestamps.If you had seven commits, and two timestamps per commit, and each timestamp could be fudged by 90 minutes without detection, you might not need any dummy comments or files at all.[1] <a href="https:&#x2F;&#x2F;github.com&#x2F;bradfitz&#x2F;gitbrute" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;bradfitz&#x2F;gitbrute</a>

It&#x27;s probably doable, but your commit will be huge with a lot of comments or dummy files to make the collision possible.

The shattered site explicitly singles out git as at risk.

&gt; What is currently still not feasible is to create a custom git repository whose HEAD matches that of the Linux kernel.I&#x27;m not convinced that&#x27;s good enough.In git, the SHA1 is always the hash of a gzip, which is subject to tricks[1] where a header might be prepared and then some padding inserted to collide a malicious tail.[1]: <a href="http:&#x2F;&#x2F;swtch.com&#x2F;r.zip" rel="nofollow">http:&#x2F;&#x2F;swtch.com&#x2F;r.zip</a>

&gt; 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&#x27;t matter though, does it?I was under the impression that git&#x27;s SHAs were to be treated as repo-wise unique; not universally. There must non-adversarial &#x27;collisions&#x27; 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.

This is not a pre-image attack, so you can&#x27;t create a file that matches an existing SHA1. It&#x27;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 still not feasible is to create a custom git repository whose HEAD matches that of the Linux kernel.See also: <a href="http:&#x2F;&#x2F;crypto.stackexchange.com&#x2F;questions&#x2F;1173&#x2F;what-are-preimage-resistance-and-collision-resistance-and-how-can-the-lack-ther" rel="nofollow">http:&#x2F;&#x2F;crypto.stackexchange.com&#x2F;questions&#x2F;1173&#x2F;what-are-prei...</a>

Circa 870,000 USD using AWS p2.xlarge instances.edit.: they seem to quote 560k, I overlooked using both the CPUs and the GPUs.

There&#x27;s a good explanation here:<a href="http:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;34599081&#x2F;6448137" rel="nofollow">http:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;34599081&#x2F;6448137</a>

Read the &#x27;whole&#x27; [not that big] page. The explanation is there, in short: yes.&gt;How is GIT affected?
GIT strongly relies on SHA-1 for the identification and integrity checking of all file objects and commits. It is essentially possible to create two GIT repositories with the same head commit hash and different contents, say a benign source code and a backdoored one. An attacker could potentially selectively serve either repository to targeted users. This will require attackers to compute their own collision.

No.Linus&#x27; 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&#x27;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 weaknessIf 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&#x27;t trust remote repos more than your local repo. This isn&#x27;t how git is used by most users today

Linus&#x27; answer: <a href="http:&#x2F;&#x2F;marc.info&#x2F;?l=git&amp;m=115678778717621&amp;w=2" rel="nofollow">http:&#x2F;&#x2F;marc.info&#x2F;?l=git&amp;m=115678778717621&amp;w=2</a>tl;dr it&#x27;s a non-issue

By design, in case of a collision the new version will not replace the old (older version has preference in case of a collision). Not sure if you could somehow fiddle with the meaning of old and new from the systems POV though.

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

Thank you. It took me a while to realize that the paper you&#x27;re citing is not directly linked in the Google blog article. It is actually found at shattered.io:<a href="http:&#x2F;&#x2F;shattered.io&#x2F;static&#x2F;shattered.pdf" rel="nofollow">http:&#x2F;&#x2F;shattered.io&#x2F;static&#x2F;shattered.pdf</a>

The PDF says:&gt; Using a p2.16xlarge instance, featuring
16 K80 GPUs and nominally costing US 14.4 per hour would cost US 560 K for the necessary 71 device years

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&#x27;t already done so.

Probably peanuts to any 3 letter government agency.

With depreciation over a year, that falls to a USD 100k investment per attack; if realistic to depreciate over 3 years, that falls to USD 30k per replication.  Not so expensive on these terms.

&gt;There isn&#x27;t anything new about this result actually, Google just set aside the necessary resources to demonstrate it.I think that was the point. Google wanted to show that anyone with sufficient resources could easily pull this off.

Say you want to replicate this in 1 month, you need 1320 GPUs for a month. They didn&#x27;t specify which ones, but say at 1000 bucks per GPU, that&#x27;s a 1.3M USD investment. And some pocket change for power etc.There isn&#x27;t anything new about this result actually, Google just set aside the necessary resources to demonstrate it.

I wonder if this is really the case.Because if we can drive storage costs much closer to zero (e.g.: a beefed up local server), we can keep storing hashes and the next collision should be much closer. Starting and stopping and throwing away the previous work does work out to $560K per collision, but doesn&#x27;t it just keep getting cheaper if you keep going?

Eh, at that point you may as well buy the servers yourself and let them run on-premises. Even with power, etc. that cost could easily come down 50% or more. Once you own the servers, additional tasks just cost power.

They provide an estimate in their paper:&gt; The monetary cost of computing the second block of the&gt; attack by renting Amazon instances can be estimated from&gt; these various data. Using a p2.16xlarge instance,&gt; featuring 16 K80 GPUs and nominally costing&gt; US$ 14.4 per hour would cost US$ 560 K for the&gt; necessary 71 device years. It would be more economical&gt; for a patient attacker to wait for low “spot prices” of&gt; the smaller g2.8xlarge instances, which feature four K520&gt; GPUs, roughly equivalent to a K40 or a GTX 970. Assuming&gt; thusly an effort of 100 device years, and a typical spot&gt; price of US$ 0.5 per hour, the overall cost would be of&gt; US$ 110 K.

Probably nothing, because they&#x27;ll just used compromised aws keys to spin up instances for free.

&gt;Nine quintillion computations; 6,500 years of CPU; 110 years of GPUIs there a rough calculation in terms of today&#x27;s $$$ cost to implement the attack?

Maybe just writing 2^63 would have been easier to interpret than that huge number in the context of cryptography. (Unless you assume this targets a non-technical audience, which I doubt.)Pretty impressive, though. And worrying, because if Google can do it, you know that state-level actors have been probably doing it for some time now (if only by throwing even more computing power at the problem).

You haven&#x27;t seen my collection of cat pics torrent ;)Also from a more serious stance the danger is the malware vector or the destruction of the ability to have integrity and not the data in the torrent itself.

i can imagine the torrent thing to be worth the $100k per collision.

Create 2 torrents with the same hash.Release one into the wild.Wait.Infect.

It was broken 12 years ago, so no serious software that require cryptographically secure hash functions should use it.

anilgulecha is correct. Consider the following attack:You wish to undermine the security of an important codebase managed by git.You write a valuable and useful contribution to the code. You also create another version of the commit that has the same SHA-1 as the first, which breaks the security of that code.You submit the first commit, it is accepted and merged.Now you wait for your target to do a git clone on the repository, perhaps because it&#x27;s a build environment. You then MITM it (e.g. using infrastructure like QUANTUM INSERT) and redirect the clone to your own git server, which serves the bad commit.The target compares the top commit hashes of what it expected to get and what it actually got, and is none the wiser. They now compile the code and produce a backdoored binary.

None of what you mentioned is affected since this is a collision attack. They purposely created 2 files with the same hash.Creating a file with the same hash as legit file is a preimage attack and is much more difficult to perform (many orders of magnitude more difficult).This still doesn&#x27;t mean that SHA-1 isn&#x27;t dogshit however. It should have been phased out years ago.

Correct, and if you have 2 images that have the same hash, you can serve one or the other at different times. This is the attack.

&gt;* Distribution software checksum. SHA1 is the most common digest provided (even MD5 for many).Maybe I&#x27;m mistaken, but isn&#x27;t the purpose of those mainly to verify that you&#x27;ve downloaded the file correctly? At least, the use of MD5 suggests that this is the case.

PGP V4 key fingerprints still use SHA-1 exclusively. There hasn&#x27;t been an update to this part of the RFC as far as I know [1]. Collisions where both preimages are of the attacker&#x27;s choosing matter less in this context, but who knows what clever attacks people can come up with.[1] <a href="https:&#x2F;&#x2F;tools.ietf.org&#x2F;html&#x2F;rfc4880#page-71" rel="nofollow">https:&#x2F;&#x2F;tools.ietf.org&#x2F;html&#x2F;rfc4880#page-71</a>

&gt; * PGP&#x2F;GPG -- Any old keys still in use. (New keys do not use SHA1.)&gt; * 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.

Big things affected:* DHT&#x2F;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&#x2F;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&#x27;s still a attack vector as 2 same blocks can be generated now, with one published, widely deployed (torrent&#x2F;git), and then replaced at a later date.

Excellent.More generally, there is this fantastic repo on github that lists a bunch of such things that can be tweaked in about:config (mostly from a security&#x2F;privacy standpoint):
<a href="https:&#x2F;&#x2F;github.com&#x2F;pyllyukko&#x2F;user.js" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;pyllyukko&#x2F;user.js</a>

Why chance with Firefox?    Google has Chrome already safe and clearly on top of things.   This is not a static thing as in there will be others with parts of the crypto tool chain or maybe stack?

&gt; If you use Chrome, you will be automatically protected from insecure TLS&#x2F;SSL certificates, and Firefox has this feature planned for early 2017.No need to wait. The option to reject SHA-1 certificates on Firefox is `security.pki.sha1_enforcement_level` with value `1`.<a href="https:&#x2F;&#x2F;blog.mozilla.org&#x2F;security&#x2F;2016&#x2F;01&#x2F;06&#x2F;man-in-the-middle-interfering-with-increased-security&#x2F;" rel="nofollow">https:&#x2F;&#x2F;blog.mozilla.org&#x2F;security&#x2F;2016&#x2F;01&#x2F;06&#x2F;man-in-the-midd...</a>Other configs worth doing:`security.ssl.treat_unsafe_negotiation_as_broken` to `true` and `security.ssl.require_safe_negotiation` to `true` also. Refusing insecure algorithms (`security.ssl3.&lt;alg&gt;`) might also be smart.

SHA1 use cases are not limited into integrity verification of documents, but used a lot for traffic integrity and generation of authentication codes:- Torrents of all kinds.
- Version control systems (where ability attacks like displacing release pointers become easier). 
- IpSec, SSH, PGP and a number of other protected data exchange systems.Being able to subvert integrity guarantees is a nice building block for complicated man-in-the-middle attacks.

There are many areas of security where you can genuinely get by with obfuscation, hoping the attacker looks elsewhere, or general security-through-obscurity.You can&#x27;t in crypto. When the entire system relies on an axiom being true, you need to make sure it&#x27;s true. The attacks are only going to get better. The attacks are going to come from the future. The embedded systems will not be replaced in time.

Computing a collision today costs about $100K from my reading of the paper. So most uses of SHA1 are protecting documents of far lower value, and would not be likely attack targets (today).

Saying it was shown to be flawed is being nice. It was outright broken 12 years ago as it was shown that you could find collisions with far less complexity that a bruteforce attack.What has happened is that someone created the code to actually carry out an attack, and showed that it will cost around $110K today.

Right, the Wikipedia page for SHA1 does show research on a variety of possible attacks, starting from 2005.

SHA1 was shown to be flawed in 2005. That&#x27;s more than 30 days ago.

The article states 90 days.&gt; we will wait 90 days before releasing code that allows anyone to create a pair of PDFs that hash to the same SHA-1 sum given two distinct images with some pre-conditions

I may have misread, but I thought from the article they said that the period would be 90 days before the release?

git does some other funky things, usually it just uses the pre-existing object, or crashing<a href="http:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;9392525" rel="nofollow">http:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;9392525</a>It might change, but the response could quite likely be a stubborn &quot;I said no before, so I&#x27;ll say no now&quot;- - -This attack has been known since 2013, that is a really long disclosure time (the main thing today is proving that the attack isn&#x27;t theoretical)

Is a 30 day disclosure period really enough for something like this? It&#x27;s obviously not possible to &#x27;fix&#x27; big systems that rely on SHA-1 such as git or github in only 30 days. Hardware devices that use SHA-1 as a base for authenticating firmware updates?

The two private keys need not be the same; if their corresponding public keys both hash to the same value, a signature from either private key is acceptable.

The method presented works only with data formats where you can add section of &#x27;calculated junk&#x27; into the data.Public key can&#x27;t contain junk and work, so I don&#x27;t see how this method would work.

About tor: if an attacker produces a public key that collides with the SHA-1 hash of someone else&#x27;s hidden service, then he would still need to generate the corresponding RSA-1024 private key, which is infeasible as of today.Is this correct?

If they MPAA could subvert torrents of their property and and replace sections of the footage with just warnings (ruinning the download) i would find that much less objectionable than DRM.Frustrate the people pirating instead of punishing everyone else.

It&#x27;ll only work for a few days&#x2F;months after people start noticing it.

To be honest this is a lovely evil plan. cough MPAA cough

You could replace the video by an executable probably, I&#x27;m sure many users would launch it, especially if the source of the torrent is &quot;reputable&quot; and with positive comments.Alternatively you could exploit a vulnerability in a codec library or something similar.

You could have a buffer overflow attack talking advantage of a specific popular video player out there.Since video players are usually not very security focused, someone determined could do it.And since video torrents are unzipped, a single chunk can be replaced with the malicious chunk with the attack code. It can look like a tiny jitter depending on the chunk size&#x2F;total video size.

It can use buffer overflow (which is often easier than it looks in a large codebase written with memory unsafe languages) to execute arbitrary code. Modern OS have protections from such attack vectors, but they are not sufficient enough and well-funded attacker can bypass them.

There is&#x2F;was this: <a href="https:&#x2F;&#x2F;arstechnica.com&#x2F;security&#x2F;2016&#x2F;11&#x2F;elegant-0day-unicorn-underscores-serious-concerns-about-linux-security&#x2F;" rel="nofollow">https:&#x2F;&#x2F;arstechnica.com&#x2F;security&#x2F;2016&#x2F;11&#x2F;elegant-0day-unicor...</a>

Plenty of people download executables on BitTorrent too, so it&#x27;d be easier just to target that.  Go inject your malware into a popular torrent for pirating the latest version of Photoshop, or Windows, or a popular game.

With a buffer overflow. Video players are supposedly pretty vulnerable to these kinds of attacks since they need to deal with many different types of media, which means there is quite a large attack surface and they have to accept all kinds of odd video files.There&#x27;s a book called &quot;A Bug Hunters Diary&quot; that explained this exact thing in a video played using a particular version of VLC. Quite far over my head how he did it but it was interesting to read.see <a href="http:&#x2F;&#x2F;www.trapkit.de&#x2F;books&#x2F;bhd&#x2F;en.html#videos" rel="nofollow">http:&#x2F;&#x2F;www.trapkit.de&#x2F;books&#x2F;bhd&#x2F;en.html#videos</a> (Chapter 2 — Back to the 90s)Demonstration Videos of the exploit at <a href="http:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=qSyLkglLX-c&amp;fmt=22" rel="nofollow">http:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=qSyLkglLX-c&amp;fmt=22</a> and <a href="http:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=5ZbX9zfnTuI&amp;fmt=22" rel="nofollow">http:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=5ZbX9zfnTuI&amp;fmt=22</a>

Malware in a video? Is that possible? How does it work?

Wouldn&#x27;t that make the attack easier, since you just have to manufacture a pair of pieces with the same hash, instead of having to make the whole file have the same hash?

Does bt have checksums for pieces and files? I thought it was only pieces.

Okay, so the challenge gets broken down into creating a single piece that hides the malware. Even better really, I can join the network with a fleet of hosts all sharing that particular piece at a very high rate- but it&#x27;s my bad version of it. Those hosts can focus on just distributing the malware, rather than the whole file.

this isn&#x27;t quite true, bittorrent have checksums for each piece in the torrent, I not saying its impossible to do but its significantly harder than just finding 2 files with the same hash.

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: <a href="https:&#x2F;&#x2F;i.stack.imgur.com&#x2F;JVdvj.png" rel="nofollow">https:&#x2F;&#x2F;i.stack.imgur.com&#x2F;JVdvj.png</a>

Well, you really don&#x27;t need the complete file either. Since torrents are usually shared unzipped, they can just replace a chunk with a bad one (It varies usually from 256KB-2MB) and a single chunk can be replaced with a bad one embedded with malware to cause problems.Especially something like a buffer overflow attack on a video file.

I may be confusing p2p protocols, but doesn&#x27;t BitTorrent grab different chunks from different sources, so that if there are different people spreading different versions that are viewed as the same, people are going to mostly get either the original (and initially more common) version or broken junk that is a mix of the two versions?

Video files are purposely made to work even with some data blocks missing. It&#x27;s the feature that enables video streaming. Valid header is usually enough for video player to at least try to play a file.

I don&#x27;t actually know the in&#x27;s and out&#x27;s of BitTorrent structure but wouldn&#x27;t that not work as the 2 files would be completely different?ie: I&#x27;d be downloading (and putting together) some blocks of the &quot;real&quot; movie and some blocks of the &quot;malware&quot;. I&#x27;m guessing the resultant file wouldn&#x27;t even open?

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&#x27;t get seeded as widely, but you can do the same thing again next week.

&gt; the latest hot TV show in high def or whateverSince it takes 6,500 CPU years and 110 GPU years, it won&#x27;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.

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

&gt;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.

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

Your &quot;computable nonce&quot; can exist in an unimportant place of the binary. Such as an unused portion of .data

But you can&#x27;t control the data in the malware. It will be garbage.

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&#x27;t know much about video codecs, but this assumes there&#x27;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.

Interesting premise, some objections:1) wouldn&#x27;t search time be proportional to file size for hashes? These guys worked on 400kb pdf&#x27;s, while most popular torrent content is in the GB range2) Wouldn&#x27;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.

No, that&#x27;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.

I really don&#x27;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.

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&#x27;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&#x27;d have to find one with the additional constraints of &quot;one copy is malware free while the other isn&#x27;t&quot;, which would be significantly more difficult (at least, as I understand it).That said, I agree it&#x27;s probably time for torrents to start moving to another hash function. With time and additional research, it&#x27;s entirely possible that theoretical attacks like the one you described could eventually become practical.

It&#x27;s easier just to upload malware to a torrent site. Windows crack, let other people or botnet to download it and suckers will get your malware too. If AV complains, say that is an expected behavior.

It&#x27;s would more profitable to just develop undetectable malware and spread that from the start.

Well, it&#x27;s practical on a small scale. You could wait until a torrent has only 1-2 seeders, and then you can hope to give leechers all blocks of a file. Or, you could deliver a torrent with a 1GB installer (for some software package) and a 100kb keygen (which you replace with malware) fitting inside a 1MB block and you can be sure to spread that around regardless of the number of other seeders.

&gt;Edit: some people have pointed out some totally legitimate potential flaws in this idea. And they&#x27;re probably right, those may sink the entire scheme. But keep in mind that this is one idea off the top of my head, and I&#x27;m not any security expert.Well to be fair to those people, you started out saying its a practical attack when it wasn&#x27;t even a theoretical one.

It doesn&#x27;t have to be a new torrent. You could just join the swarm for an existing torrent and seed different data for selected parts of the torrent.

I wrote a small proof of concept here: <a href="https:&#x2F;&#x2F;github.com&#x2F;michaf&#x2F;shattered-torrent-poc" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;michaf&#x2F;shattered-torrent-poc</a>Both Installer.py and Installer-evil.py result in the same piece hashes, with piece size chosen as 512. The only difference between the files is the shattered pdf fragment, encapsulated in a variable. This fragment starts exactly at the piece boundary, resulting in identical hashes.

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&#x27;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&#x27;s the real thing, but now you&#x27;ve got 1000 people purposely downloading ransomware from you- and sharing it with others.Apparently it costs around $100,000 to compute the collisions, but so what? If I&#x27;ve got 10,000 installing my 1BTC-to-unlock ransomware, I&#x27;ll get a return on investment.This will mess up torrent sharing websites in a hurry.Edit: some people have pointed out some totally legitimate potential flaws in this idea. And they&#x27;re probably right, those may sink the entire scheme. But keep in mind that this is one idea off the top of my head, and I&#x27;m not any security expert. There&#x27;s plenty of actors out there who have more reasons and time to think up scarier ideas.The reality is, we need to very quickly stop trusting SHA1 for anything. And a lot of software is not ready to make that change overnight.

Schneier predicted &quot;between 2018--2021 depending on resources&quot;. He explicitly says &quot;Since this argument only takes into account commodity hardware and not [...] GPUs&quot;. Since Google used GPUs that very well explains the speedup to 2017.

[2012] Schneier - When Will We See Collisions for SHA-1?<a href="https:&#x2F;&#x2F;www.schneier.com&#x2F;blog&#x2F;archives&#x2F;2012&#x2F;10&#x2F;when_will_we_se.html" rel="nofollow">https:&#x2F;&#x2F;www.schneier.com&#x2F;blog&#x2F;archives&#x2F;2012&#x2F;10&#x2F;when_will_we_...</a>Pretty close in his estimation.

OTOH, 12 years of reliability from a checksum in the age of Moore&#x27;s law and quantum computers is pretty good, frankly.I don&#x27;t think they ever expected sha-1 to survive forever.

Git was released in 2005, 12 years ago, and it&#x27;s based around SHA-1. They&#x27;ve done a massive miscalculation there.

Looks like a typo. They might have been referring to sucessful cryptanalysis of SHA-1 which seems to have started around 2005 <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;SHA-1#Cryptanalysis_and_validation" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;SHA-1#Cryptanalysis_and_valida...</a> or maybe the BOINC project to create a collision, which did start 10 years ago.

&gt; &quot;10 years after of SHA-1 was first introduced&quot;wasn&#x27;t SHA-1 introduced in the 90&#x27;s?

As has already been mentioned, the digest of a torrent&#x27;s pieces is also checkedSource: my own crappy implementation of a BitTorrent client, e.g.: <a href="https:&#x2F;&#x2F;github.com&#x2F;charmeleon&#x2F;BitClient&#x2F;blob&#x2F;master&#x2F;src&#x2F;connection&#x2F;torrent.py#L84" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;charmeleon&#x2F;BitClient&#x2F;blob&#x2F;master&#x2F;src&#x2F;conn...</a>

wont an easy fix be to just hash it again with sha256? Sure that will take time to bake it into software, but wont they just be able to put a text label next to the description and say &quot;sha256: abc...123&quot; ?

You don&#x27;t really need to talk to anybody about this except people who torrent both illegal and legal torrents.Torrent poisoning is the most ripe for exploitation and the one with the highest return for a malicious attacker.So when you talk to someone who torrents, just tell them that the way the torrents verify a file is the correct one is no longer secure, and they have to keep an eye out for the next software update. And if anyone is paranoid, then stop downloading new torrent files, although there is no problem with seeding.Now that I think about it, I think it is crucial for everyone to keep seeding as much as they can, because it reduces the probability of a bad torrent chunk from spreading as much across the network.EDIT: Here&#x27;s a good article that isn&#x27;t very technical<a href="https:&#x2F;&#x2F;www.wired.com&#x2F;2017&#x2F;02&#x2F;common-cryptographic-tool-turns-majorly-insecure&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.wired.com&#x2F;2017&#x2F;02&#x2F;common-cryptographic-tool-turn...</a>

Google created a complicated and expensive method of undermining an integrity check, making that integrity check less safe to use. The method will get cheaper and easier to use, so systems using that integrity check have to be moved to integrity checks that are believed to be better.

Er, if I&#x27;m following your metaphor correctly, you seem to be implying that if I create something and &quot;seal&quot; it, then send it along, that you can no longer trust it because someone may have tampered with it. That is not an accurate assessment of this vulnerability. The attacker needs to construct both the &quot;good&quot; and the &quot;bad&quot; document in order for this to work.In non-technical terms I guess it&#x27;s more like getting a document notarized with an embossed stamp or something, and this vulnerability is something that allows you to create a special document where you can get the stamp to apply to two documents at the same time (maybe one of them could be a document accepting $100 inheritence, and the hidden one is a document signing over the title of your house).It&#x27;s a bit hard to explain why this matters because most people have no non-technical equivalent of the sort of thing that this would matter for, because people use fuzzy social proofs where forgery isn&#x27;t out of the question anyway (even notarized documents don&#x27;t really have any indication of the contents of the document, as far as I can tell).

&gt; How am I going to explain this to my wife?Someone has discovered a computational equivalent of bypassing tamper-proof seals, but only a specific brand of seals (SHA1) which is very currently popular. Other types of seals still work fine. This means we can no longer trust if the cake from the baker hasn&#x27;t been tampered with even though the packaging it comes in has an intact SHA1 seal, we should therefore demand that the baker start using SHA256 seals lest we get poisoned by the delivery boy who wants to steal the shiny PS4 he noticed the other day.Edit: perhaps delivery boy underplays how costly the attack currently is. Perhaps make the poisoner a person of means who wants inheritance money. As the attack costs go down, even delivery boys will start to afford it, multiplying the risk.

Google found a way to crack an algorithm designed to ensure the uniqueness of documents, allowing them to be forged. Although it&#x27;s expensive to do this, the price will fall, and it&#x27;s a good idea to retreat to a different algorithm that does the same thing but is so much more difficult to break that no one will be able to do so for many years.

One-way functions are not cryptographic hash functions, which have the three properties preimage resistance, second preimage resistance, and collision resistance.For example, say f(x) is a one-way function. Then defineg(0x) = f(x)g(1x) = f(x)Here given some z, it&#x27;s easy to find another z that maps to the same output, just flip the first bit. However, g is still a one-way function:Assume we could break g with non-negligible probability, that some program A(y) outputs x such that g(x) = y with probability p.Then say someone gives us q = f(a) for some a. We can compute A(q) that will either give us 1a or 0a by the definition of g with probability p. In either case we can discard the first bit to find the preimage for a. By contradiction, g is a one-way function.

&gt; How am I going to explain this to my wife?I don&#x27;t know. What&#x27;s your wife&#x27;s background? If she already knows what one-way functions are, you could just explain that we&#x27;ve found collisions for the first time in an old one-way function that was used for file authenticity but isn&#x27;t used much anymore because we knew ten years ago we were probably going to start finding collisions in it.If she doesn&#x27;t know what one-way functions are, it seems like something that could be explained with examples to an average person who was interested in learning?

For the general public, it&#x27;s easy:Some cryptography (everything that uses SHA-1) has been broken and we need to move on to a better scheme. Luckily, we did this years ago because we suspected it could be broken. But unfortunately some people are still using the old stuff so if they haven&#x27;t switched already they DEFINITELY need to switch now.If you are talking to the general public, the words &#x27;hash&#x27;, &#x27;one-way&#x27;, &#x27;function&#x27;, &#x27;trapdoor&#x27;, &#x27;collision&#x27; should not appear in your statement.

Assume there is a machine that is giving out unique numbers per person. If person A presses the button twice, they get the same number they got previously. If person B presses the button, they get a different unique number. Now, I searched for a long time to find a person who is not A, but will get the same unique number as A.So now your wife can agree that the machine does not provide unique numbers per person and is, thus, broken.

How am I going to explain this to my wife?Actually a serious question. How do we communicate something like this to the general public?

Would providing multiple SHA-1&#x27;s from both the whole and N subsections (or defined regions) of the byte stream make this impractical... or at this point is the cost just going to drop and make this not relevant?Like a NURBS based sudoku multi-hash...

Love this page. Someone should remind her to update the table for sha1 now.

I&#x27;m a programmer and I exhibit some of the column 3 behavior.

Heh, RIPEMD-160, forever under peer review :)

On a quick scroll of the comments, I haven&#x27;t seen this posted so far: <a href="http:&#x2F;&#x2F;valerieaurora.org&#x2F;hash.html" rel="nofollow">http:&#x2F;&#x2F;valerieaurora.org&#x2F;hash.html</a>We&#x27;re at the &quot;First collision found&quot; stage, where the programmer reaction is &quot;Gather around a co-worker&#x27;s computer, comparing the colliding inputs and running the hash function on them&quot;, and the non-expert reaction is &quot;Explain why a simple collision attack is still useless, it&#x27;s really the second pre-image attack that counts&quot;.

If we think that intentional collision is not a threat vector, while, as life shows, it is:
<a href="https:&#x2F;&#x2F;bugs.webkit.org&#x2F;show_bug.cgi?id=168774#c23" rel="nofollow">https:&#x2F;&#x2F;bugs.webkit.org&#x2F;show_bug.cgi?id=168774#c23</a>

Nothing: the risk of a fucked up rebase is still much higher than a hash collision.

Now I really wonder what will happen to Git we all know and love.

The person who collected it was most likely not a Google employee; just the first person to download those files who knew about the bounty.

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

Someone just made about $2500See <a href="https:&#x2F;&#x2F;lists.linuxfoundation.org&#x2F;pipermail&#x2F;bitcoin-dev&#x2F;2013-September&#x2F;003253.html" rel="nofollow">https:&#x2F;&#x2F;lists.linuxfoundation.org&#x2F;pipermail&#x2F;bitcoin-dev&#x2F;2013...</a> and <a href="https:&#x2F;&#x2F;bitcoinchain.com&#x2F;block_explorer&#x2F;address&#x2F;37k7toV1Nv4DfmQbmZ8KuZDQCYK9x5KpzP" rel="nofollow">https:&#x2F;&#x2F;bitcoinchain.com&#x2F;block_explorer&#x2F;address&#x2F;37k7toV1Nv4D...</a>

&gt;since it takes some time to implement those things as ASICs.not really. it&#x27;s just a few man-years to develop a kickass hdl and a lot of money and you&#x27;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?

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&#x27;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.

Give it a few years and your average Russian hacker with a handful of stolen credit cards will be able to buy enough VPS muscle to crack it.

Well, certainly there&#x27;s a lot of work that can be done by a computer network that spans what? 500+k computers all pegging their many cpu&#x2F;gpu&#x2F;asic processors at 100% 24&#x2F;7. The bitcoin network, if seen as one processing unit, is history&#x27;s most powerful computer. Of course it can punch out difficult work quickly. That doesn&#x27;t mean your average Russian hacker can.Of course this cuts both ways, we&#x27;ll probably be seeing ASIC&#x27;s designed just for this work that&#x27;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&#x27;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.

&gt; say, break SHA1 SSL certsMaybe, 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.

&gt; break SHA1 SSL certs.It&#x27;s not possible to break existing SHA1 certificates because this attack is to generate collisions, not finding preimages.

It&#x27;s almost certain that intelligence agencies could invest this effort to say, break SHA1 SSL certs.To the contrary, it is unlikely that they can do so.There is a world of difference between &quot;come up with two things that hash to the same value&quot; and &quot;come up with something that hashes to a particular known value&quot;. It gets harder still if you&#x27;re trying to add constraints about the format of your text (such as making them look like a potentially valid SSL cert).To illustrate the difference, suppose that you can constrain the algorithm to produce one of a trillion values. If you generate a million possibilities, odds are good that 2 of them will have the same hash value. You&#x27;ve generated a collision! But you need to do a million times as much work to have good odds of generating any particular value.That said, attacks only improve over time. While it is highly unlikely that intelligence agencies can break SHA1 certs today, it is extremely likely that they will eventually. Where eventually is 5-20 years.

A few considerations though:- Google used GPUs, much of the Bitcoin network relies on fully custom ASICs now and mining without them isn&#x27;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&#x27;s almost certain that intelligence agencies could invest this effort to say, break SHA1 SSL certs.

It certainly raises an interesting question. The go-to response when anybody discusses brute forcing bitcoin is that the sheer number of possibilities makes finding a collision infinitesimally small. And that&#x27;s true. Same for .onion certificates.But Google certainly haven&#x27;t been attacking this for the last 6,500 years. With a sufficiently obscene amount of resources, it IS feasible to create an index of every possible public&#x2F;private keypair. It&#x27;s not profitable to do so just for the purpose of plundering bitcoin wallets, but if you&#x27;re a government doing it for other reasons, it might be worthwhile.

This says more about the Bitcoin network than it does about the ease with which one can create a SHA-1 collision.From the article:Nine quintillion (9,223,372,036,854,775,808) SHA1 computations in total.6,500 years of CPU computation for 1st phase of attack.110 years of GPU computation for 2nd phase of attack.

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,000G = 9,223,372,036,854,775,808Every 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 approach; this comment is only meant to put into perspective the sheer number of hashes calculated.

The newest SHA members are based on sponge functions. <a href="http:&#x2F;&#x2F;keccak.noekeon.org&#x2F;" rel="nofollow">http:&#x2F;&#x2F;keccak.noekeon.org&#x2F;</a> gives a good overview.

But overuse of social media has left me with the attention span of a gnat!

In 90 days the team will release their PoC code and you can take a look.

From what I understand, no hash function has ever stood the test of time as some block ciphers have. SHA-2 is of related design and although no one&#x27;s found an effective collision attack yet, I don&#x27;t think it would really surprise anyone if one were found. This was in large part the motivation for picking a SHA-3. If you use SHA-3, it&#x27;s of unrelated design to SHA-1, but it&#x27;s also much newer and hasn&#x27;t gotten as much cryptanalysis yet.

For those of us who are totally clueless about the construction of these hash functions, what is the fundamental flaw in SHA-1 that allows this attack? How do newer hash functions avoid it?

Worth noting that Facebook stopped offering SHA-1 back in November[1]. Cloudflare still offers SHA-1 for paying customers (via a root certificate pulled from trust stores, i.e. which are only supported on outdated devices&#x2F;browsers). Not sure about Twitter.[1]: <a href="https:&#x2F;&#x2F;www.facebook.com&#x2F;notes&#x2F;protect-the-graph&#x2F;retiring-sha-1-certificates&#x2F;1814716098768533" rel="nofollow">https:&#x2F;&#x2F;www.facebook.com&#x2F;notes&#x2F;protect-the-graph&#x2F;retiring-sh...</a>

Never forget: when Facebook, Twitter, and Cloudflare tried to slow-down SHA-1 deprecation:<a href="https:&#x2F;&#x2F;www.facebook.com&#x2F;notes&#x2F;alex-stamos&#x2F;the-sha-1-sunset&#x2F;10153782990367929" rel="nofollow">https:&#x2F;&#x2F;www.facebook.com&#x2F;notes&#x2F;alex-stamos&#x2F;the-sha-1-sunset&#x2F;...</a><a href="https:&#x2F;&#x2F;blog.twitter.com&#x2F;2015&#x2F;sunsetting-sha-1" rel="nofollow">https:&#x2F;&#x2F;blog.twitter.com&#x2F;2015&#x2F;sunsetting-sha-1</a><a href="https:&#x2F;&#x2F;blog.cloudflare.com&#x2F;sha-1-deprecation-no-browser-left-behind&#x2F;" rel="nofollow">https:&#x2F;&#x2F;blog.cloudflare.com&#x2F;sha-1-deprecation-no-browser-lef...</a>I think Microsoft tried to do it too early on, but eventually agreed to a more aggressive timeline.

Except all exchanges between mercurial client and server happen with changegroups and changegroups are still limited to 20 bytes for the hash.

Yes, as it uses a similar hashing scheme as git.
<a href="https:&#x2F;&#x2F;www.mercurial-scm.org&#x2F;wiki&#x2F;FAQ#FAQ.2FTechnicalDetails.What_about_hash_collisions.3F_What_about_weaknesses_in_SHA1.3F" rel="nofollow">https:&#x2F;&#x2F;www.mercurial-scm.org&#x2F;wiki&#x2F;FAQ#FAQ.2FTechnicalDetail...</a>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).
<a href="https:&#x2F;&#x2F;www.mercurial-scm.org&#x2F;wiki&#x2F;RevlogNG" rel="nofollow">https:&#x2F;&#x2F;www.mercurial-scm.org&#x2F;wiki&#x2F;RevlogNG</a>

This only works if the attacker controls both sides, or at least a piece of both sides. That&#x27;s a collision attack, and it&#x27;s much easier than a pre-image or second pre-image attack which tries to match an existing hash.

As I understand it the attacker would have to generate both versions of the message. If an attacker could generate a second message with a hash that matches that of an existing message from a third party, that would be a second-preimage attack, not merely a collision attack.Even MD5 is still considered to be second-preimage resistant: <a href="http:&#x2F;&#x2F;crypto.stackexchange.com&#x2F;q&#x2F;3441&#x2F;21238" rel="nofollow">http:&#x2F;&#x2F;crypto.stackexchange.com&#x2F;q&#x2F;3441&#x2F;21238</a>

If you trust a signer, does this attack do anything to invalidate their SHA-1-based signatures? Or is the scenario strictly an attacker generating both versions of the message?

It must be supposed to say 10 years after first known collision of SHA-1 or something.

&gt; &quot;Today, 10 years after of SHA-1 was first introduced, ...&quot;That part from the original article seems to be missing something?

I love the fact that there is a tool for detecting any collision using this algorithm:
<a href="https:&#x2F;&#x2F;github.com&#x2F;cr-marcstevens&#x2F;sha1collisiondetection" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;cr-marcstevens&#x2F;sha1collisiondetection</a>and it&#x27;s super effective: The possibility of false positives can be neglected as the probability is smaller than 2^-90.It&#x27;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).

But I thought files in git were also identified by the sha1 of their contents? Why isn&#x27;t there a conflict&#x2F;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?

That&#x27;s not the attack on git -- it&#x27;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.

Why wouldn&#x27;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&#x27;d imagine the two files compress differently since they are actually different?)

Git stores the files as so-called blob objects, they&#x27;re prefixed with a simple header. So even if sha1(file1)==sha1(file2), your git will still get different hashes, because it&#x27;s doing sha1(prefix+file1), sha1(prefix+file2). You&#x27;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&#x2F;gpu cluster google used to make it feasible. Maybe there are precomputations that can be reused somehow.

It&#x27;s semi-relevant to your question, but if you want to learn more about Git internals, I recommend the last chapter of the &quot;Pro Git&quot; book, which is free:<a href="https:&#x2F;&#x2F;git-scm.com&#x2F;book&#x2F;en&#x2F;v2&#x2F;Git-Internals-Plumbing-and-Porcelain" rel="nofollow">https:&#x2F;&#x2F;git-scm.com&#x2F;book&#x2F;en&#x2F;v2&#x2F;Git-Internals-Plumbing-and-Po...</a>

The compression is applied after the hashing, so it doesn&#x27;t make any difference. Only the &quot;blob &lt;size&gt;&quot; header matters.

Probably just as easy. They used a fixed header for PDF and a tweakable middle. So just add the git blob header, as long as the tweakable middle is fixed size.

This is because git adds a header and zlib compresses the PDFs such that they no longer collide when stored in git. But of course, they still collide when extracted from git:<pre><code> $ ls -l; for i in 1 2; do sha1sum &lt; shattered-$i.pdf; \
 git cat-file -p $(git hash-object -w shattered-$i.pdf) |
 sha1sum; done; find .git&#x2F;objects -type f -print0 | xargs -0 ls -l
 total 1664
 -rw-r--r--@ 1 jay staff 422435 Feb 23 10:32 shattered-1.pdf
 -rw-r--r--@ 1 jay staff 422435 Feb 23 10:32 shattered-2.pdf
 38762cf7f55934b34d179ae6a4c80cadccbb7f0a
 38762cf7f55934b34d179ae6a4c80cadccbb7f0a
 38762cf7f55934b34d179ae6a4c80cadccbb7f0a
 38762cf7f55934b34d179ae6a4c80cadccbb7f0a
 -r--r--r-- 1 jay staff 381104 Feb 23 10:41 .git&#x2F;objects&#x2F;b6&#x2F;21eeccd5c7edac9b7dcba35a8d5afd075e24f2
 -r--r--r-- 1 jay staff 381102 Feb 23 10:41 .git&#x2F;objects&#x2F;ba&#x2F;9aaa145ccd24ef760cf31c74d8f7ca1a2e47b0
</code></pre>
See &quot;Object Storage&quot; for details at <a href="https:&#x2F;&#x2F;git-scm.com&#x2F;book&#x2F;en&#x2F;v2&#x2F;Git-Internals-Git-Objects" rel="nofollow">https:&#x2F;&#x2F;git-scm.com&#x2F;book&#x2F;en&#x2F;v2&#x2F;Git-Internals-Git-Objects</a>It&#x27;s worth noting that either of the changes, adding a header or deflating the content, would remove the collision. The former because this is a chosen-prefix collision attack, the latter because the compression alters the content entirely.I&#x27;m not a cryptographer, so I wonder: do the git header and zlib compression add significant complexity to manufacturing two files that collide inside git?

I&#x27;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&#x27;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 &quot;git status&quot; to say &quot;no changes&quot; after overwriting the first (committed) pdf with the second pdf?

It&#x27;s still quite impractical, m sure with some quantum computer or a custom ASIC built by those &quot;super nerds&quot; at the NSA its possible but but for you general adversary aka &quot;hackers&quot; (skiddies IMHO) it will be infeasible.What this means is for all of you [developers], is to start new projects without SHA1 and plan on migrating old ones (if it&#x27;s totally necessary, normally don&#x27;t unless you use SHA1 for passwords).A Great resource for those who still don&#x27;t know how or what hash to use, is paragonie: <a href="https:&#x2F;&#x2F;paragonie.com&#x2F;blog&#x2F;2016&#x2F;02&#x2F;how-safely-store-password-in-2016" rel="nofollow">https:&#x2F;&#x2F;paragonie.com&#x2F;blog&#x2F;2016&#x2F;02&#x2F;how-safely-store-password...</a>

For me it says &quot;Collision found in shattered-1.pdf&quot;

I get &quot;Collision found&quot;. Couldn&#x27;t even begin to guess what&#x27;s causing it to say it&#x27;s safe on your end, unless you modified the files.

This tool is simply testing whether or not the file has a disturbance vector that makes it a potential file with higher than usual probability to be in a collision

I&#x27;m confused by the &quot;File Tester&quot; at <a href="https:&#x2F;&#x2F;shattered.it&#x2F;" rel="nofollow">https:&#x2F;&#x2F;shattered.it&#x2F;</a>It says &quot;Upload any file to test if they are part of a collision attack.&quot;When I upload either of their two sample collision documents, it says they are &quot;Safe.&quot;

I don&#x27;t think that&#x27;s how averages work. But it&#x27;s true that relying on the birthday paradox, you can reduce the average. I was just trying to compute the &quot;cloud&quot; cost of 110 GPUs for 1 year (or the equivalent for a day, assuming this is embarrassingly parallel).

This would still be just an average, right?  Isn&#x27;t it 0$ to $2.8M depending on luck?

I found my mistake g2.8xlarge have 4 GPUs each, so it cuts the cost by 4 (~626k per collision). p2.16xlarge have 16 GPUs (~867k per collision). Exact model of GPU not taken into account, so this could vary widely.

Anyone good enough in AWS pricing can reproduce the $100k pricing for one collision ? Using EC2 g2.xlarge instances I&#x27;m more at $2.8M.

It should also be noted that their examples files also have the same file size, in this case 422435 bits, after creating the collision - which I find fascinating!

If there was, then that would have been the first SHA-1 collision, right? ;P

They have almost 83,000,000 public repositories (<a href="https:&#x2F;&#x2F;api.github.com&#x2F;repositories?since=82960000" rel="nofollow">https:&#x2F;&#x2F;api.github.com&#x2F;repositories?since=82960000</a>).Many of them will be forks of the same projects, but I think it&#x27;s fair to say there&#x27;s a sizable number of unique commits.Granted, the number will only be a tiny fraction of total address space of SHA1, but it&#x27;d still be an interesting thing to investigate.

How many commits are there in total on Github ?

I wonder if there are any 2 single commits on Github from different repositories that have the same SHA1 hash.

They said &quot;in practice&quot; for a reason.

&gt; In practice, collisions should never occur for secure hash functions.That is mathematically impossible when reducing an N bit string to an M bit string, where N &gt; M.All hashes have collisions; it&#x27;s just how hard are they to find.

10 million GPUs is not insane when you have a billion dollar security cracking infrastructure budget. Especially when you compare it to the rest of the cyber warfare budget.

No, that&#x27;s irrelevant. You don&#x27;t hold off showing the first SHA-1 collision to have it have MD5 collisions as well.I don&#x27;t think anyone in the field is surprised that the MD5 signatures are different for this file.

Seeing how they ridicule MD5, I think they should have spent a bit more time on the proof PDFs, and have their MD5 digests collide also.

The differing bytes are interesting<a href="http:&#x2F;&#x2F;imgur.com&#x2F;a&#x2F;wI4xb" rel="nofollow">http:&#x2F;&#x2F;imgur.com&#x2F;a&#x2F;wI4xb</a>

It’s actually not much harder at all, as first noted by Joux, “Multicollisions in iterated hash functions. Application to cascaded constructions”, 2004.<a href="https:&#x2F;&#x2F;www.iacr.org&#x2F;archive&#x2F;crypto2004&#x2F;31520306&#x2F;multicollisions.pdf" rel="nofollow">https:&#x2F;&#x2F;www.iacr.org&#x2F;archive&#x2F;crypto2004&#x2F;31520306&#x2F;multicollis...</a>

It would certainly be harder, but as with breaking any hash, it becomes more feasible every day.It&#x27;s likely easier to replace &quot;sha1&quot; with &quot;sha256&quot; in your code than it is to construct a Frankenstein&#x27;s monster of hashing.

As someone who knows only the very basics of cryptography - would verifying hashes of a file using SHA-1 and a &quot;weak&quot; 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&#x27;m guessing theoretically&#x2F;mathematically it&#x27;s only a little bit harder given how easy collisions in MD5 are?

This is not as far fetched as you think.In UK, rental contracts are often digitally signed by the renter and landlord.I am sure in finance world many other types of contracts are signed digitally, also under the assumption that both parties sign the same thing.

Presumably they&#x27;re talking about digital signatures. I don&#x27;t know how common that is in the U.S., but it&#x27;s used quite a bit in many European countries as a means to sign contracts and such. (I also don&#x27;t know enough about the implementation details to say whether a colliding pdf file would be sufficient to trick these systems, but let&#x27;s assume so for the sake of this argument.)

Obviously the landlord doesn&#x27;t know or care what SHA-1 is, but he may care if his Adobe Reader says &quot;This file was signed by the Department of Housing&quot; at the top of the screen when he opens the PDF. As Reader fully supports signed PDFs and they do get used, believe it or not, this attack is not theoretical.

The PDF example given is somewhat ridiculous.&quot;For example, by crafting the two colliding PDF files as two rental agreements with different rent, it is possible to trick someone to create a valid signature for a high-rent contract by having him or her sign a low-rent contract. &quot;Talk about ridiculous scenarios only people living in a tech bubble could come up with.How many landlords do you imagine know what sha-1 checksums even are, let alone would try and use it as proof the evil version of the rental agreement is incorrect?&quot;I would have gotten away with it, if it wasn&#x27;t for you meddling kids and your fancy SHA-256 checksums!&quot;

Linked <a href="http:&#x2F;&#x2F;shattered.io&#x2F;" rel="nofollow">http:&#x2F;&#x2F;shattered.io&#x2F;</a> has two PDFs that render differently as examples. They indeed have same SHA-1 and are even the same size.<pre><code> $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
</code></pre>
Of course other hashes are different:<pre><code> $shasum -a 256 sha*.pdf

 2bb787a73e37352f92383abe7e2902936d1059ad9f1ba6daaa9c1e58ee6970d0 shattered-1.pdf
 d4488775d29bdef7993367d541064dbdda50d383f89f0aa13a6ff2e0894ba5ff shattered-2.pdf 

 $md5 sha*.pdf
 
 MD5 (shattered-1.pdf) = ee4aa52b139d925f8d8884402b0a750c
 MD5 (shattered-2.pdf) = 5bd9d8cabc46041579a311230539b8d1</code></pre>

Announcing the first SHA-1 collision