5 ms·

> This was fun, but my gut reaction to the title was “it doesn’t have to be easy, just possible” and that holds. It really depends why you’re hashing and what

> This was fun, but my gut reaction to the title was “it doesn’t have to be easy, just possible” and that holds. It really depends why you’re hashing and what the consequences of a collision are. Using a hashing algorithm to protect sensitive data (should I hash passwords with SHA-1?) should weight the value of this answer significantly differently than using it as a convenient lookup optimization (should I use SHA-1 to identify git references?). And there’s a spectrum between those, where that convenience might be an attack surface (can I impersonate someone’s git commit?) or might be worth the risk (does it matter if I can easily find a collision?). Unless I’ve missed some new proof, it should be assumed the answer to “is it possible?” will likely always be yes. The question then becomes “has the known wisdom on the following questions changed since I last asked?”, followed in no specific order by, “how plausible is the collision? how much do I care if it happens? how motivated are people to find it? are there other plausible mitigations in place? is the known wisdom on these questions likely to change in a way meaningful to me? how soon?”

l33t2328 5y ago
It is always possible to generate a collision for any hash function since they are not injective by definition.
- eyelidlessness 5y ago
  My point wasn’t to address whether any hashing technique might be collision-free, but that assessing that fact is not a good metric for the fitness of a given hashing technique.
