In this article I will explain how I solved lagalopex crackme from crackmes.de.You can download my keygen and its source code from here.

These are the rules and information:

Get a working keygen.
Allowed are only GPLed-tools.
Patching/Hijacking prohibited ;)

Difficulty: 3 – Getting harder
Platform: Unix/linux etc.
Language: C/C++

Ok, first let’s execute it to see what’s going on and if we are prompted for something:

daniel@gargamel:~/crackme/lagalopex$ ./cm3
Your name: daniel
Hello daniel, lets see what you've done so far...
daniel@gargamel:~/crackme/lagalopex$

Ok, we have done nothing so far so we cannot expect anything else. If we test the binary with the ‘file’ command we will see that it is not stripped so we might get some useful information from its ‘nm’ and ‘strings’ output:

daniel@gargamel:~/crackme/lagalopex$ nm cm3
0804bf58 T gcd1
0804bf92 T gcd2
0804bfcc T gcd3
0804bea6 T gcd_
U getline@@GLIBC_2.0
U getppid@@GLIBC_2.0
U getpwuid@@GLIBC_2.0
U getsid@@GLIBC_2.0
U getuid@@GLIBC_2.0
0804c007 T gs
0804c0ee T main
U memcpy@@GLIBC_2.0
U open@@GLIBC_2.0
U printf@@GLIBC_2.0
U pthread_attr_destroy@@GLIBC_2.0
U pthread_attr_init@@GLIBC_2.1
U pthread_attr_setdetachstate@@GLIBC_2.0
U pthread_create@@GLIBC_2.1
U pthread_exit@@GLIBC_2.0
U pthread_join@@GLIBC_2.0
U puts@@GLIBC_2.0
0804c03d T rad
0804bf04 T rad_
0804c086 T calc
0804bc34 t rmd160_final
0804be4a T rmd160_hash_buffer
080488b4 t rmd160_init
080488fe t rmd160_trans
0804bb15 t rmd160_write

daniel@gargamel:~/crackme/lagalopex$ strings cm3
[...]
Get a name first...
Hello %s, lets see what you've done so far...
%s/.key_%s
%s/.key_%s_%i
Nice, you got it!

I didn’t list all of them but the interesting ones. We can see that there are threads involved which will probably make our reversing job harder. Also, we can see the presumably goodboy string: ‘Nice, you got it’ and some print format strings. I will not go much in detail with the reversing process and I will just show a flow diagram:

As you can see in the flow diagram, it first computes a hash value of 20 bytes (RIPEMD-160) and then iterates over it through some calculations performed by 6 threads (hence, a total of 120 threads are created). I will describe briefly what these threads do:

• gcd1

0804bf58 gcd1:
 804bf58:	55                   	push   ebp
 804bf59:	89 e5                	mov    ebp,esp
 804bf5b:	83 ec 08             	sub    esp,0x8
 804bf5e:	8b 45 08             	mov    eax,DWORD PTR [ebp+8]
 804bf61:	8b 50 04             	mov    edx,DWORD PTR [eax+4]
 804bf64:	8b 45 08             	mov    eax,DWORD PTR [ebp+8]
 804bf67:	8b 00                	mov    eax,DWORD PTR [eax]
 804bf69:	89 54 24 04          	mov    DWORD PTR [esp+4],edx
 804bf6d:	89 04 24             	mov    DWORD PTR [esp],eax
 804bf70:	e8 31 ff ff ff       	call   gcd_
 804bf75:	83 f8 01             	cmp    eax,0x1
 804bf78:	75 0c                	jne    804bf86
 804bf7a:	c7 04 24 01 00 00 00 	mov    DWORD PTR [esp],0x1
 804bf81:	e8 5e c7 ff ff       	call   pthread_exit
 804bf86:	c7 04 24 00 00 00 00 	mov    DWORD PTR [esp],0x0
 804bf8d:	e8 52 c7 ff ff       	call   pthread_exit

In this code you can see a pointer to a vector holding Xi, Yi and (Xi+Yi). So, as you can see this thread is computing the greatest common divisor of Xi and Yi. If this value is 1 (ie, they are coprimes), then the thread will return 1. Otherwise, the returned value will be zero.

• gcd2

