Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Linus on Git and SHA-1

plus.google.com

Post reply on HN
Print view View original

131–140 of 187 posts

Re: Linus on Git and SHA-1

#131

Post by astrodust »

ageofwant wrote: post #121
astrodust wrote: post #120

Earlier quoted context omitted.

The kernel, and OpenSSH to name another project, is full of random crud nobody noticed. Everyone does their best to review patches and ensure things are sane when going in, but there's a lot of change in projects at scale, and sometimes the standards one patch wrangler has are different from another. Mistakes happen. If at-patch time is your only code review, you've got problems. If your code base is too huge to look…

And context is important as well. Worrying about sha-exploits in an environment like this is like wondering whether you watered the plants while the house burns down. The security-theater troupe wails like there's no tomorrow when their buttons get pushed. As Linus, said, given the context and the risk, its of almost no consequence.

I'm in agreement with Linus, but it also highlights problems with code-bases this complex. We depend on code being readable to spot malicious activity. Generating a SHA1 collision to jam in a very subtle bug is highly improbable, and might even be unfeasible if the diff is small enough.

There's certainly a concern if your code is more opaque, as is the case in this bug. If you're taking in raw asm.js code, for example, from various sources...

Re: Linus on Git and SHA-1

#132

Post by usrusr »

chainsaw10 wrote: post #21
bascule wrote: post #3

Linus's transition plan seems to involve truncating SHA-256 to 160-bits. This is bad for several reasons: - Truncating to 160-bits still has a birthday bound at 80-bits. That would still require a lot more brute force than the 2^63 computations involved to find this collision, but it is much weaker than is generally considered secure - Post-quantum, this means there will only be 80-bits of preimage resistance (Also:…

> reversing commit hashes back into their contents Somewhat off topic, but is this actually possible? Given hashing is inherently lossy, I'm inclined to assume it's not possible for anything must longer than a password, but commits are text, which I suppose is low entropy per character, so I don't know.

Most commits are not just text, they are source code. If you had a feasible way to enumerate all the byte sequences that collapse into a given hash value, you might find the subset that is syntactically correct code to be very low. Except if it's Perl, of course.

And the likelihood of all the characters aligning in a way a compiler might find acceptable gets lower with every increase in length of your collisions, so it would be extremely unlikely that the shortest nontrivial match (for both the hash and for code sanity) would not be the right one. The code constraint certainly would not make it easier to find the collision in the first place, but it would give you great confidence in the result of you did.

Re: Linus on Git and SHA-1

#133

Post by posterboy »

Dylan16807 wrote: post #127
posterboy wrote: post #125

Earlier quoted context omitted.

>If somebody inserts random odd generated crud in the middle of your source code, you will absolutely notice. Just as they noticed the intrusion on kernel.org servers after how long? edit: > If an attacker is pushing commits into your repository, you're long since toast on all possible security fronts, right? Sure, that's always true, in the worst case. Perfect security doesn't exist. But does it need to be an attack…

> Just as they noticed the intrusion on kernel.org servers after how long? It doesn't work retroactively. That crud needs to be there in the initial commit when it's accepted by multiple people. > Couldn't it just happen that an important bugfix isn't recorded because the hash collides? The hashes will never collide if there's no attacker. And that bugfix would have to have a blob of crud in the 'good' version, which…

> It doesn't work retroactively. That crud needs to be there in the initial commit when it's accepted by multiple people.

Do you assume that a proper preimage-attack would be needed? Instead, the good looking object could be committed, I guess after reading https://news.ycombinator.com/item?id=13721237

edit:

> And that bugfix would have to have a blob of crud in the 'good' version

