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

81–90 of 187 posts

Re: Linus on Git and SHA-1

#81

Post by logicallee »

bascule wrote: post #63
infinity0 wrote: post #58

Earlier quoted context omitted.

> "A hash that is used for security is basically a statement of trust [..] In contrast, in a project like git, the hash isn't used for "trust". I don't pull on peoples trees because they have a hash of a4d442663580. Our trust is in people, and then we end up having lots of technology measures in place to secure the actual data." This is horseshit, and Linus should not be saying these hugely misleading statements abou…

Yes, exactly. If Linus truly doesn't care about security, then git could use any error correcting code that produces a uniform distribution of tags, such as CRC64. The size of the tag only affects the number of objects we'd expect to be able to commit before we see a collision: over 4 billion in the case of CRC64. Linux mistakenly claims using a cryptographic hash function helps avoid non-malicious collisions, but th…

>Linux mistakenly claims using a cryptographic hash function helps avoid non-malicious collisions, but this is not the case.

of course it does. It is using a different field (cryptography) as a CRC that "really, really won't collide" because there is a whole field (cryptography) that is completely busted if it does.

Let me put it this way. If I really, really need a random distribution of white noise, I might use a different field, cryptography, to provide it: because if the distribution is not effectively random and uniformly distributed, that field in some fundamental sense is broken: no information is supposed to make it into the ciphertext, it should be indistinguishable from white noise.

So encrypting your source of white noise for the sole purpose of making it statistically closer to noise is a perfectly valid choice.

Actually in your commment you said it yourself: in as little as four billion commits CRC64 expects to see a collision. That is tiny compared to the search space cryptographers work with.

If you look at the history of git there was originally no reason to use cryptographic functions except in the same way as the analogy I just made (for white noise): he borrowed a property from a different field from the one he was working in.

Re: Linus on Git and SHA-1

#82

Post by jmount »

Probably isn'y the sky falling. But if knowing the length fixed all hash function issues then cryptographic hashes would just use a some more bits for length.

Re: Linus on Git and SHA-1

#83

Post by yawaramin »

eslaught wrote: post #17
tytso wrote: post #4

Earlier quoted context omitted.

That's not the plan. That was an idea that was thrown out if this was an emergency (it's handling different length hashes, and doing so that we don't have to force a flag day conversion which is hard), but once people realized that in fact, the sky was not following, the plan which Linus outlined in his G+ post was devised --- which does not involve truncating a 256-bit hash.

Can you link the new plan? I didn't see it described in his G+ post.

The G+ post was not meant to describe the plan, it was an overview of the situation for git users who aren't necessarily security experts.

The plan is outlined at https://marc.info/?l=git&m=148787163023435&w=2

Re: Linus on Git and SHA-1

#84

Post by bascule »

logicallee wrote: post #81
bascule wrote: post #63

Earlier quoted context omitted.

Yes, exactly. If Linus truly doesn't care about security, then git could use any error correcting code that produces a uniform distribution of tags, such as CRC64. The size of the tag only affects the number of objects we'd expect to be able to commit before we see a collision: over 4 billion in the case of CRC64. Linux mistakenly claims using a cryptographic hash function helps avoid non-malicious collisions, but th…

>Linux mistakenly claims using a cryptographic hash function helps avoid non-malicious collisions, but this is not the case. of course it does. It is using a different field (cryptography) as a CRC that "really, really won't collide" because there is a whole field (cryptography) that is completely busted if it does. Let me put it this way. If I really, really need a random distribution of white noise, I might use a d…

You seem to be operating under the same sort of "cryptographic hash functions are magic!" delusions as Linus.

CRC and SHA1 both produce a uniform distribution. SHA1 does not magically do this better because cryptography. The only things that make CRC and SHA1 are any different are:

  - SHA1 produces a longer tag (of course CRC256 is a thing)
  - SHA1 is hardened against preimage attacks
  - SHA1 was intended to be secure against collision attacks (not anymore!)
SHA1, truncated to 32 or 64-bits, will produce a distribution just as uniform as CRC.

