Breaking some homemade crypto

Posted on 01 Aug 2017 in security • 3 min read

I recently did a code review assessment on an application for one of my client. The best part of the application was their own cryptography algorithm.

Moreover, the application was written in PHP and PHP do some strange things with string, characters and XOR operations. It only needed a few lines of python in order to break it.

TL;DR : please do not write your own crypto!

The cryptography algorithm was a symmetric one, that means there is always a private key shared between the encryption and the decryption. In fact the key was shared for the application.

Encryption algorithm

The encryption algorithm is the following (I rewrote it in python for a better comprehension):

def crypt(clearText):
    privateKey = '123456'
    cipherText = ''

    key= hashlib.md5(str(randint(0, 32000)).encode('ascii')).hexdigest()

    i = 0
    j = 0
    while (i< len(clearText)):
        if (j == len(key)):
            j=0
        cipherText += key[j]+chr(ord(clearText[i])^ord(key[j]))
        i += 1
        j += 1

    key2 = hashlib.md5(privateKey.encode('ascii')).hexdigest()
    i = 0
    j = 0
    result = ''

    while (i< len(cipherText)):
        if (j == len(key2)):
            j=0
        result += chr(ord(cipherText[i]) ^ ord(key2[j]))
        i+=1
        j+=1

    return result

We observe that there is only XOR operations. Quick reminder about XOR operations:

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

Moreover, by definition: a XOR b XOR a = b

Breaking things

In our situation we need to find cipherText in order to find the md5 hash of the private key. However cipherText is build using the clear text and a random number included between 0 and 32 000. Therefore by a Known-plaintext attack we can generate the 32 001 values of cipherText, XOR it with the encrypted string, search for the resulting sting which will be repeating every 36 characters and get the md5 hash of the private key. Our only constrain in that the plain text must be longer than 36 characters in order to easily find the md5 hash (an other option might have be to search for ascii characters).

Here is the python code:

def brute():
    clearText='this is a test in order to break some home made crypto'
    codedText=crypt(clearText)
    k=0
    while (k<32001):
        key= hashlib.md5(str(k).encode('ascii')).hexdigest()
        cipherText= ''

        i = 0
        j = 0
        while (i< len(clearText)):
            if (j == len(key)):
                j=0
            cipherText += key[j]+chr(ord(clearText[i])^ord(key[j]))
            i += 1
            j += 1

        i = 0
        j = 0
        result = ''

        while (i< len(codedText)):
            if (j == len(cipherText)):
                j=0
            result += chr(ord(codedText[i]) ^ ord(cipherText[j]))
            i+=1
            j+=1
        l = 0
        s = 0
        while (l<32):
            if (result[l]==result[l+32]):
                s +=1
            l+=1
        if s==32:
            print(k)
            print(result[:32])
            break
        k+=1

I put the two function in a file, added a main and run it:

[maggick@eridani ~]$ time python crypt.py
23467
e10adc3949ba59abbe56e057f20f883e

real    0m2.186s
user    0m2.186s
sys 0m0.000s
[maggick@eridani ~]$ echo -en '123456' | md5sum
e10adc3949ba59abbe56e057f20f883e  -

We got the md5 hash of the private key. The default key used in the application was 8 characters long and was use in other algorithms not home made.

PHP: character XOR character

PHP is doing really funny things, most of you know that. When analysing the original PHP code of the encryption function, I found something very strange:

$tmp .= mb_substr($text, $i, 1) ^ mb_substr($key, $j, 1);

How can you make a xor operation between two characters?!

In fact PHP make a xor operation between the ASCII value of the character and convert the result back to the ASCII character. For instance 'a' xor 'B' will result in 65 xor 98 which give 35 therefore 'a' xor 'B' → '#'

As you may have seen in the above code this is equivalent to the following python code:

tmp += chr(ord(clearText[i])^ord(key[j]))

Full code

The complete code is the following:

import hashlib
import base64
from random import randint

def crypt(clearText):
    privateKey = '123456'
    cipherText = ''

    key= hashlib.md5(str(randint(0, 32000)).encode('ascii')).hexdigest()

    i = 0
    j = 0
    while (i< len(clearText)):
        if (j == len(key)):
            j=0
        cipherText += key[j]+chr(ord(clearText[i])^ord(key[j]))
        i += 1
        j += 1

    key2 = hashlib.md5(privateKey.encode('ascii')).hexdigest()
    i = 0
    j = 0
    result = ''

    while (i< len(cipherText)):
        if (j == len(key2)):
            j=0
        result += chr(ord(cipherText[i]) ^ ord(key2[j]))
        i+=1
        j+=1

    return result

def brute():
    clearText='this is a test in order to break some home made crypto'
    codedText=crypt(clearText)
    k=0
    while (k<32001):
        key= hashlib.md5(str(k).encode('ascii')).hexdigest()
        cipherText= ''

        i = 0
        j = 0
        while (i< len(clearText)):
            if (j == len(key)):
                j=0
            cipherText += key[j]+chr(ord(clearText[i])^ord(key[j]))
            i += 1
            j += 1


        i = 0
        j = 0
        result = ''

        while (i< len(codedText)):
            if (j == len(cipherText)):
                j=0
            result += chr(ord(codedText[i]) ^ ord(cipherText[j]))
            i+=1
            j+=1
        l = 0
        s = 0
        while (l<32):
            if (result[l]==result[l+32]):
                s +=1
            l+=1
        if s==32:
            print(k)
            print(result[:32])
            break
        k+=1


def main():
    brute()

if __name__ == "__main__":
    main()

Previous Post Next Post