5 ms·

Can someone ELI5 why collisions are so serious? As far as I understand what a collision is, it means you have two source files that produce the same hash output

Can someone ELI5 why collisions are so serious? As far as I understand what a collision is, it means you have two source files that produce the same hash output, but why is this so bad? How do you have any control over what the contents of those two files are?

iforgotpassword 4y ago
If you use the hash (that we assume you aquired overa secure channel) to verify the download of eg an installer for some sensitive software, and someone manages to give you a backdoored installer instead with the same hash, that would be rather bad.
- iso1210 4y ago
  I think the question is that how is it useful if you happen to have two hashes that match - it's very unlikely that they will be Where the problem comes is when you can generate a matching 128 bit hash with your own content without having to do 2^128 different hashes (or strike ridiculously (lottery winner being struck by lightning) lucky and only need to do 2^100 hashes)
  - walls 4y ago
    Lets say you have an anti-malware service that sees file1, analyzes it, and decides the file is benign. The service then updates a database saying 'hash xyz has been analyzed and is benign'. Then you send file2 which is actually malicious, and the service decides it has already analyzed this file and lets it go. This would work on a lot of big AV appliances and software. A surprising amount of these are still using md5 for de-duplication.
- pornel 4y ago
  This specific attack is not possible against SHA-1 (yet). The known collision weakness only allows generating two colliding pieces ahead of time with a hash value that you don't control. It does not give you ability to collide with a pre-existing file/pre-existing hash, so you can't attack any existing SHA-1-verified file. You can only attack files that you've specifically crafted/tricked to contain your colliding block.
kafrofrite 4y ago
There's some theoretical background on how collision functions work. Generally, the assumption is that the hashing functions in cryptography meet the following: - Each input can be quickly converted to a digest (hash). - Getting from a digest to the input should be infeasible. - It should be infeasible to produce two inputs such that they map to the same digest (although strictly mathematically, people tend to prove it is inefficient to do so). and a few more assumptions that are irrelevant for your question. In a nutshell, the idea is that hashing functions are deterministic. One input maps to one output and by knowing the output I cannot find the input nor I can produce two inputs that map to the same output. Now, those attacks basically violate the principle that one input maps to one output. Suddenly, many inputs map to the same output. What's the risk though? You want to download a Linux Distro with hash digest of value ABC. I'm somewhat interested in people using that linux distro so I tamper the distro to introduce a tracking mechanism that also produces ABC when hashed. You download the distro, verify that the hash is indeed ABC and install it. A more structured answer to your question is available here https://github.com/corkami/collisions https://github.com/corkami/collisions (he also put together a presentation that I can't find right now). Hope this helps :)
- donatj 4y ago
  > One input maps to one output and by knowing the output I cannot find the input nor I can produce two inputs that map to the same output. > Now, those attacks basically violate the principle that one input maps to one output That’s not really… the principal. That’s an impossible desire. You simply cannot fit a larger set in a smaller set. Any function that transforms an arbitrary set of data into a smaller set of data is definitionally going to have collisions. A flawless hashing function that transforms an arbitrary amount of data into a fixed amount of data is subject to an infinite number of collisions for every given output. The problem is not that there are collisions, it’s mathematically impossible for there not to be. The problem is the speed at which they can be found. If you can find them quickly enough, the potential exists in finding malicious inputs in the mix.
  - omginternets 4y ago
    > You simply cannot fit a larger set in a smaller set. Just restating this in a different way: hash functions are surjective.
