Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
That “isn’t possible” is incorrect… instead, “extremely unlikely” would have been a better choice of wording. –  e-sushi Jul 25 at 17:45
    
AES25 is not very precise. If a truly randomized Padding is used this is so extraordinary unlikely that you could consider it impossible. However if a deterministic padding is used it would still depend on the mode being used. The probability of this effect occuring randomly stays the same for each mode. But it is easier to construct such a case with ECB or CTR mode than with, say, OFB or CBC mode. –  marstato Jul 26 at 17:54
    
@marstato : $\:$ In fact, AES25 is even less precise than AES256. $\;\;\;\;$ –  Ricky Demer Jul 26 at 21:52
    
Oh sorry, excuse the typo. –  marstato Jul 26 at 22:20

1 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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