naniwaduni 5y ago
> Using a hashing algorithm to protect sensitive data (should I hash passwords with SHA-1?) You're almost certainly fine! A collision oracle doesn't actually make it any easier to conduct a preimage attack. We normally recommend against using hashing algorithms with known collision attacks for password hashing because (a) these hashes aren't well-suited to password hashing in the first place (b) because having a collision attack implies structural weakness and you don't really want to be caught relying on that hash if a preimage attack does turn up (c) as a fashion statement. > using it as a convenient lookup optimization (should I use SHA-1 to identify git references?) Now this is a bad idea, because having collisions in the wild means that someone can swap out one for the other without the hash catching it, so now you need to build in extra complexity to mitigate that. (Of course, collisions always exist in theory, so you want to design around the possibility. The difference having collisions in the wild makes is that as long as they're only theoretical, you can get away with e.g. screaming loudly about running into an impossible situation and guarantee that you don't do something actively dangerous, or falling back to something horrendously slow but always correct; once collisions exist in the wild, that's a denial-of-service.)
- eyelidlessness 5y ago
  > Now this is a bad idea Somebody better tell Linus? I kid. But yeah the answer is you use it as part of your lookup and then mitigate collisions with more expensive comparisons.
  - usr1106 5y ago
    He was told weeks after git was published, I guess 2005. Sorry, no link handy. They are working on it since 2017. https://github.com/bk2204/git/commits/transition-stage-4/Documentation/technical/hash-function-transition.txt https://github.com/bk2204/git/commits/transition-stage-4/Doc... Not that it's particularly urgent...
  - dezren39 5y ago
    It's a non-issue he's addressed many times. What happens after you collide a single hash, you need to have a useful commit that isn't going to destroy the ability of the code to run AND do something useful to you, etc etc? Also what happens after the next commit, where all the hashes recalculate? It's possible to be an issue, but highly improbable. More likely your creds are hacked or the fact that no one signs their commits finally bites us on a wide scale.
  - naniwaduni 5y ago
    Well, it's well known since basically as soon as git was published and determined to have not been a big deal, with work on the way ever since an actual collision was published. Anyway, practically you're going to write a collision fallback anyway, the difference is that as long as collisions aren't likely, you can be pretty sure that collision handling is a very cold code path that's never going to have more than a handful of items in a bucket. The point I'm trying to make, though, is that while practical collision attacks do have practical implications, they aren't relevant to password hashing. People routinely assume that collision attacks make a hash unsuitable for password hashing. They're not exactly wrong, but it's kind of a non sequitur. I felt that this was a point that had to be made because the framing of parent ("what the consequences of a collision are") implied that the expected answers were exactly the opposite.
- 5y ago
jmyeet 5y ago
The interesting thing about your comment is that you view password hashing as needing more security but git commit hashes to be less of an issue. I couldn't disagree more. First, for a password hash function to matter, the hashed password must be compromised. If you don't have the hash it doesn't really matter all that much. Yes, hashed passwords do get compromised but many don't. Second, I can't think of many bigger security threats than intentionally creating an SHA1 collision for a git repository. Poisoning a Linux git repo could be truly disastrous. Remember too that if you can poison a git repo, you can also make the binary output have the same size and hash too. I mean that's much more difficult but not impossible and it wouldn't surprise me if state actors have dedicated a lot of computing power to this. And "is it possible?" is by definition always "yes".
- eyelidlessness 5y ago
  > The interesting thing about your comment is that you view password hashing as needing more security but git commit hashes to be less of an issue. I do? I should have been more clear that I think this is another case which very much depends on the other considerations I addressed and probably many more. > And "is it possible?" is by definition always "yes". You’re not the only person to say so, and… I know. I left the possibility open in my response mainly because I wanted to focus on the other considerations without dismissing the parent comment. Even if the answer was less definitive I believe considering level and degree of risk should be a bigger factor in these conversations than what’s theoretically possible.
- Salgat 5y ago
  The issue is that your commit still has to do something useful and have the proper colliding hash, which dramatically increases the effective collision complexity for something that is already nearly impossible to occur. Sure you could have some garbage commit with a colliding hash, but all that means is an inconvenience while they remove that commit.
  - m_eiman 5y ago
    Well, you can just comment out the garbage you create to match the hash so that's not a big problem in the case of source code. Creating a correct binary file may or may not be a bigger problem, depending on the file format.

l33t2328 5y ago

It is always possible to generate a collision for any hash function since they are not injective by definition.

eyelidlessness 5y ago
My point wasn’t to address whether any hashing technique might be collision-free, but that assessing that fact is not a good metric for the fitness of a given hashing technique.

naniwaduni 5y ago

> Using a hashing algorithm to protect sensitive data (should I hash passwords with SHA-1?) You're almost certainly fine! A collision oracle doesn't actually make it any easier to conduct a preimage attack. We normally recommend against using hashing algorithms with known collision attacks for password hashing because (a) these hashes aren't well-suited to password hashing in the first place (b) because having a collision attack implies structural weakness and you don't really want to be caught relying on that hash if a preimage attack does turn up (c) as a fashion statement. > using it as a convenient lookup optimization (should I use SHA-1 to identify git references?) Now this is a bad idea, because having collisions in the wild means that someone can swap out one for the other without the hash catching it, so now you need to build in extra complexity to mitigate that. (Of course, collisions always exist in theory, so you want to design around the possibility. The difference having collisions in the wild makes is that as long as they're only theoretical, you can get away with e.g. screaming loudly about running into an impossible situation and guarantee that you don't do something actively dangerous, or falling back to something horrendously slow but always correct; once collisions exist in the wild, that's a denial-of-service.)

eyelidlessness 5y ago
> Now this is a bad idea Somebody better tell Linus? I kid. But yeah the answer is you use it as part of your lookup and then mitigate collisions with more expensive comparisons.
- usr1106 5y ago
  He was told weeks after git was published, I guess 2005. Sorry, no link handy. They are working on it since 2017. https://github.com/bk2204/git/commits/transition-stage-4/Documentation/technical/hash-function-transition.txt https://github.com/bk2204/git/commits/transition-stage-4/Doc... Not that it's particularly urgent...
- dezren39 5y ago
  It's a non-issue he's addressed many times. What happens after you collide a single hash, you need to have a useful commit that isn't going to destroy the ability of the code to run AND do something useful to you, etc etc? Also what happens after the next commit, where all the hashes recalculate? It's possible to be an issue, but highly improbable. More likely your creds are hacked or the fact that no one signs their commits finally bites us on a wide scale.
- naniwaduni 5y ago
  Well, it's well known since basically as soon as git was published and determined to have not been a big deal, with work on the way ever since an actual collision was published. Anyway, practically you're going to write a collision fallback anyway, the difference is that as long as collisions aren't likely, you can be pretty sure that collision handling is a very cold code path that's never going to have more than a handful of items in a bucket. The point I'm trying to make, though, is that while practical collision attacks do have practical implications, they aren't relevant to password hashing. People routinely assume that collision attacks make a hash unsuitable for password hashing. They're not exactly wrong, but it's kind of a non sequitur. I felt that this was a point that had to be made because the framing of parent ("what the consequences of a collision are") implied that the expected answers were exactly the opposite.
5y ago

jmyeet 5y ago

The interesting thing about your comment is that you view password hashing as needing more security but git commit hashes to be less of an issue. I couldn't disagree more. First, for a password hash function to matter, the hashed password must be compromised. If you don't have the hash it doesn't really matter all that much. Yes, hashed passwords do get compromised but many don't. Second, I can't think of many bigger security threats than intentionally creating an SHA1 collision for a git repository. Poisoning a Linux git repo could be truly disastrous. Remember too that if you can poison a git repo, you can also make the binary output have the same size and hash too. I mean that's much more difficult but not impossible and it wouldn't surprise me if state actors have dedicated a lot of computing power to this. And "is it possible?" is by definition always "yes".

eyelidlessness 5y ago
> The interesting thing about your comment is that you view password hashing as needing more security but git commit hashes to be less of an issue. I do? I should have been more clear that I think this is another case which very much depends on the other considerations I addressed and probably many more. > And "is it possible?" is by definition always "yes". You’re not the only person to say so, and… I know. I left the possibility open in my response mainly because I wanted to focus on the other considerations without dismissing the parent comment. Even if the answer was less definitive I believe considering level and degree of risk should be a bigger factor in these conversations than what’s theoretically possible.
Salgat 5y ago
The issue is that your commit still has to do something useful and have the proper colliding hash, which dramatically increases the effective collision complexity for something that is already nearly impossible to occur. Sure you could have some garbage commit with a colliding hash, but all that means is an inconvenience while they remove that commit.
- m_eiman 5y ago
  Well, you can just comment out the garbage you create to match the hash so that's not a big problem in the case of source code. Creating a correct binary file may or may not be a bigger problem, depending on the file format.