MarcellusDrum 4y ago
Follow-up question: Wouldn't another use case be if passwords from a database were leaked, but they were hashed, you can still login as a user if you found a collision? But I think salting would prevent you from doing that, as the collision you found would be of the salted password, which will be salted again before being hashed and compared, correct?
- spi 4y ago
  Not (at all) an expert, but I think what you are referring to is a harder problem: given an SHA1-hash, to find something that maps to it. Getting a collision is quite simpler: just create two inputs that map to the same thing, or (more realistically in attacks) you know the original content (and therefore its SHA1 hash) and you want to create another content that has the same SHA1. If, on top, you can also decide (to some margin) what to put in, you can add some "invisible" malevolent pieces. As far as I understand, this is much easier than reversing an arbitrary SHA1-key (with or without "chosen" additional content) without knowing one decrypted key, because the collisions that were found so far were always of rather big files sharing a vast majority of their contents. An ideal hashing would give totally different results changing just any byte in the contents, but apparently this is not the case for SHA1 (but again, I'm just a casual reader about these things!).
- remram 4y ago
  This serious be a "preimage attack" not a "collision attack". And the salting mechanism doesn't usually involve two rounds of hashing.
jbverschoor 4y ago
Because people use it as a unique identifier for data. Let's say you have a file on dropbox and they use SHA1 for data de-duplication. Someone else creates a file with the same SHA1. Dropbox will recognize the SHA1 and do one of two things: - sync their file on top of your, or; - sync your file to their file system (not a real example, and an actual implementation will be less naive, but this is what can happen)
- bick_nyers 4y ago
  I would expect a tiered approach when it comes to deleting data. E.g. before deleting you actually check byte by byte, but because that is too expensive to run on every file, you use the hash to narrow down what files you are testing against each other (and maybe even a cheaper hash on top of that one that determines whether you will spend CPU cycles on doing an expensive hash). Perhaps that's how it's actually done, I'm not sure.
Strilanc 4y ago
Cryptography is disastrous to use incorrectly, and "make sure a prankster can't add suffixes to anything" is exactly the kind of property that's easy to screw up. For example, have you ever run "git fetch" on a pull request? You just hashed files you didn't make, and stored them under their hash. Whoops. Have you ever used nix? A distributed content addressing system? Validated something is safe then signed a hash of that thing? Anything where a file and its hash are assumed to be interchangeable for identification? If you just go looking, the world abounds with chances for mischief.
xenophonf 4y ago
TL;DR—credential forgery, for starters Here's a good example of why SHA-1 collisions are so serious: Let's say there's a cloud service where you configure SAML by setting the SHA-1 thumbprint of your identity provider's response signing certificate instead of uploading the IdP's XML metadata or its signing certificate directly. If an attacker can create their own SAML response signing certificate that hashes to the same value as your identity provider's, the attacker can forge seemingly valid SAML responses that would give them access to the cloud service. This attack would work because in SAML, the following things are true: 1. The public half of the key used to sign a SAML response is embedded in the response alongside the signature. 2. SAML does not use PKIX's hierarchy of certificate authorities, only the X.509 public key certificate format. Trust relationships between SAML identity providers (a/k/a credential service providers) and SAML service providers (a/k/a relying parties) are normally established by directly exchanging entity metadata that includes at a minimum the identity provider's signing certificate or by using metadata aggregates signed by a trusted third party (e.g., all multilateral trust federations—eduGAIN, JISC, InCommon, INFED, etc.) But in this thought experiment, an attacker would be able to generate their own signing key-pair and append whatever junk to the user-defined fields of the X.509 public key certificate is needed to cause a SHA-1 collision. That's basically how the Shattered proof of concept works, only using junk JPEG data embedded in a PDF: https://shattered.io/static/pdf_format.png https://shattered.io/static/pdf_format.png

iforgotpassword 4y ago

If you use the hash (that we assume you aquired overa secure channel) to verify the download of eg an installer for some sensitive software, and someone manages to give you a backdoored installer instead with the same hash, that would be rather bad.

iso1210 4y ago
I think the question is that how is it useful if you happen to have two hashes that match - it's very unlikely that they will be Where the problem comes is when you can generate a matching 128 bit hash with your own content without having to do 2^128 different hashes (or strike ridiculously (lottery winner being struck by lightning) lucky and only need to do 2^100 hashes)
- walls 4y ago
  Lets say you have an anti-malware service that sees file1, analyzes it, and decides the file is benign. The service then updates a database saying 'hash xyz has been analyzed and is benign'. Then you send file2 which is actually malicious, and the service decides it has already analyzed this file and lets it go. This would work on a lot of big AV appliances and software. A surprising amount of these are still using md5 for de-duplication.
pornel 4y ago
This specific attack is not possible against SHA-1 (yet). The known collision weakness only allows generating two colliding pieces ahead of time with a hash value that you don't control. It does not give you ability to collide with a pre-existing file/pre-existing hash, so you can't attack any existing SHA-1-verified file. You can only attack files that you've specifically crafted/tricked to contain your colliding block.

kafrofrite 4y ago

There's some theoretical background on how collision functions work. Generally, the assumption is that the hashing functions in cryptography meet the following: - Each input can be quickly converted to a digest (hash). - Getting from a digest to the input should be infeasible. - It should be infeasible to produce two inputs such that they map to the same digest (although strictly mathematically, people tend to prove it is inefficient to do so). and a few more assumptions that are irrelevant for your question. In a nutshell, the idea is that hashing functions are deterministic. One input maps to one output and by knowing the output I cannot find the input nor I can produce two inputs that map to the same output. Now, those attacks basically violate the principle that one input maps to one output. Suddenly, many inputs map to the same output. What's the risk though? You want to download a Linux Distro with hash digest of value ABC. I'm somewhat interested in people using that linux distro so I tamper the distro to introduce a tracking mechanism that also produces ABC when hashed. You download the distro, verify that the hash is indeed ABC and install it. A more structured answer to your question is available here https://github.com/corkami/collisions https://github.com/corkami/collisions (he also put together a presentation that I can't find right now). Hope this helps :)

