Showing posts with label reverser. Show all posts
Showing posts with label reverser. Show all posts
Tuesday, December 12, 2017
Best Reverser Write Up Analyzing Uncommon Firmware
Best Reverser Write Up Analyzing Uncommon Firmware
While developing tasks for PHDays’ contest in reverse engineering, we had a purpose of replicating real problems that RE specialists might face. At the same time we tried to avoid allowing cliche solutions.
Let us define what common reverse engineering tasks look like. Given an executable file for Windows (or Linux, MacOS or any other widely-used operating system). We can run it, watch it in a debugger, and twist it in virtual environments in any way possible. File format is known. The processor’s instruction set is x86, AMD64 or ARM. Library functions and system calls are documented. The equipment can be accessed through the operating system only. Using tools like IDAPro and H?xRays makes analysis of such applications very simple, while debug protection, virtual machines with their own instruction sets, and obfuscation could complicate the task. But large vendors hardly ever use any of those in their programs. So there’s no point in developing a contest aimed at demonstrating skills that are rarely addressed in practice.
However, there’s another area, where reverse engineering became more in-demand, that’s firmware analysis. The input file (firmware) could be presented in any format, can be packed, encrypted. The operating system could be unpopular, or there could be no operating system at all. Parts of the code could not be changed with firmware updates. The processor could be based on any architecture. (For example, IDAPro “knows” not more than 100 different processors.) And of course, there’s no documentation available, debugging or code execution cannot be performed?a firmware is presented, but there’s no device.
Part One: Loader
At the first stage, the input file is an ELF file compiled with a cross compiler for the PA-RISC architecture. IDA can work with this architecture, but not as good as with x86. Most requests to stack variables are not identified automatically, and you’ll have to do it manually. At least you can see all the library functions (log, printf, memcpy, strlen, fprintf, sscanf, memset, strspn) and even symbolic names for some functions (?32, exk, cry, pad, dec, cen, dde). The program expects two input arguments: an email and key.
It’s not hard to figure out that the key should consist of two parts separated by the “-“ character. The first part should consist of seven MIME64 characters (0-9A-Za-z+/), the second part of 32 hex characters that translate to 16 bytes.
Further we can see calls to c32 functions that result in:
t = c32(-1, argv[1], strlen(argv[1])+1)
k = ~c32(t, argv[2], strlen(argv[2])+1)
Name of the function is a hint: it’s a ?RC32 function, which is confirmed by the constant 0xEDB88320.
Next, we call the dde function (short for doDecrypt), and it receives the inverted output of the CRC32 function (encryption key) as the first argument, and the address and the size of the encrypted array as the second and third ones.
Decryption is performed by BTEA (block tiny encryption algorithm) based on the code taken from Wikipedia. We can guess that it’s BTEA from the use of the constant DELTA==0x9E3779B9. It’s also used in other algorithms on which BTEA is based on, but there are not many of them.
The key should be of 128-bit width, but we receive only 32 bits from CRC32. So we get three more DWORDs from the exk function (expand_key) by multiplying the previous value by the same DELTA.
However, the use of BTEA is uncommon. First of all, the algorithm supports a variable-width block size, and we use a block of 12-bytes width (there are processors that have 24-bit width registers and memory, then why should we use only powers of two). And in the second place, we switched encryption and decryption functions.
Since data stream is encrypted, cipher block chaining is applied. Enthropy is calculated for decrypted data in the cen function (calc_enthropy). If its value exceeds 7, the decryption result is considered incorrect and the program will exit.
The encryption key is 32-bit width, so it seems to be easily brute-forced. However, in order to check every key we need to decrypt 80 kilobytes of data, and then calculate enthropy. So brute-forcing the encryption key will take a lot of time.
But after the calculation, we call the pad function (strip_pad), which check and remove PKCS#7 padding. Due to CBC features, we need to decrypt only one block (the last one), extract N byte, check whether its range is between 1 and 12 (inclusive) and each of the last N bytes has value N. This allows reducing the number of operations needed to check one key. But if the last encrypted byte equals 1 (which is true for 1/256 keys), the check should be still performed.
The faster method is to assume that decoded data have a DWORD-aligned length (4 bytes). Then in the last DWORD of the last block there may be only one of three possible values: 0x04040404, 0x08080808 or 0x0C0C0C0C. By using heuristic and brute force methods you can run through all possible keys and find the right one in less than 20 minutes.
If all the checks after the decryption (entropy and the integrity of the padding) are successful, we call the fire_second_proc function, which simulates thelaunch of the second CPU and the loading of decrypted data of the firmware (modern devices usually havemore than one processor—with differentarchitectures).
If the second processorlaunches, it receives the user’s email and 16 bytes with the second part of the key via the function send_auth_data. At this point we made a mistake: there was the size of the string with the email instead of the size of the second part of the key.
Part Two: Firmware
The analysis of the second part is a little bit more complicated. There was no ELF file, only a memory image—without headings, function names, and other metadata. Type of the processorand load address were unknown as well.
We thought of brute force as the algorithm of determining the processor architecture. Open in IDA,set the following type, and repeat until IDA showssomething similar to a code. The brute force should lead to the conclusion that it is big-endian SPARC.
Now we need to determine the load address. The function 0x22E0 is not called, but it contains a lot of code. We can assume that is the entry point of the program, the start function.
In the third instruction of the start function, an unknown library function with one argument == 0x126F0 is called,and the same function is called from the start function four more times, always with arguments with similar values (0x12718, 0x12738, 0x12758, 0x12760).And in the middle of the program, starting from 0x2490, there are five lines with text messages:
00002490 .ascii "Firmware loaded, sending ok back."<0>
000024B8 .ascii "Failed to retrieve email."<0>
000024D8 .ascii "Failed to retrieve codes."<0>
000024F8 .ascii "Gratz!"<0>
00002500 .ascii "Sorry may be next time..."<0>
Assuming that the load address equals 0x126F0-0x2490 == 0x10260, then all the arguments will indicate thelines when calling the library function, and the unknown function turns out to be the printf function (or puts).
After changing the load base, the code will look something like this:
The value of 0x0BA0BAB0, transmitted to the function sub_12194, can be found in the first part of the task, in the function fire_second_proc, and is compared with what we obtain from read_pipe_u32 (). Thus sub_12194 should be called write_pipe_u32.
Similarly, two calls of the library function sub_24064 are memset (someVar, 0, 0x101) forthe email and code, while sub_121BC is read_pipe_str (), reversed write_pipe_str ()from the first part.
The first function (at offset 0 or address 0x10260) has typical constants of MD5_Init:
Next to the call to MD5_Init, it is easy to detect the function MD5_Update () and MD5_Final (), preceded by the call tothe library strlen ().
Not too many unknown functions are left in the start() function.
The sub_12480 function reverses the byte array of specified length. In fact, it’s memrev, which receives a code array input of 16 bytes.
Obviously, the sub_24040function checks whether the code is correct. The argumentstransfer the calculated value of MD5(email),the array filled in function sub_12394, and the number 16. It could be a call tomemcmp!
The real trick is happening in sub_12394. There is almost no hintsthere, but the algorithm is described by one phrase—the multiplication of binary matrix of the 128 by the binary vector of 128. The matrix is stored in the firmware at 0x240B8.
Thus, the code is correct if MD5(email) == matrix_mul_vector (matrix, code).
Calculating the Key
To find the correct value of the code, you need to solve a system of binaryequations described by the matrix, where the right-hand side are the relevant bits of the MD5(email). If you forgot linear algebra: this is easily solved by Gaussian elimination.
If the right-hand side of the key is known (32 hexadecimal characters), we can try to guess the first seven characters so that the CRC32 calculation result was equal to the value found for the key BTEA. There are about 1024 of such values, and they can be quickly obtained by brute-force, or by converting CRC32 and checking valid characters.
Now you need to put everything together and get the key that will pass all the checks and will be recognized as validby our verifier :)
We were afraid that no one would be able to solve the task from the beginning to the end. Fortunately, Victor Alyushin showed that our fears were groundless. You can find his write-up on the task at http://nightsite.info/blog/16542-phdays-2015-best-reverser.html. This is the second time Victor Alyushin has won the contest (he was the winner in 2013 as well).
A participant who wished to remain anonymous solved a part of the task and took second place.
Thanks to all participants!
Available link for download
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
Subscribe to:
Posts (Atom)