5 ms·

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 describ

by bascule 10y ago

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 and error detection, and the 'cryptographic' nature is mainly because a cryptographic hash is really good at those things." CRC produces a distribution just as uniform as a cryptographic hash function, and it's faster to boot. If these are the only things he actually cares about, and he's explicitly discounting security, he's choosing a slower primitive for no reason. He writes off CRC inexplicably earlier in the post: "Other SCM's have used things like CRC's for error detection, although honestly the most common error handling method in most SCM's tends to be 'tough luck, maybe your data is there, maybe it isn't, I don't care'." Linus seems to think that SHA1 has some sort of magic crypto sauce which magically makes the distribution it produces more uniform than CRC's. It doesn't. The only difference is SHA1 was originally designed to be resistant to preimage and collision attacks, both of which are irrelevant outside of a security context.

pvg 10y ago
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.
- bascule 10y ago
  "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 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.
  - pvg 10y ago
    No no, I don't have any requirements, I just did the numbers and missed a zero instead of sensibly looking at a table. But that doesn't change the argument much - if one in a million isn't crazy, one in ten million is not completely insane either. With a 64 bit hash, you probably should write code to deal with a potential collision. Beside the (tiny) chance, someone might legitimately plop some test vectors that collide into a repo, just like the webkit people did the other day. With SHA-1 (in 2005), you can just punt and spend the time you saved yelling at people complaining to you about the choice of SHA-1 on mailing lists. It seems like a pragmatic implementation decision for the time. I'm not trying to defend Linus's somewhat confused explanations, it's just that git's 'security' requirements are somewhat woolly and one could reasonably get away with half-assing it a bit for a while.
    - bascule 10y ago
      If you feel CRC64 does not meet the requirements, use CRC128. For what it's worth, I think CRC64 should be fine for git-like workloads (but would still recommend using a cryptographically secure hash function, because git's usage is security-critical despite Linus constantly insisting it's not).
      - pvg 10y ago
        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 properties. That seems like a really odd angle.
        bascule 10y ago
        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 to the original point: Linus's argument is that cryptographic functions have unique properties that make them specifically useful in non-security contexts. He's wrong. They don't. The non-cryptographic constructions he namedropped then glossed over work fine in these contexts.
CalChris 10y ago
> 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-md5-sha1-sha256-sha512/ http://atodorov.org/blog/2013/02/05/performance-test-md5-sha... Also, you can easily argue that version control is a security context.
- bascule 10y ago
  I absolutely believe git should use a cryptographically secure hash function. But you're completely missing my point, which is about Linus's claims that git's use of SHA1 isn't security-critical, but why he's using a cryptographically secure hash function anyway.
- knweiss 10y ago
  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 https://blake2.net/acns/slides.html
beagle3 10y ago
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.

by bascule 10y ago

pvg 10y ago

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.

bascule 10y ago
"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 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.
- pvg 10y ago
  No no, I don't have any requirements, I just did the numbers and missed a zero instead of sensibly looking at a table. But that doesn't change the argument much - if one in a million isn't crazy, one in ten million is not completely insane either. With a 64 bit hash, you probably should write code to deal with a potential collision. Beside the (tiny) chance, someone might legitimately plop some test vectors that collide into a repo, just like the webkit people did the other day. With SHA-1 (in 2005), you can just punt and spend the time you saved yelling at people complaining to you about the choice of SHA-1 on mailing lists. It seems like a pragmatic implementation decision for the time. I'm not trying to defend Linus's somewhat confused explanations, it's just that git's 'security' requirements are somewhat woolly and one could reasonably get away with half-assing it a bit for a while.
  - bascule 10y ago
    If you feel CRC64 does not meet the requirements, use CRC128. For what it's worth, I think CRC64 should be fine for git-like workloads (but would still recommend using a cryptographically secure hash function, because git's usage is security-critical despite Linus constantly insisting it's not).
    - pvg 10y ago
      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 properties. That seems like a really odd angle.
      - bascule 10y ago
        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 to the original point: Linus's argument is that cryptographic functions have unique properties that make them specifically useful in non-security contexts. He's wrong. They don't. The non-cryptographic constructions he namedropped then glossed over work fine in these contexts.

CalChris 10y ago

> 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-md5-sha1-sha256-sha512/ http://atodorov.org/blog/2013/02/05/performance-test-md5-sha... Also, you can easily argue that version control is a security context.

bascule 10y ago
I absolutely believe git should use a cryptographically secure hash function. But you're completely missing my point, which is about Linus's claims that git's use of SHA1 isn't security-critical, but why he's using a cryptographically secure hash function anyway.
knweiss 10y ago
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 https://blake2.net/acns/slides.html

beagle3 10y ago

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.