Return
to Miscellaneous Papers (RSA)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
RSA Tool 2 v1.2 - RSA key generation and factoring tool - http://egoiste.cjb.net/
SoftICE, IDA & MASM.
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
Return
to Miscellaneous Papers (RSA)