Jade CTF 2022 - Bit Set Go
Bit Set Go is a reversing challenge that was part of the 2022 Jade CTF. We were given a binary and its output, and had to find the flag.
Overview
output consists of 41 seemingly random bytes:
0206541B 175B135B 17375C17 0C3A5C11 37510409
15125C16 370B5811 370D550F 1E2E312B 000C0402 37
bitsetgo is a 64-bit ELF go binary containing debug symbols. By running it, we see that it reads the two files flag.txt and key.txt and
writes the output to output. Since we are neither given the flag nor the key, we have to reverse the binary.
Reversing
Despite the fact that reversing Go binaries is generally a pain, the given debug symbols and a recent version of IDA Free make the pain bearable. The main function does all the work:
void __cdecl main_main()
{
__int128 v0; // rdi
int v1; // r14
__int128 v2; // xmm15
int v3; // rax
int v4; // rax
int v5; // rcx
unsigned int x; // rdi
int i; // rdx
char flag_bytes_i; // r9
int i_1; // r8
unsigned int i_mod_seven; // rdx
unsigned int iterations_done; // rax
unsigned int y; // rdx
unsigned int v13; // rbx
int v14; // rsi
unsigned int x_; // r9
signed int x_half; // rdi
unsigned int y_; // r10
char v18; // r11
int v19; // rax
unsigned int v20; // rcx
unsigned int j; // rax
unsigned int v22; // r10
char v23; // dl
unsigned int v24; // rdi
unsigned int v25; // r9
int k; // rdx
char v27; // r10
int v28; // rax
string v29; // [rsp-46h] [rbp-98h]
_BYTE v30[24]; // [rsp-46h] [rbp-98h]
_BYTE v31[96]; // [rsp-46h] [rbp-98h]
_slice_interface_ v32; // [rsp-46h] [rbp-98h]
int v33; // [rsp+2Ah] [rbp-28h]
int flag_bytes_array; // [rsp+32h] [rbp-20h]
__int128 v35; // [rsp+3Ah] [rbp-18h] BYREF
if ( (unsigned int)&v35 <= *(_QWORD *)(v1 + 16LL) )
runtime_morestack_noctxt();
*(_QWORD *)&v30[16LL] = (unsigned int)os_ReadFile(v29);
flag_bytes_array = v3;
if ( (_QWORD)v0 )
{
v35 = v2;
*(_QWORD *)&v0 = *(_QWORD *)(v0 + 8LL);
v35 = v0;
log_Fatal(*(_slice_interface_ *)v30);
}
*(retval_4730E0 *)&v31[16LL] = os_ReadFile(*(string *)v30);
if ( (_QWORD)v0 )
{
v33 = v4;
v35 = v2;
*(_QWORD *)&v0 = *(_QWORD *)(v0 + 8LL);
v35 = v0;
log_Fatal(*(_slice_interface_ *)v31);
v4 = v33;
}
v5 = flag_bytes_array;
x = 8LL;
for ( i = 0LL; i < 8LL; i = i_1 + 1LL )
{
flag_bytes_i = *(_BYTE *)(i + flag_bytes_array);
i_1 = i;
i_mod_seven = i % 7LL;
if ( i_mod_seven >= 7LL )
runtime_panicIndex();
*(_BYTE *)(flag_bytes_array + i_1) = *(_BYTE *)(i_mod_seven + v4) ^ flag_bytes_i;
}
iterations_done = 0LL;
y = 0LL;
v13 = 0LL;
v14 = 0LL;
while ( 1LL )
{
x_ = x;
x_half = x >> 1LL;
if ( (int)iterations_done >= x_half )
break;
if ( x_ <= iterations_done )
runtime_panicIndex();
y_ = y + 1LL;
v18 = *(_BYTE *)(iterations_done + v5);
if ( v13 < y + 1LL )
{
*(_QWORD *)&v31[88LL] = iterations_done;
v31[71LL] = *(_BYTE *)(iterations_done + v5);
*(_QWORD *)&v31[72LL] = y;
*(_DWORD *)&v31[40LL] = (unsigned __int32)runtime_growslice(
*(runtime__type_0 **)v31,
*(runtime_slice_0 *)&v31[8LL],
*(__int64 *)&v31[32LL]);
y_ = v14 + 1LL;
y = *(_QWORD *)&v31[72LL];
x_ = 8LL;
v18 = v31[71LL];
v14 = v19;
v13 = v20;
iterations_done = *(_QWORD *)&v31[88LL];
v5 = flag_bytes_array;
}
*(_BYTE *)(v14 + y) = v18;
++iterations_done;
x = x_;
y = y_;
}
for ( j = 0LL; (int)j < x_half; ++j )
{
v22 = y - 1LL;
if ( y <= y - 1LL )
runtime_panicIndex();
v23 = *(_BYTE *)(y + v14 - 1LL);
if ( x_ <= j )
runtime_panicIndex();
*(_BYTE *)(v5 + j) = v23;
y = v22;
}
v24 = x_;
v25 = x_ >> 2LL;
for ( k = (int)(3LL * v24) / 4LL; (int)v24 > k; ++k )
{
if ( v24 <= k )
runtime_panicIndex();
v27 = *(_BYTE *)(v5 + k);
if ( v24 <= v25 )
runtime_panicIndex();
*(_BYTE *)(v5 + k) = *(_BYTE *)(v25 + v5);
*(_BYTE *)(v5 + v25++) = v27;
}
os_WriteFile(*(string *)v31, *(_slice_uint8 *)&v31[16LL], *(io_fs_FileMode *)&v31[40LL]);
if ( v28 )
{
v35 = v2;
*(_QWORD *)&v35 = *(_QWORD *)(v28 + 8LL);
*((_QWORD *)&v35 + 1LL) = 6LL;
log_Fatal(v32);
}
}
By tracing data to the IO functions, we can see that the flag is being xor’d with the bytes of the unknown key. The function is then performing a series of operations on the flag bytes, and finally writing the result to a file.
Fixing the flag byte order
By passing zero bytes as the key and comparing some made up inputs and outputs, we can see that the function is merely shuffling the flag bytes around:
jadectf{fake_flag} -> f{ftflag}ake_cedaj
The shuffle order doesn’t seem to depend on the input being shuffled:
0123456789->4378956210abcdefghij->edhijfgcba
This means that there is no need to reverse the shuffle function, as we can simply pass 41 ascending bytes and derive the shuffle order from the output.
Deriving the xor key
With the shuffle order known, all that’s left is to derive the xor key. Since we know the flag format, we can obtain the xor key by simply xor’ing the known flag prefix with the reordered output.
def main():
# Define the scrambled order, starting at 0x01
scrambled_order = [0x14, 0x13, 0x12, 0x11, 0x10, 0x0F, 0x0E, 0x0D, 0x0C, 0x0B, 0x1F, 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x16, 0x17, 0x18, 0x19, 0x1A, 0x1B, 0x1C, 0x1D, 0x1E, 0x0A, 0x09, 0x08, 0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x15]
# This is the encoded flag.
scrambled_flag = [0x02, 0x06, 0x54, 0x1B, 0x17, 0x5B, 0x13, 0x5B, 0x17, 0x37, 0x5C, 0x17, 0x0C, 0x3A, 0x5C, 0x11, 0x37, 0x51, 0x04, 0x09, 0x15, 0x12, 0x5C, 0x16, 0x37, 0x0B, 0x58, 0x11, 0x37, 0x0D, 0x55, 0x0F, 0x1E, 0x2E, 0x31, 0x2B, 0x00, 0x0C, 0x04, 0x02, 0x37]
# Unscramble the flag.
flag = [0] * len(scrambled_flag)
for i in range(len(scrambled_flag)):
flag[scrambled_order[i] - 1] = scrambled_flag[i]
# We can determine the key by XORing the unscrambled flag
# with the first 8 bytes of the flag.
flag_start = b"jadeCTF{"
key = [0] * len(flag_start)
for i in range(len(flag_start)):
key[i] = flag[i] ^ flag_start[i]
# XOR the flag with the key to get the flag.
for i in range(len(flag)):
flag[i] ^= key[i % len(key)]
# Print the flag.
print("".join([chr(x) for x in flag]))
if name == "main":
main()