## TMG Keygen-Me #2

"It seems that the 'mystique' there has been around RSA protections (perpetuated by certain scene groups) has now been well and truly exposed. I think as +spath noted on a message board post recently, no-one is actually questioning the integrity of the RSA scheme itself, only elegant weaknesses in implementation. The truth with many of these encryption schemes is that once you've identified and isolated them or gotten lucky in some other cases :-), writing a key generator is not that difficult. Anyway, my thanks to goatass for this tutorial which should help many more people play with the RSA boys :-)." "Slightly edited by CrackZ".

Important Note :- This tutorial will not make you a member of TMG, so don't try submitting the keygen here.

Handbook of Applied Cryptography from tE's site :- http://egocentrica.orcon.net.nz/ (Note from CrackZ 13/9/1 : I am aware now that this page displays the TPA's handiwork, regrettable that they chose to hit another knowledge site).
CrackZ RSA Paper
FTP Voyager v6.1.1.1 factoring RSA by PaRKeR :- Parker2.htm

#### Tools

RSA Tool 2 v1.2 - RSA key generation and factoring tool - http://egoiste.cjb.net/
SoftICE, IDA & MASM.

#### Target

RSA Keygen-Me - http://www.tmg.f2s.com/index.html

So what's RSA? well if you read the Required / Recommended Readings you should know what it is, if you didn't go read them now, with out them you might as well give up. This Keygen-Me coded by tE of TMG was my first ever attempt at reversing a target that uses RSA. After reading everything I could find on RSA I sort of got the concept of what is going on but I was still lost as to what I am looking for when reversing it. This paper is intended to clear this issue up. What we need to know about RSA that will help us reverse it :-

Modulus - n
Public Exponent - e
Private Exponent - d
Primes - p and q
Keysize in bits - will find this out later

We need to find out the target's public key which consists of (e,n) then calculate its private key (d,n).

Encryption --> C=M^e mod n
Decryption --> M=C^d mod n

Let the real work begin.

First we run the program, don't type anything and just press the Check button. What do you see ? "Invalid Username", type something in and press Check again. "Invalid Company", type something in there and press Check. "Registration code is incorrect". The first two errors should tell you something, if they haven't told you anything by now I'll give you a hint. There is a length check.

OK, type in your name, some company and a serial, set some breakpoints and click the Check button. Well nothing breaks, it uses SendMessageA to get text from a text box, so set a BPX MessageBoxA to break on the error message and scroll up until you see the 3 SendMessageA calls, the first is for the name, second for the company and the third for our serial. Set a BPX 401197 (the first line of the SendMessageA call for the username). Get out of SoftICE and click Check again. F10 passed the SendMessageA and you will see :-

```004011A6 call j_SendMessageA 004011AB cmp eax, 5 004011AE jl loc_40139B```

A length check on the user name, the company is the same. Lets look at the serial number :-

```004011E6 call j_SendMessageA ; gets serial number, EAX=length of serial 004011EB mov ds:word_402370, 0Ah 004011F4 push 3 004011F6 xor edx, edx 004011F8 imul eax, 7B5h ; multiply length by 7B5h 004011FE pop ebx ; EBX=3 004011FF div ebx ; EAX/EBX 00401201 lea eax, [eax-66C2h] ; subtract 66C2h from EAX's value 00401207 cmp eax, 1 ; was the result 1 ? 0040120A sbb eax, eax 0040120C jz loc_401382 ; jumps to ERROR 00401212 mov edi, offset unk_402372 ; buffer 00401217 mov esi, offset unk_4021F0 ; serial 0040121C push esi 0040121D call j_CharUpperA```

I like the trick tE used here because if you type in characters in the serial box it only allows 50 chars. That makes you think that the serial should be 50 chars long, but it's NOT. Looking at the algorithm here we figure that in order to NOT jump at 0040120C our final value must be 0 so we start with 1 and follow the algorithm up. Hint :- you can use SoftICE to do these calculations, for example :- ? 66c3*3 or ? 13449/7b5.

1 + 66C2h = 66C3h
66C3h * 3 = 13449h
13449h / 7B5h = 28h
28h = 40d

