Probability that two different files can have same MD5 hash for both an unencrypted and encrypted version (AES256, same key between files)

Question

This math is way over my head, and don't even know if it can be done, but here are the assumptions:

1. Take unencrypted File [Fu] of variable length, but assume 100KB as an example.
2. Let File [Fe] be the AES256 encrypted version of [Fu].
3. Let Hash [Hu] be the cryptographic hash using MD5 Algorithm of [Fu]
4. Let Hash [He] be the cryptographic hash using MD5 Algorithm of [Fe]
5. Let File [Fmu] be an unencrypted file that is different from file [Fu] by at least one bit.
6. Let File [Fme] be the AES256 encrypted version of [Fmu]
7. Let Hash [Hmu] be the cryptographic hash using MD5 Algorithm of [Fmu]
8. Let Hash [Hme] be the cryptographic hash using MD5 Algorithm of [Fme]
9. Assume the key for AES256 to be constant.

Question: What is the probability that both [Hu] = [Hmu] and [He] = [Hme]. In english, what is the chance that two different files can have identical hashes in both an unencrypted and encrypted form? My guy says it isn't possible, or the odds are dependent on the size of [Fu]. Thoughts?

Answer 1

What is the probability that both [Hu] = [Hmu] and [He] = [Hme]. In english, what is the chance that two different files can have identical hashes in both an unencrypted and encrypted form?

Depends on whether they are "random" files or attacker controlled.

MD5 is a 128-bit hash, so for two random files that differ the probability that they have the same MD5 hash is $2^{-128}$. If they are encrypted with strong encryption, their encrypted versions will be random files with again $2^{-128}$ probability of having the same hash. The chance that both happen for the same files is then $2^{-256}$.

For attacker chosen files it's a different matter. It is easy to construct two files with the same MD5. If the attacker knows the encryption key, they may even be able to construct two files with equal hashes in both unencrypted and encrypted forms (brute force search takes about $2^{64}$ if nothing else helps).

My guy says it isn't possible, or the odds are dependent on the size of [Fu]. Thoughts?

As for file size, it doesn't matter beyond the files having to be large enough that collisions exist. In practice something like 512 bits (64 bytes) is enough. In theory there are inputs that are only about 64 bits and collide, but finding them may be more difficult.