Description FTP client (read PaRKeR's note at the end)
Protection Type RSA.
Target Name FTP Voyager v6.1.1.1 French, but this essay can be easily changed to fit v7.0.0.0 (English) since the algorithm is the same. By PaRKeR.

"Yes indeed, it was about time someone took the initiative and gave us some real reading material on RSA protections which as PaRKeR says are certainly the future. I'd been hoping to give you something similar using a 512-bit key yet sadly factoring the modulus has proved a task too much for my P166. Read this very good tutorial slowly, perhaps follow along, you'll certainly learn something unless you've cracked many of these protections before. In fact what we need are ways of bypassing RSA schemes (changing the keys for example) because pretty soon all of our targets will use key lengths which are unfactorable in a reasonable length of time. This is a very good essay and please read PaRKeR's note at the bottom". "Slightly edited by CrackZ".

Happy new year too all. Have a lot of fun with cryptography this new year and beware, RSA will get into the public domain soon now. For my part, I promised for this new year to learn Russian and to keygen Secure CRT (damn ElGamal :-) ).

RSA, A Practical Example

More and more shareware authors are now choosing to use cryptographic algorithms instead of their own serial schemes. RSA is a "common" choice for these authors. This paper will not deal with RSA basics but with a practical example of this technique used in FTP Voyager. If you want to learn more about RSA, read CrackZ's essay, Lucifer48's one or the RSA FAQ available at rsasecurity.com.

Now the tools needed to follow this paper :-

- FreeLIP v1.1 (stands for Free Large Integer Package) : a package of C sources giving an implementation for large integers and common operations with them. Since it was first developed for a RSA challenge, it also has some factorization functions. In my view, this package is better than the MIRACL library.

You can easily find it by doing a FTP search.

- RSAREF v2.0 : a cryptographic toolkit by RSA Laboratories giving implementation for RSA, MD5, DES and more. Once again it is pure C and you can find it doing a FTP search.

- SoftICE v4.01, or whatever version you want.
- IDA v3.84b to get a nice dead listing.
- FTP Voyager v6.1.1.1 French, but this essay can be easily changed to fit v7.0.0.0 English since the algorithm is the same.

FTP Voyager uses RSA256 as a part of the key checking algorithm, and I first decided to have a look at it after egis released his keygen giving n and e in the nfo in order for us to practice RSA. So greetings for this tutorial go to him.

Let's get started.

Launch the program, go to the register dialog, enter your name, e-mail, and a serial number. Having a look at a valid serial, you will notice it is 64 chars long. Indeed, when you encrypt some number using RSA using the private key (maybe some people will say it is decrypt, I kinda got lost with that since there is an encryption and decryption function with both private and public key in RSAREF), the encrypted number has the length of the modulus, in our case 32 bytes. Having 2 chars per byte, it gives you a length of 64 chars for the encrypted serial.

So enter a serial (64 bytes : with 0-9 or a-f), put a bpx on GetWindowTextA, click on OK. SoftICE will break three times on this function, then you will have to trace through the code a little while. You'll get to some remarkable piece of code where the
author has blacklisted a load of dudes. This is particularly gaudy with IDA :-

.text:0044AFF4 PUSH aMarquis ; "MARQUIS"
.text:0044AFF9 LEA ECX, [ESP+18h]
.text:0044AFFD CALL j_?Find@CString@@QBEHPBD@Z ; CString::Find(char const *)
.text:0044B002 TEST EAX, EAX
.text:0044B004 JZ loc_0_44BE3C
.text:0044B00A PUSH aTheStardoggCha ; "ThE STaRDoGG CHaMPioN"
.text:0044B00F LEA ECX, [ESP+18h]
.text:0044B013 CALL j_?Find@CString@@QBEHPBD@Z ; CString::Find(char const *)
.text:0044B018 TEST EAX, EAX
.text:0044B01A JZ loc_0_44BE3C

We are getting near to our aim. You will get to a point where the length of the serial entered is compared to 0x1C. To prevent you from doing unnecessary tracing I will just tell you that this piece of code is also used for the decrypted serial and it is this
code which has to be 28 bytes long. So we just go on and get here :-

