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

111–120 of 210 posts

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

#111

Post by a1369209993 »

oconnore wrote: post #37
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…

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…

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

To be fair, this is totally irrelevant to git, since the attacker knows the whole message and can just recompute the extra bits themselves. That said:

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

Very seconded. You could even shove the extra 96 bits in a optional metadata field and have new versions of git throw up a giant air-raid-siren-level error if they don't match (since that will never happen by accident[0]) and still have the full 256-bit-hash worth of security for most purposes. Git already allows (arguably encourages) people to truncate hashes to 28 bits or so at the UI level, so there's precendent for that already.

0: You do not have anywhere near 2^80 commits in the world, much less in the same repo.

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

#112

Post by ganzuul »

contravariant wrote: post #101
ganzuul wrote: post #91

Earlier quoted context omitted.

I can imagine the output of program space. That's pretty big. All possible universes in fact. It's an issue of probability and bins. While natural data is infinite, there is vastly more unnatural data. At some point you have enough metadata (e.g. natural vs. random) to know that the original data came from Earth to pick out the right needle from the needle stack. Unless the data is from a completely alien source, we…

It's somewhat irrelevant how many unnatural data there is. The point is that there's way more plausible data (or sentences if we're restricting ourselves to natural language) than there are possible 160; 256 or 512 bit hashes. Unless of course you enumerate all of human communication, but like I said that doesn't count as 'easy'.

I'm not trying to claim this is practical with current technology.

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

#113

Post by fsckboy »

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…

mining bitcoin on one GPU is uneconomical, so mining bitcoin an a large number of them is... also.

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

#114

Post by simias »

umvi wrote: post #79
simias wrote: post #62

Earlier quoted context omitted.

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

> You know that plenty of software out there that interfaces with git expecting that the commit hash will be unique You also know that plenty of software out there that interfaces with git has hardcoded assumptions (like, for example, the assumption that the commit hash will be exactly 40 characters long). Some tools parse the output of git log and other commit-bearing commands to make decisions. Will changing git to…

The difference is that this breakage would be immediately visible. All code that mishandles these hash would immediately break. With collisions it can remain undetected for a long time, and potentially until somebody smart and with bad intentions finds a way to break your system in some creative way.

And again, if we had done this when it should have been done, i.e. pre-2010, we wouldn't be having this discussion. The longer we wait the more painful the migration will be whenever somebody manages to actually bruteforce collisions for git commits. We're not there. Yet.

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

#115

Post by djur »

umvi wrote: post #79
simias wrote: post #62

Earlier quoted context omitted.

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

> You know that plenty of software out there that interfaces with git expecting that the commit hash will be unique You also know that plenty of software out there that interfaces with git has hardcoded assumptions (like, for example, the assumption that the commit hash will be exactly 40 characters long). Some tools parse the output of git log and other commit-bearing commands to make decisions. Will changing git to…

The current plan is for Git to essentially use SHA-1 hashes as aliases for SHA-256, using a lookup table. This would mean that any given SHA-1 hash would, in a particular repository, map to one and only one SHA-256 hash, which is then used to retrieve the object. Eventually the SHA-1 hashes would be deprecated (via a per-repository mode switch, so every Git user or host would migrate according to their preferences).

https://git-scm.com/docs/hash-function-transition/

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

#116

Post by renewiltord »

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…

It is a law of nature that all successful products find themselves not accounting for some predictable problems.

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

#117

Post by FredPret »

fsckboy wrote: post #113
asdfman123 wrote: post #55

Earlier quoted context omitted.

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…

mining bitcoin on one GPU is uneconomical, so mining bitcoin an a large number of them is... also.

Unless your research grant pays for the electricity

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

#118

Post by deckard1 »

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…

> swap out the commit

What's the method for doing this? Does a "git push" replace objects with identical hashes on the remote? Or a "git pull" replace identical hashes on the local repo?

I suspect finding a hash collision is only the first difficult part of actually pulling this off. You may need direct write access to the file system of the target. And even then everyone else that has already fetched the repo may not be impacted. At which point collisions becomes moot because you can rewrite the entire git history however you want.

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

#119

Post by valec »

fsckboy wrote: post #113
asdfman123 wrote: post #55

Earlier quoted context omitted.

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…

mining bitcoin on one GPU is uneconomical, so mining bitcoin an a large number of them is... also.

this is a retarded and pedantic comment. op clearly meant cryptocurrency and put bitcoin as a stand in instead of ethereum, maybe out of ignorance. this comment doesn't address the meat of their comment and contributes nothing.

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

#120

Post by ufo »

noway421 wrote: post #50
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…

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

Post reply on HN