0804bf92 gcd2:
 804bf92:	55                   	push   ebp
 804bf93:	89 e5                	mov    ebp,esp
 804bf95:	83 ec 08             	sub    esp,0x8
 804bf98:	8b 45 08             	mov    eax,DWORD PTR [ebp+8]
 804bf9b:	8b 50 08             	mov    edx,DWORD PTR [eax+8]
 804bf9e:	8b 45 08             	mov    eax,DWORD PTR [ebp+8]
 804bfa1:	8b 00                	mov    eax,DWORD PTR [eax]
 804bfa3:	89 54 24 04          	mov    DWORD PTR [esp+4],edx
 804bfa7:	89 04 24             	mov    DWORD PTR [esp],eax
 804bfaa:	e8 f7 fe ff ff       	call   gcd_
 804bfaf:	83 f8 01             	cmp    eax,0x1
 804bfb2:	75 0c                	jne    804bfc0
 804bfb4:	c7 04 24 01 00 00 00 	mov    DWORD PTR [esp],0x1
 804bfbb:	e8 24 c7 ff ff       	call   pthread_exit
 804bfc0:	c7 04 24 00 00 00 00 	mov    DWORD PTR [esp],0x0
 804bfc7:	e8 18 c7 ff ff       	call   pthread_exit

This thread will compute gcd(Xi,Xi+Yi), ie, the first and the third elements of our vector. If again they are coprimes, the thread will return 1; zero otherwise.

• gcd3

0804bfcc gcd3:
 804bfcc:	55                   	push   ebp
 804bfcd:	89 e5                	mov    ebp,esp
 804bfcf:	83 ec 08             	sub    esp,0x8
 804bfd2:	8b 45 08             	mov    eax,DWORD PTR [ebp+8]
 804bfd5:	8b 50 08             	mov    edx,DWORD PTR [eax+8]
 804bfd8:	8b 45 08             	mov    eax,DWORD PTR [ebp+8]
 804bfdb:	8b 40 04             	mov    eax,DWORD PTR [eax+4]
 804bfde:	89 54 24 04          	mov    DWORD PTR [esp+4],edx
 804bfe2:	89 04 24             	mov    DWORD PTR [esp],eax
 804bfe5:	e8 bc fe ff ff       	call   gcd_
 804bfea:	83 f8 01             	cmp    eax,0x1
 804bfed:	75 0c                	jne    804bffb
 804bfef:	c7 04 24 01 00 00 00 	mov    DWORD PTR [esp],0x1
 804bff6:	e8 e9 c6 ff ff       	call   pthread_exit
 804bffb:	c7 04 24 00 00 00 00 	mov    DWORD PTR [esp],0x0
 804c002:	e8 dd c6 ff ff       	call   pthread_exit

This thread will compute gcd(Yi,Xi+Yi), ie, the second and the third elements of our vector. If again they are coprimes, the thread will return 1; zero otherwise.

• gs

0804c007 gs:
 804c007:	55                   	push   ebp
 804c008:	89 e5                	mov    ebp,esp
 804c00a:	83 ec 08             	sub    esp,0x8
 804c00d:	8b 45 08             	mov    eax,DWORD PTR [ebp+8]
 804c010:	8b 00                	mov    eax,DWORD PTR [eax]
 804c012:	85 c0                	test   eax,eax
 804c014:	7e 1b                	jle    804c031
 804c016:	8b 45 08             	mov    eax,DWORD PTR [ebp+8]
 804c019:	8b 50 04             	mov    edx,DWORD PTR [eax+4]
 804c01c:	8b 45 08             	mov    eax,DWORD PTR [ebp+8]
 804c01f:	8b 00                	mov    eax,DWORD PTR [eax]
 804c021:	39 c2                	cmp    edx,eax
 804c023:	7e 0c                	jle    804c031
 804c025:	c7 04 24 01 00 00 00 	mov    DWORD PTR [esp],0x1
 804c02c:	e8 b3 c6 ff ff       	call   pthread_exit
 804c031:	c7 04 24 00 00 00 00 	mov    DWORD PTR [esp],0x0
 804c038:	e8 a7 c6 ff ff       	call   pthread_exit

This thread will return 1 when Xi > Yi and zero otherwise.

• rad

