Breaking Software Protection - RSA

Introduction

Hopefully you are familiar with Assembly language and have some little knowledge on how to use reverse engineering tools such as Debuggers, Disassemblers, PE Analyzers, etc.

FREE role-guided training plans

Get 12 cybersecurity training plans — one for each of the most common roles requested by employers.

Download Now

This article will only concentrate on the RSA cryptosystem and how to reverse it to get a valid key for your name. We will be targeting a challenge made especially for this tutorial to demonstrate how to do that.

Tools Needed

Assuming you've already got the required knowledge on how to use reverse engineering tools, these are the essential tools for this article (the download links are in the bottom):

What is RSA?

RSA is a public-key cryptosystem. It was developed in 1977 by Ronald Rivest, Adi Shamir and Leonard Adleman. The fact that it's a public-key cryptosystem means that it uses a public and a private key for the encryption/decryption of data. Its strength lies in the integer factorization problem (the larger the number, the harder and longer it will take to factorize) commonly known as the RSA Problem.

RSA uses the following parameters:

1. P: 1st large prime number.
2. Q: 2nd large prime number.
3. E: Public Exponent.
4. N: Public Modulus.
5. D: Private Exponent.

Key generation

1. Choose a key length (measured in bits).
2. Generate the two random prime numbers P and Q.
3. Choose a public exponent E such that GCD(E, (P-1)*(Q-1))==1), the most commonly used number is 65537.
4. Compute the Public Modulus N = P * Q.
5. Determine the Private Exponent (D) using the Modular multiplicative inverse formula D=E^(-1) mod ((P-1)*(Q-1)).
   1. The symbol (^) is used as the Exponent and not the XOR operator.
   2. (Mod) means modulo/modulus in computing and is an operation that finds the remainder of the division of one number by another.
   3. D must be kept private and must never be published! Alongside P and Q.

Encryption

To encrypt a message (M) (where M < N), we would use the following formula:

C = M ^ E mod N

Decryption

To decrypt a given cipher (C) we would use the following formula:

M = C ^ D mod N

Example (in base 16)

By following the steps above:

1. Let's choose a Keysize: 32 bits (which is totally unsecure).
2. P = 2F6DB
3. Q = 19CD3
4. E = 10001 (base 16 of 65537).
5. N = P*Q = 4C7B9EA81
6. D = E^(-1) mod ((P-1)*(Q-1)) = 10001^(-1) mod ( (2F6DB-1) * (19CD3-1) ) = 10001^(-1) mod (2F6DA * 19CD2) = 10001^(-1) mod (4C7B556D4) = 72C6E47D
7. That was calculated using TiBiNuCa:
   

Now that we have our key pairs, we can encrypt our message:

M = InfoSec which equals 49 6E 66 6F 53 65 63 in base 16. And since M > N we can split M into blocks smaller than N (M<N) as follows:

496E666F ^ 10001 mod 4C7B9EA81 = 143B30CF8

00536563 ^ 10001 mod 4C7B9EA81 = 380323BEB

C = 143B30CF8380323BEB

Now in order to decrypt the above cipher we should have the Private Exp (D) but what happens if we don't! That's where the factorization comes. That's the job of RSA-Tool. (We'll see how to do Factor N later).

143B30CF8 ^ 72C6E47D mod 4C7B9EA81 = 496E666F

380323BEB ^ 72C6E47D mod 4C7B9EA81 = 536563

M = 496E666F536563 = InfoSec.

Target analyses

Let's try to apply all of the above in our challenge.

I always check the target before everything, so that's what we will do.

Open up the target "CryptoChallenge1.exe" and Type any Name/Serial, I've typed my name, and for the serial I had to make many tries before it gave me that message "SERiAL STATUS: UNREGiSTERED" (the target checks for the serial's length).

Now we analyze our target to see if it's packed/protected.

As you can see, the analysis shows it was compiled using MASM32 / TASM32. But the crypto analysis using KANAL shows the target has some crypto inside (MD5 and BigLib: an assembly bignum library)

Alright, now that we know what we're dealing with, we will use IDA to extract these cryptos' signatures from our target. To do that you should have the sig file "RE-SIGS" (download link in the bottom).

PS: Before opening IDA, you should copy the signature file "RE-SIGS" in the folder IDAsig.

Open the target in IDA and go to menu View > Open subviews > Signatures or just press
Shift+F5. A list of applied library modules shows up. To apply a new signature, you can either press "Ins" or right-click > Apply new signatures. A new window will show up.

Choose RESIGS and click OK. You will be able to see the changes in the functions window. 33 functions were applied, which means it has found the crypto algorithms and libraries and has given them their real names. Now we will export this result so that we can use it in our debugger. To do that, go to File > Produce file > Create MAP file as shown below:

Save your file in a place you can remember, and leave the MAP file options as they are, as shown below (just click OK).

Now that we have our map file, let's debug.

PS: Before opening OllyDBG you should put the plugin "GODUP Plugin" in the plugins section of the debugger you're using, because that's what we will be using to import our map file.

Fire up the target file into OllyDbg and go to:

Plugins > GODUP Plugin > Map Loader > Load labels

And choose the map file you've saved before.

The code is easy and simple, there are the initial API's that load the PE file and after that there is GetDlgItemTextA (gets a text from an editbox/textbox and puts it in a buffer).

Let's put a breakpoint on that API and see what it really gets (simple click on address 0040107A and press F2).

