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

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

#191

Post by api » Wed, Oct 13, 2021, 11:08 AM UTC

tialaramex wrote: post #67

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…

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

Git != GitHub

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

#192

Post by kragen » Wed, Oct 13, 2021, 11:09 AM UTC

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…

That's a good point! I didn't think about either of those issues. The second one raises the average team's chances of such a spate of unrelated attacks significantly, if anything related to this formula could be said to be significant, because the increase in risk to teams in West Bengal and Ukraine is enormously larger than the decrease in risk to teams in Atlanta.

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

#193

Post by kragen » Wed, Oct 13, 2021, 11:10 AM UTC

xinniethepooh wrote: post #161

perl4ever wrote: post #160

Earlier quoted context omitted.

There was an organization devoted to reintroducing wolves to the northeastern US, but I don't believe they found it politically feasible. However, I have seen (and photographed) something I called a coyote, but others insisted was a wolf. It has been asserted that coyotes tend to evolve to resemble wolves, when there are none in an ecosystem.

Wolves are slowly coming back, they were recently taken off the endangered species list in Idaho, Wyoming, and Montana.[1] [1] https://www.nps.gov/yell/learn/nature/wolves.htm

For whatever reason, American wolves attack people much, much less frequently than Eurasian wolves.

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

#194

Post by kragen » Wed, Oct 13, 2021, 12:10 PM UTC

Jensson wrote: post #183

Dylan16807 wrote: post #180

Earlier quoted context omitted.

> that REALLY depends on where you are There's only 10 fatal shark attacks per year. What's your calculation for the sharkiest area to live? It has to be something like 100+ times sharkier than average for your claim to be true. And keep in mind that half the US population can easily day trip to the ocean. Edit: Actually, that's using a number of 2000 lightning fatalities which might be 10x too low. And lightning inj…

You focused on the shark side and not on the lightning side. You will never get struck by lightning in a city, so there the probability is 0. Similarly if you go out swimming in the ocean on a sunny day the probability of getting struck by lightning is also 0, but the probability of getting eaten by a shark is not 0.

0 is not a probability; trying to use it as one leads to division-by-zero errors.

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

#195

Post by oshiar53-0 » Wed, Oct 13, 2021, 1:46 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…

FYI signed git commits and tags weren't a thing back then.

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

#196

Post by account42 » Wed, Oct 13, 2021, 2:28 PM UTC

sirclueless wrote: post #141

dude187 wrote: post #126

Earlier quoted context omitted.

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.

It's true that semantically git commits store the whole tree but doing that naively would be inefficient. Instead, packfiles will store some objects as deltas which could either result in inconsitencies or noticeable knock-on changes if the original object contents are changed.

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

#197

Post by ganzuul » Wed, Oct 13, 2021, 2:50 PM UTC

dTal wrote: post #107

ganzuul wrote: post #81

Earlier quoted context omitted.

Your examples really fall out of the scope of the premise.

Forgive me if I've misunderstood - the premise was that, out of the infinite set of data that hashes to a particular hash/checksum, there is a unique data set that is "obviously" the real one? Or at least, that the set is meaningfully bounded? My reply is that this is not the case. There will be infinitely many "plausible" data sets as well. You could collide every hash in existence merely by making undetectably tiny…

Not obviously, no. - Just a very high probability. Perhaps that provides noise immunity to some degree. If it does, it is a form of AI.

This admittedly open question presumes a very large fuzzy 'code book' with which it can re-assemble the data. The length of the input in cleartext is valuable metadata that speeds up the search.

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

#198

Post by ganzuul » Wed, Oct 13, 2021, 3:00 PM UTC

bscphil wrote: post #131

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…

I understand your confusion, because it took me a minute to think about it and confirm that this doesn't work. It might be surprising that even a machine with complete information and infinite compute power couldn't pick out the needle; after all, SHA-1 is a 160 bit hash. Are there really 2^160 ≈ 10^48 different texts in English that could reasonably have been written by someone living on Earth (add as much additiona…

Taking a book and randomly swapping words means you are introducing noise. This is high-entropy and really it's outside the scope of what I'm comfortable speculating on.

Image data is much simpler to think about in this paradigm, but the obvious AI applications of natural language are of course fascinating.

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

#199

Post by dTal » Wed, Oct 13, 2021, 3:10 PM UTC

ganzuul wrote: post #197

dTal wrote: post #107

Earlier quoted context omitted.

Forgive me if I've misunderstood - the premise was that, out of the infinite set of data that hashes to a particular hash/checksum, there is a unique data set that is "obviously" the real one? Or at least, that the set is meaningfully bounded? My reply is that this is not the case. There will be infinitely many "plausible" data sets as well. You could collide every hash in existence merely by making undetectably tiny…

Not obviously, no. - Just a very high probability. Perhaps that provides noise immunity to some degree. If it does, it is a form of AI. This admittedly open question presumes a very large fuzzy 'code book' with which it can re-assemble the data. The length of the input in cleartext is valuable metadata that speeds up the search.

You still seem to be missing the point. The problem is that the SHA-1 hash is one of 2^160 possible values, while a 1GB plaintext is one of 2^8000000000 possible values. That means that the hash disambiguates your message down to one of 2^7999999840 values.

Let's go smaller. Let's say our plaintext is a single kilobyte. One 80x25 terminal's worth of ASCII. Knowing the SHA-1 hash narrows our search space, yes, but the search space is so absurdly large that it only solves 0.0000... (insert over two thousand zeros here) ..0001% of the problem.

It tells you basically nothing.

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

#200

Post by CobrastanJorji » Wed, Oct 13, 2021, 4:38 PM UTC

nkmnz wrote: post #162

CobrastanJorji wrote: post #137

Earlier quoted context omitted.

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…

Plot twist: two developers of your remote team live in Rome and have been raised by a female wolf. How to account for that?

This is problematic because it must be 2774 years ago, when wolve attacks were substantially more common. I'm also not thrilled that a good chunk of my dev team lives near the Lupercal. The one good piece of news is that at least one of my headcount is fated to die by the hand of man, which might bring the odds of simultaneous wolf attack deaths down to zero unless he quits beforehand.