So the length of our serial number should be 40 characters long. Type in a new serial with 40 characters in it. After the call to CharUpperA which makes our serial all upper case we reach :-

```00401225 lodsw ; loads first 2 chars of serial to AX 00401227 and ax, 7F7Fh 0040122B sub ax, 3030h 0040122F cmp al, 19h ; checks if the character is between 0-F 00401231 ja loc_401382 ; if not jumps to ERROR 00401237 cmp ah, 19h 0040123A ja loc_401382 00401240 movzx ebx, ah 00401243 movzx eax, al 00401246 mov al, ds:byte_401258[eax] ; HEX table for comparison 0040124C or al, ds:byte_401273[ebx] ; converts to HEX 00401252 stosb ; stores result in EDI 00401253 dec ecx 00401254 jg short loc_401225 00401256 jmp short loc_40128E```

After this routine we have a buffer EDI that contains our serial in HEX format (just as you typed it in). Converting from 31 which is HEX for the character 1 into the HEX value of 1. Continuing on we reach some funky code at 0040128E :-

```0040128E mov edi, offset unk_402230 ; buffer 00401293 xor eax, eax 00401295 push 5 00401297 pop ecx ; counter 00401298 repe stosd ; stores value from EAX into edi, 5 DWORDs 0040129A dec eax ; eax = -1 0040129B mov esi, offset unk_4020F0 ; username 004012A0 mov edi, offset unk_402230 ; buffer 004012A5 mov ecx, [ebp+var_4] ; length of name 004012A8 xor edx, edx```

All the above does is clears out the buffer and puts our username into ESI and it's length into ECX. Here comes the fun :-

```004012AA lodsb ; puts first byte from EDI into AL 004012AB xor ah, al 004012AD imul eax, 89177313h ; maths, no point in reversing 004012B3 and eax, 55AA55AAh 004012B8 imul eax, 12299381h 004012BE xor eax, 0AA55AA11h 004012C3 imul eax, 61h 004012C6 xor ah, al 004012C8 or eax, 10030118h 004012CD imul eax, 988279h 004012D3 rcl eax, cl 004012D5 xor [edi+edx], eax 004012D8 add edx, 3 004012DB and edx, 0Fh 004012DE inc edx 004012DF dec ecx 004012E0 jg short loc_4012AA ; loops for the entire length of our name```

```004012E2 mov esi, offset unk_402170 ; company 004012E7 mov edi, offset unk_402230 ; buffer 004012EC mov ecx, [ebp+var_8] ; length of company 004012EF xor edx, edx 004012F1 lodsb 004012F2 sub ah, al ; as above 004012F4 imul eax, 89157313h 004012FA and eax, 55AA55AAh 004012FF imul eax, 12299387h 00401305 or eax, 0AA55AA11h 0040130A imul eax, 61h 0040130D xor eax, 10010114h 00401312 imul eax, 7918279h 00401318 xor ah, al 0040131A rcr eax, cl 0040131C xor [edi+edx], eax 0040131F add edx, 3 00401322 and edx, 0Fh 00401325 inc edx 00401326 dec ecx 00401327 jg short loc_4012F1 00401329 sub eax, [edi+8] ; additional (to top it off) 0040132C imul eax, 34814815h 00401332 add [edi+10h], eax 00401335 shr eax, 0Bh 00401338 and eax, 3 0040133B mov [edi], al```

What this mess of code does is take our name, one character at a time, manipulate it and store it, this is done for the entire length of our name. Notice how it only uses 28h bytes from the buffer.

```004012D8 add edx, 3 ; EDX started at 0, add 3 to it 004012DB and edx, 0Fh ; only allow for DL to hold 4 bits 004012DE inc edx ; increment by one to get to next DWORD```

As you can see the index to the buffer (EDX) can only go from 0 to F. Notice how it uses the same destination buffer, this overwrites the name code with the company code which is built from some of the name code. Just trace this routine a couple times you will get it. All this work generated a code 40 digits long which will be used later to compare against the RSA generated code from our serial number.

