> matryoshka>> 738>> There was a downloader found on a Mac desktop. It's your job to have layers of fun getting the flag.> > Written by malwareunicorn>> Download: [matryoshka.tar.gz](https://0xd13a.github.io/ctfs/fbctf2019/matryoshka/matryoshka.tar.gz)
[Matryoshka](https://en.wikipedia.org/wiki/Matryoshka_doll) is a fitting name for this challenge as there is a number of nested levels one has to unroll to solve it. It was a lot of fun (and hair pulling) to solve and a great opportunity to try [Ghidra](https://ghidra-sre.org/).
We start with a Mach-O 64-bit executable. It reverses in Ghidra easily (in absence of a Mac or an emulator we will be doing static analysis). Here are the most important pieces:
```c  ...   _send_request(&local_1c);  _receive_response(&local_1c,&local_28);
  ...   png_header_offset = _check_png_header(local_28);
  ...   pcVar2 = local_28 + png_header_offset  lVar3 = (*pcVar2)(0);   ...   pcVar2 = local_28 + png_header_offset + lVar3  _data = (*pcVar2)(0);
  ...   _data = __OSSwapInt64(_data);
  ...   intflag_idx1 = 7;  while (-1 < intflag_idx1) {    local_60 = local_60 << 8 | (ulong)intermid_flag[(long)intflag_idx1];    intflag_idx1 = intflag_idx1 + -1;  }  intflag_idx2 = 0xf;  while (7 < intflag_idx2) {    local_68 = local_68 << 8 | (ulong)intermid_flag[(long)intflag_idx2];    intflag_idx2 = intflag_idx2 + -1;  }  intflag_idx3 = 0x17;  while (0xf < intflag_idx3) {    local_70 = local_70 << 8 | (ulong)intermid_flag[(long)intflag_idx3];    intflag_idx3 = intflag_idx3 + -1;  }  intflag_idx4 = 0x1b;  while (0x17 < intflag_idx4) {    local_74 = local_74 << 8 | (uint)intermid_flag[(long)intflag_idx4];    intflag_idx4 = intflag_idx4 + -1;  }  if (((((local_60 ^ local_68) == 0x3255557376f68) && ((local_68 ^ local_70) == 0x393b415f5a590044))      && ((local_70 ^ (ulong)local_74) == 0x665f336b1a566b19)) &&     (((ulong)local_74 ^ 0x115c28da834feffd) == _data)) {   ...
```
Application goes through the following steps:
* Send a GET request to address [http://157.230.132.171/pickachu_wut.png](https://0xd13a.github.io/ctfs/fbctf2019/matryoshka/pickachu_wut.png). The image contains embedded code that we will analyze next. 
* Find PNG header in the response and count offset ```0x60000``` from it
* Call code at that location and receive second offset as a response
* Call code at the second location and receive a 64bit value response
* XOR that value with 4 other 64bit constants to verify flag contents
Let's download the image, cut it at the ```0x60000``` mark and load it in Ghidra again. The code asks for us to enter a key, and then does a ROT13 on it and compares it to the encoded string at offset ```0x172```: ```4ZberYriryf2TbXrrcTbvat``` (this string decodes to ```4MoreLevels2GoKeepGoing```). If the user input matches, then the first 2 characters from this string (```4M```) are XORed with ```0x354c``` and returned. The result is ```0x7878``` and this becomes our offset for the code in the next stage.
We repeat the cutting of the file (this time at offset ```0x67878```) and analyze it in Ghidra. Here complexity increases, the code asks for the next key (4 bytes in length) and then uses its value to decode (via repeating ```SUB mod 0x100```) ```0x678``` bytes at offset ```0x137```. However the correctness check before a call to decoded block makes sure that the 4 bytes at that location match a constant value (```0xe5894855```):
```        000000e4 41 8b 55 00     MOV        EDX,dword ptr [R13]=>SUB_00000137                = C7h        000000e8 81 fa 55        CMP        EDX,0xe5894855                 48 89 e5        000000ee 75 1f           JNZ        LAB_0000010f        000000f0 b8 04 00        MOV        EAX,0x2000004                 00 02        000000f5 bf 01 00        MOV        EDI,0x1                 00 00        000000fa 48 8d 35        LEA        RSI=>DAT_00000e37,[0xe37]                        = 4Bh    K                 36 0d 00 00        00000101 ba 0c 00        MOV        EDX,0xc                 00 00        00000106 0f 05           SYSCALL        00000108 31 c0           XOR        EAX,EAX        0000010a 41 ff d5        CALL       R13=>SUB_00000137```
This tells us what the key is:  ```0xe5894855``` subtracted from ```0x59b978c7``` (bytes at the beginning of the encoded section) gives us ```r00t``` (reversed to account for little-endianness).
After decoding with the key let's repeat file cutting again and reverse code at offset ```0x137```. This gives us yet another iteration that asks for an 8-byte key and this time around XORs it with ```0x44a``` values at offset ```0x300```:
```c  ...   if ((int)((ulong)DAT_00000576 >> 0x20) == 0x4a514f75) {    lVar2 = 0;    while (lVar2 < 0x44a) {      *(byte *)(lVar2 + 300) = *(byte *)(lVar2 + 300) ^ *(byte *)((long)((int)lVar2 % 8) + 0x576);      lVar2 = lVar2 + 1;    }    if (_SUB_0000012c == -0x1a76b7ab) {      syscall();      uVar1 = (*(code *)&SUB_0000012c)(1,0x586,0xc);      return uVar1;    }  }   ...```
Here we are helped again as 2 constants are now embedded in the code - ```0x4a514f75``` and ```-0x1a76b7ab```. The first one is the half of the key, the second one we can use to determine the other half of the key by XORing it with the appropriate bytes in the encoded section. After a few calculations we get the key ```LJcbuOQJ``` and use it to decode the code block.
Rinse and repeat - we cut the file again and disassemble the encoded section. The new code is a little more complex. It too asks for the key and calls two subroutines that use it to decode yet another encoded section and return 8 bytes from it:
```c  ...   if ((int)((ulong)DAT_00000254 >> 0x20) == 0x36395477) {    FUN_00000113(0,0x254,8,0x254,0x264);    FUN_00000194(uVar3,uVar2,0x30,0x224,0x224,0x264);    syscall();    return ZEXT816(DAT_00000224);  }   ...```
However, this time around only half of the key is known - ```0x36395477``` (```wT96```), so we will have to bruteforce the remaining 4 characters. The subroutines create an encoding table based on the key and use it to decode the encoded ```0x30``` bytes (of which we will really only need the first 8 bytes).
But how do we determine which 4-character combination is correct? We need some kind of a test. Thankfully in the original dowloader we have 4 8-byte checksum values, which we can apply, and see if the all the resulting characters in the flag are in the sane character range (```[a-zA-Z0-9_]```).
Let's reimplement the decoding algorithm in Python, add flag correctness check, and bruteforce through all possible 4-character key values:
```pythonfrom pwn import *
def tryKey(key): 	#build initial table	tab = bytearray(256)	for i in range(256):	  tab[i] = i 	# create full key	fullkey = key+"wT96" 	# update table based on key	k = 0	uv = 0	for i in range(256):		cv = tab[i]		uv = (uv + cv + ord(fullkey[k])) & 0xff		tab[i] = tab[uv]		tab[uv] = cv		k = (k + 1) % 8
	# data to decode - taken from the binary	enc_data = bytearray(b'\xF6\x2C\x72\x1A\x03\x99\x0E\x78\xBD\x90\xE9\x68\xD0\x69\x37\x29\xF8\x12\xF4\xE5\xD0\xFB\xF3\x7E\x72\x61\x79\x19\xED\x44\x12\x52\xF5\xF9\xAA\x14\x36\x0D\x1F\xB2\x52\x6B\xF2\x6A\xDA\x9D\xEC\x3C') 	# decode base value for the flag	uv3 = 0	uv4 = 0	for i in range(8): 		uv3 = (uv3 + 1) & 0xff		cv1 = tab[uv3]		uv4 = (cv1 + uv4) & 0xff		cv2 = tab[uv4]		tab[uv3] = cv2		tab[uv4] = cv1		enc_data[i] = tab[(cv1 + cv2) & 0xff] ^ enc_data[i] 	x0 = b'\x11\x5c\x28\xda\x83\x4f\xef\xfd'	x1 = b'\x66\x5f\x33\x6b\x1a\x56\x6b\x19'	x2 = b'\x39\x3b\x41\x5f\x5a\x59\x00\x44'	x3 = b'\x00\x03\x25\x55\x57\x37\x6f\x68' 	flag = bytearray(8*4) 	# now decode 4 8-byte pieces of the flag	for x in range(8):		enc_data[x] ^= ord(x0[x])		flag[x] = enc_data[x]		enc_data[x] ^= ord(x1[x])		flag[x+8] = enc_data[x]		enc_data[x] ^= ord(x2[x])		flag[x+16] = enc_data[x]		enc_data[x] ^= ord(x3[x])		flag[x+24] = enc_data[x] 	# reverse the string and only leave 28 bytes of it	flag = flag[::-1][0:28] 	# are the string characters in [a-zA-Z0-9_]?	for x in range(len(flag)):		if chr(flag[x]) not in string.ascii_letters+string.digits+'_':			return False 	print "\n\n\n\nFlag found! key: "+fullkey+"   flag: fb{"+flag+"}\n\n\n\n"		return True
s = iters.mbruteforce(lambda x: tryKey(x), string.ascii_letters + string.digits, 4, 'fixed') ```
When we run the script we get the flag within several minutes:
```sh$ python decode.py [-] MBruteforcing: Trying "XzDw","XHXF","XHXG","Xrjr","YnAm","Yjqj","XL7O","XYB1" -- 80.155%
Flag found! key: YrQmwT96   flag: fb{Y0_daWg_1_h34rd_u_1ik3_fl4gs}
[+] MBruteforcing: Found key: "YrQm"```
The flag is ```fb{Y0_daWg_1_h34rd_u_1ik3_fl4gs}```.