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

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

#171

Post by Greek0 » Wed, Oct 13, 2021, 6:10 AM UTC

lokedhs wrote: post #166

throw_away wrote: post #10

Earlier quoted context omitted.

Looks like there's a migration plan for git to SHA-256: https://git-scm.com/docs/hash-function-transition/

Last updated in 2017. What is the current status of this?

As of January 2021, SHA256 repositories are supported, but experimental. They can be created with `git init --object-format sha256`. If I understand correctly, they don't mix at all with SHA1 repositories (i.e. you can't pull/push from/to between SHA1 and SHA256 repos).

See https://stackoverflow.com/questions/65870508/git-and-sha-256

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

#172

Post by HWR_14 » Wed, Oct 13, 2021, 6:19 AM UTC

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.

> Aside from being bullshit, it's also irrelevant, since we're discussing a collision being generated on purpose, not by accident.

I think you just pointed out the error in your own reasoning. This is defending against a deliberate attack. Therefore, your proper odds would be that your programming team is deliberately set upon by 6 different wolves. So, have they offended people who have access to 6 wolves, and the time and inclination to train them (or hire others to) in an effort to pull off a murder spree?

Edit: Actually, the hash attack already assumes motivation and skill. So, I don't know what the odds would have to be computed. That at least one programmer on your team could fight off a trained attack wolf (to whatever level of "training" is the current state of the art for attack wolves)?

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

#173

Post by zzo38computer » Wed, Oct 13, 2021, 6:21 AM UTC

brirec wrote: post #167

zzo38computer wrote: post #157

My idea is a different hash construction, which is 2D construction, which has a infinite internal state and infinite output length. Each row and each column also has a sequence number input, and then there are two mixing up functions (each of which has a finite input and output of equal size than the input); part of the result is propagated horizontally and part of it vertically, so each cell has two inputs and the i…

Reading your post I’m sure you know far more about information theory than I do, so forgive me if this is a stupid question, but… 1. How is infinite internal state and output size possible? There has to be some actual limit for internal state, at least, right? Or else you’ll just run out of memory? 2. Wouldn’t a larger output size risk leaking data? The chance of collision becomes lower, but it also seems to toy with…

1. Because you will probably be truncating the output to a short finite hash, and because each block of internal state only leads in one direction (it affects all later ("up") blocks of internal state for all later ("right") message blocks, but not previous ("left" and "down")), you can optimize it by only implementing the part that you need. So, yes, an actual implementation will be limited, but if you have enough memory and enough time then the limit can be as high as you want to be. (Maybe a diagram might explain it better; I am not sure that this explanation is any good.) (SHAKE also has infinite output (but finite internal state), and when using SHAKE also you would truncate the output to a finite size.)

2. A larger output size might risk leaking data, although I would think it would be difficult.

3A. Like I described, it then needs O(1MB) space and O(1GB) time, so it will be slow. However, I do not expect you should need a hash that long.

3B. I don't know; probably about as predictable as any random number generator, if the hash is designed correctly. (I only describe a construction, and the hash algorithm design involves more than that.)

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

#174

Post by [deleted] » Wed, Oct 13, 2021, 6:36 AM UTC

kragen wrote: post #128

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…

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…

[deleted]

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

#175

Post by wheybags » Wed, Oct 13, 2021, 6:41 AM UTC

dude187 wrote: post #168

sirclueless wrote: post #141

Earlier quoted context omitted.

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.

Well, the contents of the commit is a patch plus metadata. They point to a parent commit, and layer themselves in the tree. The problem would be if a clone doesn't fetch the new version of the patch and generates a new commit that would conflict with the modified commit. You're changing the base all the future diffs are based off of. It might just jumble the source essentially corrupt the file, but I'm not sure.

Contents of a commit is not a patch, it's the whole tree. The got ui presents it as a patch, but that's generated at runtime by the "git diff" command. It does internally use delta compression to save storage space, but it's not necessarily a straight delta between a commit and its direct ancestor (and that's just an internal optimisation).

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

#176

Post by filmor » Wed, Oct 13, 2021, 6:50 AM UTC

formerly_proven wrote: post #57

outworlder wrote: post #41

Earlier quoted context omitted.

> presumably you can later substitute the initial commit with the other one without anybody being able to detect the substitution. How? Which operation would be involved? Will it not show anywhere else(reflog)?

The reflog shows changes to references. References are hashes. Git is CAS, and uses the CAS assumption: H(m1) = H(M2) m1 = m2.

What do you mean by "CAS"?

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

#177

Post by smsm42 » Wed, Oct 13, 2021, 6:58 AM UTC

filmor wrote: post #176

formerly_proven wrote: post #57

Earlier quoted context omitted.

The reflog shows changes to references. References are hashes. Git is CAS, and uses the CAS assumption: H(m1) = H(M2) m1 = m2.

What do you mean by "CAS"?

I think it means Content Addressable Storage - https://en.wikipedia.org/wiki/Content-addressable_storage

In short, it's a method of storage where object's identity is derived from object's content (usually via hashing it). So the assumption is: same hash => same content => same object.

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

#178

Post by slim » Wed, Oct 13, 2021, 7:24 AM UTC

outworlder wrote: post #41

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…

> presumably you can later substitute the initial commit with the other one without anybody being able to detect the substitution. How? Which operation would be involved? Will it not show anywhere else(reflog)?

By replacing the file on disk (you need to have the capability of acquiring access to the server)

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

#179

Post by cerved » Wed, Oct 13, 2021, 7:40 AM UTC

noway421 wrote: post #56

outworlder wrote: post #41

Earlier quoted context omitted.

> presumably you can later substitute the initial commit with the other one without anybody being able to detect the substitution. How? Which operation would be involved? Will it not show anywhere else(reflog)?

`git push --force` I assume. In GitHub, this will leave a trail of events though - Webhook events and auditing.

force push only updates a remote ref if it's not a fast forward. it doesn't do any forced pushing of objects.

you need to modify the object store manually, so access to the filesystem

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

#180

Post by Dylan16807 » Wed, Oct 13, 2021, 8:16 AM UTC

cortesoft wrote: post #150

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…

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.

> 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 injuries are another 10x higher than that. So you'd need somewhere that shark attacks are a thousand or ten thousand times more likely than average. That's also without interpreting "eaten" literally...