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

131–140 of 210 posts

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

#131

Post by bscphil »

ganzuul wrote: post #91
contravariant wrote: post #61

Earlier quoted context omitted.

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.

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 additional metadata as you like)? The answer is yes: there are simply too many needles.

Take your favorite book with 160 or more characters. (Probably a large book, but such a book could certainly exist.) Now, for each character, create version of the book with their name swapped out for exactly one other name which does not already appear in the book. So if a character is named Alex, in some other edition of the book that character is named Jason.

Now, consider how many editions of the book there are. There are two combinations (for each character) that are exactly alike other than that character's name being swapped out. So there are 2×2 = 4 combinations where two characters' names are swapped. And 2×2×2 = 8 combinations where 3 characters' names are swapped. If you think about how many versions of the book there are in total, it's 2^C, where C is the number of characters whose names can be swapped for only one other name.

In other words, it's guaranteed that you can generate SHA-1 collisions using one book alone, using only entirely reasonable alternative names for its characters.

Too many needles.

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

#132

Post by kragen »

ori_b wrote: post #130
kragen wrote: post #128

Earlier quoted context omitted.

They might not need to commit to your repo to break it using SHA-1 collisions. They might, for example, compute a collision, commit the malicious version to a private GitHub repository, and then send you a patch with the non-malicious version via email, or by sending you a merge request on GitLab. When you accept and merge in their changes and then push to GitHub, perhaps GitHub will recognize the hash of one of your…

The correctness of git is based on hashes not colliding within a repo . This just means GitHub may need to give up on a cost saving measure like dedup between forks It's a GitHub issue, not a git issue.

Agreed. There are lots of other scenarios, though.

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

#133

Post by akomtu »

hyperpape wrote: post #27
akomtu wrote: post #21

Earlier quoted context omitted.

Not so simple. A hash corresponds to infinitely many messages, but how many of them are in ASCII charset under 1KB long? It may happen that each hash has a unique message within these constraints.

Ignoring punctuation, capitalization and spaces, you have (26 ^ 1024) / (2 ^ 160) ascii texts, which is too large for python to do the division. Thinking harder, that's: >>> (13 * (160)) * (26 ** (1024 - 160)) 586015382205826960727672544401463871212215837535709025412643135464856100047507808667927549205890681326798481562717865671371914861707033271010401105757243098374422354323280335989456977123883814519788789676409601…

Good point. I've realized that 2^160 can be just 160 words, each word is a choice of two synonyms.

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

#134

Post by simpleguitar »

I have a question.

Is it not possible to create a good cryptographic hashing algorithm that results in 128bit or 160bit hash?

It seems all the modern, secure ones are 256 bits or larger. Is that because 160 bits is too easy to compute collisions for any algorithm, or are we just not able to fully realize the entropy that can be recorded into 160 (or even 128) bits?

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

#135

Post by asdfman123 »

FredPret wrote: post #117
fsckboy wrote: post #113

Earlier quoted context omitted.

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

Ding ding ding

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

#136

Post by exciteabletom »

valec wrote: post #119
fsckboy wrote: post #113

Earlier quoted context omitted.

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.

> When disagreeing, please reply to the argument instead of calling names. "That is idiotic; 1 + 1 is 2, not 3" can be shortened to "1 + 1 is 2, not 3."

> Be kind. Don't be snarky.

https://news.ycombinator.com/newsguidelines.html

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

#137

Post by CobrastanJorji »

kragen wrote: post #123
tantalor wrote: post #45

Earlier quoted context omitted.

> A higher probability exists that every member of your programming team will be attacked and killed by wolves in unrelated incidents on the same night. - Scott Chacon

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 consideration is much different than if our developers live in Atlanta. Atlanta doesn't have any wild wolves. There is a Wolf's guenon in the zoo, but that probably doesn't count as a risk because they mostly eat small animals and also are monkeys.

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

#138

Post by upofadown »

simias wrote: post #62
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…

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…

If the lead solder is actually functional in some way then they may have to attempt to find an exception under RoHS. They could attempt to define the usage so as to have an application not covered by RoHS for example.

This analogy is kind of confusing because RoHS is an imposed standard. A user of SHA1 is expected to make their own decision about appropriate usage. They might reasonably continue the usage of SHA1 for their specific use case. The real world is full of such compromises.

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

#139

Post by duskwuff »

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…

> I was surprise that no one suggested truncating SHA-256 to 160 bits...

To do that, you have to stop generating commit hashes with SHA-1, breaking compatibility with existing git clients.

And if you're going to do that, you might as well just use the whole SHA-256 hash, since compatibility is out the window already.

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

#140

Post by seoaeu »

lamontcg wrote: post #94
ori_b wrote: post #53

Earlier quoted context omitted.

For someone to be able to break your repo using sha1 collisions, they need to be able to commit to it. If you don't trust someone, don't let them commit to your repo. > Were they so in love with the performance of C/C++ being able to pass around 20 byte hashes on the stack without worrying about a more complicated structure (eg a collection of variable length hashes)? The hashes show up everywhere. They're how every…

Yeah I don't think any of these proposed attacks work without write access to the repo, at which point the game is already pretty much over already.

There's plenty of workflows where untrusted people have their proposed changes audited and then written to a git repo
Post reply on HN