Fu Challenge #1 taken apart
			h4z4rd [memearser@yahoo.com]

0x1 [intro]
0x2 [quick_hack]
0x3 [decompilation]
0x4 [analysis]
0x5 [conclusion]



	0x1 [intro]

In Fu#1 we got a binary and are supposed to make it print "Hurray! You win!",
and it was up to us to decide how to do it. I decided it would be a good idea to
decompile binary and to see how it looks like in C because it would give me
better understanding of the algorithm used to generate hash, and could reuse the
code for decryptor. Plus it will be a good excersise ;)
Tools used to solve this challange where lida, gdb, ht, ida, and calculator.



	0x2 [quick_hack]

The fastest method to solve this level is to patch the binary. One of the best
places to patch it would be at the end of main where it checks if the return
value of function is 1 and prints the string or jumps to exit.

(gdb) x/5i 0x804880b
0x804880b:      test   %eax,%eax	
0x804880d:      je     0x804881b	*** < nop out
0x804880f:      movl   $0x80489a5,(%esp)
0x8048816:      call   0x8048338	
0x804881b:      leave			***
0x804881c:      ret

So what we do is just replace that jump with nops, and whatever the result from
function is it will print Hurray. We patch it with ht and observer the result:

[hazard: 1]$ ./edited h4z4rd
6070;<8<;<6<08
Hurray! You win!

So lets move on to the c00l part.



	0x3 [decompilation]

The decompilation proces was done in three steps. First quick analysis with lida
to see roughly what is happening. Second was commenting gdb asm dump of executable. 
And third was rewriting executable in C. Second step is not necessary but allows 
for quickier recovery of source, because everything is allready written in pseudo 
code, and it just has to be translated into C. Decompilation process will not
be explained in detail because it will take too much time, and there are some
good tutorials on that topic on the internet. Libc functions were identified
with the help of ida. They were strcpy (for someone to exploit the program),
printf and exit. User defined functions were given names function 1-5. First
four functions are used to mutate user string, and last one is used to compare
user sting with the hardcoded one. Source code is locatet at the end of the
article. If you didn't understand some asm portiton of code well you can extract 
it from source and study.



	0x4 [analysis]

The program has 3 buffers used to store mutated strings each used for different
computation. Function1 is the first one to perform mutation of user string. It
first substracts 0x20 from each character, then it adds hardcoded value 0x2a,
then it substracts from character (((((buf1[i]/0x2)*0xaf)/0x100)/0x20)*0x5e)).
This line is very interesting because it gave me some troubles when reversing
crypto algorithm. In some cases it will have value greater than 255 (1byte) and
thus go into negative. So in the decrypt function looks like this:
        for(i=0;i<k;i++)
        {
                buf[i]=(buf[i]-0x20)&0xff;
                buf[i]=(buf[i]+0x5e)&0xff;
                buf[i]=(buf[i]-0x2a)&0xff;
                buf[i]=(buf[i]+0x20)&0xff;

                if(buf[i]<0)
                        buf[i]=buf[i]-0x5e;
        }               

Function2 just swaps characters with xor trick. Now function3 uses 2 buffers,
first one with string, and second one to store new string. It divides sting by 8
and or-s it with c1 character, and then updates or value of c1 to be old
character * 32. This is very interesting code because it allows us to decrypt
hash. It is due specific computation done that new character has lower 4 bits
from buf1, and higher 4 bits from or-d value that is previous character. If
it wheren't like this we couldn't get original value of character because when
char is divided by 8 it gets rounded, so we can loose as much as 3 bits from
original char. But by extracting 4 bits from current lower byte and next higher
we can compute original value. That operation is:
        for(i=0;i<(j-1);i++)
        {
                a=buf2[i]&0x0f;
                b=buf2[i+1]&0xf0;
                a=a*8;
                b=b/32;
                c=a+b;
                buf[k]=c;
                k++;
        }

Function4 extends the length of string by splitting char to lower and higher
part allowing us to easily recover original character. Decrypting this is done
like this:
        for(i=0;i<len;i+=2)
        {
                tmp1=(str[i]-0x30)&0xf;
                tmp2=((str[i+1]-0x30)&0xf)<< 0x4;

                buf2[j]=tmp1|tmp2;
                j++;
        }

Function5 is used to compare user string with hardcoded string, in a manner that
it compares every second char. But this function is flawed because it doesn't
check the whole length of encoded hash but the length of user string so it is
possible to bypass it by passing as a argument character or string that
partially looks like encoded hash. For example we can bypass it with letter l:
[hazard: decomp]$ ./challenge1 l
70
Hurray! You win!

Well this is pretty much everythin, for more detailed information on workings of
challenge1 look at source. 