donatj 4y ago
> One input maps to one output and by knowing the output I cannot find the input nor I can produce two inputs that map to the same output. > Now, those attacks basically violate the principle that one input maps to one output That’s not really… the principal. That’s an impossible desire. You simply cannot fit a larger set in a smaller set. Any function that transforms an arbitrary set of data into a smaller set of data is definitionally going to have collisions. A flawless hashing function that transforms an arbitrary amount of data into a fixed amount of data is subject to an infinite number of collisions for every given output. The problem is not that there are collisions, it’s mathematically impossible for there not to be. The problem is the speed at which they can be found. If you can find them quickly enough, the potential exists in finding malicious inputs in the mix.
- omginternets 4y ago
  > You simply cannot fit a larger set in a smaller set. Just restating this in a different way: hash functions are surjective.

MarcellusDrum 4y ago

Follow-up question: Wouldn't another use case be if passwords from a database were leaked, but they were hashed, you can still login as a user if you found a collision? But I think salting would prevent you from doing that, as the collision you found would be of the salted password, which will be salted again before being hashed and compared, correct?

spi 4y ago
Not (at all) an expert, but I think what you are referring to is a harder problem: given an SHA1-hash, to find something that maps to it. Getting a collision is quite simpler: just create two inputs that map to the same thing, or (more realistically in attacks) you know the original content (and therefore its SHA1 hash) and you want to create another content that has the same SHA1. If, on top, you can also decide (to some margin) what to put in, you can add some "invisible" malevolent pieces. As far as I understand, this is much easier than reversing an arbitrary SHA1-key (with or without "chosen" additional content) without knowing one decrypted key, because the collisions that were found so far were always of rather big files sharing a vast majority of their contents. An ideal hashing would give totally different results changing just any byte in the contents, but apparently this is not the case for SHA1 (but again, I'm just a casual reader about these things!).
remram 4y ago
This serious be a "preimage attack" not a "collision attack". And the salting mechanism doesn't usually involve two rounds of hashing.

jbverschoor 4y ago

Because people use it as a unique identifier for data. Let's say you have a file on dropbox and they use SHA1 for data de-duplication. Someone else creates a file with the same SHA1. Dropbox will recognize the SHA1 and do one of two things: - sync their file on top of your, or; - sync your file to their file system (not a real example, and an actual implementation will be less naive, but this is what can happen)

bick_nyers 4y ago
I would expect a tiered approach when it comes to deleting data. E.g. before deleting you actually check byte by byte, but because that is too expensive to run on every file, you use the hash to narrow down what files you are testing against each other (and maybe even a cheaper hash on top of that one that determines whether you will spend CPU cycles on doing an expensive hash). Perhaps that's how it's actually done, I'm not sure.

Strilanc 4y ago

Cryptography is disastrous to use incorrectly, and "make sure a prankster can't add suffixes to anything" is exactly the kind of property that's easy to screw up. For example, have you ever run "git fetch" on a pull request? You just hashed files you didn't make, and stored them under their hash. Whoops. Have you ever used nix? A distributed content addressing system? Validated something is safe then signed a hash of that thing? Anything where a file and its hash are assumed to be interchangeable for identification? If you just go looking, the world abounds with chances for mischief.

xenophonf 4y ago

TL;DR—credential forgery, for starters Here's a good example of why SHA-1 collisions are so serious: Let's say there's a cloud service where you configure SAML by setting the SHA-1 thumbprint of your identity provider's response signing certificate instead of uploading the IdP's XML metadata or its signing certificate directly. If an attacker can create their own SAML response signing certificate that hashes to the same value as your identity provider's, the attacker can forge seemingly valid SAML responses that would give them access to the cloud service. This attack would work because in SAML, the following things are true: 1. The public half of the key used to sign a SAML response is embedded in the response alongside the signature. 2. SAML does not use PKIX's hierarchy of certificate authorities, only the X.509 public key certificate format. Trust relationships between SAML identity providers (a/k/a credential service providers) and SAML service providers (a/k/a relying parties) are normally established by directly exchanging entity metadata that includes at a minimum the identity provider's signing certificate or by using metadata aggregates signed by a trusted third party (e.g., all multilateral trust federations—eduGAIN, JISC, InCommon, INFED, etc.) But in this thought experiment, an attacker would be able to generate their own signing key-pair and append whatever junk to the user-defined fields of the X.509 public key certificate is needed to cause a SHA-1 collision. That's basically how the Shattered proof of concept works, only using junk JPEG data embedded in a PDF: https://shattered.io/static/pdf_format.png https://shattered.io/static/pdf_format.png