The Best Reverse Contest for PHDays III: Developer's Perspective

When we started preparing the task 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 machine code, convert it into an understandable algorithm, find errors or weaknesses in this algorithm, and, if possible, exploit them. At the same time, the code proposed for analysis should be similar to real program code.

A 64-bit version of Windows was chosen as the platform. 64 bits - because using the Hex-Rays Decompiler for x86 greatly simplifies the task, but there is no decompiler for x64 yet. Anyway, 64-bit applications have already become commonplace.

So, a small program was built using Qt (and static libraries). In this case, the executable file turned out to be almost 10 MB in size. But is this 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 grains from the chaff ...

To start, the program required two dynamic libraries ( msvcp110.dlland msvcr110.dll) in the system . Some of the contestants complained that his program did not start at all, but fell with the exception. But for the rest of the participants, either the settings were set as it should, or the motivation turned out to be stronger;)

At the first stage, it was required to enter the username and key. The program checked compliance and reported success or failure. In addition to Base64 decoding (which was determined elementarily by a string with the alphabet), the main check was written using OpenSSL. The library is convenient for the reverser in that for it there is an opportunity to look into the sources and determine the name of almost any function in a matter of minutes.
In the sources, 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 module El_pby which operations are performed is 500 bits, and such a signature is considered stable. So the key cannot be calculated on the forehead.

A separate code branch checked that the length of the key entered was 6 characters, counted SHA1 from it, and compared the first 8 bytes with the sequence {0xEE,0xD1,0xAC,0xA8,0xD0,0xCC,0xA3,0x3F}. The 6-character strings consisting of the Base64 alphabet are just 2 ³⁶ options. If you sort them out (which was not necessary - just fix the transition condition), 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 to wait for the result. At each iteration, a large number is generated, not exceeding in value El_p, multiplied by the El-Gamal public key El_y moduloEl_p, and the result should be 313373. If this happens, the generated number is used as the encryption key for the RC4 algorithm, and this key decrypts the line with the code containing the correct El-Gamal signature. In theory, a random number generator will someday produce a sequence of bytes that 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 receive the correct RC4 key - simply by calculating the algebraic complement using the extended Euclidean algorithm.

Obtaining a valid Al-Gamal signature is not a decision of 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 line cannot be entered as a name: zero bytes will be discarded.

Attentive cryptographers should immediately notice that the verification code described in the algorithm is missing from the signature verification code ( 0 < r < El_p). For this case, the book Handbook of Applied Cryptography (section 11.66.iv) contains an attack that allows you to calculate the signature for any message if there is 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 key entered was not tied to the user name. The key was decoded by Base64, then some tricky actions were performed on it, and as a result we should get a set of bytes in which the substring was searched for "PHDays III validator ;)\0". Initially, we planned that the substring would be searched anywhere, but due to a coding error (developers are also people), the match was checked only at the beginning of the output byte set.

The complexity of the task was that it also used public key cryptography elements , but they were implemented independently and in a not entirely obvious way. In fact, the entered key was raised to a power modulo a large (1000-bit) number, which is the product of two primes. And this is exactly the mathematics that underlies the creep osistemy RSA. Exponentiation been realized through the Montgomery multiplication, and the input number should be given in advance by Montgomery.

The public exponent had a value of 5, and if the verification was implemented correctly, the calculation of the input secret would require factorization of a 1000-bit number, which so far has not been possible for anyone. 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 in 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 was proposed to solve the problem mathematically. But first things first. The key verification algorithm decoded the data entered by the user into a buffer the size sizeof(El_p)*2+1024of the Base64 algorithm. Moreover, if the decoded data took more thansizeof(El_r), such a key was not recognized as valid. After the decoded data, the SHA-3 hash was taken, 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.

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

The verification of the solution of the entire task was structured as follows: it checked 3 bits in a global variable — for each bit for each part of the task — and, if all bits were set, displayed a window with a congratulation on passing the task. 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 a congratulation.

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 branded PHDays backpackand AR Drone 2.0, other winners of the competition also received memorable gifts. Congratulations!



PS Victor Alyushin wrote an excellent writing dedicated to the contest.