SHA-1 'fully and practically broken' by new collision (2020) • Hacker News Board

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

#61

Post by contravariant » Tue, Oct 12, 2021, 9:24 PM UTC

ganzuul wrote: post #19

fwip wrote: post #14

Earlier quoted context omitted.

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.

Natural data is easily identifiable.

Only if you count all natural looking data of which there is way more than you could possibly imagine.

It is of course likely that humanity hasn't yet created more than 2^100 (~10^30) files, so in theory given a registry of all files in existence you might be able to identify it by its hash. However while this is simple it's definitely not easy.

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

#62

Post by simias » Tue, Oct 12, 2021, 9:29 PM UTC

alerighi wrote: post #28

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…

SHA-1 will still work fine for the purpose of git. It is just no longer considered secure for cryptographic operations, such as digital signature, that doesn't mean that you can't use it for other purposes, like git does. Using it is still fine and will ever be fine. Making the hashing algorithm exchangeable would have introduces complexity in a software that is already complex, and also less efficient (one of the re…

Honestly I find these rationalizations around the use of SHA-1 annoying and counter-productive. The rule is simple: don't use SHA-1. If you already use SHA-1 migrate away from it. You know that plenty of software out there that interfaces with git expecting that the commit hash will be unique. Is it a security risk? Maybe, maybe not. I don't care to find out.

It doesn't matter until it starts mattering. If the Git devs had done the right thing over a decade ago we wouldn't be having this discussion. The longer they wait the more painful the migration will be.

SHA-2 was published in 2001, git was released in 2005 and now we're in 2021 and we're having this discussion again. The first concrete attack was released in "early 2005" according to wikipedia, so there's really no excuse.

Just do it, make a major change where you replace SHA-1 with SHA-256 and call it a day. It's going to be painful for a few months and then we'll move on.

For me these discussions demonstrate the immaturity of software engineering. In other industries regulators would've banned the use of SHA-1 and you couldn't get certified if you used it.

Do electronic engineers regularly try to argue "well ok RoHS says we can't have lead solder in this product but frankly for this one it's fine the casing is completely waterproof and there are no risks for the customer"? No, they don't. If the spec says no lead, then either it's no lead or you can't sell your product. End of story.

SHA-1 is the lead solder of software engineering. Only acceptable for military use.

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

#63

Post by simias » Tue, Oct 12, 2021, 9:30 PM UTC

cogman10 wrote: post #59

alerighi wrote: post #28

Earlier quoted context omitted.

SHA-1 will still work fine for the purpose of git. It is just no longer considered secure for cryptographic operations, such as digital signature, that doesn't mean that you can't use it for other purposes, like git does. Using it is still fine and will ever be fine. Making the hashing algorithm exchangeable would have introduces complexity in a software that is already complex, and also less efficient (one of the re…

And, to that point, I'm not really convinced that a cryptographic hashing algorithm is really a great choice for git. It is nice that it checks off the boxes for even distribution of hashes, but there's a bunch of other hashing algorithms that can do that without the performance penalty inherent in crypto hashes. For example, FNV seems like a good fit for something like git.

Is hashing a significant bottleneck in any git deployment? I'd expect that the diffing would be vastly more expensive for instance.

Besides don't many modern CPU supports things like SHA-256 in hardware?

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

#64

Post by noway421 » Tue, Oct 12, 2021, 9:31 PM UTC

y4mi wrote: post #60

madars wrote: post #54

Earlier quoted context omitted.

Collisions definitely do matter for git security: many people pin explicit git hashes for their dependancies, and thus they can be tricked in running malicious forks. This requires placing a chosen commit in the git repo (so unlike second preimage break it does not mean that you could attack repos you have no control over) but that's not an unrealistic threat model overall.

What is the thread model though? I don't think it's possible to create a collision that's also executeable code which adds a security hole or anything. So what exactly would they achieve with the collision? And how do they push these gigantic files that have the hash collisions to a server? The upload time would be significant.

The possible attack is to prepare 2 versions of a commit, both resulting in the same commit id. Then later on, after the project is successful/etc, swap out the commit with the second version, while keeping the other commits intact.

Granted, the file that the commit touches would need to be not touched in other commits. That's not out of question in a typical software project - maybe a file in the utils folder which is only written once and never changed?

> I don't think it's possible to create a collision that's also executeable code

You can include an unreadable binary blob in the commit. Tweak the blob to find the collision while keeping the code the way attack requires.

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

#65

Post by dec0dedab0de » Tue, Oct 12, 2021, 9:32 PM UTC

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…

Linus posted about it on google plus in 2017. I haven't re-read it yet, but I remember one of the ideas floating around hn at the time was to just have two hashes per commit. That is, two insecure hashes may be secure together for git's purposes. Even though we can generate collisions for md5, and sha1, it would be much more difficult to have a file generate an arbitrary collision for both at the same time.

Here is a link to Linus's post on the internet archive

https://web.archive.org/web/20170717192607/https://plus.goog...

And here are some hn posts around the same time

https://news.ycombinator.com/item?id=13733481

https://news.ycombinator.com/item?id=13719368

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

#66

Post by OJFord » Tue, Oct 12, 2021, 9:33 PM UTC

y4mi wrote: post #60

madars wrote: post #54

Earlier quoted context omitted.

Collisions definitely do matter for git security: many people pin explicit git hashes for their dependancies, and thus they can be tricked in running malicious forks. This requires placing a chosen commit in the git repo (so unlike second preimage break it does not mean that you could attack repos you have no control over) but that's not an unrealistic threat model overall.

What is the thread model though? I don't think it's possible to create a collision that's also executeable code which adds a security hole or anything. So what exactly would they achieve with the collision? And how do they push these gigantic files that have the hash collisions to a server? The upload time would be significant.

A denial of service of sorts? (Something broken and unusable is delivered instead, as distinct from something usable but maliciously so.)

I agree that the chances of ever getting a second pre-image that not only makes sense, but does so in some malicious way may as well be zero, surely?

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

#67

Post by tialaramex » Tue, Oct 12, 2021, 9:34 PM UTC

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…

The defence used by GitHub specifically defends against these intentional collisions, not some mirage of random collisions.

Basically you collide a hash like SHA-1 or MD5 by getting it into a state where transitions don't twiddle as many bits, and then smashing the remaining bits by brute force trial. But, such states are weird so from inside the hash algorithm you can notice "Huh, this is that weird state I care about" and flag that at a cost of making the algorithm a little slower. The tweaked SHA1 code is publicly available.

If you're thinking "Oh! I should rip out our safe SHA256 code and use this unsafe but then retro-actively safer SHA1" No. Don't do that. SHA-256 is safer and faster. This is an emergency patch for people for whom apparently 20 years notice wasn't enough warning.

In theory the known way to do this isn't the only way, but, we have re-assuring evidence for MD5 that independent forces (probably the NSA) who have every reason to choose a different way to attack the hash to avoid detection do trigger the same weird states even though they're spending the eye-watering sum of money to break hashes themselves not just copy-pasting a result from a published paper.

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

#68

Post by [deleted] » Tue, Oct 12, 2021, 9:34 PM UTC

noway421 wrote: post #64

y4mi wrote: post #60

Earlier quoted context omitted.

What is the thread model though? I don't think it's possible to create a collision that's also executeable code which adds a security hole or anything. So what exactly would they achieve with the collision? And how do they push these gigantic files that have the hash collisions to a server? The upload time would be significant.

The possible attack is to prepare 2 versions of a commit, both resulting in the same commit id. Then later on, after the project is successful/etc, swap out the commit with the second version, while keeping the other commits intact. Granted, the file that the commit touches would need to be not touched in other commits. That's not out of question in a typical software project - maybe a file in the utils folder which…

[deleted]

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

#69

Post by mypalmike » Tue, Oct 12, 2021, 9:37 PM UTC

motohagiography wrote: post #36

fwip wrote: post #14

Earlier quoted context omitted.

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 prob…

Using the pigeonhole principle, consider how many 100 megabit values must, on average, hash to the same 32 bit value. The answer is a huge number (I could be wrong but it seems to me it might be 2 ^ (100,000,000 - 32)?). This is a bit of a paradox in cryptographic hashing, where finding a collision is difficult, but the number of collisions is enormous.

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

#70

Post by TonyTrapp » Tue, Oct 12, 2021, 9:37 PM UTC

cogman10 wrote: post #59

alerighi wrote: post #28

Earlier quoted context omitted.

SHA-1 will still work fine for the purpose of git. It is just no longer considered secure for cryptographic operations, such as digital signature, that doesn't mean that you can't use it for other purposes, like git does. Using it is still fine and will ever be fine. Making the hashing algorithm exchangeable would have introduces complexity in a software that is already complex, and also less efficient (one of the re…

And, to that point, I'm not really convinced that a cryptographic hashing algorithm is really a great choice for git. It is nice that it checks off the boxes for even distribution of hashes, but there's a bunch of other hashing algorithms that can do that without the performance penalty inherent in crypto hashes. For example, FNV seems like a good fit for something like git.

FNV is really cool and has a reasonable quality given its simplicity. But it does have issues (sticky state, and I think the avalanche characteristics also weren't great) that are solved by only slightly more complex hashing algorithms.