3
$\begingroup$

I'm attempting to break a system which uses decryption code functionally equivalent to the following:

$key = md5($somePassword) . foo($somePassword);
for ($i = 0; $i < $payloadLength; $i++)
{
    $data[$i] = (ord($data[$i]) - ord($key[$i]) % 256;
}

Where foo() is a bunch of nonsense pseudo-cryptographic logic involving substrings of MD5s of reverse password strings and ord() returns the numeric value of the character. For non-PHP devs, a . denotes concatenation.

I have two samples of ciphertext which differ a little, which makes me think they're using the same key but with different ciphertexts. Unfortunately I can't make many guesses about the ciphertext since it is compressed with the DEFLATE algorithm in raw mode, so there's no header.

It is important to note that the md5 function, in this case, does not return 16 raw bytes, but rather 32 ASCII hexadecimal characters in the set 0-9 a-f.

I would like to recover the MD5 hash.

My initial thought is to break it like I would a Vigenère cipher, as follows:

$c_1 = m_1 + k \pmod{256}$

$c_2 = m_2 + k \pmod{256}$

thus:

$\require{cancel} c_2 - c_1 = m_2 + \cancel{k} - m_1 + \cancel{k} = m_2 - m_1 \pmod{256}$

However, without known plaintext I'm finding it difficult to continue. I had a think about eliminating potential nybbles of keys based on whether the resulting key bytes would contain hexadecimal characters, but I'm not really sure where to go from here. The plaintext has some known or predictable bits (see RFC1951) but not many.

Is it possible to recover the hash in this scheme?

$\endgroup$
  • $\begingroup$ When you say that md5 returns hexadecimal characters, does this imply that $key will only consist of hexadecimal character as well? $\endgroup$ – SEJPM Jun 29 '17 at 17:06
  • $\begingroup$ I clarified it a little further, and yes. $key will be a hexadecimal string such as "a744e1091c25babd36b50e40fb8d311a", under which $key[0] is 'a' or 0x61. $\endgroup$ – Polynomial Jun 29 '17 at 17:08
  • $\begingroup$ You can trivially crack this with 32-byte of continuous known plaintext, you can brute-force it with 16 bytes of continuous known plaintext and if the known bits are at the right positions in the bytes, you can cut these numbers as well, which leaves the question: Can you quantify the "not many"? Are these two samples both only as wide as the key or wider (ie is the key applied multiple times on them)? $\endgroup$ – SEJPM Jun 29 '17 at 17:15
  • 1
  • $\begingroup$ Unfortunately I'm limited to just a few bits of known plaintext - certainly not known sequential bytes. $\endgroup$ – Polynomial Jun 30 '17 at 8:45

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.