In a non-security setting, we can pick the size of the tag based on the rough number of objects we'd like to be able to store before we'd expect to see a collision (i.e. the birthday bound). If that number is ~4 billion, then CRC64 is sufficient.

Re: Linus on Git and SHA-1

#85

Post by [deleted] »

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

[deleted]

Re: Linus on Git and SHA-1

#86

Post by pvg »

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…

You can still make a not-totally-unreasonable argument that something like CRC64 is simply too small - that maybe the 1 in a million collision chance for a few million hashes is too high. The fast, keyed 'semi-cryptographic' big hashes that are common now weren't around when git was written so the easiest thing to reach for would have been something like SHA-1.

Re: Linus on Git and SHA-1

#87

Post by iamgopal »

keeperofdakeys wrote: post #68
theseoafs wrote: post #34

Have there been writings on what exactly git's migration strategy to a new hash function will be? Apparently they have a seamless transition designed that won't require anyone to update their repositories, which seems like a pretty crazy promise in the absence of details.

In git the SHA-1 hash is simply an identifier for an object - it's used in the filename, but not stored in the object. And when a commit or tree object references others, it's just a name that can be looked up in the database. So a commit object hashed with SHA-256 can easily reference a previous commit that was hashed with SHA-1. During the switch, a bit of deduplication may be lost. But the only interesting issue I…

Git update repo kind of command may be ??

Re: Linus on Git and SHA-1

#88

Post by ploxiln »

infinity0 wrote: post #58
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:…

> "A hash that is used for security is basically a statement of trust [..] In contrast, in a project like git, the hash isn't used for "trust". I don't pull on peoples trees because they have a hash of a4d442663580. Our trust is in people, and then we end up having lots of technology measures in place to secure the actual data." This is horseshit, and Linus should not be saying these hugely misleading statements abou…

You're saying Linus's statements are "hugely misleading", but it's just that you wish git were designed to be used differently. So, your argument is "horseshit".

Linus could have designed a cryptographically perfect system such that he could pull Tytso's signed commit from anywhere on the internet - but he didn't

Linus used sha1 as a useful tool for an effective DVCS with an initially simple implementation.

He still depends on the security of the kernel.org servers, his work computers, and the top submaintainer's work computers. His git trees and all the submaintainers he pulls from are hosted on kernel.org servers. Security of the kernel.org servers is taken very seriously, especially since the well-known break-in a few years ago. Now even two-factor auth is involved in all git pushes to kernel.org servers. Sub-maintainers make pull-requests by branch name - "please pull branch for-linus ...". More peripheral contributors submit their work via patches on LKML, no commit hashes involved.

Finally, no well-known SCM previous to git was based on perfect cryptographic proof of source history, or anything like that. It wasn't a big issue, and it's not the problem git focused on solving. Before git, we all used CVS, SVN, tarballs, and patches. And a significant portion of developers did not use any VCS at all. How could any of us have trusted any source code before 2005?! Somehow we did, though...

Re: Linus on Git and SHA-1

#89

Post by azernik »

infinity0 wrote: post #58
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:…

> "A hash that is used for security is basically a statement of trust [..] In contrast, in a project like git, the hash isn't used for "trust". I don't pull on peoples trees because they have a hash of a4d442663580. Our trust is in people, and then we end up having lots of technology measures in place to secure the actual data." This is horseshit, and Linus should not be saying these hugely misleading statements abou…

This should really be a top-level comment.

Re: Linus on Git and SHA-1

#90

Post by bascule »

pvg wrote: post #86
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…

You can still make a not-totally-unreasonable argument that something like CRC64 is simply too small - that maybe the 1 in a million collision chance for a few million hashes is too high. The fast, keyed 'semi-cryptographic' big hashes that are common now weren't around when git was written so the easiest thing to reach for would have been something like SHA-1.

"maybe the 1 in a million collision chance for a few million hashes is too high"

Well, let's look at what the actual numbers are. There's a nice table on this page:

https://en.wikipedia.org/wiki/Birthday_attack

For a 64-bit tag, even with 6,100,000 objects we'd only have a 1 in 10 million chance of a collision, so a 64-bit tag is more than sufficient to meet your stated requirements.

Post reply on HN