Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

SHA-1 'fully and practically broken' by new collision (2020)

duo.com

Post reply on HN
Print view View original

31–40 of 210 posts

Re: SHA-1 'fully and practically broken' by new collision (2020)

#31

Post by elfchief »

cletus wrote: post #25

Git was created 16 years ago. The impending breakage of SHA-1 was known even at that time, just like how MD5 had been broken before it. I'm honestly still shocked that updating the hashing algorithm wasn't built into Git from day one. I really wonder why. Did people think this wouldn't happen? Were they so in love with the performance of C/C++ being able to pass around 20 byte hashes on the stack without worrying abo…

Git was not intended (AFAIK) to be cryptographically secure. Being unsuitable for crypto != being unsuitable for other uses.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#32

Post by AnimalMuppet »

__s wrote: post #22
ganzuul wrote: post #19

Earlier quoted context omitted.

Natural data is easily identifiable.

That's because natural data has low entropy But let's say every paragraph only offers 1 bit of entropy. Then a 160 bit hash gives you fuzzy accuracy up to 160 paragraphs. After that you'll have to extend the hash with hints to guide which sequence of paragraphs you're looking for, & hints for where the typos are ofc, 100x compression of English text doesn't require this amount of compute to decompress: https://en.wik…

"Paragraph" is highly optimistic. IIRC, each English character has about 1 bit of entropy.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#34

Post by formerly_proven »

cletus wrote: post #25

Git was created 16 years ago. The impending breakage of SHA-1 was known even at that time, just like how MD5 had been broken before it. I'm honestly still shocked that updating the hashing algorithm wasn't built into Git from day one. I really wonder why. Did people think this wouldn't happen? Were they so in love with the performance of C/C++ being able to pass around 20 byte hashes on the stack without worrying abo…

Git is designed around content-addressed storage and while you can cater for hash migrations, it gets pretty messy design-wise. Gits core data structures were also designed really quickly to patch a very urgent need of the kernel hackers. I doubt it has anything to do with being in love passing 20 byte strings on the stack. The fine git folks have produced a rather detailed document about the hash migration (https://git-scm.com/docs/hash-function-transition/) and it is not particularly simple to do this.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#35

Post by jfrunyon »

api wrote: post #7
ImJasonH wrote: post #3

Reminder that GitHub has blocked Git commit collisions since 2017, and as far as anybody is aware hasn't seen one in the wild. https://github.blog/2017-03-20-sha-1-collision-detection-on-...

Random collisions in 160-bit space are incredibly unlikely. This is talking about intentional collision, and means that it's entirely feasible for someone with significant compute power to create a git commit that has the exact same hash as another git commit. This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software. The modified repository woul…

https://stackoverflow.com/questions/23584990/what-data-is-be... says git signing just signs the commit hash (plus metadata: committer, commit message, etc).

Re: SHA-1 'fully and practically broken' by new collision (2020)

#36

Post by motohagiography »

fwip wrote: post #14
motohagiography wrote: post #13

Earlier quoted context omitted.

I only half joke when I ask, when you break a cryptogrpahic hash, does it mean that now it's just a really amazing compression algorithm, but with a very heavy compute requirement? The non-joking half is speculating what data compression in a post-quantum compute world looks like.

No, because reversing the hash has infinite possible answers (well, "very many" for bounded input size). You can't decompress 32 bytes into 1GB because you don't know which of the 1GB-sized answers is the intended one.

This is what made it a funny thought experiement to me. I was doing some space related stuff a while back and when you're dealing with something as small as 100mb, and you add the constraint of up to a light-year or more of latency, which makes error correction immensely costly, having a quantum processor reciever find the collision of a unique hash could be faster than transmitting the data with errors.

There's probably a distance where the latency in light years is longer than it takes for a quantum processor with some shortcuts to exhaust the search space for the collision on the hash - and potential hashing algorithms that contain information and hints about a hyperplane that generates the original data over the field of possibilities. To a quantum computer with sufficient qbits at a long enough latency distance away, the 32-bit hash of a 2048bit RSA key may "arrive" faster than transmitting the whole key.

It feels like a fundamental misunderstanding of something in communication theory, but this was the thinking that prompted it.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#37

Post by oconnore »

api wrote: post #7
ImJasonH wrote: post #3

Reminder that GitHub has blocked Git commit collisions since 2017, and as far as anybody is aware hasn't seen one in the wild. https://github.blog/2017-03-20-sha-1-collision-detection-on-...

Random collisions in 160-bit space are incredibly unlikely. This is talking about intentional collision, and means that it's entirely feasible for someone with significant compute power to create a git commit that has the exact same hash as another git commit. This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software. The modified repository woul…

I was surprise that no one suggested truncating SHA-256 to 160 bits (same as for SHA2-256/224, or SHA2-512/256). The attacks on SHA-1 are not directly based on the length of the hash, they are based on weaknesses in the algorithm.

Even attacking SHA2-256/128 would be quite difficult as I understand it, even though it's the same length as MD5.

Truncated hashes also of course have the great property that they mitigate the length extension in Merkle-Damgard

Re: SHA-1 'fully and practically broken' by new collision (2020)

#38

Post by jfrunyon »

AnimalMuppet wrote: post #26
api wrote: post #7

Earlier quoted context omitted.

Random collisions in 160-bit space are incredibly unlikely. This is talking about intentional collision, and means that it's entirely feasible for someone with significant compute power to create a git commit that has the exact same hash as another git commit. This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software. The modified repository woul…

Can you create an intentional collision, and also have the counterfeit have compilable code? (Or, in other circumstances, intelligible English text?)

Yes, just like you can create an intentional collision, and also have the counterfeit be a PDF. [https://shattered.io/]

Re: SHA-1 'fully and practically broken' by new collision (2020)

#39

Post by adrian_b »

api wrote: post #7
ImJasonH wrote: post #3

Reminder that GitHub has blocked Git commit collisions since 2017, and as far as anybody is aware hasn't seen one in the wild. https://github.blog/2017-03-20-sha-1-collision-detection-on-...

Random collisions in 160-bit space are incredibly unlikely. This is talking about intentional collision, and means that it's entirely feasible for someone with significant compute power to create a git commit that has the exact same hash as another git commit. This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software. The modified repository woul…

It is not yet possible "to create a git commit that has the exact same hash as another git commit" in the sense that if someone else has already done a commit you can make another commit with the same hash.

What is possible now is something that is much easier: if you have enough money and time, you can create 2 commits with the same hash, which start with some different parts, which may be chosen arbitrarily, then they have to include some parts that must be computed to ensure that the hashes will match and which will be gibberish that might be disguised in some constants or some binary blob, if possible.

Then you can commit one of them and presumably you can later substitute the initial commit with the other one without anybody being able to detect the substitution.

Re: SHA-1 'fully and practically broken' by new collision (2020)

#40

Post by outworlder »

api wrote: post #7
ImJasonH wrote: post #3

Reminder that GitHub has blocked Git commit collisions since 2017, and as far as anybody is aware hasn't seen one in the wild. https://github.blog/2017-03-20-sha-1-collision-detection-on-...

Random collisions in 160-bit space are incredibly unlikely. This is talking about intentional collision, and means that it's entirely feasible for someone with significant compute power to create a git commit that has the exact same hash as another git commit. This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software. The modified repository woul…

> This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software.

You need a collision. You also need it to be syntactically correct. You need it to not raise any red flags if you are contributing a patch. And ultimately you need it to do what you want.

That's a pretty tall order.

Post reply on HN