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

141–150 of 210 posts

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

#141

Post by sirclueless »

dude187 wrote: post #126
outworlder wrote: post #40

Earlier quoted context omitted.

> 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.

You'd also need the actual patch to survive future commits, especially without introducing any merge conflicts

Commits aren't patches. They contain the whole tree. Retroactively changing a commit can't possibly introduce conflicts with other commits on top of it, the worst it can do is introduce big funny-looking diffs.

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

#142

Post by urda »

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…

> SHA-1 will still work fine for the purpose of git.

So why are so many corporations, individuals, and orgs working hard to protect against it?

Hint: because it's not actually fine.

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

#143

Post by motohagiography »

fwip wrote: post #109
motohagiography wrote: post #36

Earlier quoted context omitted.

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…

Yeah, you're fundamentally missing what I wrote, as well as pigeonhole principle and the basics of information theory. Let's say you replace the quantum computer with an oracle. You have an infinitely long dictionary, and you can turn to any page and see your hash, as well as every possible input that could form that hash. There's billions and billions of options that all match your hash - how could you pick which on…

This part about a massive number of possible collisions for a given plaintext in a cryptographic hash, but just spread over such a large field and incrememting with the input size so that it is just unlikely you will find another one is the counterintuitive part. I haven't implemented a secure hashing algorithm from scratch, so this aspect would have come out in the exercise.

Even working with security and crypto, the presumption of a cryptographic hash from a standard algorithm is that it is universally unique for the data it hashes - barring someone finding collisions, and then it gets deprecated. Most people deal with them at a higher level of abstraction.

Hash collisions have been used in a few high profile attacks in the last decade, most notably when some SSL certificates were still using MD5, and the most recent smart contract issue where the contract was only validating the last 4 bytes of a cryptographic hash and someone produced a key that exploited that with a collision. Unfortunately the people who don't make those mistakes are both very rare, and often dynamic to work with.

The idea that there are many, many potential collisions for a given input to a cryptographic hash doesn't come up much unless someone manages to find single a collision in one. I'd even posit nobody outside academic cryptography circles is including sha256 collisions in their threat scenarios right now.

However, the absurd/imaginary/hypotehtical/counterfactual I was raising is that a future quantum computer can produce all outputs of that length in a reasonable amount of time. The question was more about what was sufficient to reconstruct the data, and it was funny to know something was specifically wrong but not know why.

However, I appreciate the time taken to illustrate it.

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

#144

Post by fierro »

CobrastanJorji wrote: post #137
kragen wrote: post #123

Earlier quoted context omitted.

This turns out to be wrong; for a 6-member programming team, that probability is about 2⁻²⁴⁵, which is about 2⁸⁵·³ times less likely than an accidental 160-bit SHA-1 collision: http://canonical.org/~kragen/sw/dev3/rpn-edit#3_8_0_1_0_0_0_... Aside from being bullshit, it's also irrelevant, since we're discussing a collision being generated on purpose, not by accident.

Just to nitpick, I don't think that formula is valid. We're primarily interested in "unrelated" wolf attacks, but it counts the total fatalities, not the total number of fatal incidents. If we count each fatal attack as only one incident, regardless of the casualties, we get 2^-258 instead. But of course we also need to take into account where the 6-member team lives. If they all live in West Bengal, India, the consi…

I concur.

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

#145

Post by sirclueless »

ufo wrote: post #120
noway421 wrote: post #50

Earlier quoted context omitted.

From a practical point of view, how would injecting malware happen? If you're trying to insert a malicious diff somewhere deep in the git history, you would need to recompute all the other commits after the injected commit - which would most certainly change their commit ids too if they are touching the same file. When other commit ids change, the malicious change becomes detectable. There's also the case for auditin…

Presumably the attacker would modify the most recent commit which edits the file that they are targeting. It is true that the attack becomes more difficult if you try to target an older commit. Auditing helps if they try to force push the original repo, but doesn't protect vs someone redistributing malicious clones of the repo. Reproduceable builds do help, but only for projects that can take advantage of it...

Every commit references every file. If you change the content of an old commit you would only affect people who check out the old commit. So this is utterly pointless and not what someone would do.

Instead what you would do is attempt to make a file-object that has a certain SHA1 hash identifying it, and a colliding file-object that has the same SHA1 hash. Then you are free to give people who clone the repository different file contents depending on when/who/how someone requests it (if the file content is hosted on github, how to change the file object identified by a given SHA1 hash is an additional hurdle since it's assumed to be immutable and indefinitely cacheable; if you control the host yourself you can just change it whenever you like).

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

#146

Post by garmaine »

adrian_b wrote: post #39
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…

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

It doesn't take any money or time. Google's break of SHA-1 was fully reusable. So long as committing a PDF to the repo counts, there's a script that will trivially concat two PDFs in such a way as that they each render to their original (different) contents, but both have the same SHA-1 hash. Put in a repo and `git add foo.pdf` and you're done.

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

#148

Post by garmaine »

asdfman123 wrote: post #55
bjarneh wrote: post #9

> The technique that the researchers developed is quite complex and required two months of computations on 900 individual GPUs.

I wonder how much money in Bitcoin they would have made if they had used those hashes to mine instead. Speaking of which, it would be funny if they were pretending to do security research but added a secret backdoor to mine bitcoin instead, somehow exporting those hashes or using the partial results of SHA-1 calculations (BTC isn't SHA-1). I'm just joking, but I wonder if that's possible. If anyone is Machiavellian e…

Well, they made 2.4994722 BTC directly by exploiting a smart contract on bitcoin that pays out to anyone demonstrating a SHA-1 collision.

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

#149

Post by marcan_42 »

garmaine wrote: post #146
adrian_b wrote: post #39

Earlier quoted context omitted.

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

It doesn't take any money or time. Google's break of SHA-1 was fully reusable. So long as committing a PDF to the repo counts, there's a script that will trivially concat two PDFs in such a way as that they each render to their original (different) contents, but both have the same SHA-1 hash. Put in a repo and `git add foo.pdf` and you're done.

Nope. Google's break of SHA-1 was reusable in the sense that you can add an arbitrary (identical) suffix to both PDFs and keep the collision. But Git does not use raw SHA-1 hashes, it adds a prefix before computing object hashes. Therefore, Google's break of SHA-1 cannot be reused to break Git.

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

#150

Post by cortesoft »

CobrastanJorji wrote: post #137
kragen wrote: post #123

Earlier quoted context omitted.

This turns out to be wrong; for a 6-member programming team, that probability is about 2⁻²⁴⁵, which is about 2⁸⁵·³ times less likely than an accidental 160-bit SHA-1 collision: http://canonical.org/~kragen/sw/dev3/rpn-edit#3_8_0_1_0_0_0_... Aside from being bullshit, it's also irrelevant, since we're discussing a collision being generated on purpose, not by accident.

Just to nitpick, I don't think that formula is valid. We're primarily interested in "unrelated" wolf attacks, but it counts the total fatalities, not the total number of fatal incidents. If we count each fatal attack as only one incident, regardless of the casualties, we get 2^-258 instead. But of course we also need to take into account where the 6-member team lives. If they all live in West Bengal, India, the consi…

This is why I always get mad when people say something like "you are more likely to be struck by lightning than eaten by a shark!".... we'll, that REALLY depends on where you are.
Post reply on HN