```0040133D push offset unk_402270 ; buffer 00401342 push offset word_402370 ; serial number we entered 00401347 push offset unk_402000 ; n 0040134C call sub_4013CD ; RSA Encrypt code```

The above code takes our serial number and the modulus n along with a return buffer and calls the RSA Encrypt function which will return the encrypted serial number.

```00401351 push 5 00401353 pop ecx 00401354 mov esi, offset unk_402272 ; RSA generated code from our serial 00401359 mov edi, offset unk_402230 ; serial we typed in 0040135E lodsd ; loads first 5 bytes of the RSA code to EAX from ESI 0040135F xor [edi], eax ; XORs 5 first bytes of our serial with the RSA one 00401361 jnz short loc_401382 ; if they are not equal jump to ERROR 00401363 add edi, 4 00401366 dec ecx 00401367 jg short loc_40135E ; try the entire 40 bytes 00401369 push 0 0040136B push offset aWellDone ; "Well done" 00401370 push offset aTheEnteredRegi ; "The entered Registration code is correct" 00401375 push ds:dword_4020D8 0040137B call j_MessageBoxA```

The comparison is a simple XOR of the values if they are the same the XOR will result in a 0. So lets sit back for a minute and think what we have to do to generate a valid serial number?. Did you figure out what scheme this keygen uses yet?. This is what it does :-

Serial = (Mangle(Name+Company)) ^ d mod n

Hold up!, We don't know what d is. Or do we ?, remember this piece of code :-

```00401347 push offset unk_402000 ; n 0040134C call sub_4013CD ; RSA Encrypt code```

Look what value unk_402000 holds :-

```00402000 db 0Ah 00402001 db 0 00402002 db 0D2h 00402003 db 0E9h 00402004 db 0BFh 00402005 db 9Bh 00402006 db 3Dh 00402007 db 25h 00402008 db 8Eh 00402009 db 47h 0040200A db 9Dh 0040200B db 8Ch 0040200C db 0C2h 0040200D db 3Ch 0040200E db 7Ah 0040200F db 33h 00402010 db 0E1h 00402011 db 0F8h 00402012 db 0EBh 00402013 db 0B3h 00402014 db 0ADh 00402015 db 0B1h```

This is our modulus n, it's in BIGNUM format which is used by RSA. The first 2 bytes tells RSA the size of the key. In our case it's 0Ah which is 10d, to get that value you do (10 * 16 = 160), 16 is the number base. The result is 160 bits, that's our keysize, so this means we are working with 160-bit RSA encryption. Now that we have n and we know our keysize we need to find e and d. In this case e is easy since you don't see it being pushed as a parameter into the RSA encrypt function we can assume it's the default value of 65537.

Start up tE's RSA Tool change the keysize to 160, put in the Modulus box the n that we found above and press the Factor N button. If you want press the small Get Size button to see that our key is truly 160 bits. After a few minutes you will get the P and Q values. Now click the Calc. D button and we will have our Decryption Exponent d which is what we need in order to have the program's private key (d,n) remember?. That is it pretty much, all that is left is coding a keygen that will take the username and company, mangle them like our target did (you just copy the mangling code from the target to your own code), pass the mangled code (make sure it's in BIGNUM format) along with d and n to the RSA Encrypt function and the return value will be your valid serial number.

From my keygen :-

```call Mangle ; mangles name and company to create our M```

; Keygenme uses the scheme: Serial = (Mangle(Name+Company)) ^ d mod n

```push 028h ; length of message to enc/dec push offset szTemp ; return buffer push offset szBuffer ; string to encrypt/decrypt (Mangle(Name+Company)) push offset RSA_n ; n push offset RSA_d ; decryption exponent call RSA_PRIVATE_ENCRYPT```

Refer to the included MASM code for a complete keygen (7k). I use the RSA functions taken from tE's keygens available at his site. I hope you learned something, I sure did.

Greets

tHE EGOiSTE :- thanks for the RSA Tool, sample keygens, and for this Keygen-Me.
My pals :- zip, CrackZ, and everyone else that I can't mention here :-).

Signing off - Goatass