Git fscked by SHA-1 collision? Not so fast, says Linus Torvalds

Re: That's not how hashes work

Sorry, but no it doesn't! Any hash key can produce only a limited number of distinct results, and while the greater the number of bits in use, the less chance of *accidentally* encountering a collision. To go from "the chances of a random collision are vanishingly small" to "it always produces a unique result" is the sort of dangerous mistake that hackers love to exploit.

Linus was using SHA-1 as a cheap way of calculating a hash that was *very unlikely* to collide, the hackers are using a known algorithm to produce a predetermined result.

Imaging Linus was simply summing the bits mod 1024. there would a 1 in 1024 chance of a collision. If a hackers target has a hash of 512 and the code they want to use has a hash of 384, then they just have to add 128 to produce a valid fake.

Re: That's not how hashes work

"A 160 bit hash _does_ in practice produce a unique result for any given input (unless you spend 6,600 years of CPU time to search for two given inputs with the same result)."

AIUI there is now a method of constructing a colliding pair of files with rather less than the 6,600 years you suggest. That's what's set off this whole discussion.

I think one of Linus' points is that constructing a file which gives the same hash as an existing file and having it compilable is problem of a very different order of magnitude.

Re: That's not how hashes work

"The mathematical operation should produce a unique result for any given input"

Given that "any given input" is conceptually an infinite set, always expecting a unique 160bit hash is just ludicrous. The main thing with these hashes is that small changes in the code will give hugely differing hashes, making collisions rare. We all know that it is possible to engineer (by brute force) a collision, but it's a hard problem. Doing so in such a way as to be undetectable in Git is an even harder problem. Way harder. I look forward to seeing the attempts, though :-)

Re: That's not how hashes work

"Electron, what you post is nonsense. A 160 bit hash _does_ in practice produce a unique result for any given input (unless you spend 6,600 years of CPU time to search for two given inputs with the same result)."

160 bits make for a big number. A really big number, with lots and lots of zeros after it. And any halfway decent hash algorithm worth it's salt [*] will be designed such that even a tiny change in the input will produce a significantly different output.

However, 160 bits is not infinity. It's not even a googleplex. And if someone's deliberately trying to force collisions, you'd be foolish indeed to assume that things are safe.

Then too, assuming they're using the "1 GFLOP machine working for a year" definition of CPU-years [**], that figure of 6,600 years isn't as impressive as it sounds.

An Intel i7 can run at over 350 GFLOPs in dual-precision mode, while a modern GPU (e.g. Radeon RX 480) can theoretically churn out up to 5 TFLOPs in single-precision mode; the Tesla K80 used by Amazon for their cloud-computing back-end can churn out 8.74 TFLOPS in single-precision mode.

Then too, there's always the possibility of using distributed computing or specialised hardware - this type of problem is inherently parallelisable and bitcoin mining has shown how effective ASICs can be for this type of number crunching. Also, since the people most likely to want to force a collision are nation-states or hackers, they could well have access to a supercomputer or maybe even botnets - I wouldn't be surprised to see people offering collision-detection as a service, as more traditional profit streams continue to dry up (albeit with botnets increasingly being based on IoT low-power devices, there may not be many of these).

So, yeah. 160 bits is good. But these days, it arguably ain't good enough.

[*] sorrynotsorry

[**] http://www.gridrepublic.org/joomla/index.php?option=com_mambowiki&Itemid=35&compars=help_documentation&page=GFlops,_G-hours,_and_CPU_hours

Re: That's not how hashes work

"A 160 bit hash _does_ in practice produce a unique result for any given input "

Wtf does this ridiculous sentence even mean?

A 160 bit hash is 20 bytes, isn't it?

So if one assumes that the source data being hashed is bigger than 20 bytes, it doesn't matter what hash algorithm is in use, there must by definition be more than one set of input data which will generate particular hash values. Otherwise e.g. a disk would store the hash value not the input data. Same logic applies to any sensible hash size.

"Someone did a calculation for backup systems that calculate hash codes to see if an identical file is already stored. It is _possible_ that you have a different file with the same hash as one that is already stored, and your file isn't going to be backed up"

Fancy that. What are the odds that the "someone" in this picture was a disk deduplication vendor? And/or that the logic in question actually was "if the hash of the new data and the already-stored data are different then we know that the old and new data ARE different, and therefore we must store the new data. IF (and only if) the hashes match, we must THEN compare the actual old data and new data, rather than the old and new hashes, and do some other extra work to ensure that the new data CAN be stored and recovered safely."

Re: Common sense approach

I do not quite follow. What exactly would an attacker manipulate in a git repository?

For the purpose of this discussion, git calculates the hash based on the author signature in addition to the files' contents (http://stackoverflow.com/a/17278248/1736944). So yes, there are some fields that can be exploited to hide away stuff that won't ruin the source code.

Are you concerned someone will push a commit having an identical sha-1 hash? Well, if you push a commit having an identical hash as a previous commit, then git will assume you are trying to push something it already has. It will ignore it. (http://stackoverflow.com/a/34888325/1736944)

Or is the concern here that somebody will break into the repository and change something directly? Well... Who would notice that, based on the hash...? Is the suggestion here that the hash is somehow protecting the git users?

AFAICT, the weakest link is the pull request. The person(s) maintaining the repository must be trusted to not accept pull requests containing nefarious code. The hash algorithm has no bearing on this process. And naturally: users have to know which repository to fetch.

I am new to git. We only started using it a year ago. I am obviously missing something in this discussion.

Re: SHA1 still "useful" then?

Just imagine how Paul Neil Milne Johnstone of Redbridge feels...

Re: I missed this reading the original collision notification

@Naselus : ""I actually missed the part that the attack produced by Google needs to meddle with both sides - "good" and "bad" of the collision." You missed it because it doesn't 'need' to. "

That is seriously wrong. The attack absolutely *does* need to fiddle with both sides. Fiddling with only one side is not a collision attack, it is a pre-image attack - and nobody has demonstrated a pre-image attack against even MD5 yet.

Re: Context is King

@Richard 12

"Google have proven that it is feasible for an entity to produce two PDFs with different content and the same SHA-1 hash, by means of embedding some "junk" in the unused data sections of both documents."

I am not a mathematically sound person, coming from that well know lilberal arts route to low level programming. I am, though, bemused that this is news to anyone? Particularly the smartest people in the room? Did sane people really think that the output of a hash, given unlimited input data, was always going to be unique?

edit: I see DougS made the same/a similar point below/earlier. The hash doesn't matter, it's how you roll it...

Or have Google just disproved unicorns?

Re: Am I missing something here?

> Git is using SHA1 signatures the same way RS232 used parity, to detect corruption

Ah, those were the days! When a 50% chance of problem detection was good enough. :-)

At 300 baud, you could almost transcribe the data by ear from the modem chirps anyway (talk about silly bets).

Re: Lifetime of Hash Algorithms

So yes, a small visible difference. Sufficient to turn a "site licence" into a "named user licence".

Particularly if those are check boxes on a list...