Linus' reply on Git and SHA-1 collision

> but git doesn't actually just hash the data, it does prepend a type/length field to it.

To me it feels like this would just be a small hurdle? But I don't really know this stuff that well. Can someone with more knowledge share their thoughts?

I think Linus also argued that SHA-1 is not a security feature for git (https://youtu.be/4XpnKHJAok8?t=57m44s). Has that been changed?

I don't think that comparison is quite right: ten years ago we already had two of Xiaoyun Wang's attacks which significantly reduced the work factor to break SHA-1. They were already cited at the time as reasons to move away from the algorithm (and I doubt we'd be able to do the 2⁸⁰ work needed to get a collision without cryptanalytic research! — notably the successful Stevens attack today reported performing a total of 2⁶³ hash operations while claiming to be "one of the largest computations ever completed").

There's also important concern about SHA-512 (which has led to SHA-3 and other options), but I'm not sure it can be put in the same category; at least all of the best attacks today are significantly reduced-round.

https://en.wikipedia.org/wiki/SHA-2#Cryptanalysis_and_valida...

By contrast, Wang's original attack (which we had more than 10 years ago) achieved a 2¹¹ speedup for collisions against full SHA-1 and her second attack later the same year achieved 2¹⁷ speedup.

Evidently the speedup for the final version of Stevens's attack (which worked) was also around 2¹⁷. By contrast, a Moore's law improvement over 10 years would only be expected to make computers around 2⁶ times faster! (At the risk of mixed or mangled metaphors, we might say that mathematical insight during the time period you mention has been about 2¹¹ times more useful for attacking SHA-1 than computer power increases.)

Edit: someone else linked to Valerie Aurora's chart, which I'd forgotten about, which gives a synopsis of the historical status of the most popular hashes. On that chart, SHA-1 from 2005 was one category worse ("Weakened") than SHA-512 is today ("Minor weakness").

http://valerieaurora.org/hash.html

Downloading the PDFs [1] and comparing their sizes takes less than a minute. They're the exact same size. Yet here we have Linus making one bet after another that size has to be different for this attack.

Now to be fair, he also keeps repeating that he hasn't seen the attack yet. Which leads me to question why is this post interesting to HN? Is it to show how Linus aimlessly speculates and gets his guesses wrong?

--

[1] http://shattered.it/

> > If we want to have any kind of confidence that the hash is reall yunbreakable, we should make it not just longer than 160 bits, we should make sure that it's two or more hashes, and that they are based on totally different principles.

Why is this quoted in support of an argument that Linus used to come across as a lunatic in online correspondence ?

This seems to me like an entirely reasonable way to make it very, very difficult to ever attack, because an attacker would have to be able to generate collisions for both of your hash functions.

(I'm not a crypto expert -- maybe you are, if so and my above comment is totally wrong, can you explain how it's wrong?)

I think Linus' point at the time was that the computational cost added to every transaction to protect against a (at the time) highly infeasible event of questionable impact was a poor cost vs. benefit argument. Adding complexity isn't free, and there needs to be a measurable benefit against a threat.

But of course, now is not then. And I think zkms' metaphor "there's angry and armed people shooting at my plane with armour-piercing ammunition" is apt here. The threat is much more sizable now, and so the cost vs. benefit analysis has changed.

Incidentally, one of the requirements of the SHA-3 competition was that it not be related to previous hashes. So while there are no demonstratable attacks against SHA-2, we nonetheless have "two ...hashes, and that they are based on totally different principles."