0804c03d rad:
 804c03d:	55                   	push   ebp
 804c03e:	89 e5                	mov    ebp,esp
 804c040:	83 ec 08             	sub    esp,0x8
 804c043:	8b 45 08             	mov    eax,DWORD PTR [ebp+8]
 804c046:	8b 10                	mov    edx,DWORD PTR [eax]
 804c048:	8b 45 08             	mov    eax,DWORD PTR [ebp+8]
 804c04b:	8b 40 04             	mov    eax,DWORD PTR [eax+4]
 804c04e:	0f af d0             	imul   edx,eax
 804c051:	8b 45 08             	mov    eax,DWORD PTR [ebp+8]
 804c054:	8b 40 08             	mov    eax,DWORD PTR [eax+8]
 804c057:	0f af c2             	imul   eax,edx
 804c05a:	89 04 24             	mov    DWORD PTR [esp],eax
 804c05d:	e8 a2 fe ff ff       	call   rad_
 804c062:	89 c2                	mov    edx,eax
 804c064:	8b 45 08             	mov    eax,DWORD PTR [ebp+8]
 804c067:	8b 40 08             	mov    eax,DWORD PTR [eax+8]
 804c06a:	39 c2                	cmp    edx,eax
 804c06c:	7d 0c                	jge    804c07a
 804c06e:	c7 04 24 01 00 00 00 	mov    DWORD PTR [esp],0x1
 804c075:	e8 6a c6 ff ff       	call   pthread_exit
 804c07a:	c7 04 24 00 00 00 00 	mov    DWORD PTR [esp],0x0
 804c081:	e8 5e c6 ff ff       	call   pthread_exit

This thread will calculate the radical of (Xi*Yi*(Xi+Yi)) and if it’s less than (Xi+Yi) it will return 1.

• calc

0804c086 calc:
 804c086:	push   ebp
 804c087:	mov    ebp,esp
 804c089:	push   ebx
 804c08a:	sub    esp,0x14
 804c08d:	mov    eax,DWORD PTR [ebp+8]
 804c090:	mov    ecx,DWORD PTR [eax]
 804c092:	mov    DWORD PTR [ebp-8],0x6bca1af3
 804c099:	mov    eax,DWORD PTR [ebp-8]
 804c09c:	imul   ecx
 804c09e:	sar    edx,0x3
 804c0a1:	mov    eax,ecx
 804c0a3:	sar    eax,0x1f
 804c0a6:	mov    ebx,edx
 804c0a8:	sub    ebx,eax
 804c0aa:	mov    eax,DWORD PTR [ebp+8]
 804c0ad:	mov    ecx,DWORD PTR [eax+4]
 804c0b0:	mov    DWORD PTR [ebp-8],0xae4c415d
 804c0b7:	mov    eax,DWORD PTR [ebp-8]
 804c0ba:	imul   ecx
 804c0bc:	lea    eax,[edx+ecx]
 804c0bf:	mov    edx,eax
 804c0c1:	sar    edx,0x6
 804c0c4:	mov    eax,ecx
 804c0c6:	sar    eax,0x1f
 804c0c9:	mov    ecx,edx
 804c0cb:	sub    ecx,eax
 804c0cd:	mov    eax,ecx
 804c0cf:	lea    edx,[ebx+eax]
 804c0d2:	mov    eax,edx
 804c0d4:	sar    eax,0x1f
 804c0d7:	mov    ecx,eax
 804c0d9:	shr    ecx,0x18
 804c0dc:	lea    eax,[edx+ecx]
 804c0df:	and    eax,0xff
 804c0e4:	sub    eax,ecx
 804c0e6:	mov    DWORD PTR [esp],eax
 804c0e9:	call   pthread_exit

Now we have to find out what this function does since, at first glance, it’s not as simple as the other ones.
It makes some operations with the first and second values of our vector, ie, Xi and Yi. And right before the call to pthread_exit instruction we can see that the returned value is AND’ed with 0xFF so the output of this function will be between 0x00 and 0xFF. I will not dig too much into all the shifts and the multiplications details; instead I will print its equivalent C source.

int calc(int *v)
{
	int x, y;
	x=v[0];
	y=v[1];

	return (   ((int)(x/19) + (int)(y/94)) % 256  );
}

Now let’s have a look at the way the binary is collecting all this data and how it is processed:

 804c677:	call   80486c4
 804c67c:	test   eax,eax
 804c67e:	je     804c68f
 804c680:	mov    DWORD PTR [ebp-0x2510],0x3
 804c687:
 804c68a:	jmp    804c869
 804c68f:	mov    eax,DWORD PTR [ebp-0x360]
 804c695:	add    DWORD PTR [ebp-20],eax

This is the code which actually collects the data returned by the ‘gcd1 threads’. Essentially it does the same than the ‘gcd2’, ‘gcd3’, ‘gs’, and ‘rad’ threads so I will just comment this one.

After the call to pthread_join, the returned value is at [ebp-0x360] address. If it is not zero (ie, if it is 1), the value is added to the value at [ebp-0x360] which is the counter shown in the flow chart.