.text:0044BC29 MOV WORD PTR [ESP+0F0h], 0B45Dh
.text:0044BC33 MOV WORD PTR [ESP+0F2h], 0BAAAh
.text:0044BC3D MOV WORD PTR [ESP+0F4h], 0CC51h
.text:0044BC47 MOV WORD PTR [ESP+0F6h], 5083h
.text:0044BC51 MOV WORD PTR [ESP+0F8h], 68ACh
.text:0044BC5B MOV WORD PTR [ESP+0FAh], 556Fh
.text:0044BC65 MOV WORD PTR [ESP+0FCh], 2EB5h
.text:0044BC6F MOV WORD PTR [ESP+0FEh], 1A52h
.text:0044BC79 MOV WORD PTR [ESP+100h], 356h
.text:0044BC83 MOV WORD PTR [ESP+102h], 0E126h
.text:0044BC8D MOV WORD PTR [ESP+104h], 0FC3Eh
.text:0044BC97 MOV WORD PTR [ESP+106h], 0DF20h
.text:0044BCA1 MOV WORD PTR [ESP+108h], 8DDh
.text:0044BCAB MOV WORD PTR [ESP+10Ah], 38A8h
.text:0044BCB5 MOV WORD PTR [ESP+10Ch], 0D7C2h
.text:0044BCBF MOV WORD PTR [ESP+10Eh], 1E2Bh


Hmm, 32 bytes, interesting, isn't it? Having a closer look, we see just before this part :-

.text:0044BC05 MOV EAX, 1
.text:0044BC0A PUSH ECX
.text:0044BC0B MOV [ESP+108h], AX
.text:0044BC13 MOV [ESP+10Ah], AX


If you had a look at the RSAREF, you will probably know that 0x10001 is often used as a public exponent. So it seems we have our modulus n and our public exponent e. This supposition is confirmed with a call a little further : we push our entered
serial, the modulus, the exponent, and get in return a new number :-

.text:0044BCE3 LEA EDX, [ESP+0F8h]
.text:0044BCEA LEA EAX, [ESP+118h]
.text:0044BCF1 PUSH EDX
.text:0044BCF2 LEA ECX, [ESP+0D8h]
.text:0044BCF9 PUSH EAX
.text:0044BCFA PUSH ECX
.text:0044BCFB CALL sub_0_44A410

You can trace into this call, it will give you some hints on what RSA in assembler can look like. That's where I will end the tracing of the code. After this decryption, other checks are made on the new code dealing with the user name and e-mail, the
date, the type of license, etc. I will not get into them, because it is not the main point of the paper. If you want to register FTP Voyager then egis' keygen will suit you (even if it doesn't allow to choose the license type *grin*), but I think the length of the
RSA key will be increased soon (I was surprised in fact to see that v7.0.0.0 was still using the same key...).

Now for the mathematics. We have the following :-

n=0x1E2BD7C238A808DDDF20FC3EE12603561A522EB5556F68AC5083CC51BAAAB45D
e=0x10001

The next step is the factorisation of the modulus to get the two primes p and q. I did that operation on a Unix server with 8 processors (but the algorithm was not multithreaded so in fact only one processor was used, I'd like to take this opportunity to ask for a distributed algorithm btw :-), and it lasted 16 hours. I used a factorisation function of FreeLIP based on the Pollard-Rho algorithm : you just have to make a simple C program asking for a large integer and displaying the two primes when done. Read the doc of FreeLIP, it is basic.

Now, we have :-

n=0x1E2BD7C238A808DDDF20FC3EE12603561A522EB5556F68AC5083CC51BAAAB45D
e=0x10001
p=0xA7893C5A9B2A1D345435341FDC34534AE91BEEF6476DCF6D
q=0x2E1A41AB164732B1

Now we just have to use some small C programs with FreeLIP to make multiplications and divisions, or use some mathematical program as MatLab or Mathematica or Maple (recommended by CrackZ - contact me if you need it), and we
can then have the private exponent :-

d=0x5376957703A4546122D8F84E540B73A51A982FDC2F71F2C2F1F26F2E82FA6C1

We are done with all the maths :-) Now the implementation using RSAREF. First of all, you have to know that some modifications have to be done in RSAREF. Indeed, in my first attempt, I tried to use the public functions of rsa.c : RSAPublicEncrypt, RSAPrivateEncrypt, RSAPublicDecrypt, RSAPrivateDecrypt. But they were not doing what I expected them to do. In fact it is because the "main" RSA functions are static for rsa.c : RSAPublicBlock, RSAPrivateBlock. So just remove the static and add them to rsa.h and you will get some functions doing "straight" encryption and decryption. We
now have all that we need. The structure for RSA private key (R_RSA_PRIVATE_KEY) uses more numbers than the usual n and d, in order to make faster operations using the Chinese remainders theorem, just read the docs to be fixed.

