3 ms·

> 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 m

> 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.
_nalply 5y ago
One concrete example is using hashes as identifier for objects. It is possible that this a bad idea because of collisions. However, if you have for example a federated system you don't have a central instance issuing identifiers for objects. So you create a hash. In reality it doesn't matter if you used SHA1, MD5 or even a random identifier. As long as you have enough bits, a collision becomes unlikely. However again, if you have many objects consider the birthday paradox. The interesting thing here is that this is an issue in any case: Even if you have an extremely secure hash algorithm, in the end you have less bits than the original data, so collisions must occur, even if they are immensely improbable. If you then decide that you ignore collisions because after considering the birthday paradox collisions won't occur practically it can be worth thinking about what would happen if such a collision does occur. Let's say your application executes a database update and has a hash collision. Then another object would be overwritten. This is a use case of not mixing object creation and object update. If you program carefully such that you never overwrite another object if you update your object you'll get an internal error if you have a hash collision. That's better than losing unrelated data. However this is difficult to test. And I am sure that other bugs are a lot more probable. But this thinking shows me that it is useful to program defensively. If you have assumptions, encode them in assertions. So even if you don't have tests for this rare problem, your chance of being lucky is higher.
- blincoln 5y ago
 However, if you have for example a federated system you don't have a central instance issuing identifiers for objects. So you create a hash. In reality it doesn't matter if you used SHA1, MD5 or even a random identifier. But it does matter. Usually it's only a big problem in edge cases, but sometimes those edge cases are extremely important. TLS certificates use a hash as their identifier in a distributed/federated model like you describe. By generating collisions, one can submit a normal signing request to a trusted public CA, but then use the resulting signature with a second certificate that has malicious properties (being for a domain name belonging to someone else, having additional properties like it being trusted to sign other certificates, etc.).[1] This is why you can't get new MD5 or SHA1 certificates signed by public authorities anymore. As you say, there is always going to be at least an infinitesimally small chance that two realistic inputs to the same hashing function will produce the same output, but IMO virtually any system that uses hashes as identifiers will have its security degraded in some way if it's practical to generate a collision. If you program carefully such that you never overwrite another object if you update your object you'll get an internal error if you have a hash collision. It sounds challenging to handle this gracefully in a distributed system without some fairly complex logic. Alice uploads a PDF of sensitive data that hashes to value A on node 1. Node 1 grants Alice full access to the file with that hash. Bob uploads some meeting notes that also hash to value A, but on node 2. Node 2 grants Bob full access to the file with that hash. When the nodes are synchronized an hour later, the system detects a collision. What does it do? [1] https://www.win.tue.nl/hashclash/rogue-ca/ https://www.win.tue.nl/hashclash/rogue-ca/

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.

_nalply 5y ago

One concrete example is using hashes as identifier for objects. It is possible that this a bad idea because of collisions. However, if you have for example a federated system you don't have a central instance issuing identifiers for objects. So you create a hash. In reality it doesn't matter if you used SHA1, MD5 or even a random identifier. As long as you have enough bits, a collision becomes unlikely. However again, if you have many objects consider the birthday paradox. The interesting thing here is that this is an issue in any case: Even if you have an extremely secure hash algorithm, in the end you have less bits than the original data, so collisions must occur, even if they are immensely improbable. If you then decide that you ignore collisions because after considering the birthday paradox collisions won't occur practically it can be worth thinking about what would happen if such a collision does occur. Let's say your application executes a database update and has a hash collision. Then another object would be overwritten. This is a use case of not mixing object creation and object update. If you program carefully such that you never overwrite another object if you update your object you'll get an internal error if you have a hash collision. That's better than losing unrelated data. However this is difficult to test. And I am sure that other bugs are a lot more probable. But this thinking shows me that it is useful to program defensively. If you have assumptions, encode them in assertions. So even if you don't have tests for this rare problem, your chance of being lucky is higher.

blincoln 5y ago
However, if you have for example a federated system you don't have a central instance issuing identifiers for objects. So you create a hash. In reality it doesn't matter if you used SHA1, MD5 or even a random identifier. But it does matter. Usually it's only a big problem in edge cases, but sometimes those edge cases are extremely important. TLS certificates use a hash as their identifier in a distributed/federated model like you describe. By generating collisions, one can submit a normal signing request to a trusted public CA, but then use the resulting signature with a second certificate that has malicious properties (being for a domain name belonging to someone else, having additional properties like it being trusted to sign other certificates, etc.).[1] This is why you can't get new MD5 or SHA1 certificates signed by public authorities anymore. As you say, there is always going to be at least an infinitesimally small chance that two realistic inputs to the same hashing function will produce the same output, but IMO virtually any system that uses hashes as identifiers will have its security degraded in some way if it's practical to generate a collision. If you program carefully such that you never overwrite another object if you update your object you'll get an internal error if you have a hash collision. It sounds challenging to handle this gracefully in a distributed system without some fairly complex logic. Alice uploads a PDF of sensitive data that hashes to value A on node 1. Node 1 grants Alice full access to the file with that hash. Bob uploads some meeting notes that also hash to value A, but on node 2. Node 2 grants Bob full access to the file with that hash. When the nodes are synchronized an hour later, the system detects a collision. What does it do? [1] https://www.win.tue.nl/hashclash/rogue-ca/ https://www.win.tue.nl/hashclash/rogue-ca/