Aerosol Posted December 19, 2014 Report Posted December 19, 2014 IntroductionHopefully 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.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 NeededAssuming 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):The target file (CryptoChallenge1.exe)IDA (Interactive Disassembler): Disassembler for computer software which generates assembly language source code from machine-executable code.OllyDBG: An x86 debugger that emphasizes binary code analysis, which is useful when source code is not available.PEiD: PE analyzes tool, detects most common packers, cryptors and compilers for PE files, it also detects hashes and cryptographic algorithms used in the PE file.RE-SIGS: IDA signature file to detect libraries used by programs.GODUP: OllyDBG plugin to load IDA signature files.RSA-Tool: Useful for generation of key pairs, encryption/decryption and also integer factorization (and that’s what we will use it for).TiBiNuCa: A Tiny Big Number Calculator (requires dotNetFx4).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:P: 1st large prime number.Q: 2nd large prime number.E: Public Exponent.N: Public Modulus.D: Private Exponent.Key generationChoose a key length (measured in bits).Generate the two random prime numbers P and Q.Choose a public exponent E such that GCD(E, (P-1)*(Q-1))==1), the most commonly used number is 65537.Compute the Public Modulus N = P * Q.Determine the Private Exponent (D) using the Modular multiplicative inverse formula D=E^(-1) mod ((P-1)*(Q-1)).The symbol (^) is used as the Exponent and not the XOR operator.(Mod) means modulo/modulus in computing and is an operation that finds the remainder of the division of one number by another.D must be kept private and must never be published! Alongside P and Q.EncryptionTo encrypt a message (M) (where M < N), we would use the following formula:C = M ^ E mod NDecryptionTo decrypt a given cipher © we would use the following formula:M = C ^ D mod NExample (in base 16)By following the steps above:Let’s choose a Keysize: 32 bits (which is totally unsecure).P = 2F6DBQ = 19CD3E = 10001 (base 16 of 65537).N = P*Q = 4C7B9EA81D = E^(-1) mod ((P-1)*(Q-1)) = 10001^(-1) mod ( (2F6DB-1) * (19CD3-1) ) = 10001^(-1) mod (2F6DA * 19CD2) = 10001^(-1) mod (4C7B556D4) = 72C6E47DThat 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 = 143B30CF800536563 ^ 10001 mod 4C7B9EA81 = 380323BEBC = 143B30CF8380323BEBNow 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 = 496E666F380323BEB ^ 72C6E47D mod 4C7B9EA81 = 536563M = 496E666F536563 = InfoSec.Target analysesLet’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 pressShift+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 labelsAnd 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 APIthat 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 address0x40115A, which calls another address: CALL 0×401189.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:lstrlenA at 0x40118E is used to get the length of our name, and then that length is moved to EBX.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 0×407847.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.The three next calls (0x4011F4, 0×401206 and 0×401218) 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 bufferPUSH 16 // basePUSH input // (typed serial, public modulus n, public exponent e)CALL _BigInNow we have:0x4083F8 = Serial in bignum.0×408400 = Public Modulus (N) in bignum.0×408404 = Public Exponent (E) in bignum.N = 8640FF9C022F0FB3447F82C6F23CA36703741985A9E35EE670B36B6553926A9DE = 10001Next is the call at 0×401235 is a reference to the function BigPowMod, which is the encryption formula, used as follows:0x4083FC = 0x4083F8 ^ 0×408404 mod 0×408400 or C=Serial^E mod NAfter that, a call at 0×401247 to BigOut function. It is the opposite of BigIn, convert from bignumber to base 16 string. The result is put in 0x407C47.Next comes the algorithm from 0x40124C to 0x40126E which has a loop that compares each character from 0×407847 (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 0×401266 into NOP’s. But that’s not ideal.The JNZ at 0×401266 inside the loop checks if two characters are equal, if not it jumps to address 0×401290 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).0x4012B0 is a function that has three calls to RtlZeroMemory which is used to clear the data.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:The Name must be longer than 3 and shorter than 15 characters.The Serial must contain either 63 or 64 characters.N = 8640FF9C022F0FB3447F82C6F23CA36703741985A9E35EE670B36B6553926A9DE = 10001The target compares the MD5 hash of the Name with the result of the BigPowMod (C=Serial^E mod N).The Public Exponent N is 256 bits.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 = 960A589F7B9AA6E2FBF05A5F5E507465Q = E5109FD956BC44F85A6B0CF071A22DD9Now click “Calc. D.”D = 82CC4CBC47FC65C57814EAEABD128AF6DEB2475AE59DF66F78C90BA1924D57C1Now that we have our Private Exponent, let’s calculate our valid serial:We know that the encryption formula is:C = Serial ^ E mod NAnd:C must be equal to MD5(NAME) which means C=MD5(NAME)So the decryption formula must be:Serial = C ^ D mod NLet’s try that out:NAME = Jamal ChahirC = MD5(NAME) = 4D945493477571DE563E281CA4145EB9D = 82CC4CBC47FC65C57814EAEABD128AF6DEB2475AE59DF66F78C90BA1924D57C1N = 8640FF9C022F0FB3447F82C6F23CA36703741985A9E35EE670B36B6553926A9DSerial = C ^ D mod NThe calculation in TiBiNuCa gives us the following result as you can see below:20F9C3683546ECDBF4F4469525B1DE915056F81E6708F78B7210858E40D25416Trying that on the challenge gives us the right message.ConclusionIn 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:IDA : https://www.hex-rays.com/products/idaOllyDBG: OllyDbg v1.10PEiD: PEiD Download - SoftpediaRSA-Tool: https://tuts4you.com/download.php?view.455RE-SIGS: https://tuts4you.com/download.php?view.3407GODUP: https://tuts4you.com/download.php?view.54TiBiNuCa: https://www.dropbox.com/s/4dipnjrlggrpz1w/TiBiNuCa.rar?dl=0Target: https://www.dropbox.com/s/4va2kyqyd729hjd/CryptoChallenge1.rar?dl=0Sources:en.wikipedia.org/wiki/RSA_(cryptosystem) Quote
