Introduction
BsidesSF had really really good reverse engineering challenges, but I loved two challenges. One windows reverse challenge called chameleon and another esp32 firmware reverse challenge called smart-locky which I didn't manage to solve in time.
The challenge
Problem statement
We are given two files chameleon.exe and flag.png.enc, this looks trivial enough we need to reverse the encryption algorithm to give us the original flag.png.
The problem statment also says that file was encrypted in the last months.
Reading the statment it looked like a simple challenge where you brute force the seed of a default mt19937 implementation, but the problem had only two solves, so I thought there must be some twist.
First glance at the binary
When you first execute the binary it gives you two options, to encrypt or decrypt files.
Usage: chameleon.exe [--encrypt|<--decrypt --id=<id>>] <infile> <outfile> Example: chameleon.exe --encrypt plaintext.txt ciphertext.txt Example: chameleon.exe --decrypt --id=abcd1234 ciphertext.txt plaintext.txt
I knew where to look and I didn't focus on the decryption stuff to be honest.
Reversing the binary
After identifying the encrypt function and changing some function names here is what the assembly looks like (you might want to zoom):
And here is what the hexrays decompiler gives us after changing some types and variable names:
void __usercall encrypt(const CHAR *output@<ebx>, const CHAR *input) { void *file_content; BYTE *new_file_ptr; FILE *v4; DWORD pdwDataLen; HCRYPTKEY phKey; HCRYPTPROV phProv; byte pbData[20]; char v9[8]; file_content = read_file(input, &pdwDataLen); new_file_ptr = (BYTE *)realloc(file_content, pdwDataLen + 16); if ( !CryptAcquireContextA(&phProv, 0, "Microsoft Enhanced Cryptographic Provider v1.0", 1u, 0xF0000000) ) goto failure; mersenne_twister((int)v9); // generate 8 byte key *(_WORD *)&pbData[2] = 0; pbData[0] = 8; *(_DWORD *)&pbData[8] = 8; *(_DWORD *)&pbData[12] = *(_DWORD *)v9; *(_DWORD *)&pbData[16] = *(_DWORD *)&v9[4]; pbData[1] = 2; *(_DWORD *)&pbData[4] = 26113; if ( !CryptImportKey(phProv, pbData, 0x14u, 0, 1u, &phKey) || !CryptEncrypt(phKey, 0, 1, 0, new_file_ptr, &pdwDataLen, pdwDataLen + 8) ) { failure: v4 = _iob_func(); fprintf(v4 + 2, "Encryption failed\n"); exit(1); } sub_E51AA0((int)v9); sub_E51F50(output, new_file_ptr, pdwDataLen); free(new_file_ptr); }
All right looks simple enough, here are the algorithm steps:
- call to CryptAcquireContextA, this is like an encryption algorithm factory in windows
- call to a function that I called mersenne_twister
- sets some values in pbData
- call to CryptImportKey
- call to CryptEncrypt
If you read this tutorial you can understand how CryptImportKey works.
This is an example key blob from the page above:
BYTE DesKeyBlob[] = { 0x08,0x02,0x00,0x00,0x01,0x66,0x00,0x00, // BLOB header 0x08,0x00,0x00,0x00, // key length, in bytes 0xf1,0x0e,0x25,0x7c,0x6b,0xce,0x0d,0x34 // DES key with parity };
We can see that our example also uses DES using CBC mode of operation, we also see that the DES key is passed as the last 8 bytes (with byte of parity) of the array.
Ok so the bread and butter of this problem is knowing how the mersenne twister works.
Reversing mersenne_twister
This is what the code looks like:
We can see that there are two loops.
Here is the decompiled code, it looks really clean after some type changes
char __usercall mersenne_twister@<al>(int a1@<edi>) { int v1; // eax signed int v2; // ecx unsigned int v3; // esi char result; // al v1 = time64(0); v2 = 0; do { v1 = 29945647 * v1 - 1; mt[v2++] = v1; } while ( v2 < 351 ); dword_E54018 = v2; v3 = 0; do { result = getrandom() ^ 0x55; *(_BYTE *)(v3++ + a1) = result; } while ( v3 < 8 ); return result; }
If you implemented mersenne twister, the first loop is the set seed function, this is gonna put numbers in an array I call mt.
The interesting part to notice is the call to time64, the twister is seeded with current time.
Let's reverse getrandom now
Reversing getrandom
Here is what the code looks like:
The decompiled code looks good enough.
int getrandom() { int v0; // eax int v1; // eax int *v2; // ecx int v3; // esi int v4; // eax int v5; // edi unsigned int v6; // esi int v7; // eax int v8; // esi unsigned int v9; // edi int v10; // eax int v11; // edi unsigned int v12; // esi int v13; // eax unsigned int v14; // esi unsigned int v15; // ecx int v16; // ecx v0 = dword_E54018; if ( dword_E54018 >= 351 ) { v1 = 175; v2 = &dword_E54384; do { v3 = *v2; v4 = v1 + 1; *(v2 - 1) = ((*(v2 - 1) ^ (*v2 ^ *(v2 - 1)) & 0x7FFFFu) >> 1) ^ dword_E5437C[v4] ^ -((*((_BYTE *)v2 - 4) ^ (unsigned __int8)(*(_BYTE *)v2 ^ *((_BYTE *)v2 - 4))) & 1) & 0xE4BD75F5; if ( v4 >= 351 ) v4 = 0; v5 = v2[1]; v6 = ((v3 ^ (v3 ^ v2[1]) & 0x7FFFFu) >> 1) ^ mt[v4] ^ -(((unsigned __int8)v3 ^ (unsigned __int8)(v3 ^ *((_BYTE *)v2 + 4))) & 1) & 0xE4BD75F5; v7 = v4 + 1; *v2 = v6; if ( v7 >= 351 ) v7 = 0; v8 = v2[2]; v9 = ((v5 ^ (v5 ^ v2[2]) & 0x7FFFFu) >> 1) ^ mt[v7] ^ -(((unsigned __int8)v5 ^ (unsigned __int8)(v5 ^ *((_BYTE *)v2 + 8))) & 1) & 0xE4BD75F5; v10 = v7 + 1; v2[1] = v9; if ( v10 >= 351 ) v10 = 0; v11 = v2[3]; v12 = ((v8 ^ (v8 ^ v2[3]) & 0x7FFFFu) >> 1) ^ mt[v10] ^ -(((unsigned __int8)v8 ^ (unsigned __int8)(v8 ^ *((_BYTE *)v2 + 12))) & 1) & 0xE4BD75F5; v13 = v10 + 1; v2[2] = v12; if ( v13 >= 351 ) v13 = 0; v14 = ((v11 ^ (v11 ^ v2[4]) & 0x7FFFFu) >> 1) ^ mt[v13] ^ -(((unsigned __int8)v11 ^ (unsigned __int8)(v11 ^ *((_BYTE *)v2 + 16))) & 1) & 0xE4BD75F5; v1 = v13 + 1; v2[3] = v14; if ( v1 >= 351 ) v1 = 0; v2 += 5; } while ( (signed int)v2 < (signed int)&dword_E548FC ); dword_E548F8 = dword_E54638 ^ ((dword_E548F8 ^ (dword_E548F8 ^ mt[0]) & 0x7FFFFu) >> 1) ^ -(((unsigned __int8)dword_E548F8 ^ (unsigned __int8)(dword_E548F8 ^ LOBYTE(mt[0]))) & 1) & 0xE4BD75F5; v0 = 0; } v15 = mt[v0]; dword_E54018 = v0 + 1; v16 = ((((v15 >> 11) ^ v15) & 0xCABCA5) << 7) ^ (v15 >> 11) ^ v15; return (unsigned __int8)(v16 ^ ((((v16 & 0xFFFFFFAB) << 15) ^ v16) >> 17)); }
Looks like a normal getrandom function from mt19937 but the thing is, it is not. Because the length of the array is 351, this is called mt11213.
Putting it all together
After looking on the internet for some constants I found this page, maybe we can work with that.
The only difference with the program was the factor, also I had to change from long to int because this was written for a 32 bit machine (I spent two hours debugging this lol).
I wrote a program to generate all possible keys from october 2019 to february 2020.
#include <math.h> #include <stdio.h> #define RAND_MASK 0x3FFFFFFF #define N 351 #define M 175 #define R 19 #define TEMU 11 #define TEMS 7 #define TEMT 15 #define TEML 17 #define MATRIX_A 0xE4BD75F5 #define TEMB 0x655E5280 #define TEMC 0xFFD58000 static unsigned int mt[N]; static int mti=N; extern void set_seed (int seed) { unsigned int s = (unsigned int)seed; for (mti=0; mti<N; mti++) { // s = s * 29943829 - 1; s = s * 29945647 - 1; mt[mti] = s; } return; } void dump() { for (int i = 0; i < N; i++) { printf("%x\n", mt[i]); } } int genrandom () { unsigned int y; if (mti >= N) { const unsigned int LOWER_MASK = (1u << R) - 1; const unsigned int UPPER_MASK = -1 << R; int kk, km; for (kk=0, km=M; kk < N-1; kk++) { y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK); mt[kk] = mt[km] ^ (y >> 1) ^ (-(y & 1) & MATRIX_A); if (++km >= N) km = 0; } y = (mt[N-1] & UPPER_MASK) | (mt[0] & LOWER_MASK); mt[N-1] = mt[M-1] ^ (y >> 1) ^ (-(unsigned int)(y & 1) & MATRIX_A); mti = 0; } y = mt[mti++]; y ^= y >> TEMU; y ^= (y << TEMS) & TEMB; y ^= (y << TEMT) & TEMC; y ^= y >> TEML; return y&0xff; } int main(void) { for (int t = 1569888000 /*1546300800*/; t < 1582583270; t++) { set_seed(t); for (int i = 0; i<8; i++) { printf("%x", genrandom() ^ 0x55); } printf("\n"); } }
This generates a 263 MiB file:
gcc bruteforce.c && ./a.out > keys.txt
Then I wrote a little program in python to try to brute force the key, since we know that the file is png, and the first 8 bytes are fixed.
from Crypto.Cipher import DES cipher = "cd0c8716e99ae841".decode("hex") with open("keys.txt") as myfile: lines = myfile.read().splitlines() p = 0.01 pas = p l = float(len(lines)) for i, key in enumerate(lines): if i / l >= p: print("{}%".format(p * 100)) p += pas keyh = key key = key.zfill(16).decode("hex") out = DES.new(key).decrypt(cipher) if out[0] == chr(0x89) and out[1] == chr(0x50) and out[2] == chr(0x4e) and out[3] == chr(0x47) and \ out[4] == chr(0x0d) and out[5] == chr(0xa) and out[6] == chr(0x1a) and out[7] == chr(0x0a): print("FOUND .....") print(keyh) exit(0)
After 5 minutes I find the key, and I decrypt the image:
from Crypto.Cipher import DES key = "a051b8a16f8542da".decode("hex") with open("flag.png.enc") as myfile: image= myfile.read() content = DES.new(key, DES.MODE_CBC, IV="\x00" * 8).decrypt(image) with open("flag.png", "w") as myfile: myfile.write(content)
And yaas! we have the flag
