Breaking a custom encryption algorithm

Challenge Overview:

This challenge is about breaking a custom designed encryption algorithm. In order to do that you need to reverse engineer how the algorithm works then once you figure that out you need to write a piece of software that will allow you to decrypt the provided ciphertext so that you can submit the decrypted plaintext as your solution to the challenge.

Challenge Details:

Website: www.hackthissite.org
Section: Programming Challenge 3

The following resources were provided:

An example of what the plain text looks like.

    99Z-KH5-OEM-240-1.1
    QGG-V33-OEM-0B1-1.1
    Z93-Z29-OEM-BNX-1.1
    IQ0-PZI-OEM-PK0-1.1
    UM4-VDL-OEM-B9O-1.1

A encrypted blob (Note: Includes unix style line endings '\n').

    -203 -156 -173 -197 -178 -143 -104 -198 -179 -162 -187 -175 -147 -155
    -198 -206 -178 -178 -176 -221 -161 -175 -157 -187 -147 -120 -175 -177
    -127 -165 -191 -156 -134 -175 -143 -179 -118 -157 -178 -214 -142 -160
    -148 -188 -224 -125 -156 -191 -109 -181 -171 -174 -149 -117 -190 -223
    -151 -206 -152 -223 -156 -151 -141 -222 -114 -138 -157 -171 -140 -101
    -153 -196 -146 -144 -125 -200 -185 -209 -151 -247 -142 -145 -216 -169
    -200 -137 -181 -149 -141 -126 -165 -211 -187 -156 -129 -188 -206 -186
    -166 -229

Source code to the encryption algorithm which is made of two functions.

function encryptString($strString, $strPassword)
{
    // $strString is the content of the entire file with serials
    $strPasswordMD5 = md5($strPassword);
    $intMD5Total = evalCrossTotal($strPasswordMD5);
    $arrEncryptedValues = array();
    $intStrlen = strlen($strString);
    for ($i=0; $i<$intStrlen; $i++)
    {
        $arrEncryptedValues[] = ord(substr($strString, $i, 1))
        + ('0x0' . substr($strPasswordMD5, $i%32, 1)) - $intMD5Total;
        $intMD5Total = evalCrossTotal(substr(md5(substr($strString,0,$i+1)),0,16)
                       .substr(md5($intMD5Total), 0, 16));
    }
    return implode(' ' , $arrEncryptedValues);
}

function evalCrossTotal($strMD5)
{
    $intTotal = 0;
    arrMD5Chars = str_split($strMD5, 1);
    foreach ($arrMD5Chars as $value)
    {
        $intTotal += '0x0'.$value;
    }
    return $intTotal;
}

The breakdown:

First things first I needed to understand how the two php functions worked to encrypt the data. I'll start with the second function since it is easier to undertand and it is used by the first function. The second function is relatively simple. It takes a string as input which it expects to be a string of hex characters. It takes the hex value of each character and sums them all up and returns the total. So if you passed "12345" it would return 15 or 0xF (1+2+3+4+5=15)

The first function encryptString(string, password) takes a plaintext string and a password as its two inputs. It starts by taking the MD5 hash for the password and stores it in strPasswordMD5.

$strPasswordMD5 = md5($strPassword);

It then passes strPasswordMD5 to our second function which returns the total from summing all of those hex characters.

$intMD5Total = evalCrossTotal($strPasswordMD5);

Next it creates an empty array to hold the encrypted values and stores the length of the plaintext input string.

$arrEncryptedValues = array();
$intStrlen = strlen($strString);

It then enters a loop from 0 to the length of the input string ad takes the ordinal value of the plaintext character at position i and adds that to the hex value of the digit in strPasswordMD5 at position i mod 32 and subtracts the value of intMD5total from this. The result of this is stored in the arrEncryptedValues array and the intMD5Total is updated by taking the first 16 characters of the MD5 of the plaintext string that has been sonsumed to this point and concatenating that with the first 16 characters of the MD5 of intMD5Total's value.

for ($i=0; $i&lt;$intStrlen; $i++)
{
    $arrEncryptedValues[] = ord(substr($strString, $i, 1))
    + ('0x0' . substr($strPasswordMD5, $i%32, 1)) - $intMD5Total;
    $intMD5Total = evalCrossTotal(substr(md5(substr($strString,0,$i+1)),0,16).substr(md5($intMD5Total), 0, 16));
}

When it has finished this loop it returns a string which is made by concatenating the arrEncryptedValues together with spaces.

return implode(' ' , $arrEncryptedValues);

When you start this challenge you are given 120 seconds to complete it before the timer runs out and any submissions will be invalid. Note: that doesn’t mean you need to write the software that fast, just that when it is operating it needs to get the input and produce a valid output within 120 seconds.

My solution:

Warning: Spoiler alert! A solution is given below

So to solve this without knowing what the original input string is and without knowing what the original password used was you must figure out a weakness in the encryption routine.

In this case the weakness comes from the way that the encrypted text is produced. Since we know that the maximum value of the intMD5Total is 480 (15 * 32) and that there are 16 possible values for the strPasswordMD5 character used we can simply bruteforce through the 7680 possible values eliminating any of the ones that don't produce an ASCII characcter in the following range 0-9, A-Z. After finding the possible starting points the program then takes the possible starting plain text characters and intMD5Totals and attempt to try each of the possible 16 values for the next strPasswordMD5 value again discarding any that produce an invalid output. The process is repeated paying special attention to the characters that are known in the plain text such as the '-' and '-OEM-' and '1.1\n' which help to significantly reduce the possibilities. Once we have recovered the original MD5 through this process then we can just do a standard decryption at that point because we will have only 1 intMD5Total and 1 MD5.

I’m sure there are many more creative ways of attacking this problem that others have used but this was the way I decided to attack it.

The failed attempts:

As always I try to take the easiest approach before moving on to more complicated techniques. So originally I had started out trying to attack the input password by creating a simple decryption routine and passing various wordlists to it but that was a dead end because whatever the password they had used to encrypt the text it wasn’t one found in any of my wordlists, I assumed this would be the case but this was quick to test. I had also messed around with bruteforcing the MD5 to eliminate the step of computing the MD5’s on each attempt (by feeding pre-computed MD5 values into the decryption routine) but as before this was a dead end.

The challenge that I wrote about here can be found on https://www.hackthissite.org/
Note: You must join the site to see the challenges