Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Can there be two messages M, M' both of the same length such that both MD5(M)=MD5(M') and SHA-256(M)=SHA-256(M')?
Let's compare two files: if they have the same length, they are candidates for having the same content; if they share the MD5 sum they are stronger candidates for having the same content (I understand there are MD5 collisions on same-size inputs so this could lead to a false positive), but then if they also share a SHA-256 sum, can I be certain the files have the same content?
It is possible such collisions exist, but because SHA-256 is collision resistant, finding any collisions would be computationally infeasible. You may safely assume without further checking that if two files have the same SHA-256 hash, then they contain the same content.
You can so safely assume that, given current cryptographic knowledge, that there's no reason to use MD5 at all; you can just use SHA-256. In fact, you should actively avoid MD5 if at all possible.
What I mean is can there be two messages M, M' both of the same length such that both md5(M)=md5(M') and sha256(M)=sha256(M')?
Yes, such a pair of messages must exist, for the same reason that any function that ranges over a larger set of inputs than its output domain must have collisions. In math this is called the pigeonhole principle.
The use case I'm thinking is comparing two files, if they have the same lenght they are candidates for having the same content, if they share the md5 sum they are stronger candidates for having the same content (I understand there are md5 collisions on same size inputs so this could lead to a false positive), but then if they also share a sha256 sum, can I be certain the files have the same content?
In terms of pure probability, two different files could in theory have the same SHA-256 result as well. Again because of the pigeonhole principle.
But the cryptographic question isn't just how probable it is with random pairs of files (= astronomically unlikely), but rather how difficult it would be for a bad guy to maliciously construct such a pair of files. The problem with MD5 isn't that collisions exist per se; it's that there are known algorithms for finding MD5 collisions efficiently, that a bad guy can use to defeat such checks.
But no such algorithms are known for SHA-256. So:
MD5 collisions are imminent, within seconds one can file two collisions, see corkami. Therefore adding MD5 hashes to countermeasure against collision doesn't produce much effort for the attacker. Due to the MD design, a collision can be used to produce many pairs very easily.
What the attacker is need produce $2^{128}$ MD5 collision pairs and check that they are colliding or not with the SHA-256. This is due to the probabilistic birthday-attack and the attacker has a 50% chance to find a colliding pair.
$$(2^{128})^2/2^{256}/2 = 2^{256 - 256-1} = 1/2$$
Reaching $2^{128}$ is not easy if you consider that the collective power of the bitcoin miners can reach around $2^{92}$ double SHA-256 hashes. They need around $2^{34}$ years to find one.
In the attacker's since the 50% is high, they can, for example, look in 112-bit with success probability;
$$(2^{112})^2/2^{256}/2 = 2^{224 - 256-1} = 1/2^{33},$$ and of cource the lower search double lower chance they will get. This is still beyond for all.
This is not your concern, by reading that you compare files one local and remote to compare, since we don't expect that both files are under the control of an attacker, they need to find second-preimages that is given a message $m$ and its hash value $h = hash(m)$, find another message $m' \neq m$ such that $h = hash(m')$. The generic cost of finding one has cost $2^{128}$ for MD5 and $2^{256}$ for SHA-256. That is beyond of all.
The collision is important for signatures that you can prepare two colliding messages for your own and in this way you can win!. $H(m) = H(m')$ implies $sign(m) = sign(m')$, since we sign the hash of the messages and this is necessary for the security of the signatures since Rabin defined (1979) hashing messages in their signature scheme and it is still secure against existential unforgeability under chosen-message attack (EUF-CMA).
If you are an evil developer then it is a concern for us, not for you. You will look for collision pairs good and evil (CD ISOs) and one non-colliding bad to foil everybody. See in detail in this answer.
Conclusion: Whether collision or secondary-pre-images one doesn't need MD5. Just use a hash function that has at least 256-bit output like SHA-256, BLAKE2b, and SHA3-256.
In theory, finding a collision is always possibe but not practically.
