Contest "The Best Reverser" on PHDays III: Developer’s View

When we set about preparing the assignment for the competition , we wanted to make it interesting, difficult, but at the same time solvable.

From our point of view, a good reverser should be able to read the machine code, convert it into a clear algorithm, find errors or weak points in this algorithm and exploit them if possible. In this case, the code proposed for analysis should be similar to real program code.

The 64-bit version of Windows was chosen as the platform. 64 bits - because using Hex-Rays Decompiler for x86 greatly simplifies the task, but for x64 there is no decompiler yet. Anyway, 64-bit applications have already become commonplace.
')
So, a small program was built using Qt (and static libraries). At the same time, the executable file turned out to be almost 10 MB in size. But is it a lot for a real reverser? Although, according to reviews, some participants were scared by the file size. On the other hand, Qt leaves a bunch of useful information, and the reverser should be able to separate the wheat from the chaff ...

To start, the program required the presence of two dynamic libraries in the system ( msvcp110.dll and msvcr110.dll ). Some of the contestants complained that his program did not run at all, but fell with an exception. But the other participants or settings were set as follows, or the motivation was stronger;)

The first step was to enter the username and key. The program checked compliance and reported success or failure. In addition to decoding Base64 (which was simply determined by the string with the alphabet), the main test was written using OpenSSL. The library is convenient for the reverser in that it has the opportunity to look into the source code and determine the name of almost any function in a matter of minutes.
In the source code, the verification function looked like this:

phdInt checkDSAsig (BIGNUM *h, BIGNUM *r, BIGNUM*s) {
BN_CTX *ctx = BN_CTX_new();
BIGNUM *g = BN_bin2bn(El_g, sizeof(El_g), NULL);
BIGNUM *p = BN_bin2bn(El_p, sizeof(El_p), NULL);
BIGNUM *y = BN_bin2bn(El_y, sizeof(El_y), NULL);
BIGNUM *v1 = BN_new();
BIGNUM *v2 = BN_new();
BIGNUM *t1 = BN_new();
BIGNUM *t2 = BN_new();
phdInt rc = 0;

if (BN_mod_exp(v1, g, h, p, ctx) && BN_mod_exp(t1, y, r, p, ctx) && BN_mod_exp(t2, r, s, p, ctx) && BN_mod_mul(v2, t1, t2, p, ctx) && 0 == BN_cmp (v1, v2)) rc = 1;

BN_clear_free(t2);
BN_clear_free(t1);
BN_clear_free(v2);
BN_clear_free(v1);
BN_clear_free(y);
BN_clear_free(p);
BN_clear_free(g);
BN_CTX_free(ctx);
return rc;

Some knowledge of cryptography allows you to immediately understand that this is a digital signature verification using the El-Gamal algorithm. The size of the El_p module on which operations are performed is 500 bits, and such a signature is considered to be stable. So the key can not be calculated in the forehead.

A separate code branch checked that the key length was 6 characters, {0xEE,0xD1,0xAC,0xA8,0xD0,0xCC,0xA3,0x3F} SHA1 from it and compared the first 8 bytes with the sequence {0xEE,0xD1,0xAC,0xA8,0xD0,0xCC,0xA3,0x3F} . The 6-character Base64 alphabetic strings are just 2 ³⁶ choices. If we go through them (which was not necessary - just correct the condition of the transition), then there is an Easter egg - the word "PHDays".

When the Easter egg is activated, the program starts to do something hard, but it is unlikely that it will be possible to wait for the result. At each iteration, a large number not exceeding El_p , multiplied by El_p 's public key El_y modulo El_p , and the result should be equal to 313373. If this happens, the generated number is used as an encryption key for the RC4 algorithm, and this key The line with the code containing El Gamal’s signature is decrypted. In theory, a random number generator will ever produce such a sequence of bytes, which will be the correct RC4 key, but this is unlikely to happen before the Sun goes out. Therefore, it was assumed that the contestants should get the correct RC4 key - simply calculating the algebraic addition using the advanced Euclidean algorithm.

Obtaining El Gamal's valid signature is not yet a solution to the first stage, since the name for which the signature was generated contains zero bytes: " |<33p y0ur pr1v473 $3cr37\0\0\0 ". And such a string can not be entered as a name: zero bytes will be discarded.

Attentive cryptographers should have immediately noticed that the verification code described in the algorithm is missing in the signature verification code ( 0 < r < El_p ). In this case, the Handbook of Applied Cryptography (Section 11.66.iv) contains an attack that allows you to calculate a signature for any message with only one valid signature. Through this attack, a signature is obtained for any name recognized by the program.

In the second part of the task, the entered key was not tied to the user name. The key was decoded with Base64, then some tricky actions were performed on it, and the result was to get a set of bytes in which the substring " PHDays III validator ;)\0 . Initially, we planned that the substring would be searched anywhere, but due to a coding error (developers are people too), the match was checked only at the beginning of the output set of bytes.

The difficulty of the task was that it also used elements of public-key cryptography, but they were implemented independently and not in an entirely obvious way. The key actually entered was raised to the power modulo a large (1000-bit) number, which is the product of two prime numbers. And this is exactly the mathematics that underlies the RSA cryptosystem. The exponentiation was realized through Montgomery multiplication, and the input number must be given in advance according to Montgomery.

The public exhibitor had a value of 5, and if the verification was correctly implemented, the calculation of the input secret would require factorization of a 1000-bit number, which no one has yet succeeded. But since only the presence of a 24-byte substring was checked, it was possible to calculate the 5th root of the desired result (not modulo!), Bring it along Montgomery, encode Base64 and get the key for the second part.

The third part was not quite ordinary from the point of view of the usual crackme-tasks, where it is proposed to solve the problem mathematically. But first things first. The key verification algorithm decoded the data entered by the user into a buffer of size size sizeof(El_p)*2+1024 using the Base64 algorithm. And if the decoded data occupied more than the sizeof(El_r) , such a key was not recognized as valid. After that, the SHA-3 hash was taken from the decoded data, which was compared with the string " ESETESETESETESETESETESETESETESET ". Obviously, even the author of the assignment did not know the correct input value, which should have provoked the participants to search for an alternative solution.

The attentive reader has already noticed that the vulnerability in the first part allows you to choose El_r such length that it will be possible to overflow the buffer into which the decoded data has been copied. And this buffer is located on the stack. The program was compiled without stack protection and with a fixed load base, which allowed using the ROP technique to exploit the vulnerability and bypass the solution check function of the entire task.

The verification of the solution of the entire assignment was structured as follows: it checked 3 bits in the global variable - for each bit for each part of the assignment - and, if all the bits are set, it displayed a window with congratulations on the progress of the assignment. So, to solve the task, it remains to find ROP-gadgets that allow you to write the number 7 at the address of the global variable and correctly complete the function of checking the third part. Then you could see the window with congratulations.

According to the results of the competition, the podium looks like this:

I place: Victor Alyushin

II place: Mikhail Voronov , Denis Litvinov

III place: Anton Cherepanov

The winner received a corporate backpack PHDays and AR Drone 2.0, the other winners of the competition also received memorable gifts. Congratulations!



PS Viktor Alyushin wrote a great raitap dedicated to the competition.