Let’s now analyze the ‘pthread_join’ to the ‘calc’ threads:

 804c7f8:	call   pthread_join
 804c7fd:	test   eax,eax
 804c7ff:	je     804c80d
 804c801:	mov    DWORD PTR [ebp-0x2510],0x3
 804c808:
 804c80b:	jmp    804c869
 804c80d:	mov    eax,DWORD PTR [ebp-24]
 804c810:	movzx  eax,BYTE PTR [ebp+eax-0x24fc]
 804c817:
 804c818:	movsx  eax,al
 804c81b:	movzx  edx,al
 804c81e:	mov    eax,DWORD PTR [ebp-0x360]
 804c824:	cmp    edx,eax
 804c826:	je     804c834
 804c828:	mov    DWORD PTR [ebp-0x2510],0x5
 804c82f:
 804c832:	jmp    804c869

 804c869:	mov    eax,DWORD PTR [ebp-0x2510]
 804c86f:	add    esp,0x252c
 804c875:	pop    ecx
 804c876:	pop    ebx
 804c877:	pop    edi
 804c878:	leave
 804c879:	lea    esp,[ecx-4]
 804c87c:	ret

This code gets the value returned from the ‘calc’ thread and compares it to the H[i] which holds the i-th hash value. If they don’t match, the program will exit with code 5. Otherwise, it will continue picking up the values returned by the threads. So for the sake of writing the keygen we now know that the (Xi,Yi) values read from the file must satisfy this constraint. If not, the program will just exit without printing out the goodboy message.

After all the exit values are collected and processed we will find the following code:

 804c841:	8b 5d ec             	mov    ebx,DWORD PTR [ebp-20]
 804c844:	83 eb 64             	sub    ebx,0x64
 804c847:	e8 78 bf ff ff       	call   rand
 804c84c:	0f af c3             	imul   eax,ebx
 804c84f:	85 c0                	test   eax,eax
 804c851:	75 0c                	jne    804c85f
 804c853:	c7 04 24 b4 c9 04 08 	mov    DWORD PTR [esp],0x804c9b4
 804c85a:	e8 55 bf ff ff       	call   puts

The ‘result’ value is loaded into ebx, then 0x64 is substracted from it and multiplied by a random value.
If the multiplication returns zero, the goodboy string is moved onto the stack and printed out through puts function:

if( (counter-0x64) * rand()  ==  0)
   puts("Nice, you got it!");

The way to go is making ‘counter’ to be 0x64. In every iteration, counter is incremented by 5 if the conditions are satisfied; as there are 20 iterations, counter will be 100 (0x64) if (Xi,Yi) pairs are correctly chosen. And this is what our keygen should do.

Putting it all together:

To get a working keygen, we must implement a sort of intelligent brute-force keeping in mind all the constraints listed above.

• ABC Conjecture

This conjecture was first put forward in 1980 by Joseph Oesterle of the University of Paris and David Masser of the Mathematics Institute of the University of Basel in Switzerland, which is now considered one of the most important unsolved problems in number theory. This conjecture deals with numbers that have no common factors. For example, if A=3 and B=7 then we’ll have C=10. These 3 numbers are relative primes but rad(A*B*C) > C. Occasionally this is not always true; for instance, if A=1 and B=8, then C=9, rad(A*B*C)=1*2*3=6 < 9.

From here we can read:

If rad(a*b*c) can be less than c, just how much less? Can we find an example where rad(abc) is so much smaller that the square of rad(abc) is also less than c? No one knows of such a triple, but there are some examples where [rad(abc)]^α < c for some exponent α greater than 1 though less than 2. Take the triple {2, 6436341, 6436343}. Here b is equal to 3¹⁰ × 109 and c is equal to 23⁵, and so rad(abc) = 2 × 3 × 23 × 109 = 15042. And 15042^α < 6436343 for any α < 1.6299.

In 1985 Joseph Oesterlé of the University of Paris and David W. Masser of the University of Basel conjectured that there are only finitely many such exceptional triples. Given a positive number ε that can be made arbitrarily small, [rad(abc)]^{1 + ε} can be less than c only in a finite number of cases (which will depend on ε). That’s the abc conjecture.

First of all we should try only the (Xi,Yi) pairs so that calc(Xi,Yi) = H(i); to achieve this we need a way to solve that equation:

int solve_calc(int x, int k)
{
	int d = k - (int)(x/19);
	return  d*94;
}

