Saturday, November 25, 2017
Best Reverser at PHDays III — Developers Overview
Best Reverser at PHDays III — Developers Overview
When we put hand to the contest, we wanted to make it interesting, difficult and feasible at the same time.
We believe that a good reverser should be able to read computer code, convert it to a clear algorithm, find mistakes and flaws of this algorithm, and, if possible, to exploit them. Besides the code provided for analysis should be close to true software code.
The 64-bit Windows version was chosen as a platform, because Hex-Rays Decompiler for x86 makes everything easier and there are no decompilers for x64. And 64-bit applications have become common anyway.
So a small program with Qt (and static libraries) was developed. And the executable file was almost 10 MB. But is it unbearable for a talented reverser? Though, according to feedback, the file size scared some participants. On the other hand, Qt leaves a lot of useful information, and a reverser must know how to separate the wheat from the chaff...
The program required two dynamic libraries (msvcp110.dll and msvcr110.dll) for startup. Some of the participants complained that their program ended with exception. The other participants either had proper settings or were better motivated.
A username and key were requested at the first stage. The program verified data and reported on success or failure. Except for Base64 decoding (which was easily determined by the alphabet string), the main check was written with OpenSSL. The library is useful for a reverser, because it provides source code so that to quickly define almost any function name.
The check function looked as follows in the source code:
Some knowledge in cryptography allows identifying that it is the digital signature check by the ElGamal algorithm. The size of the El_p module used for operations is 500 bits and such a signature is considered strong. So there is no direct way to acquire the key.
A specific code branch verified if the key consisted of 6 characters, calculated SHA1, and compared the first 8 bytes with the sequence {0xEE,0xD1,0xAC,0xA8,0xD0,0xCC,0xA3,0x3F}. 6-character strings composed of the Base64 alphabet are only 236 options. If going through all of them (it was unnecessary — one only needed to fix the transition condition), then the Easter egg "PHDays" appeared.
After the egg activation, the program started to do something very actively, but it was hardly possible to see the result. A huge number, the value of which did not exceed El_p, was generated within each iteration, multiplied by El_y modulo El_p, and the result should be 313373. If it happened, the generated number could be used as an encryption key for the RC4 algorithm, and this key was used to decrypt the string with code containing the correct ElGamal signature. In theory, a random number generator would once generate such a byte sequence that would be the necessary RC4 key, but the sun would sooner fall from heaven than this would happen. So we supposed that the participants would obtain the necessary RC4 key by calculating the algebraic complement using the extended Euclidean algorithm.
The valid ElGamal signature is not the solution of the first stage, because the name, for which the signature had been generated, contained zero bytes: "|<33p y0ur pr1v473 $3cr37". And such a string cannot be input as a name — zero bytes will be skipped.
Attentive cryptographers should have been immediately noticed that signature check code lacks the check described in the algorithm (0 < r < El_p). For this case, the Handbook of Applied Cryptography (section 11.66.iv) provides an attack, which allows calculating a signature for any message with only one valid signature available. This attack results in a signature for any name considered a program.
As for the second stage, the key was not linked to a username. Base64 decoded the key, then some peculiar operations were carried out over it, and finally they should have received the set of bytes with the substring "PHDays III validator ;)". At first, we planned the substring to be found in any location, but because of a code error (developers are human as well), the compliance was checked only at the beginning of the output byte set.
The task was difficult because cryptography elements with open keys were also used, but they were implemented independently and in a disguised format. In fact, the key was exponentiated modulo big (1000 bit) number, which was the result of two prime numbers multiplied by each other. And this is the mathematics, which lies as the basis of the RSA cryptosystem. Exponentiation was implemented via the Montgomery reduction, and the input number should have been converted using the Montgomery algorithm.
The public exponent was 5 and, if the check was correctly implemented, the input secret calculation would have requested 1000-bit number factorization, which is hardly possible. However, due to the fact that only a 24-bit substring was checked, the 5th root of the necessary result could be calculated (not mudulo), then converted according to the Montgomery algorithm, encoded by Base64, and finally the key for the second part could be obtained.
The third part was uncommon from the point of view of usual crackme tasks, which can be solved mathematically. However, everything is in due order. The key check algorithm decoded input data to the buffer of the size sizeof(El_p)*2+1024 according to the Base64 algorithm. If decoded data was larger than sizeof(El_r), such a key was invalid. Then the SHA-3 hash of the decoded data was compared to the string "ESETESETESETESETESETESETESETESET". Even the task author did not know the right input value, which should have been motivated the participants to find an alternative solution.
An attentive reader has already noticed that the vulnerability of the first part allows selecting El_r of such a length that it will be possible to overflow the buffer, in which the decoded data was copied. And this buffer is located on the stack. The stack was not secured and the load base was fixed, it allowed using the ROP technique to exploit the vulnerability and bypass the task check function.
The task solution check looked as follows: it checked 3 bits (each bit per each task part) in the global variable and, if all the bits were submitted, it displayed a congratulation message. It means that to solve the task one only needed to find ROP gadgets, which allowed writing 7 at the global variable address and ending the check function of the third part. The congratulation message was displayed after it.
According to the contest results, the victory stand looks as follows:
1st place
Victor Alyushin
2nd place
Mikhail Voronov, Denis Litvinov
3rd place
Anton Cherepanov
Congratulations!
We believe that a good reverser should be able to read computer code, convert it to a clear algorithm, find mistakes and flaws of this algorithm, and, if possible, to exploit them. Besides the code provided for analysis should be close to true software code.
The 64-bit Windows version was chosen as a platform, because Hex-Rays Decompiler for x86 makes everything easier and there are no decompilers for x64. And 64-bit applications have become common anyway.
So a small program with Qt (and static libraries) was developed. And the executable file was almost 10 MB. But is it unbearable for a talented reverser? Though, according to feedback, the file size scared some participants. On the other hand, Qt leaves a lot of useful information, and a reverser must know how to separate the wheat from the chaff...
The program required two dynamic libraries (msvcp110.dll and msvcr110.dll) for startup. Some of the participants complained that their program ended with exception. The other participants either had proper settings or were better motivated.
A username and key were requested at the first stage. The program verified data and reported on success or failure. Except for Base64 decoding (which was easily determined by the alphabet string), the main check was written with OpenSSL. The library is useful for a reverser, because it provides source code so that to quickly define almost any function name.
The check function looked as follows in the source code:
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 in cryptography allows identifying that it is the digital signature check by the ElGamal algorithm. The size of the El_p module used for operations is 500 bits and such a signature is considered strong. So there is no direct way to acquire the key.
A specific code branch verified if the key consisted of 6 characters, calculated SHA1, and compared the first 8 bytes with the sequence {0xEE,0xD1,0xAC,0xA8,0xD0,0xCC,0xA3,0x3F}. 6-character strings composed of the Base64 alphabet are only 236 options. If going through all of them (it was unnecessary — one only needed to fix the transition condition), then the Easter egg "PHDays" appeared.
After the egg activation, the program started to do something very actively, but it was hardly possible to see the result. A huge number, the value of which did not exceed El_p, was generated within each iteration, multiplied by El_y modulo El_p, and the result should be 313373. If it happened, the generated number could be used as an encryption key for the RC4 algorithm, and this key was used to decrypt the string with code containing the correct ElGamal signature. In theory, a random number generator would once generate such a byte sequence that would be the necessary RC4 key, but the sun would sooner fall from heaven than this would happen. So we supposed that the participants would obtain the necessary RC4 key by calculating the algebraic complement using the extended Euclidean algorithm.
The valid ElGamal signature is not the solution of the first stage, because the name, for which the signature had been generated, contained zero bytes: "|<33p y0ur pr1v473 $3cr37". And such a string cannot be input as a name — zero bytes will be skipped.
Attentive cryptographers should have been immediately noticed that signature check code lacks the check described in the algorithm (0 < r < El_p). For this case, the Handbook of Applied Cryptography (section 11.66.iv) provides an attack, which allows calculating a signature for any message with only one valid signature available. This attack results in a signature for any name considered a program.
As for the second stage, the key was not linked to a username. Base64 decoded the key, then some peculiar operations were carried out over it, and finally they should have received the set of bytes with the substring "PHDays III validator ;)". At first, we planned the substring to be found in any location, but because of a code error (developers are human as well), the compliance was checked only at the beginning of the output byte set.
The task was difficult because cryptography elements with open keys were also used, but they were implemented independently and in a disguised format. In fact, the key was exponentiated modulo big (1000 bit) number, which was the result of two prime numbers multiplied by each other. And this is the mathematics, which lies as the basis of the RSA cryptosystem. Exponentiation was implemented via the Montgomery reduction, and the input number should have been converted using the Montgomery algorithm.
The public exponent was 5 and, if the check was correctly implemented, the input secret calculation would have requested 1000-bit number factorization, which is hardly possible. However, due to the fact that only a 24-bit substring was checked, the 5th root of the necessary result could be calculated (not mudulo), then converted according to the Montgomery algorithm, encoded by Base64, and finally the key for the second part could be obtained.
The third part was uncommon from the point of view of usual crackme tasks, which can be solved mathematically. However, everything is in due order. The key check algorithm decoded input data to the buffer of the size sizeof(El_p)*2+1024 according to the Base64 algorithm. If decoded data was larger than sizeof(El_r), such a key was invalid. Then the SHA-3 hash of the decoded data was compared to the string "ESETESETESETESETESETESETESETESET". Even the task author did not know the right input value, which should have been motivated the participants to find an alternative solution.
An attentive reader has already noticed that the vulnerability of the first part allows selecting El_r of such a length that it will be possible to overflow the buffer, in which the decoded data was copied. And this buffer is located on the stack. The stack was not secured and the load base was fixed, it allowed using the ROP technique to exploit the vulnerability and bypass the task check function.
The task solution check looked as follows: it checked 3 bits (each bit per each task part) in the global variable and, if all the bits were submitted, it displayed a congratulation message. It means that to solve the task one only needed to find ROP gadgets, which allowed writing 7 at the global variable address and ending the check function of the third part. The congratulation message was displayed after it.
According to the contest results, the victory stand looks as follows:
1st place
Victor Alyushin
2nd place
Mikhail Voronov, Denis Litvinov
3rd place
Anton Cherepanov
Congratulations!
Available link for download
