4 ms·

I understand the 32-bit time not being a good idea, but why is SHA-1 bad for a non-cryptographic application?

by nsm 11y ago

dchest 11y ago
Because a hash function in version control system is a cryptographic application — it's important to be able to verify the integrity of repository.
- nsm 11y ago
  Thanks. I am having trouble understanding how crypto would help (I did read [0]). The hash and the files are stored in the same repository. If an attacker edited a file, couldn't they update the hashes of that commit and everything related to it? [0] http://ericsink.com/vcbe/html/cryptographic_hashes.html http://ericsink.com/vcbe/html/cryptographic_hashes.html
  - __david__ 11y ago
    Yes, they could, but that's not exciting (that's really what `git --amend` and `git rebase` are, after all). What's interesting from an attacker point of view is changing the contents of the file (in a meaningful way) without changing the hash. That way anyone who pulls from you gets a different copy of the code, but they won't easily discover if since the hash is the same as the original copy. Think about what happens if you were to fork a copy of something on github and then rebase to edit one of the commits. If I pulled from your copy and the pulled from the official repo I'd get a merge (and probably some conflicts) because git identifies commits by their sha and uses that to decide what needs to be merged. But if you managed to change one of your commits without changing the sha, then I'd have a much harder time detecting it, since when I pulled from another repo later there would be no merge (even though things were actually different).
- rbehrends 11y ago
  This doesn't make sense in a patch-based VCS, where you can at best verify the integrity of individual deltas, but where there isn't a repository state that you can hash (cryptographically or otherwise) to begin with.
  - dchest 11y ago
    If integrity of deltas is not important, why use SHA-1? Why not MD5? ;) There are modern cryptographic hash functions, such as BLAKE2, that are faster than it, and I'm not even talking about non-cryptographic functions, which are many times faster.
    - rbehrends 11y ago
      Because in the end it doesn't matter much, other than that the probability of accidental collisions is low? Speed doesn't matter, because it's primarily used to look up a file, and I/O will dominate that. SHA-1 is known to work (Git, Mercurial), so what's the point in overengineering this particular implementation detail? The integrity of deltas doesn't matter much because if you have a process for maliciously inserting a falsified patch, you can generally also simply insert a genuine patch (where it's trivial to get even the most complicated cryptographic checksum right) that will be combined with the rest (because the state of the repository is the combination of the patches in it, and whether you replace one or add a different one is largely irrelevant in this context).
- crpatino 11y ago
  I think the GP question is not trivial. The rationale behind SHA-1 being obsolete is that it will be used for password protection. The back end stores Hash(password+salt) and uses it to grant access. Finding any password_prime which causes a collision with password on Hash(p+salt) will brake the security of that scheme. In this case, instead, the problem from the point of view of the attacker is to find repository_prime such that... 1. Is a syntactically correct program... 2. It is syntactically and semantically close enough to repository_orig that it will not be discovered by simple inspection. 3. The delta between repository_prime and repostory_orig causes a useful side effect in the program behavior (from the point of view of the attacker). 4. The delta between repository_prime and repostory_orig does not introduce other significant and unintended side effects that will trigger investigation beyond simple inspection from some legitimate maintainer. I will say that this is a much higher bar to cross than merely "no collision shall be found". And if you are concerned that SHA-1 is not enough to protect against such attack, you probably have to consider that SHA-2 may not be enough either... You probably need to use half a dozen of cryptographically strong hash functions, preferably based on different principles, so that we ensure that at no possible delta can simultaneously fulfill all the 4 points above for every hash function. And if you have reached that level of paranoia, you need to consider that the adversary will simply not bother and chose a different attack vector, like exploiting the bureaucracy of your commit process...
  - lomnakkus 11y ago
    ... and yet SHA-256 would cost basically nothing to use instead. While your argument "for" SHA-1 requires all kinds of qualifiers and assumptions. Just say no to SHA-1.
  - dchest 11y ago
    First of all, this has nothing to do with passwords. Indeed, this may be a higher bar to cross, but higher bars are usually being crossed. For years we known that RC4 had biases, but it was considered okay until we discovered that it was not okay after all. MD5 collisions led to rogue certificates. It's not correct that SHA-2 is not enough to fix the issue. While they share some design structure, SHA-2 is not broken, while SHA-1 is. Also, the proposal for multiple hash functions isn't particularly good: collision resistance of many cascaded hash functions is not much better than the maximal resistance of one hash function used in the cascade. It doesn't make sense to use a broken cryptographic hash function in a new project that does need cryptography. There are faster modern cryptographic hashes than SHA-1. And it doesn't make sense to use a broken cryptographic hash function in a new project that doesn't need cryptography. There are faster modern non-cryptographic hashes than SHA-1. To be fair, I don't know why we even have a discussion about this if cryptographers say that SHA-1 shouldn't be used, and you're trying to defend this choice for exactly what reason?