We will get the Yi candidates by solving the equation with some Xi and the H[i] value for each iteration. The ‘solve_calc’ function will return a valid Yi but it’s not the only one which will satisfy the ‘calc’ condition. Valids Yi will range from the returned value to the returned value+93 and we can add them n*256 (for any positive n) since the calc function performs a modulo 256 operation.

As well, for each Xi value multiple of 19, we will get the same ‘calc’ value for the next 18 ones due to the integer division.

With these in mind we now have to bruteforce the obtained pairs to find the ones who satisfy the co-primality and radical restrictions. The way I will deal with the co-primality restrictions is by computing the GCD with the Extended Euclidean Algorithm. However, the hardest part is computing the radical of the numbers since a factorization is needed.

To speed the factorization process up I will use the Sieve of Eratosthenes to compute a table with all the primes up to a limit.

Please, have a look at the source code of the keygen for a further understanding of the process I have described. In a Pentium 4 3.0 GHz a valid license is generated in less than 1 second but it also depends on the hash value.


daniel@gargamel:~/crackme/lagalopex$ time ./keygen
Username: daniel
Sieve of Eratosthenes Prime Generation...OK
100% completed
Writing license info into /home/daniel/.key_daniel

real 0m1.079s
user 0m0.420s
sys 0m0.030s

As you can see it took about 0.45 seconds to generate the numbers and write the license file. The rest of the time is how much it took me to write my username :-).


daniel@gargamel:~/crackme/lagalopex$ time ./cm3
Your name: daniel
Hello daniel, lets see what you've done so far...
Nice, you got it!

real 0m1.711s
user 0m1.020s
sys 0m0.030s

Voila ! We got a working keygen and it takes less than half the time in the bruteforcing process than the crackme itself in verifying our license.

Notes:

Regarding the string to be hashed I’d like to point out that the final part of it is a number of value: getppid()-getsid(). This number should be zero since the parent PID and the session ID are the same if the program is running from a shell. However if you are debugging the crackme (gdb, strace, ltrace, …) the parent process ID will be the PID of the debugger and this assumption is not true anymore. To debug the program with the data generated by my KeyGen I made a little trick based on LD_PRELOAD so that getppid and getsid always return 0:

int getppid() { return 0; }
int getsid(int pid) { return 0; }

gcc -shared -o fakeids.so fakeids.c
export LD_PRELOAD=$PWD/fakeids.so

daniel@gargamel:~/crackme/lagalopex$ ./testuids
ppid()=0
getsid()=0

This way, the debugging process becomes easier.

Hope you found this article interesting.

Regards,

Daniel

This KeyGenMe is pretty nice since it’s got some public key cryptography inside it.

You can download the original exe file, my KeyGen source file and the tools used from here.

The goal is to break an RSA protection to build a valid KeyGen. Let’s start by opening the executable file with PeID and its Krypto Analyzer Plugin:

As you can see there is some calls to Miracl library functions and it could identify an SHA hash function inside the binary. Let’s keep this in mind while analyzing further with IDA. I recommend you to download some Miracl signatures for IDA so that it can identify the library functions for us.

Open the KeyGenMe with IDA and locate the GetDlgItemTextA call which will retrieve our typed Serial. Analyze the code around it to see what’s going on:

.text:004027B2                 push    [ebp+var_488]
.text:004027B8                 push    [ebp+var_490]
.text:004027BE                 push    [ebp+var_494]
.text:004027C4                 push    [ebp+var_498]
.text:004027CA                 call      miracl_powmod

Powmod function prototype:

void 	powmod (big x, big y, big n, big w);

The powmod function computes w = x^y (mod n). It actually looks like RSA algorithm where x is the serial we typed in the TextBox. Now I will rename the vars for the sake of clarity:

.text:004027B2 push    [ebp+result]
.text:004027B8 push    [ebp+modulus]
.text:004027BE push    [ebp+public_key]
.text:004027C4 push    [ebp+INPUT_SERIAL]
.text:004027CA call      miracl_powmod

All these variables pushed onto the stack are mirvars and since we know its structure we can have a look at them to figure out their size:

debug025:00914F58 dword_914F58 dd 20h
debug025:00914F5C dd offset unk_914F64
debug025:00914F60 db    0
debug025:00914F61 db    0
debug025:00914F62 db    0
debug025:00914F63 db    0
debug025:00914F64 unk_914F64 db  49h ;

The first dword of a mirvar represents its length in 32bit words. So 20h means that the modulus is 1024 bits long.

From the pointer above (0x00914F64) we can take out the modulus value:

