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 -> 4378956210
  • abcdefghij -> 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()