I understand the 32-bit time not being a good idea, but why is SHA-1 bad for a non-cryptographic application?

by nsm 11y ago

I understand the 32-bit time not being a good idea, but why is SHA-1 bad for a non-cryptographic application?

Because a hash function in version control system is a cryptographic application — it's important to be able to verify the integrity of repository.

nsm 11y ago
Thanks. I am having trouble understanding how crypto would help (I did read [0]). The hash and the files are stored in the same repository. If an attacker edited a file, couldn't they update the hashes of that commit and everything related to it? [0] http://ericsink.com/vcbe/html/cryptographic_hashes.html http://ericsink.com/vcbe/html/cryptographic_hashes.html
- __david__ 11y ago
  Yes, they could, but that's not exciting (that's really what `git --amend` and `git rebase` are, after all). What's interesting from an attacker point of view is changing the contents of the file (in a meaningful way) without changing the hash. That way anyone who pulls from you gets a different copy of the code, but they won't easily discover if since the hash is the same as the original copy. Think about what happens if you were to fork a copy of something on github and then rebase to edit one of the commits. If I pulled from your copy and the pulled from the official repo I'd get a merge (and probably some conflicts) because git identifies commits by their sha and uses that to decide what needs to be merged. But if you managed to change one of your commits without changing the sha, then I'd have a much harder time detecting it, since when I pulled from another repo later there would be no merge (even though things were actually different).
rbehrends 11y ago
This doesn't make sense in a patch-based VCS, where you can at best verify the integrity of individual deltas, but where there isn't a repository state that you can hash (cryptographically or otherwise) to begin with.
- dchest 11y ago
  If integrity of deltas is not important, why use SHA-1? Why not MD5? ;) There are modern cryptographic hash functions, such as BLAKE2, that are faster than it, and I'm not even talking about non-cryptographic functions, which are many times faster.
  - rbehrends 11y ago
    Because in the end it doesn't matter much, other than that the probability of accidental collisions is low? Speed doesn't matter, because it's primarily used to look up a file, and I/O will dominate that. SHA-1 is known to work (Git, Mercurial), so what's the point in overengineering this particular implementation detail? The integrity of deltas doesn't matter much because if you have a process for maliciously inserting a falsified patch, you can generally also simply insert a genuine patch (where it's trivial to get even the most complicated cryptographic checksum right) that will be combined with the rest (because the state of the repository is the combination of the patches in it, and whether you replace one or add a different one is largely irrelevant in this context).
crpatino 11y ago
I think the GP question is not trivial. The rationale behind SHA-1 being obsolete is that it will be used for password protection. The back end stores Hash(password+salt) and uses it to grant access. Finding any password_prime which causes a collision with password on Hash(p+salt) will brake the security of that scheme. In this case, instead, the problem from the point of view of the attacker is to find repository_prime such that... 1. Is a syntactically correct program... 2. It is syntactically and semantically close enough to repository_orig that it will not be discovered by simple inspection. 3. The delta between repository_prime and repostory_orig causes a useful side effect in the program behavior (from the point of view of the attacker). 4. The delta between repository_prime and repostory_orig does not introduce other significant and unintended side effects that will trigger investigation beyond simple inspection from some legitimate maintainer. I will say that this is a much higher bar to cross than merely "no collision shall be found". And if you are concerned that SHA-1 is not enough to protect against such attack, you probably have to consider that SHA-2 may not be enough either... You probably need to use half a dozen of cryptographically strong hash functions, preferably based on different principles, so that we ensure that at no possible delta can simultaneously fulfill all the 4 points above for every hash function. And if you have reached that level of paranoia, you need to consider that the adversary will simply not bother and chose a different attack vector, like exploiting the bureaucracy of your commit process...
- lomnakkus 11y ago
  ... and yet SHA-256 would cost basically nothing to use instead. While your argument "for" SHA-1 requires all kinds of qualifiers and assumptions. Just say no to SHA-1.
- dchest 11y ago
  First of all, this has nothing to do with passwords. Indeed, this may be a higher bar to cross, but higher bars are usually being crossed. For years we known that RC4 had biases, but it was considered okay until we discovered that it was not okay after all. MD5 collisions led to rogue certificates. It's not correct that SHA-2 is not enough to fix the issue. While they share some design structure, SHA-2 is not broken, while SHA-1 is. Also, the proposal for multiple hash functions isn't particularly good: collision resistance of many cascaded hash functions is not much better than the maximal resistance of one hash function used in the cascade. It doesn't make sense to use a broken cryptographic hash function in a new project that does need cryptography. There are faster modern cryptographic hashes than SHA-1. And it doesn't make sense to use a broken cryptographic hash function in a new project that doesn't need cryptography. There are faster modern non-cryptographic hashes than SHA-1. To be fair, I don't know why we even have a discussion about this if cryptographers say that SHA-1 shouldn't be used, and you're trying to defend this choice for exactly what reason?