N=6601E15E4F6C572B0B38EDF792D426BBA6DEDB98D600C5763C5F2123A361F
49C0CAEA628887077DE01D1DE826D2496DF38802024BC00A64940C8EAB4F1D8
60443C8DE0CEB6B7611888F660B022AA32C3450BC2B6E035D6354654E8EF4666
31F0D180E978DB6960EB4061EAB52D0B281C580B8DA8FE76AB54D5AD85223DB
E1449

Repeating this process we will extract the public exponent: E in RSA scheme.

E=2B7893403C69D8FEB1C4A36D219298438722F2CEB82792230A0B9B8F2DD680
4DB9E64381AEDC6B070AF501522781368C6D76A176223F98FADBFF5F26B5FBAD
814C62143C2A430667CEDDD19C91F20E8EDCAA2A1773F71A18DA3CFAD34B75A6
23724349417E963347C9971E0EFB6E613691F2715523A53AA7CEC4E970584135F3

These two values were hardcoded into the original file each byte XOR’ed with 0x01.

If we scroll up in the disassembly we will see some interesting code:

.text:0040263D call    ds:GetVolumeInformationA
.text:00402643 push    [ebp+VolumeSerialNumber]
.text:00402649 push    offset asc_40D0FC ; "%x"
.text:0040264E lea     eax, [ebp+strVolumeSerialNumber]
.text:00402654 push    eax             ; char *
.text:00402655 call    _sprintf

Interesting, the above code is retrieving our HDD serial number and printing it as an hex ascii string into a local variable.
Then some modifications to this string will be applied:

With the help of Krypto Analyzer we could locate the SHA routine starting at 0x00401030 address which will be soon called
after retrieving the HDD serial number. Having a further look into xrefs to the identified SHA functions we may recognize
a typical hash stucture:

SHA_Init	@	0x00401000
SHA_Process	@	0x004023A4
SHA_Result	@	0x00402435

Ok, the HDD serial number is retrieved, printed to an ASCII hex string and then hashed. I checked the hash with a standard SHA-1 implementation and it differed from the 20-byte hash calculated by the keygenme. So I checked also SHA-0 which just differs from SHA-1 in a rotation but it didn’t match either. I didn’t want to waste so much time in identifying the used hash function so I decided to rip out the code from the binary itself (see sha.asm file in my sources) and build an object which will be linked against my KeyGen to produce exactly the same hash value.

After the hash of our HDD serial string was computed, the KeygenMe creates some miracl variables and a bignum which I’ll call ‘A’

A = 920CC8F0512FB63B8C2F89397A129BAA3D663BD1890C8EE23AAC836A316E231B
C = hash(strHDD_Serial) ^ 7 (mod A)

Now, the serial we typed in the TextBox will be the object of the RSA computation:

INPUT_SERIAL ^ E (mod N)

and compared with the previously calculated value C. If both match, then we have entered the right Serial.

So we have to find a serial which satisfies: C = INPUT_SERIAL ^ E (mod N) given C, E and N. This is clearly an RSA scheme:

RSA Encryption

RSA Decryption

Thus:

INPUT_SERIAL = C ^ D (MOD N)

We can see that to find a valid Serial we must know D (private exponent) and therefore we’ve got to compute it somehow.

N = P*Q, where P and Q are two large primes
E*D = 1 (MOD P-1)
E*D = 1 (MOD Q-1)
So, given P,Q and E we could easily obtain D. The problem is that factorizing N (1024-bit number) into P*Q is not feasible since it would take a nice amount of years.

There are some vulnerabilities in RSA algorithm regarding the size of the chosen exponents. One of them is exploited by the Wiener Attack which is able to find in polynomial time the secret exponent (D) if two conditions are given:

• Q < P and P < 2*Q
• D < 1/3*N^1/4

Sometimes low private exponents are chosen to speed up the decryption process. However if it falls inside these bounds we can compute it very fast. I will use the RAT (RSA Attacking Tool) by bLaCk-eye which is a very powerful tool to attack RSA in several ways. Besides he distributes this application with its source code and I recommend you to have a look at it.

If we give N and E to RAT it will immediately say the value of the private exponent which happens to be:

D = B33F

Thus, we just have to code the following actions in our KeyGen:

• Retrieve the HDD serial number
• Compute C=hash(strHDD_Serial) ^ 7 (mod A)
• Serial = C^D (mod N)

Please note that only the first 8 bytes of the hash output are used for the above calculation.

And paste this number into Pallas KeyGenMe:

For a further understanding of the process have a look at the source code included.