By running decryptor on given hash we get CoNgRaTs for one used to compare
string, and by decryption other part of hash we get :Steven: (hehe, this is for
bonus ;) )



	0x5 [conclusion]

This is an interesting challenge and got me banging my head at wall few times.
Especially till i realized that he compared every second char not every at
that time i already had decryptor but constantly got wrong pass ;) 
Hope you learned sth because i have.
Greetz: ptp people, bh crew

[hazard: decomp]$ ./finalX a
500:
Decrypted: CoNgRaTs
Decrypted: :Steven:

#include <stdio.h>
#include <string.h>
#include <unistd.h>

void function1(char *buf1, int len, int num)
{
        int i;

        for(i=0;i<len;i++)
        {
                buf1[i]=buf1[i]-0x20;
                buf1[i]=buf1[i]+num;
                buf1[i]=(buf1[i]-(((((buf1[i]/0x2)*0xaf)/0x100)/0x20)*0x5e));
                buf1[i]=buf1[i]+0x20;
        }
        buf1[i+1]=0x0;
}

void function2(char *buf, int len)
{
        int var1=len/2, i=0;

        for(i=0;i<var1;i++)
        {
                buf[i]= buf[len-i-1] ^ buf[i];
                buf[len-i-1] = buf[i] ^ buf[len-i-1];
                buf[i] = buf[len-i-1] ^ buf[i];
        }
}

void function3(char *buf1, char *buf2, int len, int num)
{
        unsigned char c1, c2;
        int i;

        c1=0x00;
        c2=0xff;

        for(i=0;i<len;i++)
        {
                buf2[i]=(buf1[i]/0x8) | c1;
                c1=(buf1[i]*32)&c2;
        }

        buf2[i]=c1;
        buf2[i+1]=0x0;
}

void function4(char *buf1, char *buf2, int len)
{
        int i;

        for(i=0;i<len;i++)
        {
                buf2[i*2]=(buf1[i] & 0xf) + 0x30;
                buf2[i*2+1]=( ( (buf1[i] >> 0x4)& 0xf)+ 0x30);
        }
        buf2[len*2+1]=0x0;
}

void decrypt(char *str, int len)
{
        int i=0,j=0,k=0;
        char buf[50], buf2[50];
        unsigned char tmp1, tmp2;
        unsigned char a,b,c;

        memset(buf,0,sizeof(buf));
        memset(buf2,0,sizeof(buf2));

        for(i=0;i<len;i+=2)
        {
                tmp1=(str[i]-0x30)&0xf;
                tmp2=((str[i+1]-0x30)&0xf)<< 0x4;

                buf2[j]=tmp1|tmp2;
                j++;
        }

        k=0;
        for(i=0;i<(j-1);i++)
        {
                a=buf2[i]&0x0f;
                b=buf2[i+1]&0xf0;
                a=a*8;
                b=b/32;
                c=a+b;
                buf[k]=c;
                k++;
        }

        for(i=0;i<k/2;i++)
        {
                buf[i]= buf[k-i-1] ^ buf[i];
                buf[k-i-1] = buf[i] ^ buf[k-i-1];
                buf[i] = buf[k-i-1] ^ buf[i];
        }

        for(i=0;i<k;i++)
        {
                buf[i]=(buf[i]-0x20)&0xff;
                buf[i]=(buf[i]+0x5e)&0xff;
                buf[i]=(buf[i]-0x2a)&0xff;
                buf[i]=(buf[i]+0x20)&0xff;

                if(buf[i]<0)
                        buf[i]=buf[i]-0x5e;
        }
        printf("Decrypted: %s\n",buf);
}


int function5(char *buf1, char *buf2, int len)
{
        int i, var;

        for(i=0;i<len;i++)
        {
                if (buf2[i*2] != buf1[i])
                {
                        var=0;
                        return var;
                }
        }
        var=1;
        return var;
}

main(int argc,char *argv[])
{
        char buffer1[800];
        char buffer2[800];
        char buffer3[800];
        char string[]="7<0047>85604?8:26684?8627?00=<6:00:8";
        char name[]="<07864826482?0<:08";
        char pass[]="704>50?:68?670=60:";

        if (argc==1)
        {
                printf("Usage: %s <password>\n",argv[0]);
                exit(0);
        }

        strcpy(buffer1,argv[1]);

        function1(buffer1, strlen(buffer1), 0x2a);

        function2(buffer1, strlen(buffer1));

        function3(buffer1, buffer2, strlen(buffer1), 0x3);

        function4(buffer2, buffer3, strlen(buffer2));
        printf("%s\n",buffer3);

        decrypt(pass, strlen(pass));
        decrypt(name, strlen(name));

        if (function5(buffer3, string, strlen(buffer3)))
                printf("Hurray! You win!\n");

}