The problem I'd like to solve looks like this:

There are two plaintexts which differ in length and letters, but contain a few common strings. The first few words and the last few words are the same, and there are some common words in the middle as well (sometimes in the same order). The two texts have pretty much the opposite meaning.

The goal is to modify these syntactically but not semantically, and achieve the variants' MD5 hash (or at least the hash values' first 4 bytes) to be the same. I know, that MD5 hash collisions can occur, but how could I implement it in a programming language (e.g. Python) which is not brute force? Is there any way to check which letters to change?

  • $\begingroup$ Is this homework? $\endgroup$ – poncho Mar 21 '20 at 15:42
  • $\begingroup$ Yes, so I'm not asking for the exact code. The sites and posts I've found about the MD5 collision weren't that helpful. $\endgroup$ – user312442 Mar 21 '20 at 16:00
  • $\begingroup$ Since this is homework, I'll just give you a hint: I expect that looking for cryptographical weaknesses in MD5 is not the best approach. Instead, consider: if we replace MD5 with a strong hash, how would you attack this problem? $\endgroup$ – poncho Mar 21 '20 at 16:27
  • $\begingroup$ If it's another (strong) algorithm, then collisions won't occur, so the problem is unsolvable. Even if some parts of the two texts match, the avalanche effect makes it impossible. Or is there something I've missed? $\endgroup$ – user312442 Mar 21 '20 at 16:49
  • 1
    $\begingroup$ "(or at least the hash values' first 4 bytes)" $\endgroup$ – poncho Mar 21 '20 at 18:13

Your Answer

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

Browse other questions tagged or ask your own question.