Crackme # 1 analysis by PE_Kill

Foreword

I have not been researching anything for a long time, so to speak retired. But then I was struck by the next craft of a lot of PE_Kill'a well-known in certain circles. Because I happened to solve his previous work in the framework of CRACKL @ B Contest 2010 , which in turn was quite interesting, I decided to look at his new “brainchild”.

What awaits you under the cut: CRC32 fake, brute key for RC4, factorization for RSA, as well as the use of collision for MD4 and the generation of two different messages with the same hashes. All this and much more under the cut.

The article is not intended for a beginner, I will not chew all the actions. The purpose of which is to write keygen.

Introduction

As mentioned above, for a long time I did not do the cut. Therefore, I had to spend some time "swinging". Also partially restore your toolkit, as I have only OllyDbg and  IDA left . The latter will not be used. And recalling his task from the contest, I was expecting something interesting that would make me activate my brain much more than usual. And I was not mistaken.

To battle

Intelligence

Well, for starters we need crackme itself . We open it in Ollydbg and see that it is packed using UPX, well, now they are unlikely to scare anyone. I took the path of least resistance, and unpacked it with QUnpack . Further, following my technique developed over the years, I decided to analyze it using various crypto, hash, and checkum algorithms. To do this, I used the SnD Reverser Tool , which informed me that I found CRC32 , RC4 , MD4 . Now, knowing all this, you can begin more active actions.

Behind Enemy Lines

So, having finished the static analysis, we proceed to the dynamic analysis, i.e. come on debiting. Again, open the crackme (hereinafter - the crack) in OllyDbg (hereinafter - the olka), but not the original, but unpacked. Press Ctrl + G and enter GetDlgItemTextA, so we go to the beginning of this function, put a breakpoint and start it. Enter the name and some license for the test and click Check. So we started at our breakpoint, press Alt + F9 and get into the code of our crack right after the call to the name function.

After that there are two checks of the length of the name, the first is that the name was entered, and the second is meaningless. In the second check, if the name is 50, we are informed that the name is long and exit. Why is it meaningless, but because the name is obtained as follows:

GetDlgItemTextA(hDlg, IDC_NAME, szName, 50);

And this means that the maximum it can take is a string of no more than 50 characters, where the 50th character is the character of the end of the line, and we have that the line will never exceed 49 characters. Similarly, with a license, but this is not critical. After all this comes the cherished function, in which all the most interesting happens, I called it - CheckLicense.

In the enemy trenches

And so we are in the heart. The first couple of functions is the translation of license characters in upper case, and then the translation of the license into an array of bytes and there is already a check for the length of the license.

In the line feed function, it will be seen that it checks the license against the alphabet (0–9, AF), i.e. A license is some kind of data array translated into a hex string, and at the end it is checked whether the length of the received array is 0 × 90 bytes. It follows that the license must have a length of 0 × 90 * 2 = 0 × 120 (288) characters.
After all this, we return to the main function. Next is the calculation of the control sum of the first 0 × 8C bytes of this array (hereinafter we will call this array - license) with 4 byte number, which is located at the end of the license.

And then there are 10 circles of manipulations with the name, the result of each circle is placed in a separate element of an array of 4 byte numbers. Looking ahead I will say that this array will be the key for RC4, so I will call it the key.

Round 0–2:

All circles except Round1 are used once, therefore they were perceived by the compiler as inline functions, but round1 itself will still be used twice at the end as a function to obtain a control sum of data.

Round 3-4:


Round 5-7:


Round 8-9:


As you can see, round9 is identical to the calculation of the control sum of the license, which was at the very beginning.
After all this, with a simple manipulation of the key, we find the values ​​for the subsequent xsor of the same key. Also, this value will be used in another test after decrypting the very first 0 × 8C bytes of the license using RC4 and with the key that we received from the name. And in another manipulation, the result of which we will need further.


Then we get two more values ​​that we will need next. With XorKey, we get the number of bits for the shift, and from the key the desired byte, which we must get when shifting a certain value by the number of bits that we received above. Well, actually the RC4 decryption itself. As I determined that this is it, well, firstly, I know the list of possible algorithms that are used here, secondly, by the key initialization algorithm, who have repeatedly met this algorithm, I also think that we would quickly recognize it.

And here is the check where this value was needed. After decryption, we should have License [34] (if we consider the license as an array of 4 byte values, which we will continue to do) the value is identical to XorKey. This ends the easiest part in this crack. What goes further, it took me much more time and effort.
Next comes the calculation of CRC32 8 bytes of license, which should be 0xFFB97FE0. If all goes well, then these 8 bytes further serve as the key to decrypt the two hardcoded values ​​according to the RC4 algorithm and should receive two faces on the output. So, here is the first interesting place that is in the crack. Googling, I did not find any collisions for RC4 that would help me find the key, because it was decided to brute. But sticking 8 bytes in the forehead is a bit silly and long. It's good that I already dealt with a fake CRC32 and I realized which way to go. For those who don’t know, in a few words it sounds like this: “from any data you can get the CRC32 we need, just add / replace the 4 necessary bytes”. You can read more about this here.. From here we have that now we need to brute not 8 bytes, but 4, which makes our life much easier. I decided not to write abstruse brutters using different technologies, multithreading, parallel computing. I wrote a simple single-threaded bruter that found a key on my AMD II X2 250 in 15 minutes.
This is what my bruter looks like:

