Pwnable.kr - collision [2]

Pwnable.kr’s second challenge goes like this:

Daddy told me about cool MD5 hash collision today.
I wanna do something like that too!

ssh col@pwnable.kr -p2222 (pw:guest)

Let us first download col.c file from server.

scp -P 2222 col@pwnable.kr:col.c .

Now, compiling it under x86 architecture:

gcc -m32 col.c

Let us check what this little beaver does when given a dummy input:

    $ ./a.out 123
    passcode length should be 20 bytes
    $ ./a.out 01234567890123456789
    wrong passcode.

Checking the source code we can clearly understand what the program does. After receiving the input and checking its length, the script compares return value of check_password( ) with the value of 0x21DD09EC. Here is the function’s code:

    unsigned long check_password(const char\* p){ 
        int* ip = (int*)p;
        int i;
        int res=0;
        for(i=0; i<5; i++){
           res += ip[i];
        }   
        return res;
    }

As you remember, the size of a char is 1 byte under x86, while int is 4 bytes. What the first line inside the function does is casting a char pointer to an int pointer. This means if we were passing 20 chars, i.e., 20 bytes, it now corresponds to 20/4=5 ints. The for loop then sums all these 5 ints into res, which is the returned value.

All in all, what check_password does is simply splitting our password string into 5 ints (4 chars each) and adding them up. What we need to find is a string that has the property of this result being equal to 0x21DD09EC.

21DD09EC / 5 = 6C5CEC8,CCCCCCCCD

Oh well, 0x21DD09EC is obviously not divisible by 5. The closest multiple of 5 is:

21DD09ED / 5 = 6C5CEC9

So we can say:

21DD09ED = 6C5CEC9 + 6C5CEC9 + 6C5CEC9 + 6C5CEC9 + 6C5CEC9
21DD09EC = 6C5CEC9 + 6C5CEC9 + 6C5CEC9 + 6C5CEC9 + 6C5CEC8

There is just a little problem here, each portion of the sum has 7 chars, instead of 8, so we add a 0 to the left as a padding.

 21DD09EC = 06C5CEC9*4 + 06C5CEC8

Before we proceed to converting it to ASCII, we must remember that x86 uses little endian notation, so the bytes should be in reverse order. Our password becomes:

\xC9\xCE\xC5\x06 * 4 + \xC8\xCE\xC5\x06

Now we are almost ready to go! converting each of these portions into chars will require more then pure ASCII, which our terminal might no be able to represent due to encoding issues. There are other ways though besides directly printing \x06 char into the terminal:

./a.out $(echo -e "\xC9\xCE\xC5\x06\xC9\xCE\xC5\x06\xC9\xCE\xC5\x06\xC9\xCE\xC5\x06\xC8\xCE\xC5\x06")

The $(…) enables us to give a command to be interpreted by the terminal. A more elegant and synthetic solution would be:

./a.out $(python2.7 -c "print '\xC9\xCE\xC5\x06'*4 + '\xC8\xCE\xC5\x06' ")

Going back to the server:

col@ubuntu:~$ ./col $(python2.7 -c "print '\xC9\xCE\xC5\x06'\*4 + '\xC8\xCE\xC5\x06' ")
daddy! I just managed to create a hash collision :)

And there it is :)