0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ But isn't md5 much faster than sha256? I get that for security purposes md5 is broken and sh256 is not, but the use case is in comparing two messages(files) without the (computational) hassle of comparing byte-by-byte. Also I'm not thinking of an attack rather on a coincidence (Although I get it, astronomically unlikely) – $\endgroup$ – Juan Feb 6 at 2:50
  • $\begingroup$ MD5 is faster, but not that much. If you need something fast, use BLAKE2b, which is both faster than MD5 and cryptographically secure. All reputable parties recommend against using MD5 for any purpose, even non-security sensitive ones. $\endgroup$ – bk2204 Feb 6 at 3:30
1
$\begingroup$

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:

  1. Given two randomly chosen files, it's astronomically unlikely that they'll have the same SHA-256 hash. Astronomically unlikely is not the same as impossible in theory, but way beyond close enough in practice.
  2. Even if a bad guy wanted to craft two colliding files, they can't do it in practice.
$\endgroup$
2
  • 1
    $\begingroup$ I get from the pigeonhole principle that everytime the possible permutations (because I'm thinking of fixed sized messages) of a message exceeds the amount of digests available a collission is unavoidable, and I get that this apply to both md5, sha256 (and I guess every other hashing algorithm). What I fail to see is how the pigeonhole principle concludes that there are two messages M and M' of the same size such that their digests collide simultaneously in md5 and sha256. $\endgroup$ – Juan Feb 6 at 2:49
  • $\begingroup$ @Juan: Because there's a function $F(x) = \mathrm{MD5}(x) \,\|\, \mathrm{SHA256}(x)$ from arbitrary-length bitstrings to 384-bit bitstrings. By the pigeonhole principle, for any length $l > 384$ bits, there's a pair of $l$-bit messages $m$ and $m'$ ($m ≠ m'$) such that $F(m) = F(m')$. From which it follows that $\mathrm{MD5}(m) = \mathrm{MD5}(m')$ and $\mathrm{SHA256}(m) = \mathrm{SHA256}(m')$. $\endgroup$ – Luis Casillas Feb 10 at 4:24
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.