This is a really easy crackme for Windows which I solved in no more than 5 minutes. I have chosen this one to make a simple tutorial for those who are starting with Reverse Engineering so here we go.

You can see the original crackme page here.

The rules from the author are:

1. NO PATCHING
2. Find Serial
3. Write Keygen
4. 😉 Enjoy

Let’s execute the program and type some name/serial to see what’s going on:

Okay, we can see the ‘Bad Boy’ message so let’s open the exe file with IDA and look for that string. Once found we can get all its references by pressing Ctrl+X and see where in the code it is being used.

As you can see in the flow chart, there is a loop making some calculations and after that, the bad/good boy decission is taken. We could patch the jump so that we always get the Good Boy but the first rule was ‘no patching’ so we have to find out how the program works to write a keygen. So let’s focus in the inputs of the loop and the loop itself. As you can see below there are some calls to GetDlgItemTextA function which will get the strings from the DialogBox with the name / serial we have entered.

mov     esi, ds:GetDlgItemTextA
push    [ebp+hMem]      ; lpString
push    3E8h            ; nIDDlgItem
push    [ebp+hDlg]      ; hDlg
call    esi ; GetDlgItemTextA		<- Get the Name into hMem
push    [ebp+nMaxCount] ; nMaxCount
push    [ebp+arg_C]     ; lpString
push    edi             ; nIDDlgItem
push    [ebp+hDlg]      ; hDlg
call    esi ; GetDlgItemTextA		<- Get the serial into arg_C

Once the program has loaded our strings it’s going to make some calculations inside a loop:

; arg_4 holds the 0x1908 value
; ebx contains the length of our name
loc_4010CC:
mov     ecx, [ebp+hMem]
mov     edx, [ebp+arg_4]
add     edx, ebx			; edx+= name_length
movsx   ecx, byte ptr [eax+ecx]		; ecx = name[i]
imul    ecx, edx			; ecx = ecx * edx;
inc     eax				; i++;
mov     [ebp+arg_4], ecx
cmp     eax, ebx			; i == name_length?
jl      short loc_4010CC		; no -> loop

When this simple algorithm’s finished it’s got its output at arg_4 variable. Let’s see the next piece of code to see what our program does with it:

push    [ebp+arg_C]     ; char *
call    _atoi
pop     ecx				; eax = atoi(input_serial)
mov     ecx, [ebp+arg_4]		; get our computed value
push    0               ; uType
xor     ecx, 0A9F9FAh			; value ^= 0xA9F9FA;
cmp     ecx, eax			; do they match?
jnz     short BadBoy			; no -> bad boy
push    offset aGoodBoy ; "Good Boy!"
push    offset aTerimaKasihKer ; "Terima kasih kerana mencuba"
jmp     short loc_401111

Simple. The computed value is XOR’ed with 0xA9F9FA and then it is compared with the atoi() of the serial. If both values match then we get the good boy. Putting this all together we can now write a valid keygen for this program. Here it is the C source code of the simple keygen I wrote:

int main(int argc, char **argv)
{
	int namelength, i, serial=0x1908;
	char *name = argv[1];

	if(argc!=2)
	{
		printf("Usage: %s n",argv[0]);
		exit(1);
	}

	namelength=strlen(name);
	if(namelength < 5)
	{
		printf("Name must be at least 5 characters longn");
		exit(1);
	}

	for(i=0;i<namelength;i++)
	{
		serial+=namelength;
		serial*=name[i];
	}
	serial^=0xA9F9FA;
	printf("Serial: %dn",serial);
	return 1;
}


daniel@gargamel:~/crackme2$./keygen_cme2 daniel
Serial: -1860565822


daniel@gargamel:~/crackme2$./keygen_cme2 535246756
Serial: 1791915272

Done!
This is an easy and good one for your first steps at RE because it’s got no protections and you have to reverse a simple algorithm.

Hope you found this article useful.
Regards,
Daniel

As you can see I’ve made another category inside the blog named ‘Reverse Engineering’. From the Wikipedia you can read:

Reverse engineering (RE) is the process of discovering the technological principles of a device, object or system through analysis of its structure, function and operation. It often involves taking something (e.g. a mechanical device, electronic component, or software program) apart and analyzing its workings in detail, usually to try to make a new device or program that does the same thing without copying anything from the original.

