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 (he also put together a presentation that I can't find right now). Hope this helps :)
> 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.
Just restating this in a different way: hash functions are surjective.
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)
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.
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.
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)
Perhaps that's how it's actually done, I'm not sure.
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:
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.
And the salting mechanism doesn't usually involve two rounds of hashing.