Looking at google's POC, the colliding pdfs don't at all stick out (edit: but they are horribly contrived and you talked about code not blobs) [https://shattered.io/]

edit: thanks for your answer, it motivated me to learn a bit more. I'm still not sure if "never" is a rounding error, hyperbole (which would be ill advised talking to laymen), or actual fact (that source files due to the reduced entropy in byte patterns could in fact never ever collide, which I doubt).

Re: Linus on Git and SHA-1

#135

Post by usrusr »

wongarsu wrote: post #71
gkya wrote: post #45

Earlier quoted context omitted.

If a repo contains binary blobs, especially executables, well, that's very bad practices right there. Also, how can somebody else modify a binary in a meaningful way and send a patch to it? How can you review a patch to a binary file before applying? I'd say that any sane project, especially if open source , would not include binaries (maybe apart from images), and even if it did, would not accept patches to them (if…

Executables in git are bad practise, but not all that uncommon. Images in git are the norm, and if somebody comes in and creates a pull request with an improved version of the existing images (better compression, better adapted for color blind people, fixing whitespace issues etc.) that's pretty unsuspicious and likely to succeed (and I've seen it multiple times).

But how would a safer hash improve resistance to that blob update scenario? How would a weaker hash make it more dangerous? If you have a fiercely audited branch next to one that is basically free for all, maybe?

Re: Linus on Git and SHA-1

#136

Post by posterboy »

leoh wrote: post #111
maxander wrote: post #96

I don't really get the threat model here. If an attacker is pushing commits into your repository, you're long since toast on all possible security fronts, right? Is there anything nefarious they could accomplish through hash collisions that couldn't be done simply by editing commit history?

Not really. From Linus — I think the most important point that has not been discussed extensively: > But if you use git for source control like in the kernel, the stuff you really care about is source code, which is very much a transparent medium. If somebody inserts random odd generated crud in the middle of your source code, you will absolutely notice.

> random odd generated crud in the middle of your source code, you will absolutely notice

like non-printing characters in comments?

Or, you know, random odd generated crud https://github.com/torvalds/linux/tree/master/firmware/radeo...

Re: Linus on Git and SHA-1

#137

Post by hannob »

infinity0 wrote: post #122
kupiakos wrote: post #98

Earlier quoted context omitted.

> when a simple s/SHA1/SHA512/g on git would suffice? That's ignoring a huge amount of changes that have to be made to have this work properly. Hardcoded constants must be changed. Backwards compatibility needs to be maintained for Git to be a viable product. Scripts that depend on the current length/format of SHA1 hashes would be broken if everything were changed all of a sudden. That would be much, much worse than…

All git repos have "repositoryversionformat", you can bump it. And nobody is going to complain about having to do a fresh clone, given what just happened. "Not having security eggs in one basket" is exactly irrelevant here. Upgrading the hash does not make the other parts of the system weaker, and should have been done years ago. Yes, SHA2 will also become weak eventually - so then you bump it again. The point is to…

> Yes, SHA2 will also become weak eventually - so then you bump it again.

I disagree here. I doubt SHA2 or any modern hash will become weak within our lifetime. JP Aumasson, who is one of the experts of the field, agrees with me on that: https://twitter.com/veorq/status/834872988445065218

Re: Linus on Git and SHA-1

#138

Post by ProblemFactory »

bascule wrote: post #114
pvg wrote: post #107

Earlier quoted context omitted.

Why would you do that? Even if you don't know exactly what you want, are wrong about whether it's the basis of 'trust', for the purposes of writing git, you'd just take SHA-1. Nothing terrible is going to happen if it's both overkill and you aren't really building a secure system. You seem to be arguing, if I'm understanding you right, that you should only use a cryptographically strong hash iff you need all its prop…

I am likewise perplexed why "cryptographic hash functions are unnecessary in the absence of an attacker" is such a difficult concept for you to grasp. It is not an "odd angle". It is literally the very purpose for which they were created in the first place: to defend against attacks (preimage, collision) If there are no attackers, the cryptography buys you nothing and merely makes the system slower. Again, to go back…

I recently worked on a project where I had to choose a hash function for non-cryptographic error checking. I investigated CRC in detail for it, even wrote two different implementations from scratch.

CRC-X is complicated to use and terrible choice.

First of all, it is not a single algorithm, it is a family of algorithms. For a CRC of size N, you have to also choose a N-bit polynomial, N-bit starting value, and N-bit output XOR value. There is no single standard, there are tens or hundreds of popular options [1]. The optimal polynomial depends on both the CRC size, and the length of the data you are feeding into it [2]. If you choose poor parameters, you will get terrible error detection characteristics (like allowing extra 0 bits at the start of data with no change to the checksum). If you choose good parameters, certain classes of common errors like zeroing out a block of more than N bits will still have much worse characteristics than 1 / 2^N random chance of collision.

Second, implementation in standard libraries is patchy. Most programming languages have some CRC32 implementation - but do not document what parameters they use, or use different notation for the same parameters (forward and reverse), or do not let you change the parameters, or do not let you change the CRC size, or all of these. There is no easy way to get a "standard CRC64 or CRC128" compatible across platforms without putting it together from github snippets and example code yourself.

Third, CRC is fast when implemented in hardware, but not that much faster than SHA-1 or SHA-512 in software. It's only 1.5-2.5x faster [3], and when you're doing one checksum per uploaded file or something, it really does not matter. It's going to be even slower when you don't have a suitable-length CRC available in optimised native code, and have to write it yourself in simple C or pure Python.

The obvious and simple solution is to pick a known popular cryptographic hash like (SHA-X) that is available in the standard library of every programming language under the exact same API and no parameters to configure, truncate its output to the digest size you want, and call it a day. No need to worry about error detection performance on specific error cases like long bursts of zeros, and you get some defense against malicious tampering as a free bonus.

[1] https://en.wikipedia.org/wiki/Cyclic_redundancy_check#Standa...

[2] http://repository.cmu.edu/cgi/viewcontent.cgi?article=1672&c...

[3] https://www.cryptopp.com/benchmarks.html

Re: Linus on Git and SHA-1

#139

Post by knweiss »

CalChris wrote: post #94
bascule wrote: post #78

Earlier quoted context omitted.

There is nothing to be gained from using cryptographic primitives in a non-security context. You could just as easily use e.g. CRC32 for the case you're describing. There is, however, a performance cost in using cryptographic primitives in non-security-related contexts. You may not care about performance, but it certainly matters for something like git. Linus claims: "So in git, the hash is used for de-duplication an…

> There is, however, a performance cost in using cryptographic primitives in non-security-related contexts. You may not care about performance, but it certainly matters for something like git. The performance difference between SHA1 and SHA256 is less than 50%. Unless hashing is a significant percentage of git, which it isn't, this is an insignificant difference. http://atodorov.org/blog/2013/02/05/performance-test-m…

There are better cryptographic hash functions (e.g. Blake2) than SHA1 that are even faster. Check out the "results" slide of this slide deck for the cycles per byte table: https://blake2.net/acns/slides.html

Re: Linus on Git and SHA-1

#140

Post by beagle3 »

bascule wrote: post #78
Anderkent wrote: post #76

Earlier quoted context omitted.

Well, if the cost of computation is not too relevant, and if you don't explicitly need the ability to craft collisions, why would you use a non-cryptographic hash function? Like, when I'm building a lookup index for files, I'm going to use sha-(something), because it's easy and well known. I don't particularly care about the security aspect; I care that everyone immediately knows the contract of sha-1.

There is nothing to be gained from using cryptographic primitives in a non-security context. You could just as easily use e.g. CRC32 for the case you're describing. There is, however, a performance cost in using cryptographic primitives in non-security-related contexts. You may not care about performance, but it certainly matters for something like git. Linus claims: "So in git, the hash is used for de-duplication an…

Probably not. It's just that CRC128/CRC160/CRC256 primitives are not as common as MD5/SHA1/SHA256.

I did not, from Linus' post, get the impression he believes SHA1 are more magical than CRC except in the "image / second primage" sense.

Post reply on HN