This is another challenge from the Volga CTF Quals 2016, involving an x64 ELF executable that encodes files. Our objective is to recover the clear text data from the encrypted file.
Here’s the description for this challenge:
This binary does something with the data. The transformation must be reversible, but the details are unknown. It shouldn’t be too difficult to reverse that transformation and obtain the flag, should it?
You can download the executable from the CTF Writeup repository on GitHub.
What I’m going to do in this writeup is simple:
- Reverse the algorithm. I will use IDA Pro, but you can also use radare2.
- Write a compatible encoder in C++.
- Invert the transformation and implement decoding functionality.
For starters, you may have noticed that this executable does not like to be run inside a debugger; you can easily pinpoint where the anti-debugger check is performed by setting a breakpoint to the exit() function.
00401070 Protection proc near 00401070 sub rsp, 8 00401070 00401070 ; terminate the process if the LD_PRELOAD variable 00401070 ; is set 00401070 00401074 mov edi, offset name ; "LD_PRELOAD" 00401079 call _getenv 00401079 0040107e test rax, rax 00401081 jnz short _terminate 00401081 00401081 ; terminate if the PTRACE_TRACEME ptrace request 00401081 ; returns -1 (meaning that a debugger is already 00401081 ; attached) 00401081 00401083 xor ecx, ecx 00401085 xor edx, edx 00401087 xor esi, esi 00401089 xor edi, edi ; request (PTRACE_TRACEME) 0040108b xor eax, eax 0040108d call _ptrace 0040108d 00401092 test rax, rax 00401095 js short _terminate 00401095 00401097 add rsp, 8 0040109b retn 0040109c 0040109c _terminate: 0040109c xor edi, edi ; status (0) 0040109e call _exit 0040109e Protection endp
We could have choosen to hook the ptrace() function and disable this check by using the LD_PRELOAD environment variable, but the code at address 401074 would have prevented us from being able to do it. What we really want to remove instead is the debugger protection and to be honest it’s easier to just patch the program. It’s not required if you don’t plan on stepping through the code or if you don’t mind skipping it manually with a breakpoint each time you start the program.
Now that we got rid of the protection, let’s take a look at the caller.
004019C0 init proc near 004019C0 push r15 004019C2 mov r15d, edi 004019C5 push r14 004019C7 mov r14, rsi 004019CA push r13 004019CC mov r13, rdx 004019CF push r12 004019CF 004019CF ; array contents: 004019CF ; Initialization01 (004013D0) 004019CF ; Protection (00401070) 004019CF ; CppIoStreamConstructor (004012F0) 004019CF 004019D1 lea r12, InitializationFunctionsList1 004019D8 push rbp 004019D8 004019D8 ; array contents: Initialization02 (004013B0) 004019D8 004019D9 lea rbp, InitializationFunctionsList2 004019E0 push rbx 004019E1 sub rbp, r12 004019E4 xor ebx, ebx 004019E6 sar rbp, 3 004019EA sub rsp, 8 004019EE call _init_proc 004019F3 test rbp, rbp 004019F6 jz short loc_401A16 004019F6 004019F6 ; it's pretty obvious that someone has messed up 004019F6 ; this opcode. replace it with a function call 004019F6 ; to address 004013B0 004019F6 004019F8 nop dword ptr [rax+rax+00000000h] 00401A00 00401A00 loc_401A00: 00401A00 00401A00 mov rdx, r13 00401A03 mov rsi, r14 00401A06 mov edi, r15d 00401A06 00401A06 ; functions called: 00401A06 ; 1. Initialization01: program initialization 00401A06 ; 2. Protection: LD_PRELOAD/debugger check 00401A06 ; 3. CppIoStreamConstructor: constructor and destructor 00401A06 ; (using atexit) for the std::ios_base c++ object 00401A06 00401A09 call qword ptr [r12+rbx*8] 00401A0D add rbx, 1 00401A11 cmp rbx, rbp 00401A14 jnz short loc_401A00 00401A16 00401A16 loc_401A16: 00401A16 00401A16 add rsp, 8 00401A1A pop rbx 00401A1B pop rbp 00401A1C pop r12 00401A1E pop r13 00401A20 pop r14 00401A22 pop r15 00401A24 retn 00401A24 init endp
If you played the previous level (named Broken) you will remember that the init() function had been patched to remove a function call that was required for the algorithm to work as intended; this challenge is no exception and you will have to fix the instruction located at address 004019F8. Again, the function we need to call can be found inside the second array.
There’s not much else to say about the rest of the functions referenced here; they’re just used for initialization and we don’t really care to analyze them, provided that we take a memory snapshot once it’s done. Let’s see how the rest of the program works; it’s pretty long, so I will use annotated pseudo-code to illustrate its internals.
// 004010B0
int main(int argc, char *argv[])
{
// 004010d0
if (argc != 3)
return 0;
const char *input_file_path = argv[1];
const char *output_file_path = argv[2];
// 0040111a
std::fstream input_file(input_file_path);
// 00401135
std::fstream output_file(output_file_path);
// 004011c5
input_file.seekg(0, std::ios_base::end);
// 004011d2
std::streamsize file_size = input_file.tellg();
// 004011ee
input_file.seekg(0, std::ios_base::beg);
// 004011fa
std::uint8_t *buffer = new std::uint8_t[file_size];
// 0040121D
input_file.read(buffer, file_size);
//
// we don't care much about the following function, as it doesn't touch
// our buffer in any way. Take a memory snapshot after this call
//
// 0040122C
call sub_401932;
//
// this is what we need to analyze
//
// 0040123A
call sub_401836;
// 00401248
output_file.write(buffer, file_size);
return 0;
}
// 00401836
void sub_401836(uint8_t *input_buffer, uint8_t *output_buffer, uint32_t buffer_size)
{
// rdi = input_buffer
// rsi = output_buffer
// rdx = buffer_size
// an xmmword is 16 bytes long; this function encodes one block
// at a time by calling sub_40179e
// 00401860
rdx = shr rdx, 0x04;
// 00401870
if (rdx == 0)
return;
do
{
// 00401877
xmm0 = *rdi;
// 0040187b
call sub_40179e;
// 00401880
*rsi = xmm0;
// 00401884
rdi += 0x10;
// 00401888
rsi += 0x10;
// 0040188c
rdx--;
} while (rdx != 0); // 00401864
// 0040189f
return;
}
// 0040179e
void sub_40179e()
{
// this is the real encoding function; it's nothing too fancy
// and you can easily invert each transformation by performing
// the same operations in reverse order
// 004017ac
xmm7 = xmm0;
// 004017c8
xmm0 = xmmword_602128;
// 004017d1
pxor xmm7, xmm0;
// 004017d6
r15 = 0x10;
do
{
// 004017e1
call sub_4015d0;
// 004017e6
call sub_40167d;
// 004017eb
call sub_40169f;
// 004017f0
xmm0 = xmmword_602128[r15];
// 004017f9
pxor xmm7, xmm0;
// 004017fe
r15 += 0x10;
} while (r15 < 0x0A); // 00401802
// 0040180b
call sub_4015d0;
// 00401810
call sub_40167d;
// 00401815
xmm0 = xmmword_602128[r15];
// 0040181e
pxor xmm7, xmm0;
// 00401823
xmm0 = xmm7
// 00401835
return;
}
// 004015d0
void sub_4015d0()
{
// 004015d9
[rsp] = xmm7;
// 004015de
for (offset = 0; offset < 0x0c; offset += 0x04)
{
ebx = [rsp + offset];
call sub_40161f;
[rsp + offset] = eax;
}
// 00401615
xmm7 = [rsp];
// 0040161e
return;
}
// 0040167d
void sub_40167d()
{
// 00401694
xmm0 = xmmword_401683;
// 00401698
pshufb xmm7, xmm0;
// 0040169e
return;
}
// 0040169f
void __usercall sub_40169f()
{
// 004016a8
[rsp] = xmm7;
// 004016ad
for (offset = 0; offset < 0x0c; offset += 0x04)
{
edi = [rsp + offset];
call sub_4016e9;
[esp] = eax;
}
// 004016df
xmm7 = [rsp];
// 004016e8
return;
}
// 0040161f
void __usercall sub_40161f()
{
// input: ebx
// output: eax
movzx ecx, bl
mov al, byte ptr qword_602268[ecx]
movzx ecx, bh
mov ah, byte ptr qword_602268[ecx]
shl eax, 10h
shr ebx, 10h
movzx ecx, bl
mov al, byte ptr qword_602268[ecx]
movzx ecx, bh
mov ah, byte ptr qword_602268[ecx]
rol eax, 10h
add rsp, 8
nop
retn
}
There’re two more functions we need to analyze: sub_40161f and sub_4016e9; I’ve added some spacing to make the listings easier to follow and understand.
0040161F sub_40161f proc near 0040161F 0040161F ; input: ebx 0040161F ; output: eax 0040161F 0040161F push rcx 00401620 jmp short loc_40162B 00401620 00401622 db 0x00 00401623 db 0x00 00401624 db 0x00 00401625 db 0xE9 00401626 db 0xA6 00401627 db 0x01 00401628 db 0x40 00401629 db 0xE9 0040162A db 0x04 0040162B 0040162B loc_40162B: 0040162B 0040162B xor rax, rax 0040162E jmp short loc_401646 ........ 00401646 loc_401646: 00401646 00401646 movzx ecx, bl 00401649 mov al, byte ptr qword_602268[ecx] 00401649 00401650 movzx ecx, bh 00401653 mov ah, byte ptr qword_602268[ecx] 0040165A 0040165A shl eax, 10h 0040165D shr ebx, 10h 00401660 00401660 movzx ecx, bl 00401663 mov al, byte ptr qword_602268[ecx] 0040166A 0040166A movzx ecx, bh 0040166D mov ah, byte ptr qword_602268[ecx] 00401674 00401674 rol eax, 10h 00401677 00401677 add rsp, 8 0040167B nop 0040167C retn 0040167C sub_40161f endp
This function is pretty easy to invert; just execute the same opcodes in reverse order and you will obtain the input value. Let’s take a look at the second procedure:
004016E9 sub_4016e9 proc near 004016E9 004016E9 ; input: edi 004016E9 ; output: eax 004016E9 004016E9 xor eax, eax 004016EB jz short loc_4016EE 004016EB 004016ED db 0xE8 004016EE 004016EE loc_4016EE: 004016EE movzx r8, dil 004016F2 shr edi, 8 004016F2 004016F5 movzx r9, dil 004016F9 shr edi, 8 004016F9 004016FC movzx r10, dil 00401700 shr edi, 8 00401700 00401703 movzx r11, dil 00401707 xor eax, eax 00401707 00401709 mov r12b, byte_602394[r11] 00401710 mov dil, byte_602494[r8] 00401717 xor edi, r9d 0040171A xor edi, r10d 0040171D xor edi, r12d 00401720 and edi, 0FFh 00401726 or eax, edi 00401728 shl eax, 8 00401728 0040172B mov r12b, byte_602494[r11] 00401732 mov dil, byte_602394[r10] 00401739 xor edi, r8d 0040173C xor edi, r9d 0040173F xor edi, r12d 00401742 and edi, 0FFh 00401748 or eax, edi 0040174A shl eax, 8 0040174D jb short loc_401752 0040174F jnb short loc_401752 0040174F 00401751 db 0E9h 00401752 00401752 loc_401752: 00401752 00401752 mov r12b, byte_602494[r10] 00401759 mov dil, byte_602394[r9] 00401760 xor edi, r8d 00401763 xor edi, r12d 00401766 xor edi, r11d 00401769 and edi, 0FFh 0040176F or eax, edi 0040176F 00401771 shl eax, 8 00401774 mov r12b, byte_602494[r9] 0040177B mov dil, byte_602394[r8] 00401782 xor edi, r12d 00401785 xor edi, r10d 00401788 xor edi, r11d 0040178B and edi, 0FFh 00401791 or eax, edi 00401791 00401793 retn 0040109e sub_4016e9 endp
This is slightly harder, and will require some work; first of all, write down how the sub_4016e9 function encodes the input value:
output[3] = byte_602494[input[0]] ^ input[1] ^ input[2] ^ byte_602394[input[3]];
output[2] = byte_602394[input[2]] ^ input[0] ^ input[1] ^ byte_602494[input[3]];
output[1] = byte_602394[input[1]] ^ input[0] ^ input[3] ^ byte_602494[input[2]];
output[0] = byte_602394[input[0]] ^ input[2] ^ input[3] ^ byte_602494[input[1]];
Then, invert the operands so that the input value is on the left:
input[1] = output[3] ^ byte_602494[input[0]] ^ input[2] ^ byte_602394[input[3]]
input[0] = output[2] ^ byte_602394[input[2]] ^ input[1] ^ byte_602494[input[3]]
input[3] = output[1] ^ byte_602394[input[1]] ^ input[0] ^ byte_602494[input[2]]
input[2] = output[0] ^ byte_602394[input[0]] ^ input[3] ^ byte_602494[input[1]]
We can now brute force the system and obtain the input value:
// ...
for (std::uint16_t input1 = 0x00; !found && input1 <= 0xFF; input1++)
{
input[1] = static_cast<std::uint8_t>(input1);
for (std::uint16_t input2 = 0x00; !found && input2 <= 0xFF; input2++)
{
input[2] = static_cast<std::uint8_t>(input2);
for (std::uint16_t input3 = 0x00; !found && input3 <= 0xFF; input3++)
{
input[3] = static_cast<std::uint8_t>(input3);
input[0] = output[2] ^ byte_602394[input[2]] ^ input[1] ^ byte_602494[input[3]];
if (input[1] != (output[3] ^ byte_602494[input[0]] ^ input[2] ^ byte_602394[input[3]]))
continue;
if (input[2] != (output[0] ^ byte_602394[input[0]] ^ input[3] ^ byte_602494[input[1]]))
continue;
if (input[3] != (output[1] ^ byte_602394[input[1]] ^ input[0] ^ byte_602494[input[2]]))
continue;
found = true;
}
}
}
// ...
We have pretty much analyzed everything we needed to invert the transformation algorithm, and we can now decode the encrypted file:
alessandro at tachikoma in ~/Projects/untransformer (master)
$ untransformer decode flag.transformed flag.decoded && cat flag.decoded
VolgaCTF{transf0rming_dat@_with_hardc0ded_key_is_not_saf33}I have published the whole source code on my GitHub page in case you want to take a look at the decoder.
If you managed to get this far, thanks for reading! I hope you found this writeup interesting; I know I at least had fun writing it.