Crackme 3 – RSA – Daniel Álvarez's Blog

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: