published by +Tsehp feb 2001

### THIS TUTORIAL WILL NOT MAKE YOU A MEMBER OF TMG ###
######## DON'T TRY SUBMITTING THIS KEYGEN IN ##########

Required/Recommended Readings:
-------------------------------
Handbook of Applied Cryptography from tE's site - http://egoiste.cjb.net/
CrackZ RSA Paper - http://zencrack2.cjb.net/Tutorials/Rsa.htm
FTP Voyager v6.1.1.1 factoring RSA by PaRKeR - http://zencrack2.cjb.net/Tutorials/Parker2.htm

Tools:
------
RSA Tool 2 v1.2 - RSA keygeneration and factoring tool - http://egoiste.cjb.net/
SoftIce
IDA
MASM/TASM

Our Target:
-----------
RSA Keygen-me - http://www.tmg.f2s.com/index.html

Introduction:
-------------
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 aswell give up now.

This keygenme 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

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

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

Now that we have some idea of what we are looking for we can begin the real work.

Lets 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 SI and click Check again. F10 passed the SendMessageA
and you will see:

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

you should know what this means, the company is the same way.

The serial number is interesting tho.

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 ; multimple 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 SI 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 chracter 1 into the HEX value of 1. Damn it you
should know this I don't have to explain it.

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 loc_4012AA:
004012AA lodsb ;puts first byte from EDI into AL
004012AB xor ah, al
004012AD imul eax, 89177313h ;does some math, no point in understanding
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
004012F1 loc_4012F1:
004012F1 lodsb
004012F2 sub ah, al ;same crap 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 crap 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 all mess of code does is take our name, one character at a time, manipulate it and
stores 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 a value
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.
After our name is screwed with the company is screwed with aswell, 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 crack a doodle 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
0040135E loc_40135E:
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 bits
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

Got it ? GOOOOOOD

Hold up !! We don't know what d is. or do we ?
Remeber this piece of code ?

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

look what value unk_402000 holds.

00402000 unk_402000 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 mean we are working with 160bit 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 truley 160bits. 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. My keygen uses 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 Keygenme
***Keep up the AWSOME work***

my pals: zip, crackz, and everyone else that I can't mention here :)

Signing off - Goatass