The tracing shows that the API is used to get the typed name. The target then checks if a name was typed, or it will show a text saying "NAME STATUS : NO NAME", after that it checks if the length of the name is longer than 15 (CMP EAX,0F) and shorter than 3 (CMP EAX,3). If the name is longer than 3 and shorter than 15, it jumps to another GetDlgItemTextA API

that gets the typed serial and does the same as for the name checks, except that the length must not be longer than 64 (CMP EAX,40) and not shorter than 63 (CMP EAX,3F). If everything is good, it will jump to address

0x40115A, which calls another address: CALL 0x401189.

What might that address (00401189) contain? Let's go check it out, shall we!

The address sends us to the challenge's RSA routine shown below:

The tracing of that function shows that:

1. lstrlenA at 0x40118E is used to get the length of our name, and then that length is moved to EBX.
2. The three following calls (MD5Init, MD5Update and MD5Final) generate the MD5 hash for the name. That hash is then converted to Hexadecimal using HexEncode at 0x4011B2 and is put in address 0x407847.
3. The calls (0x4011B9, 0x4011C5, 0x4011D1 and 0x4011DD) reference to BigCreate. This API is used by BigLib to create a bignumber and initializes it with the value InitValue.
4. The three next calls (0x4011F4, 0x401206 and 0x401218) reference to BigIn, which is used to fill the given bignumber with the null-terminated string in base (16 in this case). Here is an example of that function:

   PUSH output // our bignumber buffer

   PUSH 16 // base

   PUSH input // (typed serial, public modulus n, public exponent e)

   CALL _BigIn

Now we have:

0x4083F8 = Serial in bignum.

0x408400 = Public Modulus (N) in bignum.

0x408404 = Public Exponent (E) in bignum.

N = 8640FF9C022F0FB3447F82C6F23CA36703741985A9E35EE670B36B6553926A9D

E = 10001

1. Next is the call at 0x401235 is a reference to the function BigPowMod, which is the encryption formula, used as follows:

   0x4083FC = 0x4083F8 ^ 0x408404 mod 0x408400 or C=Serial^E mod N

2. After that, a call at 0x401247 to BigOut function. It is the opposite of BigIn, convert from bignumber to base 16 string. The result is put in 0x407C47.
3. Next comes the algorithm from 0x40124C to 0x40126E which has a loop that compares each character from 0x407847 (md5 hash of our name) with each character from 0x407C47 (our Serial). It is easy to make it accept any serial just by patching the JNZ at 0x401266 into NOP's. But that's not ideal.
4. The JNZ at 0x401266 inside the loop checks if two characters are equal, if not it jumps to address 0x401290 that has a SetDlgItemTextA which outputs "SERiAL STATUS: UNREGiSTERED", or it doesn't jump and shows "SERiAL STATUS: REGiSTERED". After each SetDlgItemTextA call, there are two calls (CALL 0x4012B0) and (CALL 0x4012DE).
5. 0x4012B0 is a function that has three calls to RtlZeroMemory which is used to clear the data.
6. 0x4012AA is a function that has four calls which reference to BigDestroy. It destroys the bignums that were created by BigCreate.

This is what we know so far:

1. The Name must be longer than 3 and shorter than 15 characters.
2. The Serial must contain either 63 or 64 characters.
3. N = 8640FF9C022F0FB3447F82C6F23CA36703741985A9E35EE670B36B6553926A9D
4. E = 10001
5. The target compares the MD5 hash of the Name with the result of the BigPowMod (C=Serial^E mod N).
6. The Public Exponent N is 256 bits.
7. The serial should be in base 16.

Alright, now we need to reverse C=Serial^E mod N into M=C^D mod N (remember RSA's Encryption/Decryption formulas!) so that we can get a valid serial. For that we need to factor N to get the Private Exponent D.

Load up RSA-Tool and copy the N into the Modulus N textbox (to get the keysize click Exact size) and click Factor N and wait until it finds P and Q. This will take a while depending on the computer you're using (it took 1h in my computer). Once the tool finishes factoring, you will see P and Q textboxes filled:

P = 960A589F7B9AA6E2FBF05A5F5E507465

Q = E5109FD956BC44F85A6B0CF071A22DD9

Now click "Calc. D."

D = 82CC4CBC47FC65C57814EAEABD128AF6DEB2475AE59DF66F78C90BA1924D57C1

Now that we have our Private Exponent, let's calculate our valid serial:

We know that the encryption formula is:

C = Serial ^ E mod N

And:

C must be equal to MD5(NAME) which means C=MD5(NAME)

So the decryption formula must be:

Serial = C ^ D mod N

Let's try that out:

NAME = Jamal Chahir

C = MD5(NAME) = 4D945493477571DE563E281CA4145EB9

D = 82CC4CBC47FC65C57814EAEABD128AF6DEB2475AE59DF66F78C90BA1924D57C1

N = 8640FF9C022F0FB3447F82C6F23CA36703741985A9E35EE670B36B6553926A9D

Serial = C ^ D mod N

The calculation in TiBiNuCa gives us the following result as you can see below:

20F9C3683546ECDBF4F4469525B1DE915056F81E6708F78B7210858E40D25416

Trying that on the challenge gives us the right message.

Conclusion

In this article, I have shown you how the RSA cryptosystem works and how to reverse it. I hope all of this was clear enough and that you've learned something new from it.

Download links:

What should you learn next?

From SOC Analyst to Secure Coder to Security Manager — our team of experts has 12 free training plans to help you hit your goals. Get your free copy now.

Get Your Plan

Sources:

• en.wikipedia.org/wiki/RSA_(cryptosystem)