Talent Yang loves to customize his own obfuscator. Unfortunately, he lost his seed when he was watching Arsenal’s UEFA game. What a sad day! His team and his seed were lost together. To save him, could you help him to get back his seed? We can not save the game, but we may be able to find out his seed.
Compile: ollvm.clang -Xclang -load -Xclang lib0opsPass.so -mllvm -oopsSeed=THIS_IS_A_FAKE_SEED source.c
Clang && LLVM Version: 3.9.1
link
flag format: flag{seed}
Summary: deobfuscating and attacking AES parts.
In this challenge we are given an obfuscation plugin for llvm and an obfuscated binary. The plugin accepts a 16-byte seed as a parameter and uses it for internal PRNG. Our goal is to analyze the binary and recover the seed from it.
The binary is basically a big state machine. Here is start of the main function:
.text:4004C0 main: ; DATA XREF: _start+1D .text:4004C0 push rbp .text:4004C1 mov rbp, rsp .text:4004C4 sub rsp, 4038Ch .text:4004CB mov dword ptr [rbp-4], 0 .text:4004D2 mov dword ptr [rbp-8], 46544330h .text:4004D9 mov dword ptr [rbp-0Ch], 4E52BCE7h .text:4004E0 .text:4004E0 main_switch: ; CODE XREF: .text:loc_7635AC .text:4004E0 mov eax, [rbp-0Ch] .text:4004E3 mov ecx, eax .text:4004E5 sub ecx, 8000DEEAh .text:4004EB mov [rbp-10h], eax .text:4004EE mov [rbp-14h], ecx .text:4004F1 jz loc_728049 .text:4004F7 jmp $+5 .text:4004FC .text:4004FC loc_4004FC: ; CODE XREF: .text:00000000004004F7 .text:4004FC mov eax, [rbp-10h] .text:4004FF sub eax, 8001EACAh .text:400504 mov [rbp-18h], eax .text:400507 jz loc_73E38A .text:40050D jmp $+5 .text:400512 .text:400512 loc_400512: ; CODE XREF: .text:000000000040050D .text:400512 mov eax, [rbp-10h] .text:400515 sub eax, 8003CC64h .text:40051A mov [rbp-1Ch], eax .text:40051D jz loc_5C0C95 .text:400523 jmp $+5 ... |
In pseudocode, it could be something like this:
state = 0x4E52BCE7 main_switch: switch(state) { case 0x8000DEEA: goto loc_728049; case 0x8001EACA: goto loc_73E38A; case 0x8003CC64: goto loc_5C0C95; ... } loc_xxxxxx: // do something state = 0x8003CC64 goto main_switch |
Note that the state ids are sorted as signed 32-bit integers. Also, during the case probing, some intermediate data is written to the stack (i.e. [rbp-14h] and lower), but there are no further reads from that area. By running the binary and checking for system calls with strace we can see that it does not do anything useful. Let’s look at the llvm plugin to see how the seed is used.
lib0opsPass.so
The plugin is written in C++ and exports a bunch of functions. The main function of our interest is Oops::OopsFlattening::flatten(). Though it’s quite big, we can quickly locate interesting parts by looking at cross-references from crypto-related functions.
First it calls prng_seed to seed its internal PRNG state:
Oops::CryptoUtils::prng_seed(cryptoutils, &seed_string); |
Then it uses the PRNG to generate 16 bytes:
memset(&key, 0, 0x20uLL); LODWORD(cryptoutils_) = llvm::ManagedStatic<Oops::CryptoUtils>::operator->(&Oops::Oopscryptoutils, 0LL); Oops::CryptoUtils::get_bytes(cryptoutils_, &key, 16); if ( crc32('FTC0', &key, 3) != 0xF9E319A6 ) ... |
Note that the hardcoded crc32 check allows us to easily find the first 3 bytes of the generated key: 179, 197, 140.
The key is then used to “scramble” values from a hardcoded array called plains:
LODWORD(plains0) = plains[0]; LODWORD(v35) = llvm::ManagedStatic<Oops::CryptoUtils>::operator->(&Oops::Oopscryptoutils, v33); v36 = plains0; v37 = Oops::CryptoUtils::scramble32(v35, plains0, &key); ... v60 = counter++; plainsCUR = plains[v60]; LODWORD(v62) = llvm::ManagedStatic<Oops::CryptoUtils>::operator->(&Oops::Oopscryptoutils, v59); v63 = Oops::CryptoUtils::scramble32(v62, plainsCUR, &key); |
It’s not clear for now how these “scrambled” values are used later. IDA tells us that there are around $2^{16}$ values in the array:
.data:2345E0 ; _DWORD plains[65806] .data:2345E0 plains dd 0F6172961h, 0CB973739h, 904F3728h, 0DB7194B9h, 81E0B166h ... |
Probably it is possible to look at the LLVM-related code and see how exactly these values are used. But in the obfuscated binary there are not so many random-looking words. The only ones which come to mind are the state ids!
Let’s log all the state ids passed to the main_switch. Here is a simple gdb script for it:
$ cat >cmd set confirm off set pagination off break *0x04004e3 commands p/x $eax cont end run $ gdb -x cmd -n ./0llvm </dev/null >log $ head -30 log GNU gdb (Ubuntu 7.11.1-0ubuntu1~16.04) 7.11.1 ... Reading symbols from ./0llvm...(no debugging symbols found)...done. Breakpoint 1 at 0x4004e3 Breakpoint 1, 0x00000000004004e3 in main () $1 = 0x4e52bce7 Breakpoint 1, 0x00000000004004e3 in main () $2 = 0x3ac545da Breakpoint 1, 0x00000000004004e3 in main () $3 = 0xff97c58e Breakpoint 1, 0x00000000004004e3 in main () $4 = 0xe83342dd $ tail log Breakpoint 1, 0x00000000004004e3 in main () $65789 = 0xf1dbf041 Breakpoint 1, 0x00000000004004e3 in main () $65790 = 0xdb9a21b8 Breakpoint 1, 0x00000000004004e3 in main () $65791 = 0xb02b5689 [Inferior 1 (process 10622) exited with code 027] (gdb) quit |
65791 values! Quite close to 65801 found in IDA. The hypothesis seems to be true. But what does it give us now?
Recovering key
What we have found is that we have $~2^{16}$ pairs of plaintext/ciphertext under the “scramble32” function. Let’s look at it closer:
__int64 __fastcall Oops::CryptoUtils::scramble32( Oops::CryptoUtils *this, unsigned int x, const char *key) { int v3; // ST20_4@1 int v4; // ST24_4@1 int v5; // ST20_4@1 v3 = AES_PRECOMP_TE3[(x ^ key[3])] ^ AES_PRECOMP_TE2[(BYTE1(x) ^ key[2])] ^ AES_PRECOMP_TE1[((x >> 16) ^ key[1])] ^ AES_PRECOMP_TE0[(BYTE3(x) ^ *key)]; v4 = AES_PRECOMP_TE3[(v3 ^ key[7])] ^ AES_PRECOMP_TE2[(BYTE1(v3) ^ key[6])] ^ AES_PRECOMP_TE1[((v3 >> 16) ^ key[5])] ^ AES_PRECOMP_TE0[(BYTE3(v3) ^ key[4])]; v5 = AES_PRECOMP_TE3[(v4 ^ key[11])] ^ AES_PRECOMP_TE2[(BYTE1(v4) ^ key[10])] ^ AES_PRECOMP_TE1[((v4 >> 16) ^ key[9])] ^ AES_PRECOMP_TE0[(BYTE3(v4) ^ key[8])]; return AES_PRECOMP_TE3[(v5 ^ key[15])] ^ AES_PRECOMP_TE2[(BYTE1(v5) ^ key[14])] ^ AES_PRECOMP_TE1[((v5 >> 16) ^ key[13])] ^ AES_PRECOMP_TE0[(BYTE3(v5) ^ key[12])] ^ ((key[2] << 8) | (key[1] << 16) | (*key << 24) | key[3]); } |
Interesting, it is related to the AES block cipher. The AES_PRECOMP_TE tables map 8-bit values to 32-bit values. Possibly these tables implement MixColumns, or even together with SBoxes and xors. Let’s compose them with inverse of MixColumns (aes.py):
from aes import AES A = AES() for i in xrange(4): for x, t in enumerate(AES_PRECOMP_TE[i]): t = [BYTE3(t), BYTE2(t), BYTE1(t), BYTE0(t)] t2 = A.mixColumn(list(t), isInv=True) print t2 print |
$ python precomp.py [99, 0, 0, 0] [124, 0, 0, 0] [119, 0, 0, 0] [123, 0, 0, 0] [242, 0, 0, 0] [107, 0, 0, 0] ... |
This is the AES SBox applied to one of the bytes! It means that
AES_PRECOMP_TE[i](x) = MixColumns(SBox(x) << 8*i).
Therefore scramble32 is a 4-round iteration of XorKey, SubBytes, MixColumn followed by another XorKey. How do we recover the key?
Recall that we know key[0], key[1], key[2] from a CRC32 check. We can guess one-byte key[3] and bypass the first round easily. Luckily, the last whitening key is the same as the first one: with the same guess we can decrypt the last round aswell! By moving the keys through the linear layers and decrypring the linear layers, we arrive at two rounds:
XK | SB | MC | XK | SB | XK.
Let’s use impossible polytopes. Assume that we have three plaintexts of the form (it is probable that we have such among the $2^{16}$ texts by birthday paradox):
- X1 = (x1, a, b, c)
- X2 = (x2, a, b, c)
- X3 = (x3, a, b, c)
We will study how a difference tuple (X1 $\oplus$ X2, X1 $\oplus$ X3) propagates through the cipher. Since it is a difference, it propagates through the key addition untouched. After SubBytes a set of possible difference tuples expands up to $2^8$ elements. Since MixColumn is linear, any difference (x, y) propagates to (MixColumn(x), MixColumn(y)). Therefore, before the last SubBytes layer, we have only $2^8$ possible differences, which can easily be precomputed. Thus, we can recover the last key byte-by-byte: guess byte of the key, decrypt through S-Box, check difference tuple (note that the middle XK does not affect it). We are truncating the differences of 32-bit values to differences of 8-bit values, but this is fine since we look at pairs of differences: $2^8$ possible pairs out of $2^{16}$ give us $1/2^8$ filtration for each key byte. By tracking the first guessed key byte, we can ensure that only the correct key survives.
The full attack implementation is available here.
Recovering Seed
We have recovered the key, but the flag is the PRNG seed! How to recover it? The code for stream generation is as follows:
// in Oops::CryptoUtils::encrypt(Oops::CryptoUtils *this, unsigned __int8 *dst, unsigned __int8 *nonce, unsigned __int8 *seed) memset(dst, 0, 0x10uLL); v5 = *(nonce_ + 1); *buf = *nonce_; *buf2 = v5; for ( i = 0; i <= 15; ++i ) { seedbyte = seed_[i]; for ( j = 0; j <= 7; ++j ) { if ( seedbyte & 1 ) { for ( k = 0; k <= 15; ++k ) dst[k] ^= buf[k]; } seedbyte = seedbyte >> 1; for ( l = 0; l <= 15; ++l ) buf[l] = TABLE[buf[l]]; } } |
Here TABLE is an 8-bit nonlinear S-Box. Nonce is constant and hardcoded (note that it is increased by 1 before calling encrypt, as a big-endian number, see Oops::CryptoUtils::inc_ctr):
// in Oops::CryptoUtils::prng_seed(struct CryptoUtils *cryptoutils, __int64 a2) noncebuf = cryptoutils->nonce; *noncebuf = 0xD7C59B4DFFD1E010LL; *(noncebuf + 1) = 0x20C7C17B250E019ALL; |
Though TABLE is nonlinear, the buf array is updated independently and therefore we can see its different versions as constants. Mixing of buf and seed is done linearly, so we can recover the seed from the PRNG output (which is the AES key) by simple linear algebra:
from sage.all import * from struct import pack, unpack def tobin(x, n): return tuple(map(int, bin(x).lstrip("0b").rjust(n, "0"))) def frombin(v): return int("".join(map(str, v)), 2 ) def tobinvec(v): return sum( [tobin(c, 8) for c in v], () ) PRNG_OUT = [179, 197, 140, 9, 31, 61, 9, 48, 214, 74, 172, 159, 200, 11, 185, 236] TABLE = [0x0ED,0x67,0x7F,0x0F6,0x0C7,0x9A,0x24,0x12,0x0BA,0x83,0x49,0x0DB,0x13,0x0BF,0x61,0x0B0,0x0FF,0x69,0x80,0x0EC,0x0DE,0x4,0x63,0x0C4,0x96,0x73,0x1B,0x6E,0x0A6,0x9E,0x87,0x4B,0x0FC,0x10,0x2A,0x0C3,0x5C,0x2E,0x36,0x0B2,0x0DF,0x0E3,0x90,0x0FE,0x1A,0x0F,0x1C,0x84,0x1,0x15,0x3A,0x85,0x0A5,0x57,0x3F,0x6D,0x0F5,0x4A,0x0A,0x0D6,0x9F,0x64,0x0B5,0x0F7,0x8F,0x99,0x68,0x4D,0x17,0x0F9,0x0EE,0x0F0,0x3,0x6,0x4C,0x0BD,0x58,0x33,0x0A9,0x0DC,0x3C,0x0A3,0x3B,0x0D1,0x0BB,0x28,0x0F4,0x0B9,0x0CF,0x47,0x0A0,0x6A,0x0C2,0x19,0x0B,0x97,0x81,0x35,0x91,0x7C,0x5D,0x7A,0x48,0x2B,0x41,0x0D9,0x0CB,0x6F,0x56,0x8D,0x5A,0x0C5,0x3E,0x0D8,0x0C0,0x60,0x1F,0x9,0x0CA,0x7B,0x25,0x0E7,0x0AE,0x0F2,0x77,0x0FA,0x3D,0x50,0x0E2,0x4F,0x0C9,0x2C,0x53,0x45,0x0C1,0x0E9,0x46,0x0D,0x70,0x8A,0x0A1,0x0D5,0x94,0x92,0x88,0x95,0x9D,0x26,0x9B,0x0E4,0x5,0x44,0x11,0x2D,0x7,0x1E,0x0A4,0x38,0x0E1,0x0A8,0x52,0x89,0x0AF,0x40,0x72,0x0E5,0x0B4,0x7E,0x51,0x6C,0x0FB,0x76,0x62,0x0D4,0x8,0x9C,0x54,0x5B,0x75,0x29,0x0C6,0x66,0x0DA,0x0FD,0x14,0x86,0x78,0x16,0x0B6,0x8B,0x39,0x0E6,0x0B7,0x1D,0x0D3,0x18,0x0A7,0x30,0x0E8,0x23,0x37,0x7D,0x82,0x0BE,0x34,0x0C,0x55,0x0D0,0x0EF,0x0,0x0CD,0x0AC,0x0A2,0x4E,0x0B3,0x0AB,0x31,0x8E,0x21,0x0E0,0x22,0x74,0x5E,0x8C,0x32,0x0F8,0x0EB,0x2F,0x79,0x0F1,0x42,0x0C8,0x0DD,0x0CE,0x65,0x27,0x5F,0x20,0x0B8,0x0AA,0x0AD,0x71,0x6B,0x0D2,0x0EA,0x0BC,0x0E,0x0CC,0x98,0x2,0x59,0x43,0x0B1,0x93,0x0D7,0x0F3,] # note 0x20... -> 0x21 nonce = pack("<QQ", 0xD7C59B4DFFD1E010, 0x21C7C17B250E019A) cols = [map(ord, nonce)] for i in xrange(127): v = [TABLE[c] for c in cols[-1]] cols.append(v) cols = [vector(GF(2), tobinvec(v)) for v in cols] target = vector(GF(2), tobinvec(PRNG_OUT)) m = matrix(GF(2), 128, len(cols)) for x, c in enumerate(cols): m.set_column(x, c) try: sol = m.solve_right(target) except ValueError: print "NO SOLUTION" quit() print "SOL", sol res = "" for i in xrange(0, 128, 8): res += chr(frombin(sol[i:i+8][::-1])) print "flag{%s}" % res |
The flag is: flag{B0s5x1AOb3At0bF~}