int main()
{
	uint32_t key[2] = {0, 0};
	uint8_t *pkey = (uint8_t *)&key;
	rc4_key skey;
	uint32_t rc4_data[2];
	do {
		fix_crc_end(pkey, 8, 0xFFB97FE0);
		prepare_key(pkey, 8, &skey);
		rc4_data[0] = 0xE6C5D5E1;
		rc4_data[1] = 0x41C98EAB;
		rc4((uint8_t *)rc4_data, 8, &skey);
		if (rc4_data[0] == 0xFACE0001 && rc4_data[1] == 0xFACE0002) {
			printf("Key: ");
			for (int i = 0; i < 8; i++) {
				printf("%02X", *pkey++);
			}
			printf("\n");
			break;
		}
	} while (key[0]++ <= 0xFFFFFFFF);
	printf("\n\n\t\tFin!\n");
	return 0;
}

I found the correct key, now I can generate keys that will pass all the above passed checks. Knowing all this, you can imagine the general form of the license:

typedef struct _LICENSE {
	unsigned char M1[0x40];
	unsigned char M2[0x40];
	unsigned int  FaceKey1;
	unsigned int  FaceKey2;
	unsigned int  AfterXorKey;
	unsigned int  LicenseCheckSum;
} LICENSE, *LPLICENSE;

The last 4 values ​​have already been parsed, only the first 0 × 80 bytes of the license remain, looking ahead I will say that these are two messages of 0 × 40 bytes.

After the faces, the function is immediately called, into which the pointer to the license is transferred, I already have it signed as  RSA . I will try to explain a little how I understood it. After entering this function, 3 identical functions go in a row, into which a pointer to the data array, its size and a pointer to the buffer with the result are passed. This function reads from the array byte-wise and in reverse order, i.e. from the last element of the array to the first. This is very similar to initializing large numbers. This is the first thing that occurred to me.

The second call to this function only confirmed my hunch, when I looked in the dump at the array from which the initialization was going on, I saw these treasured three bytes 01 00 01. This value is very often used as an exponent in the implementation of RSA decryption. It follows that the first function initialized the public key N. After which I pulled it out of the dump and factorized, for factorization I used msieve under the GPU. The key is small, only 256 bits took a little more than 4 minutes to factorize it.

Before, I always tried to adhere to the rule that in keygen you need to use the same libraries and classes as in the victim. So I decided to look for clues about what kind of library for large numbers was used. Having a bit of a traction, I came across such a message, driving the text of the message into Google, I quickly found the library that is being used, it turned out to be BigDigits .

After that there is a check that the 6th element of the first message would be equal to the same element of the second. And also so that this value when shifting to the right by ShiftCount bit has a low byte the same as NeedByte. All these two values ​​we received above.

After that there is a check that the CRC32 of the first and second messages were not equal, then the same comparison is made only with the round1 function. After everything has been taken apart, you can see that in this part the crack does not seem to be anything special, as well as in the next one.

And at the very end are the MD4 hashes of the first and second messages, and if they are equal, then we successfully passed the test. But wait, if these messages should have a different checksum for two functions, then the messages should be different, but at the same time they should have the same hashes, which does not fit here.
And here Google comes into play again with the request “md4 collisions”, and there really is infa on collisions for MD4, and it’s different, there are voluminous articles, but there are superficial ones. And in one of these articles I find that the Chinese were able to create two different messages of 0 × 40 bytes with the same hashes, here it is. Now we google with the following request “md4 collisions sources” and the truth is, there are source codes for finding two such messages, but they were written under Linux, where the random function returns a 4-byte number, and in windows it returns just 0 and RAND_MAX ( 32767). Because of what I had long problems, why it generates me the wrong messages. After the prompt, I rewrote the random function with Delphi, and it worked out with a bang.

Writing keygen

I will not describe all the steps in writing keygen, but only pay attention to some important points. First we create a key for RC4 with a name, I’ll omit it, there’s nothing complicated, for the lazy you can just rip this whole part. Next, you need to find the value for the key xor and poke the key itself, after which from this value find ShiftCount and NeedByte. This part can also be ripped, to find the desired byte, you also need to rip a 256-byte table. We write the XorKey value into the license according to the structure given above. You can also write down two values ​​that are the key to finding faces, they will be constant and the same for everyone. After that, you need to generate two messages, but the fact is that there, if you remember, the 6th element must have a certain format. The message generation function itself does not have any parameters, but since you need to pass two values ​​to it, these are ShiftCount and NeedByte. We change the prototype and add a couple more lines to the code of this function itself. It was:

if(X0[ 5] != X1[ 5])
        continue;

And it became:

if(X0[ 5] != X1[ 5])
        continue;
else
        if (((X0[5] >> c) & 0xFF) != b)
                continue;

where c is ShiftCount, b is NeedByte.
After which the messages are placed in X0 and X1, respectively. Then we combine these messages into one big one and put it into RSACrypt. The decryption itself goes in blocks of 0 × 20 bytes, so we will encrypt it. But because of this, too, I had problems, who does not know, the message (M is our block of 0 × 20 bytes) must be less than the public key (N), this is not taken into account in the cracks, and it decrypts everything in a row. Therefore, we must take this into account. I added a check to the encryption function, if N <M, then we go out and generate new messages, which is why the license generation time is delayed up to 15 seconds. After everything is successfully encrypted using RSA, we encrypt the entire license without the last value in the structure using RC4 with the key that we received from the name. And the last step is to calculate the control sum of that part of the license,

That's all!

Materials

• www.rsdn.ru/article/files/classes/SelfCheck/crcrevrs.pdf - CRC32 fake
• www.en.wikipedia.org/wiki/MD4#Collision_Attacks - MD4 collisions
• www.google.com
• www.wikipedia.org

Source code

• github.com/reu-res/Keygen-for-CrackMe-1-by-PE_Kill - Bruter and keygen

P.S. Keygen accepts the Cyrillic alphabet, but it depends on how the console is configured. I personally didn’t accept it from the console, but if I hardcode, then everything is fine. I was lazy to rewrite under the windows.