I’m really interested in security related to both software and hardware and this is the reason why I like Reverse Engineering so much. I am not a guru of this art though but I try some challenges from time to time (most of them from http://www.crackmes.de) specially those who include some kind of crypto protection.

In this category I will write some tutorials of the crackmes I manage to solve. So I’d recommend to all of you who are interested in RE to keep an eye on my blog and crackmes.de as well.

Regards,

Daniel

I have worked on several platforms based on ARM cores: ARM7, ARM9 and XScale. ARM architecture has been present in more than 2 billion embedded products over the last 10 years, ranging from cell phones to automotive braking systems. I think ARM architecture is great for embedded computers and I needed to learn it so that I could get its best.

The best book I found on this is ‘ARM System Developer’s Guide’ by Andrew Sloss (ARM Inc.), Dominic Symes (ARM Ltd.) and Chris Wright (Ultimodule Inc.). It covers all the ARM cores, XScale processors, demonstrates how to implement DSP algorithms, describes cache technologies that surround the ARM cores, as well as efficient memory management techniques.

Among the tasks I’ve had to deal with I’d point out Artificial Vision and Vocoders implementation for being computationally expensive.

In vocoders implementation and optimization case, I had to face some large of Digital Signal Processing issues which leaded me to write assembly code in order to get the best performance. Also I had to focus in the cache usage because it can speed up the execution time amazingly. Not to mention avoiding pipeline stalls and efficient use of the registers. The mentioned book covers all these topics both with theory and practical examples. There’s a dedicated chapter about DSP which even includes source code ready to use.

Even if you don’t need to write assembly code you can learn how to write efficient C code for ARM. I will show a simple example which can improve ‘intensive loop’ codes:

int checksum(int *data)
{
	unsigned int i;
	int sum=0;
	for(i=0; i<64; i++)
	{
		sum+=(*data++);
	}
}

This compiles to:

	mov	r2,r0		; r2=data
	mov	r0,#0		; sum=0
	mov	r1,#0		; i=0
checksum_loop
	ldr	r3,[r2],#4	; r3 = *(data++)
	add	r1,r1,#1	; i++
	cmp	r1,#0x40	; compare i,64
	add	r0,r3,r0	; sum+=r3
	bcc	checksum_loop	; if(i<64) loop
	mov	pc,lr		; return sum

The above code is not efficient, we can avoid the 3 steps loop: ADD 1 to i, comparison and the conditional branch instruction.
Instead:

int checksum_eff(int *data)
{
	unsigned int i;
	int sum=0;
	for(i=64; i!=0; i----)
	{
		sum += *(data++);
	}
	return sum;
}

As you can see, we just rewrote the loop to be descendent rathern than the previous incrementing loop. Let’s have a look at the compiled code:

	mov	r2,r0			; r2=data
	mov	r0,#0			; sum=0
	mov	r1,#0x40		; i=64
checksum_2_loop
	ldr	r3,[r2],#4		; r3=*(data++)
	subs	r1,r1,#1		; i-- and set flags
	add	r0,r3,r0		; sum+=r3
	bne	checksum_2_loop		; if (i!=0) loop
	mov	pc,lr			; return sum

As you can see, the loop work is done entirely by the subs and bne instructions. The comparison with zero is free since the result is stored in the condition flags. Thus we can see that it’s more efficient to make decrementing loops in ARM than incrementing ones.

Let’s have a look at the way one could have written the same function in C without taking efficiency into account:

int checksum(int *cata)
{
	char *i;
	int sum=0;
	for(i=0; i<64;i++)
	{
		sum += data[i];
	}
}

And the compiler output:

	mov	r2,r0			;r2=data
	mov	r0,#0			;sum=0
	mov	r1,#0			;i=0
checksum_loop
	ldr	r3,[r2,r1,lsl #2]	;r3=data[i]
	add	r1,r1,#1		;r1=i+1
	and	r1,r1,#0xff		;i=(char)i
	cmp	r1,#0x40		;compare i and 64
	add	r0,r3,r0		;sum+=r3
	bcc	checksum_loop		;if(i<64) loop
	mov	pc,lr			;return sum

At first, one may think that declaring i as char uses less register space or less space on the ARM stack than an int. On ARM these assumptions are wrong and that’s why the output code includes the AND instruction with 0xFF which actually slows the execution without saving space. So our checksum_eff function is pretty much faster without not so much effort just by knowing a little bit about ARM architecture.

Rewriting C functions is the first thing that should be done when optimizing before digging down into assembly. Special care must be taken in those functions with nested loops or with too many iterations. It’s also useful some profiling tool like Intel VTune Performance Analyzer to check if all our optimizations are really optimizations and how much we have speeded its execution up.

Hope you found this article useful,

Daniel