Here is the prototype for RSAPrivateBlock :

int RSAPrivateBlock (output, outputLen, input, inputLen, privateKey)
unsigned char *output; /* output block */
unsigned int *outputLen; /* length of output block */
unsigned char *input; /* input block */
unsigned int inputLen; /* length of input block */
R_RSA_PRIVATE_KEY *privateKey; /* RSA private key */

I think everyone who knows some C will get how this is working. In our case, we will enter our 28 bytes long serial as input, inputLen being 28, and our private key, and we will have in return a new code of 32 bytes long (length of the modulus, remember?) as output. To check, you can either use the RSAPublicBlock function, or directly check with SoftICE in memory.

Here is the key coming from my keygen :-

static R_RSA_PRIVATE_KEY PRIVATE_KEY = {
256,
{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x1E, 0x2B, 0xD7, 0xC2, 0x38, 0xA8, 0x08, 0xDD, 0xDF, 0x20, 0xFC, 0x3E,
0xE1, 0x26, 0x03, 0x56, 0x1A, 0x52, 0x2E, 0xB5, 0x55, 0x6F, 0x68, 0xAC,
0x50, 0x83, 0xCC, 0x51, 0xBA, 0xAA, 0xB4, 0x5D},
{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01},
{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x05, 0x37, 0x69, 0x57, 0x70, 0x3A, 0x45, 0x46, 0x12, 0x2D, 0x8F, 0x84,
0xE5, 0x40, 0xB7, 0x3A, 0x51, 0xA9, 0x82, 0xFD, 0xC2, 0xF7, 0x1F, 0x2C,
0x2F, 0x1F, 0x26, 0xF2, 0xE8, 0x2F, 0xA6, 0xC1},
{{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0xA7, 0x89, 0x3C, 0x5A, 0x9B, 0x2A, 0x1D, 0x34,
0x54, 0x35, 0x34, 0x1F, 0xDC, 0x34, 0x53, 0x4A, 0xE9, 0x1B, 0xEE, 0xF6,
0x47, 0x6D, 0xCF, 0x6D},
{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x2E, 0x1A, 0x41, 0xAB,
0x16, 0x47, 0x32, 0xB1}},
{{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x52, 0x8C, 0x20, 0xEB, 0xB7, 0xD6, 0x39, 0x4B,
0x86, 0x4E, 0x2C, 0x9F, 0xA2, 0x1D, 0x3A, 0x09, 0x07, 0xF0, 0x96, 0x7E,
0x4C, 0x55, 0x83, 0xC5},
{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x07, 0x73, 0x76, 0xE9,
0x8F, 0xD0, 0x32, 0x01}},
{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x0D, 0xF0, 0x75, 0x4E, 0x0F, 0x4A, 0x4B, 0x52,
0xF5, 0x43, 0xAF, 0xCF, 0x49, 0x17, 0x27, 0x10, 0x79, 0xB7, 0xA1, 0xFD,
0x46, 0xD1, 0x3C, 0xBA}
};

Lots of numbers :-). To conclude, I will say that this keygen was for me a pretty interesting experiment, in fact my first practical RSA exercise. But once the RSA part is done, there is still work to do to make a keygen and I advise you to have a look at the way the date is stored in the key and used. Please do not use this tutorial to make and release your own keygen, it would
be lame and noticeable. In fact you shouldn't even use this work to register the program if you didn't pay for it.

Greetings for this tutorial go to :-

TNO members : greetings and all, well nothing I have not yet told you :-).
egis : nice work with all the crypto stuff, I hope we will meet some day on IRC :-)
Dimedrol and Ivanopoulo : just the same, too bad all of you guys don't write papers.
Russ97 : good work, and don't forget your resolution for Y2K :-)
CrackZ : hope your new site will be done soon (as your reading this now, assume it is) :-).
French Scene : if there is anything remaining, keep on resisting.

PaRKeR [tNO '99]


RSA


© 1999, 2000 Hosted by CrackZ, authored by PaRKeR. 5th January 2000.