LakeCTF 2026 Writeups

Last May, I had the opportunity to participate in the prestigious LakeCTF Finals!

This CTF has been around for a relatively long time, and it had always been my dream to get to compete in it. Well, the Iran War almost ruined my plan TWICE, but I managed to pull through nonetheless, though with a small dent in my wallet and a 1 hour penalty, causing me to end up just barely missing the solve for one of the challenges.

NUS Greyhats did not perform as well as expected partly because of that, but it’s okay, we had tons of fun, and that was the most important part :)

Broken Golf

Category: rev

Solves: 9/10

This is a bit of the more on the esoteric side in terms of reversing challenges, and was a good teaser / appetizer to start off the CTF.

Essentially, we are given a suspiciously named chal_missing_24_bytes binary file, as well as checker.py logic for explaining the setup:

with open("chal", "rb") as f:
    challenge_data = f.read()

stripped_data = challenge_data[24:]
print(base64.b64encode(stripped_data).decode())
sys.stdout.flush()

decoded = base64.b64decode(sys.stdin.readline().strip())
print("Received data length:", len(decoded))

if len(decoded) != 24:
    print("Expected 24 bytes")
    sys.exit(1)

if decoded[4] != 2:
    print("Expected 64-bit executable")
    sys.exit(1)

elf_path = "/tmp/final_chal"

with open(elf_path, "wb") as f:
    f.write(decoded + stripped_data)

The challenge starts off with a regular binary living on the server; before we get to run it, we need to pass in our own 24 bytes replacing the head of the binary. The chal_missing_24_bytes is provided to us as the truncated version of the binary.

os.chmod(elf_path, 0o755)

for _ in range(100):
    args = [random.choice(["32", "64"]) for _ in range(random.randint(1, 30))]
    res = subprocess.run(
        [elf_path] + args,
        env={},
        timeout=2,
        # stdout=subprocess.DEVNULL,
        # stderr=subprocess.DEVNULL,
        preexec_fn=preexec
    )
    if res.returncode != get_expected(args):
        print("Testcase failed")
        sys.exit(1)

print(f"All tests passed! Flag: {os.environ.get('FLAG', 'flag{default_flag}')}")

The checker understandably does some hardening to prevent unintended solutions; I will be largely ignoring them. The checker attempts to run our modified binary multiple times against a random sample of inputs to ensure that its behaviour is “as intended”:

def get_expected(args):
    ebx = 1
    for arg in args:
        ebx = (ebx * 2 if arg == "32" else ebx + 2) & 0xffffffff
    return ebx & 0xff

Interesting that ebx + 2 is used instead of maybe (ebx + 1) * 2. But well I’m not here to solve Math equations; all we need to know is that it computes a checksum based on the sequence of (a variable number of) input arguments (either 32 or 64). We probably intend to emulate this behaviour via our 24-byte modification. But what can we do from just changing the header?

Before that, we shall at least see what was provided in the truncated binary:

$ objdump -D -Mintel,x86-64 -b binary -m i386 chal_missing_24_bytes 

chal_missing_24_bytes:     file format binary


Disassembly of section .data:

00000000 <.data>:
   0:   8d 00                   lea    eax,[rax]
   2:   40 00 00                rex add BYTE PTR [rax],al
   5:   00 00                   add    BYTE PTR [rax],al
   7:   00 38                   add    BYTE PTR [rax],bh
        ...
  19:   00 00                   add    BYTE PTR [rax],al
  1b:   00 40 00                add    BYTE PTR [rax+0x0],al
  1e:   38 00                   cmp    BYTE PTR [rax],al
  20:   01 00                   add    DWORD PTR [rax],eax
  22:   00 00                   add    BYTE PTR [rax],al
  24:   07                      (bad)
        ...
  31:   00 40 00                add    BYTE PTR [rax+0x0],al
  34:   00 00                   add    BYTE PTR [rax],al
  36:   00 00                   add    BYTE PTR [rax],al
  38:   00 00                   add    BYTE PTR [rax],al
  3a:   40 00 00                rex add BYTE PTR [rax],al
  3d:   00 00                   add    BYTE PTR [rax],al
  3f:   00 d7                   add    bh,dl
  41:   00 00                   add    BYTE PTR [rax],al
  43:   00 00                   add    BYTE PTR [rax],al
  45:   00 00                   add    BYTE PTR [rax],al
  47:   00 d7                   add    bh,dl
        ...
  55:   00 00                   add    BYTE PTR [rax],al
  57:   00 e8                   add    al,ch
  59:   07                      (bad)
  5a:   00 00                   add    BYTE PTR [rax],al
  5c:   00 ea                   add    dl,ch
  5e:   17                      (bad)
  5f:   00 40 00                add    BYTE PTR [rax+0x0],al
  62:   33 00                   xor    eax,DWORD PTR [rax]
  64:   48 b8 00 00 00 00 eb    movabs rax,0x6eb00000000
  6b:   06 00 00
  6e:   83 c3 02                add    ebx,0x2
  71:   c3                      ret
  72:   01 db                   add    ebx,ebx
  74:   c3                      ret
  75:   59                      pop    rcx
  76:   48 ff c9                dec    rcx
  79:   5e                      pop    rsi
  7a:   bb 01 00 00 00          mov    ebx,0x1
  7f:   48 85 c9                test   rcx,rcx
  82:   74 32                   je     0xb6
  84:   5e                      pop    rsi
  85:   8a 06                   mov    al,BYTE PTR [rsi]
  87:   3c 33                   cmp    al,0x33
  89:   74 06                   je     0x91
  8b:   3c 36                   cmp    al,0x36
  8d:   74 0b                   je     0x9a
  8f:   eb 20                   jmp    0xb1
  91:   b8 00 08 40 00          mov    eax,0x400800
  96:   b0 20                   mov    al,0x20
  98:   eb 07                   jmp    0xa1
  9a:   b8 00 08 40 00          mov    eax,0x400800
  9f:   b0 40                   mov    al,0x40
  a1:   48 89 e5                mov    rbp,rsp
  a4:   bc 00 08 40 00          mov    esp,0x400800
  a9:   e8 3f ff ff ff          call   0xffffffed
  ae:   48 89 ec                mov    rsp,rbp
  b1:   48 ff c9                dec    rcx
  b4:   eb c9                   jmp    0x7f
  b6:   b8 3c 00 00 00          mov    eax,0x3c
  bb:   89 df                   mov    edi,ebx
  bd:   0f 05                   syscall

The file starts off with non-disassemblable junk, probably what we would expect to hold additional ELF information. We do start seeing valid instructions at offset 0x6e:

6e:   83 c3 02                add    ebx,0x2
71:   c3                      ret
72:   01 db                   add    ebx,ebx
74:   c3                      ret

Well, if this is not a joy to uncover! These two “gadgets” perfectly align with our required branches in get_expected above. For example, assuming rax holds either 32 or 64, we would want to have some sort of functionality in the binary as below:

[0] cmp rax, 32
[1] jne [4]
[2] call 0x72
[3] jmp [5]
[4] call 0x6e

In terms of argument parsing, this is handled by 0x85:0xa1:

• If the current element in argv starts with 3, set rax = 0x400820
• If the current element in argv starts with 6, set rax = 0x400840

Then the function sets up stack at 0x400800 and… calls 0xffffffed (-19). What?

Oh yea, we are missing the initial 24 bytes. If we include them, we are jumping to… offset 5?

On one hand that’s convenient, we directly know that we have some control over execution. On the other hand, what freedoms are we working with inside an ELF header?

For this, we will need to dive into the ELF specification itself! I found this and this to be relatively comprehensive resources for our purposes.

Remember, we can only affect the first 24 bytes of the header, which is surprisingly limited. Looking at the first few lines we discover

#define EI_NIDENT 16

typedef struct {
        unsigned char   e_ident[EI_NIDENT];

That is already two-thirds of our controllable bytes gone! Then, what does e_ident contain, other than the \x7fELF that everyone loves? From figure 4-4:

Immediately we see something promising: Padding bytes!? To get here though, we must bypass the rest of the used bytes.

Recall first that our execution starts at byte [5]. Byte [4] seems to be important (32-bit vs 64-bit), and is enforced by the checker:

if decoded[4] != 2:
    print("Expected 64-bit executable")
    sys.exit(1)

What about the rest?

Naturally, one might think that given that the challenge routes us to [5], there are only two scenarios:

1. We have to golf our way through the constraints set by the specification.
2. The validity of the bytes don’t actually matter for execution?

No guessing needed, the most straightforward way is to test it out ourselves. First we construct a valid ELF binary (which inevitably crashes due to bad opcode at [5] and beyond) —

from pwn import read, write

write('test.elf', (
  # e_ident
  b'\x7fELF' # EI_MAG
  b'\x02'    # EI_CLASS (enforced)
  b'\x01'    # EI_DATA:       little endian
  b'\x01'    # EI_VERSION:    current version
  b'\0'      # EI_OSABI:      no extensions
  b'\0'      # EI_ABIVERSION: (irrelevant)
  b'\0\0\0\0\0\0\0' # padding bytes

  # e_type (2 bytes)
  b'\x02\0'  # executable

  # e_machine (2 bytes)
  b'\x3e\0'  # amd64

  # e_version (4 bytes)
  b'\x01\0\0\0' # current version (again?)
) + read('chal_missing_24_bytes'))

$ ./test.elf 32
Segmentation fault (core dumped)
$ echo $?
139
$ ./test.elf 40
$ echo $?
1

Behaves as expected. Now lets try to inject some bad bytes into e_ident…

from pwn import read, write

x = bytearray(read('test.elf'))
x[18:19] = b'\x67'
write('test2.elf', bytes(x))

$ ./test2.elf 32
Segmentation fault (core dumped)
$ echo $?
139
$ ./test2.elf 40
$ echo $?
1

Perfect!

Through trial-and-error, we can also discover that we cannot realistically modify e_type and e_machine. e_version however is under our control, but we will probably need to jump across the 4 bytes of moat, at which point we might as well not use it. (Though it remains an option.)

from pwn import read, write

for i in range(16, 24):
  x = bytearray(read('test.elf'))
  x[i:i+1] = b'\x67'
  write(f'test-{i}.elf', bytes(x))

for i in {16..23}; do \
    echo; \
    echo $i; \
    ./test-$i.elf 32; \
    echo $?; \
    ./test-$i.elf 40; \
    echo $?; \
    rm ./test-$i.elf; \
done

16
-bash: ./test-16.elf: cannot execute binary file: Exec format error
126
-bash: ./test-16.elf: cannot execute binary file: Exec format error
126

17
-bash: ./test-17.elf: cannot execute binary file: Exec format error
126
-bash: ./test-17.elf: cannot execute binary file: Exec format error
126

18
-bash: ./test-18.elf: cannot execute binary file: Exec format error
126
-bash: ./test-18.elf: cannot execute binary file: Exec format error
126

19
-bash: ./test-19.elf: cannot execute binary file: Exec format error
126
-bash: ./test-19.elf: cannot execute binary file: Exec format error
126

20
Segmentation fault (core dumped)
139
1

21
Segmentation fault (core dumped)
139
1

22
Segmentation fault (core dumped)
139
1

23
Segmentation fault (core dumped)
139
1

So now our updated problem statement:

Write an 11-byte payload that does the following:

• If rax = 0x400820, jump to 0x8a (+24 bytes accounted)
• If rax = 0x400840, jump to 0x86

Well not exactly as well, we need to take note of the virtual address mapping. Using our previously crafted dummy:

$ readelf -h test.elf
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x40008d
  Start of program headers:          56 (bytes into file)
  Start of section headers:          0 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         1
  Size of section headers:           0 (bytes)
  Number of section headers:         7
  Section header string table index: 0

From here I treated this as a pure golfing challenge and tried all sorts of payloads to stay within the 11 byte limit. Most of my earlier discovered payloads were ironically 12 bytes long, but I did eventually stumble upon one after like maybe an hour:

; 0x400820 -> 0x40008a
; 0x400840 -> 0x400086
shr al, 3     ; c0 e8 03
neg al        ; f6 d8
sub ax, 0x872 ; 66 2d 72 08
jmp rax       ; ff e0

This is a pretty mathematical golf 😅 Essentially, we abuse the fact that the rax available at the start of the payload is quite similar to the target address. Not to mention,

>>> 0x8a-0x86
4
>>> 0x40-0x20
32

Exactly 8x difference!

So we consider how we want to transform, for now just the last byte of rax:

         f1      f2      f3
[32] 20 ---- ?? ---- ?? ---- 8a
Δ    20       4      -4      -4
[64] 40 ---- ?? ---- ?? ---- 86

Hopefully it’s clear to follow that

Surely, we achieve:

>>> hex(f(0x20))
'0x8a'
>>> hex(f(0x40))
'0x86'

With f as simple as

def f(x):
    return (-(x//8)+0x8e) % 0x100

But remember, we still needed to get rid of the 8 in 0x400820 somehow. Not to fret, we simply extend our to a 16-bit operation… wait, it probably looks cleaner here to perform a subtraction:

def f(x):
    return (-(x//8)-0x72) % 0x100

So from sub al, 0x72, we simply extend this to sub ax, 0x872. Et voila, 11 bytes!

As I was making this writeup I vaguely remembered that the LakeCTF team did release their challenge repository, so it would be good to also reference the intended solution.

An explicitly writeup apparently wasn’t released for this challenge, but we can still find solution traces on the official reconstructed binary —

Well, I guess the intended solution was a bit longer and more involved than I expected 😓 As someone who wrote challenges before, it kind of sucked knowing I actually took the shortcut around the intended challenge design. But well, at least there wasn’t an immediately golfable solution AFAIK (so the +1h spent was still somewhat rewarding in the spirit of the CTF…)

Vault Matrix

Category: rev

Solves: 2/10

I did not manage to solve this challenge on-site :( but I was REALLY close. More on that at the end.

The setup for this is closer to a traditional reversing challenge. That is, one binary provided. For starters, it is a stripped binary, so it’s probably going to take some baseline effort before we start understanding the program mechanics. Reminder that this is a no AI challenge XD

Anyway, main isn’t directly available as expected, so we find it through IDA’s labelled start.

__int64 sub_401760()
{
  int v0; // edx
  int v1; // ecx
  int v2; // r8d
  int v3; // r9d
  __int64 result; // rax
  char *v5; // rdx
  _QWORD *v6; // rbp
  __int64 i; // rbx
  __int64 v8; // rdi
  unsigned int v9; // [rsp+14h] [rbp-44h] BYREF
  int v10; // [rsp+18h] [rbp-40h]
  char v11; // [rsp+1Ch] [rbp-3Ch]
  _QWORD v12[3]; // [rsp+20h] [rbp-38h] BYREF
  unsigned __int64 v13; // [rsp+38h] [rbp-20h]

  v13 = __readfsqword(0x28u);
  dword_4E54C0 = sub_44DDE0(0, 0, 1, 0);
  sub_44FD20(1, (unsigned int)"Give me your key quickly or bad things will happen to you:\n> ", v0, v1, v2, v3);
  if ( sub_40CD90(byte_4E54E0, 100, off_4E38B8) )
  {
    byte_4E54E0[j_ifunc_4208E0(byte_4E54E0, 4921194)] = 0;
    if ( j_ifunc_4209C0(byte_4E54E0) == 81 )
    {
      v5 = byte_4E54E0;
      while ( (unsigned __int8)(*v5 - 49) <= 8u )
      {
        if ( ++v5 == (char *)&unk_4E5531 )
        {
          v6 = v12;
          for ( i = 0; i != 3; ++i )
            sub_416180(v6++, 0, sub_401A60, i);
          sub_4171E0(v12[0], 0);
          sub_4171E0(v12[1], 0);
          sub_4171E0(v12[2], 0);
          v11 = 0;
          LOWORD(v9) = 0;
          v10 = 0;
          sub_401AC0(&v9);
          if ( !v10 )
          {
            sub_40D2F0("Validation Failed.");
            break;
          }
          v8 = -(int)sub_44C630(30) & 0x4AF740;
          if ( (unsigned int)sub_44DF40(v8, &byte_4AF8A9[-v8], 7) )
          {
            sub_40C170("mprotect");
            result = 1;
          }
          else
          {
            sub_401FF0(sub_4AF740, byte_4AF8A9 - (char *)sub_4AF740, byte_4E54E0, 81);
            sub_4AF740(byte_4E54E0, byte_4AF8A9 - (char *)sub_4AF740);
            result = v9;
          }
          goto LABEL_4;
        }
      }
    }
  }
  result = 1;
LABEL_4:
  if ( v13 != __readfsqword(0x28u) )
    sub_44FE10();
  return result;
}

Personally I find that in terms of recovering symbols, the best way is really just to have as many best guesses as possible. It’s okay to label something with a bit of uncertainty (with some marking I guess), because more often than not it’s going to be correct.

Going through them one by one:

__int64 main() /* reached from start */
{
  // ...
  /* sys_ptrace mentioned in function */
  dword_4E54C0 = _ptrace(0, 0, 1, 0);
  /* this was printed out, with 1 representing stdout fp */
  _fprintf(1, (unsigned int)"Give me your key quickly or bad things will happen to you:\n> ", v0, v1, v2, v3);
  /* off_4E38B8 is stdin */
  if ( _fgets(inp, 100, off_4E38B8) )
  {
    /* j_ifunc_xxx don't actually take arguments */
    inp[j_ifunc_4208E0()] = 0;
    if ( j_ifunc_4209C0() == 81 )
    {
      ptr = inp;
      while ( (unsigned __int8)(*ptr - 49) <= 8u ) /* 1 to 9 */
      {
        /* inp_end is guessed, but this is a standard pattern */
        if ( ++ptr == (char *)&inp_end )
        {
          v6 = v12;
          for ( i = 0; i != 3; ++i )
            /* pthread_create mentioned in function
               also the arguments for it makes sense */
            _pthread_create(v6++, 0, sub_401A60, i);
          /* less evidence for this one
             but essentially note that v12 is our pthread_t array */
          _pthread_join(v12[0], 0);
          _pthread_join(v12[1], 0);
          _pthread_join(v12[2], 0);
          v11 = 0;
          LOWORD(v9) = 0;
          v10 = 0;
          sub_401AC0(&v9);
          if ( !v10 )
          {
            /* weak evidence but looks like a library function
               and the string was printed out */
            _puts("Validation Failed.");
            break;
          }
          // [OMITTED]
        }
      }
    }
  }
  result = 1;
  // ...
  return result;
}

Can I just say I instantly clocked Sudoku mechanics just from this main function?

While solving, before I continued on with the [OMITTED] section, we could already tell that the main validation logic happens before that at sub_401AC0. We can explore that section if we need to, but it looked kind of messy and I felt that the ROI wasn’t very high at this current stage.

Also I have to say, I still haven’t figured out what the j_ifunc_xxx do. Maybe after I publish this.

Let’s explore the children functions, starting with sub_401A60:

/* a1 = 0, 1, 2 */
__int64 __fastcall sub_401A60(int a1)
{
  int v1; // edx
  char v2; // cl
  char *v3; // rax

  v1 = a1;
  if ( a1 )
  {
    if ( a1 == 1 )
    {
      v2 = 59;
    }
    else
    {
      if ( a1 > 8599 )
        return 0;
      v2 = -100;
    }
  }
  else
  {
    v2 = dword_4E54C0 + 122;
  }
  v3 = &byte_4E1120[a1];
  do
  {
    v1 += 3;
    *v3 ^= v2;
    v3 += 3;
  }
  while ( v1 <= 8599 );
  return 0;
}

Huh?

A quick scan tells us that this (multithreaded) function modifies byte_4E1120. But I didn’t really dig deeper beyond this — we will figure out what we need to figure out, as we go along. Instead I went straight to the bigger fish, sub_401AC0:

__int64 __fastcall sub_401AC0(unsigned __int16 *a1, __int64 a2, __int64 a3, __int64 a4, __int64 a5, __int64 a6)
{
  int v6; // r12d
  unsigned __int16 *v7; // r13
  int v8; // ebx
  bool v9; // bp
  int v10; // eax
  unsigned __int16 v12; // ax
  unsigned int *v13; // r15
  __int64 v14; // r14
  __int64 v15; // rax
  __int16 v16; // di
  __int64 v17; // rcx
  __int16 v18; // si
  __int64 v19; // rax
  __int64 v20; // rax
  __int64 v21; // rax
  __int64 v22; // rax
  __int64 v23; // rax
  __int64 v24; // rax
  int v25; // eax
  int v26; // eax
  int v27; // eax
  _OWORD v28[3]; // [rsp+0h] [rbp-128h] BYREF
  _DWORD v29[21]; // [rsp+30h] [rbp-F8h] BYREF
  _DWORD v30[25]; // [rsp+84h] [rbp-A4h] BYREF
  unsigned __int64 v31; // [rsp+E8h] [rbp-40h]

  v6 = *a1;
  v31 = __readfsqword(0x28u);
  *((_DWORD *)a1 + 1) = 1;
  memset(v28, 0, sizeof(v28));
  *(_OWORD *)v29 = 0;
  if ( (unsigned __int16)v6 > 0x2197u )
    goto LABEL_5;
  v7 = a1;
  v8 = 0;
  v9 = 0;
  do
  {
    a3 = (unsigned __int16)v6;
    v10 = (unsigned __int8)(*((_BYTE *)v7 + 8) ^ byte_4E1120[(unsigned __int16)v6]);
    switch ( (char)v10 )
    {
      case 1:
        v6 += 4;
        a4 = (unsigned __int8)byte_4E1120[(int)a3 + 1];
        v27 = a3 + 2;
        a3 = (unsigned __int8)byte_4E1120[(int)a3 + 3];
        *((_DWORD *)v28 + a4) = a3 | ((unsigned __int8)byte_4E1120[v27] << 8);
        continue;
      case 2:
        v26 = (unsigned __int16)v6 + 1;
        v6 += 3;
        a3 = (int)a3 + 2;
        a4 = (unsigned __int8)byte_4E1120[v26];
        *((_DWORD *)v28 + a4) = byte_4E54E0[(unsigned __int8)byte_4E1120[a3]] - 48;
        continue;
      case 3:
        v25 = (unsigned __int16)v6 + 2;
        v6 += 3;
        a3 = (int)a3 + 1;
        a4 = *((unsigned int *)v28 + (unsigned __int8)byte_4E1120[v25]);
        *((_DWORD *)v28 + (unsigned __int8)byte_4E1120[a3]) = a4;
        continue;
      case 4:
        v6 += 3;
        v24 = (unsigned __int8)byte_4E1120[(int)a3 + 1];
        a3 = *((unsigned int *)v28 + (unsigned __int8)byte_4E1120[(int)a3 + 2]);
        *((_DWORD *)v28 + v24) += a3;
        continue;
      case 5:
        v6 += 3;
        a4 = (unsigned __int8)byte_4E1120[(int)a3 + 1];
        a3 = (unsigned __int8)byte_4E1120[(int)a3 + 2];
        *((_DWORD *)v28 + a4) -= *((_DWORD *)v28 + a3);
        continue;
      case 6:
        v6 += 3;
        v23 = (unsigned __int8)byte_4E1120[(int)a3 + 1];
        a3 = *((unsigned int *)v28 + (unsigned __int8)byte_4E1120[(int)a3 + 2]);
        *((_DWORD *)v28 + v23) ^= a3;
        continue;
      case 7:
        v6 += 3;
        v22 = (unsigned __int8)byte_4E1120[(int)a3 + 1];
        a3 = *((unsigned int *)v28 + (unsigned __int8)byte_4E1120[(int)a3 + 2]);
        *((_DWORD *)v28 + v22) &= a3;
        continue;
      case 11:
        v6 += 3;
        v21 = (unsigned __int8)byte_4E1120[(int)a3 + 1];
        a3 = *((unsigned int *)v28 + (unsigned __int8)byte_4E1120[(int)a3 + 2]);
        *((_DWORD *)v28 + v21) |= a3;
        continue;
      case 12:
        v6 += 3;
        v20 = (unsigned __int8)byte_4E1120[(int)a3 + 1];
        a3 = (unsigned __int8)byte_4E1120[(int)a3 + 2];
        a4 = *((unsigned int *)v28 + a3);
        *((_DWORD *)v28 + v20) <<= a4;
        continue;
      case 13:
        v6 += 3;
        v19 = (unsigned __int8)byte_4E1120[(int)a3 + 1];
        a3 = (unsigned __int8)byte_4E1120[(int)a3 + 2];
        a4 = *((unsigned int *)v28 + a3);
        *((_DWORD *)v28 + v19) = __ROR4__(*((_DWORD *)v28 + v19), a4);
        continue;
      case 14:
        a3 = (unsigned __int16)v6 + 2;
        a4 = (unsigned __int8)byte_4E1120[(unsigned __int16)v6 + 1];
        v9 = *((_DWORD *)v28 + a4) == *((_DWORD *)v28 + (unsigned __int8)byte_4E1120[a3]);
        v6 += 3;
        continue;
      case 16:
        v6 += 2;
        if ( v9 )
        {
          a3 = (int)a3 + 1;
          LOWORD(v10) = byte_4E1120[a3];
          v6 += v10;
        }
        continue;
      case 20:
        goto LABEL_5;
      case 22:
        v15 = v8;
        v6 += 4;
        ++v8;
        v16 = (unsigned __int8)byte_4E1120[(int)a3 + 1];
        v17 = 3 * v15;
        v30[v17] = 1;
        v18 = (v16 << 8) | (unsigned __int8)byte_4E1120[(int)a3 + 2];
        LOBYTE(v30[v17 + 1]) = byte_4E1120[(int)a3 + 3];
        a1 = (unsigned __int16 *)&v29[2 * v15 + 4];
        LOWORD(v29[v17 + 20]) = v18;
        a2 = 0;
        sub_416180(a1, 0, sub_401AC0, &v29[3 * v15 + 20]);
        continue;
      case 23:
        if ( !v8 )
          goto LABEL_16;
        v13 = v30;
        v14 = 1;
        break;
      case 29:
        a4 = (unsigned __int8)byte_4E1120[(unsigned __int16)v6 + 1] << 8;
        v12 = ((unsigned __int8)byte_4E1120[(unsigned __int16)v6 + 1] << 8)
            | (unsigned __int8)byte_4E1120[(unsigned __int16)v6 + 2];
        if ( v12 <= 0x2197u )
        {
          a3 = (unsigned __int8)byte_4E1120[(unsigned __int16)v6 + 3];
          byte_4E1120[v12] ^= a3;
        }
        v6 += 4;
        continue;
      default:
        *((_DWORD *)v7 + 1) = 0;
        goto LABEL_5;
    }
    while ( 1 )
    {
      a1 = *(unsigned __int16 **)&v29[2 * v14 + 2];
      a2 = 0;
      sub_4171E0(a1, 0);
      a3 = *v13;
      if ( (_DWORD)a3 )
        break;
      *((_DWORD *)v7 + 1) = 0;
      if ( v8 <= (int)v14 )
        goto LABEL_5;
LABEL_13:
      ++v14;
      v13 += 3;
    }
    if ( v8 > (int)v14 )
      goto LABEL_13;
LABEL_16:
    if ( !*((_DWORD *)v7 + 1) )
      break;
    ++v6;
  }
  while ( (unsigned __int16)v6 <= 0x2197u );
LABEL_5:
  if ( v31 != __readfsqword(0x28u) )
    sub_44FE10(a1, a2, a3, a4, a5, a6, *(_QWORD *)&v28[0], *((_QWORD *)&v28[0] + 1));
  return 0;
}

VM!

Again from experience, the head (and occasionally tail) of the function tells you 80% of the VM infrastructure; the rest are just opcode minutiae. So let’s go through this patiently:

/* recall: argument was zeroed before being passed in as a pointer */
__int64 __fastcall run(unsigned __int16 *state)
{
  // ...

  v6 = *state;
  /* canary setup */
  *((_DWORD *)state + 1) = 1;
  memset(v28, 0, sizeof(v28));
  *(_OWORD *)v29 = 0;
  if ( (unsigned __int16)v6 > 0x2197u )
    goto _out;
  v7 = state;
  v8 = 0;
  v9 = 0;
  do
  {
    a3 = (unsigned __int16)v6;
    v10 = (unsigned __int8)(*((_BYTE *)v7 + 8) ^ vm[(unsigned __int16)v6]);
    switch ( (char)v10 )
    {
      case 1:
        v6 += 4;
        a4 = (unsigned __int8)vm[(int)a3 + 1];
        v27 = a3 + 2;
        a3 = (unsigned __int8)vm[(int)a3 + 3];
        *((_DWORD *)v28 + a4) = a3 | ((unsigned __int8)vm[v27] << 8);
        continue;
      // [OMITTED]
      default:
        *((_DWORD *)v7 + 1) = 0;
        goto _out;
    }
    // [OMITTED]
    /* rationale: all "regular" opcode branches end with `continue`,
       skipping directly to the `while` check */
  }
  while ( (unsigned __int16)v6 <= 0x2197u );
_out:
  /* canary check */
  return 0;
}

Quite quickly we can find the pc taking the form of v6 and a3, with opcode in v10; this is also a good time to derive the state struct, using this function and the callsite:

  unsigned int v9; // [rsp+14h] [rbp-44h] BYREF
  int v10; // [rsp+18h] [rbp-40h]
  char v11; // [rsp+1Ch] [rbp-3Ch]
// ...
          v11 = 0;
          LOWORD(v9) = 0;
          v10 = 0;
          sub_401AC0(&v9);
          if ( !v10 )

Giving us

[0:2] pc
[2:4]
[4:8] success
[8:9] xorkey?

No idea what state[8] does; it seems to behave as an xor key from the

    v10 = (unsigned __int8)(*((_BYTE *)v7 + 8) ^ vm[(unsigned __int16)v6]);

line, but it is initialized to 0 and doesn’t seem to change.

With most variables figured out, the bulk of the remaining work is to work through the each and every opcode… due to verbosity, I will just include the walkthrough for the first few.

      case 1:
        pc += 4;
        a4 = (unsigned __int8)vm[(int)saved_pc + 1];
        v27 = saved_pc + 2;
        a3 = (unsigned __int8)vm[(int)saved_pc + 3];
        *((_DWORD *)v28 + a4) = a3 | ((unsigned __int8)vm[v27] << 8);
        continue;

where v28, if you recall, is the memzeroed stack buffer. So for an instruction 01 xx yy zz, we will have v28[xx] = 0000yyzz. For the next opcode

      case 2:
        v26 = (unsigned __int16)pc + 1;
        pc += 3;
        saved_pc = (int)saved_pc + 2;
        a4 = (unsigned __int8)vm[v26];
        *((_DWORD *)v28 + a4) = inp[(unsigned __int8)vm[saved_pc]] - 48;
        continue;

of the structure 02 xx yy, we will have v28[xx] = int(inp[yy]) (since values of inp are 1-9).

The bulk of the remaining opcodes perform your standard binary operations of the form ## xx yy corresponding to v28[xx] ?= v28[yy] — as we parse them one by one we gradually confirm that v28 is most likely a register file. (There might be possibility of some funny OOB access? But I guess not if we don’t have control over the VM.)

However, there are a couple of “interesting” / “unorthodox” opcodes near the bottom:

      case 22:
        /* first mention of v8 in the function,
           other than initialization to 0 */
        v15 = v8;
        pc += 4;
        ++v8;
        v16 = (unsigned __int8)vm[(int)saved_pc + 1]; /* xx */
        v17 = 3 * v15;
        /* v30 is a DWORD array. so presumably it
           actually holds structs spanning 3 DWORDs each */
        v30[v17] = 1;
        v18 = (v16 << 8) | (unsigned __int8)vm[(int)saved_pc + 2];
        LOBYTE(v30[v17 + 1]) = vm[(int)saved_pc + 3];
        /* v29 now used properly. looks like struct of 2 DWORDs */
        a1 = (unsigned __int16 *)&v29[2 * v15 + 4];
        /* v29 is a DWORD[21] array right before v30
           so you can see it as v30[v17 - 1] */
        LOWORD(v29[v17 + 20]) = v18;
        a2 = 0;
        /* sub_401AC0 is the current function itself */
        _pthread_create(a1, 0, sub_401AC0, &v29[3 * v15 + 20]);
        continue;

This is quite messy — cleaned up a little:

pthread_t threads[8];
struct {
    short a;
    int   b;
    char  c;
} data[8];
// ...
char xx = vm[pc+1];
char yy = vm[pc+2];
char zz = vm[pc+3];
pc += 4;
int cur_idx = count++; /* v15 = v8; */
short xxyy = (xx << 8) | yy;
data[cur_idx] = {
    .a = xxyy,
    .b = 1,
    .c = zz,
};
_pthread_create(&threads[cur_idx], 0, sub_401AC0, &data[cur_idx]);

Which is when we realize, wait — the data that we’re passing in is exactly state which we identified at the start of the function! This is quite literally multithreading WITHIN the VM! :mind_blown:

Note that the xorkey field (state[8]) that we identified earlier finally has an effect. Most likely this means the corresponding sections of the VM are encrypted relative to each thread. We will dig more later when we analyze the bytecode.

Continuing,

      case 23:
        if ( !v8 )
          goto LABEL_16;
        v13 = v30;
        v14 = 1;
        break;
      // ...
    }
    while ( 1 )
    {
      a1 = *(unsigned __int16 **)&v29[2 * v14 + 2];
      a2 = 0;
      _pthread_join(a1, 0);
      a3 = *v13;
      if ( (_DWORD)a3 )
        break;
      *((_DWORD *)v7 + 1) = 0;
      if ( v8 <= (int)v14 )
        goto LABEL_5;
LABEL_13:
      ++v14;
      v13 += 3;
    }
    if ( v8 > (int)v14 )
      goto LABEL_13;
LABEL_16:
    if ( !*((_DWORD *)v7 + 1) )
      break;
    ++v6;
  } /* VM execution do-while body ends here */

Control flow is a bit ugly due to decompilation, but still relatively sound. We can surely write better code:

case 23:
    if (count) {
        v13 = v30;
        cur_idx = 1;
        while (1) {
            a1 = *(unsigned __int16 **)&v29[2 * cur_idx + 2];
            a2 = 0;
            _pthread_join(a1, 0);
            a3 = *v13;
            if ( !(_DWORD)a3 ) {
                state.success = 0;
                if (cur_idx >= count)
                    goto _out;
            } else if (cur_idx >= count) break;
            ++cur_idx;
            v13 += 3;
        }
    }
    if ( !state.success )
        goto _out;
    ++pc;
    continue;

which is effectively

case 23:
    if (count) {
        for (int cur_idx = 0; cur_idx < count; ++cur_idx) {
            _pthread_join(threads[cur_idx], 0);
            if (!data[cur_idx].success) {
                state.success = 0;
            }
        }
    }
    if (!state.success) { /* initialized to 1 at function start */
        break;
    }
    ++pc;
    continue;

So this is the join counterpart for 22, short-circuiting on child failure. And for our final boss:

      case 29:
        a4 = (unsigned __int8)vm[(unsigned __int16)pc + 1] << 8;
        v12 = ((unsigned __int8)vm[(unsigned __int16)pc + 1] << 8)
            | (unsigned __int8)vm[(unsigned __int16)pc + 2];
        if ( v12 <= 0x2197u )
        {
          a3 = (unsigned __int8)vm[(unsigned __int16)pc + 3];
          vm[v12] ^= a3;
        }
        pc += 4;
        continue;

This one is actually relatively chill, albeit odd and annoying to model: for 29 xx yy zz, we have vm[xxyy] ^= zz, i.e. another self-modifying layer.

With everything in place, time to disassemble the bytecode! In order to disentangle the effects of self-modification from 22 and 29, I wanted to see how far I could go without modifying the bytecode in-place for our first pass.

from pwn import read

RAW = read('./challenge')
off = RAW.find(b'\x6c\x3b\x8e\x7b\x2d')
PROGRAM = RAW[off:off+0x2197]

pc = 0
# helper functions to directly parse current bytecode values
def next8():
    global pc
    res = PROGRAM[pc]
    pc += 1
    return res
def next16():
    global pc
    res = PROGRAM[pc]<<8 | PROGRAM[pc+1]
    pc += 2
    return res

xorkey = 0
def exec():
    global pc
    print(f'{pc:04x} ||', end=' ')
    op = next8() ^ xorkey
    if op == 1:
        print(f'mov  r{next8()}, {next16():x}')
    elif op == 2:
        print(f'read r{next8()}, <<{next8()}>>')
    elif op == 3:
        print(f'mov  r{next8()}, r{next8()}')
    elif op == 4:
        print(f'add  r{next8()}, r{next8()}')
    elif op == 5:
        print(f'sub  r{next8()}, r{next8()}')
    elif op == 6:
        print(f'xor  r{next8()}, r{next8()}')
    elif op == 7:
        print(f'and  r{next8()}, r{next8()}')
    elif op == 11:
        print(f'or   r{next8()}, r{next8()}')
    elif op == 12:
        print(f'shl  r{next8()}, r{next8()}')
    elif op == 13:
        print(f'ror  r{next8()}, r{next8()}')
    elif op == 14:
        print(f'cmp  r{next8()}, r{next8()}')
    elif op == 16:
        print(f'je   {next8()}')
    elif op == 20:
        print('hlt')
        return False
    elif op == 22:
        print(f'dispatch pc={next16()} xorkey={next8()}')
    elif op == 23:
        print('join')
    elif op == 29:
        print(f'CHNG [{next16():04x}], {hex(next8())}')
    else:
        print(f'=== INVALID INSTRUCTION @ PC={pc-1} OP={op}')
    return True

# run the vm
while exec():
    pass

$ python3 parse.py | head
0000 || === INVALID INSTRUCTION @ PC=0 OP=108
0001 || === INVALID INSTRUCTION @ PC=1 OP=59
0002 || === INVALID INSTRUCTION @ PC=2 OP=142
0003 || === INVALID INSTRUCTION @ PC=3 OP=123
0004 || === INVALID INSTRUCTION @ PC=4 OP=45
0005 || === INVALID INSTRUCTION @ PC=5 OP=150
0006 || === INVALID INSTRUCTION @ PC=6 OP=60
0007 || === INVALID INSTRUCTION @ PC=7 OP=57
0008 || === INVALID INSTRUCTION @ PC=8 OP=138
0009 || === INVALID INSTRUCTION @ PC=9 OP=104

Umm…

Oh, recall the other function that we only quickly scanned through? The one that also modifies byte_4E1120, our VM? I guess it’s time to look at that now…

But actually after been through so much, reversing that function isn’t as daunting anymore:

/* pos = 0, 1, 2 */
int sub_401A60(int pos)
{
    char key;
    if (pos == 0) {
        key = dword_4E54C0 + 122;
    } else if (pos == 1) {
        key = 59;
    } else if (pos <= 8599) {
        key = 156; /* -100 */
    } else {
        return 0;
    }
    for (; pos <= 8599; pos += 3) {
        vm[pos] ^= key;
    }
    return 0;
}

where dword_4E54C0 is written back at the start of main:

  dword_4E54C0 = _pthread_create(0, 0, 1, 0);

i.e. normally 0. I suppose this is some antidebugging protection. Anyway, this small modification is relatively easy to integrate into our disassembler:

@@ -4,6 +4,9 @@
 off = RAW.find(b'\x6c\x3b\x8e\x7b\x2d')
 PROGRAM = RAW[off:off+0x2197]

+KEY = [0x7a, 0x3b, 0x9c]
+PROGRAM = [x ^ KEY[i%3] for i, x in enumerate(PROGRAM)]
+
 pc = 0
 # helper functions to directly parse current bytecode values
 def next8():

Now it should run properly:

$ python3 parse.py | head
0000 || dispatch pc=18 xorkey=1
0004 || dispatch pc=2630 xorkey=2
0008 || dispatch pc=4620 xorkey=3
000c || dispatch pc=6610 xorkey=4
0010 || join
0011 || hlt

Oh… well at least it did run properly XD

This isn’t too bad, it’s equivalent to delegating the task to 4 sub-agents. Praying that executions don’t cross each other (how much trouble would that be to craft this challenge!?), we can just emulate the sub-execution (though with a single-threaded workqueue):

@@ -20,6 +20,7 @@
     pc += 2
     return res

+saved = []
 xorkey = 0
 def exec():
     global pc
@@ -53,7 +54,10 @@
         print('hlt')
         return False
     elif op == 22:
-        print(f'dispatch pc={next16()} xorkey={next8()}')
+        fn = next16()
+        _xorkey = next8()
+        print(f'dispatch pc={fn} xorkey={_xorkey}')
+        saved.append((fn, _xorkey))
     elif op == 23:
         print('join')
     elif op == 29:
@@ -65,3 +69,11 @@
 # run the vm
 while exec():
     pass
+
+print(len(saved))
+for x, y in tuple(saved):
+    print('==========')
+    pc = x
+    xorkey = y
+    while exec():
+        pass

$ python3 parse.py | head -n 20
0000 || dispatch pc=18 xorkey=1
0004 || dispatch pc=2630 xorkey=2
0008 || dispatch pc=4620 xorkey=3
000c || dispatch pc=6610 xorkey=4
0010 || join
0011 || hlt
4
==========
0012 || mov  r0, 0
0016 || read r1, <<0>>
0019 || mov  r2, r1
001c || mov  r3, 0
0020 || xor  r2, r3
0023 || mov  r4, ff
0027 || and  r2, r4
002a || add  r0, r2
002d || CHNG [0037], 0xa5
0031 || CHNG [0038], 0x5a
0035 || mov  r1, a55c
0039 || cmp  r0, r1

Perfect! Well except just 2 lines down we have…

003c || je   1
003e || === INVALID INSTRUCTION @ PC=62 OP=21

Interestingly, searching through all INVALID INSTRUCTIONs present within the dump they ALL follow the same two pattern (with no exceptions):

002d || CHNG [0037], 0xa5
0031 || CHNG [0038], 0x5a
0035 || mov  r1, <value>
0039 || cmp  r0, r1
003c || je   1
003e || === INVALID INSTRUCTION @ PC=62 OP=21

and

0b19 || mov  r1, 3fe
0b1d || cmp  r0, r1
0b20 || je   1
0b22 || === INVALID INSTRUCTION @ PC=2850 OP=21

In fact, looking more closely, the bytecode seems extremely regular! At this point I’m already craving to start lifting the bytecode, so do that we shall:

0012 || mov  r0, 0
0016 || read r1, <<0>>
0019 || mov  r2, r1
001c || mov  r3, 0
0020 || xor  r2, r3
0023 || mov  r4, ff
0027 || and  r2, r4
002a || add  r0, r2
002d || CHNG [0037], 0xa5
0031 || CHNG [0038], 0x5a
0035 || mov  r1, a55c
0039 || cmp  r0, r1
003c || je   1
003e || === INVALID INSTRUCTION @ PC=62 OP=21

We note that the VM does a whole lot of “nothing”:

r0 = 0      # okay, valid, sure
r1 = inp[0]
r2 = r1     # r1 is reset later; might as well just use r1?
r3 = 0
r2 ^= r3    # no-op
r4 = 0xff
r2 &= r4    # no-op (given inp values are 1-9)
r0 += r2    # accumulate

That is, the whole chunk of instructions essentially just do

r0 = 0
r0 += inp[0]

The only reason why I left in r0 = 0 is because the exact same pattern between read and add is repeated for each different <<x>> value of inp access. Just to show an example to see for yourself:

003f || mov  r0, 0

0043 || read r1, <<1>>
0046 || mov  r2, r1
0049 || mov  r3, 0
004d || xor  r2, r3
0050 || mov  r4, ff
0054 || and  r2, r4
0057 || add  r0, r2

005a || read r1, <<9>>
005d || mov  r2, r1
0060 || mov  r3, 0
0064 || xor  r2, r3
0067 || mov  r4, ff
006b || and  r2, r4
006e || add  r0, r2

0071 || read r1, <<10>>
0074 || mov  r2, r1
0077 || mov  r3, 0
007b || xor  r2, r3
007e || mov  r4, ff
0082 || and  r2, r4
0085 || add  r0, r2

0088 || CHNG [0092], 0xa5
008c || CHNG [0093], 0x5a
0090 || mov  r1, a548
0094 || cmp  r0, r1
0097 || je   1
0099 || === INVALID INSTRUCTION @ PC=153 OP=21

Understandably this therefore does r0 = inp[1] + inp[9] + inp[10].

Okay, then what about that last chunk with the invalid instruction and the self-modification? Well, neither are particularly scary in this case:

• Notice that bytes 0092 and 0093 in the above example correspond to the 16-bit immediate in mov r1, a548. Thus performing ^= a55a we get mov r1, 0x12, which is then compared against our accumulated value.
• Upon a match, je skips over the invalid instruction, continuing execution; otherwise, we realize the invalid instruction simply makes VM halt execution with .success = 0. This is perfectly logical for a checker-based VM.

That is to say, the first half of the VM is simply doing

assert inp[0] == 0x6
assert inp[1]+inp[9]+inp[10] == 0x12
assert inp[2]+inp[3]+inp[4] == 0xa
assert inp[5]+inp[14] == 0xb
# ...

Okay, now onto the other half!

0a46 || mov  r0, 0

0a4a || read r1, <<0>>
0a4d || mov  r2, r1
0a50 || mov  r3, 1
0a54 || mov  r4, 0
0a58 || xor  r2, r4
0a5b || shl  r3, r2
0a5e || or   r0, r3

0a61 || read r1, <<1>>
0a64 || mov  r2, r1
0a67 || mov  r3, 1
0a6b || mov  r4, 0
0a6f || xor  r2, r4
0a72 || shl  r3, r2
0a75 || or   r0, r3

0a78 || read r1, <<2>>
0a7b || mov  r2, r1
0a7e || mov  r3, 1
0a82 || mov  r4, 0
0a86 || xor  r2, r4
0a89 || shl  r3, r2
0a8c || or   r0, r3

0a8f || read r1, <<3>>
0a92 || mov  r2, r1
0a95 || mov  r3, 1
0a99 || mov  r4, 0
0a9d || xor  r2, r4
0aa0 || shl  r3, r2
0aa3 || or   r0, r3

0aa6 || read r1, <<4>>
0aa9 || mov  r2, r1
0aac || mov  r3, 1
0ab0 || mov  r4, 0
0ab4 || xor  r2, r4
0ab7 || shl  r3, r2
0aba || or   r0, r3

0abd || read r1, <<5>>
0ac0 || mov  r2, r1
0ac3 || mov  r3, 1
0ac7 || mov  r4, 0
0acb || xor  r2, r4
0ace || shl  r3, r2
0ad1 || or   r0, r3

0ad4 || read r1, <<6>>
0ad7 || mov  r2, r1
0ada || mov  r3, 1
0ade || mov  r4, 0
0ae2 || xor  r2, r4
0ae5 || shl  r3, r2
0ae8 || or   r0, r3

0aeb || read r1, <<7>>
0aee || mov  r2, r1
0af1 || mov  r3, 1
0af5 || mov  r4, 0
0af9 || xor  r2, r4
0afc || shl  r3, r2
0aff || or   r0, r3

0b02 || read r1, <<8>>
0b05 || mov  r2, r1
0b08 || mov  r3, 1
0b0c || mov  r4, 0
0b10 || xor  r2, r4
0b13 || shl  r3, r2
0b16 || or   r0, r3

0b19 || mov  r1, 3fe
0b1d || cmp  r0, r1
0b20 || je   1
0b22 || === INVALID INSTRUCTION @ PC=2850 OP=21

Well…

r0 = 0
r1 = inp[0]
r2 = r1     # again redundant
r3 = 1
r4 = 0
r2 ^= r4    # no-op again
r3 <<= r2   # set (x+1)-th least significant bit
r0 |= r3    # transfer onto r0

If you’re less familiar with bit operations:

r0 = [False for _ in range(16)]
r0[inp[0]] = True

And the tail chunk simply checks if r0 == 0x3fe, or 0b1111111110, which in our context means

assert all(r0[i] for i in range(1, 10))

Okay the cat is out of the bag and long gone at this point. It is basically a Sudoku with extra steps. This portion makes sure that across the inp[0]...inp[8] being checked this round, there must be at least one inp[x] having a value of 1, of 2, of 3, and so on. Given that exactly 9 inp cells are checked at each round, each inp cell has to uniquely correspond to one number.

The rest basically follow the same format: the next set of checks are inp[9]...inp[17], then inp[18]...inp[26], and so on. In fact, remember the delegation to 4 different threads? Turns out each thread maps very cleanly to one type of checek:

0000 || dispatch pc=18 xorkey=1     ; sum check
0004 || dispatch pc=2630 xorkey=2   ; each row is unique
0008 || dispatch pc=4620 xorkey=3   ; each column is unique
000c || dispatch pc=6610 xorkey=4   ; each grid is unique

The last 3 checks make sense in a Sudoku context, but what about the first? Is it even solvable? I did try to just z3 it at first, but of course it did not work very well. Staring at the checks, that’s when it registered:

import re

with open('./dump.txt') as f:
    RAW = f.read().strip().splitlines()[10:]

cur = []
for line in RAW:
    if (m := re.search(r'<<(\d+)>>', line)) is not None:
        cur.append(int(m.group(1)))
    elif 'mov  r1' in line:
        target = int(line.split(', ')[1], 16) ^ 0xa55a
        print(' + '.join(map(lambda x: f'[{x}]', cur)), '==', target)
        cur = []
    elif line == '==========':
        break

[0] == 6
[1] + [9] + [10] == 18
[2] + [3] + [4] == 10
[5] + [14] == 11
[6] == 7
[7] + [8] == 10
[11] + [20] + [29] + [30] == 21
[12] + [13] == 14
[15] + [16] == 6
[17] + [26] == 8
[18] + [27] + [36] == 10
[19] + [28] == 11
[21] + [22] + [23] == 13
[24] + [25] == 14
[31] + [32] == 8
[33] + [41] + [42] == 18
[34] + [35] == 10
[37] + [45] + [46] == 16
[38] + [47] == 6
[39] + [40] + [48] == 16
[49] + [50] == 11
[51] + [52] + [53] + [62] == 16
[43] + [44] == 14
[54] + [55] == 7
[56] + [65] == 15
[57] + [66] == 15
[58] + [59] + [67] == 12
[60] + [68] + [69] + [77] == 15
[61] + [70] == 12
[63] + [64] == 7
[72] + [73] == 15
[74] + [75] + [76] == 8
[78] + [79] == 8
[71] + [80] == 17

Killer Sudoku!

Not going to lie, I’m so glad I’ve played (or at least heard of) this game before. Since it’s relatively established, there’s bound to be a solver online:

Solution:
683254791
915687243
427913865
598162437
132479586
764538912
256891374
349726158
871345629

Stringing the numbers together and sending to the binary as input yields us

$ ./challenge
Give me your key quickly or bad things will happen to you:
> 683254791915687243427913865598162437132479586764538912256891374349726158871345629

Good job! Here is the flag: af71644eb345468223e196bee35f61ac:87a8bceff6b7c062b0d75c2d07fc2fea78caefd0adb1167e982c79f76379265527d3d4c9ab05bc3206438b2e96179c4456a65d54a92339cca74933424b76540

At which point I had 20 minutes left in the CTF, so I spiritually gave up. Anyway, it’s time to dig into the last mechanic, the block of code that I omitted in main at the very start of our analysis:

          sub_401AC0(&v9); /* vm run function */
          if ( !v10 )
          {
            _puts("Validation Failed.");
            break;
          }
          /* no idea at all what this does but
             that name is mentioned in the function */
          v8 = -(int)_get_pthread_stack_min(30) & 0x4AF740;
          /* makes sense with the idiom below,
             also arguments make sense */
          if ( (unsigned int)_mprotect(v8, &byte_4AF8A9[-v8], 7) )
          {
            /* common c idiom */
            _perror("mprotect");
            result = 1;
          }
          else
          {
            sub_401FF0(sub_4AF740, byte_4AF8A9 - (char *)sub_4AF740, inp, 81);
            sub_4AF740(inp, byte_4AF8A9 - (char *)sub_4AF740);
            result = v9;
          }
          goto LABEL_4;

Now it comes to the two mysterious functions in the else branch. What’s even more mysterious, if you’ve noticed, is that sub_4AF740 seems to get modified (cue from mprotect + passed as buffer to sub_401FF0) before getting called!

For sure, the current state of sub_4AF740 looks corrupted:

// positive sp value has been detected, the output may be wrong!
__int64 __fastcall sub_4AF740(__int64 a1, _BYTE *_RSI, _BYTE *a3, __int64 a4)
{
  unsigned __int8 v5; // bp
  _BYTE retaddr[16]; // [rsp+0h] [rbp+0h]

  __asm { rep sahf }
  *a3 *= 2;
  __asm { outsd }
  __outbyte((unsigned __int16)a3, v5);
  BYTE1(a4) &= *_RSI;
  return MK_FP(*(_WORD *)retaddr, *(_QWORD *)retaddr)(a1, _RSI, a3, a4);
}

I took a preliminary look at sub_401FF0 and was frankly quite bamboozled. It almost looks like a memcpy, except

• The buffer sizes don’t match (361 vs 81)
• memcpy doesn’t accept a destination size
• There are mentions of malloc in the function somehow

But this looks like something dynamic analysis would easily resolve, that is, simply enter the correct Sudoku input and stop execution before the sub_4AF740 call (remembering to bypass the antidebugging):

$ gdb challenge
# ...
pwndbg> b *0x401794 # after _pthread_create()
Breakpoint 1 at 0x401794
pwndbg> b *0x4018ef # before calling sub_4AF740
Breakpoint 2 at 0x4018ef
pwndbg> r
# ...

Breakpoint 1, 0x0000000000401794 in ?? ()
# ...
 RAX  0xffffffffffffffff
# ...
pwndbg> set $rax=0 # neutralize antidebugging from _pthread_create()
pwndbg> c
Continuing.
Give me your key quickly or bad things will happen to you:
> 683254791915687243427913865598162437132479586764538912256891374349726158871345629
# ...

Thread 1 "challenge" hit Breakpoint 2, 0x00000000004018ef in ?? ()
# ...
pwndbg> dump binary memory patch.bin 0x4af740 0x4af8a9

from pwn import read, write

a = bytearray(read('./challenge'))
i = a.find(bytes.fromhex('F3 9E 36 D0 32 6F 65 95'))
a[i:i+(0x4af8a9-0x4af740)] = read('./patch.bin')
write('./challenge_patched', bytes(a))

It now looks much better!

unsigned __int64 __fastcall sub_4AF740(__int64 a1)
{
  int v1; // r8d
  int v2; // r9d
  __int64 v3; // rax
  int i; // edx
  __int64 v5; // rcx
  int v6; // ecx
  int v7; // r8d
  int v8; // r9d
  __int8 *v9; // rbx
  int j; // edx
  char *v11; // rbx
  int v12; // ecx
  int v13; // r8d
  int v14; // r9d
  int k; // edx
  unsigned __int64 result; // rax
  _OWORD v17[4]; // [rsp+0h] [rbp-D8h]
  _BYTE v18[32]; // [rsp+40h] [rbp-98h] BYREF
  __m128i si128; // [rsp+60h] [rbp-78h] BYREF
  _OWORD v20[4]; // [rsp+70h] [rbp-68h] BYREF
  char v21; // [rsp+B0h] [rbp-28h] BYREF
  unsigned __int64 v22; // [rsp+B8h] [rbp-20h]

  v22 = __readfsqword(0x28u);
  v17[0] = _mm_load_si128((const __m128i *)&xmmword_4B1190);
  v17[1] = _mm_load_si128((const __m128i *)&xmmword_4B11A0);
  si128 = _mm_load_si128((const __m128i *)&xmmword_4B11B0);
  v20[0] = _mm_load_si128((const __m128i *)&xmmword_4B11C0);
  v20[1] = _mm_load_si128((const __m128i *)&xmmword_4B11D0);
  v20[2] = _mm_load_si128((const __m128i *)&xmmword_4B11E0);
  v20[3] = _mm_load_si128((const __m128i *)&xmmword_4B11F0);
  sub_402110(a1, v18);
  v3 = 0;
  for ( i = 71; ; i = *((unsigned __int8 *)v17 + v3) )
  {
    LOBYTE(i) = v18[v3] ^ i;
    v5 = (int)v3++;
    *((_BYTE *)&v17[2] + v5) = i;
    if ( v3 == 32 )
      break;
  }
  _fprintf(1, (unsigned int)"\nGood job! Here is the flag: ", i, v5, v1, v2, v17[0]);
  v9 = &si128.m128i_i8[1];
  for ( j = 175; ; j = (unsigned __int8)*v9++ )
  {
    _fprintf(1, (unsigned int)"%02x", j, v6, v7, v8, v17[0]);
    if ( v9 == (__int8 *)v20 )
      break;
  }
  v11 = (char *)v20 + 1;
  /* 58 is ASCII for ':' */
  _putchar(58);
  for ( k = 135; ; k = (unsigned __int8)*v11++ )
  {
    _fprintf(1, (unsigned int)"%02x", k, v12, v13, v14, v17[0]);
    if ( v11 == &v21 )
      break;
  }
  _putchar(10);
  result = v22 - __readfsqword(0x28u);
  if ( result )
    sub_44FE10();
  return result;
}

Still a bit messy though, with the AVX stuff and byte-level manipulation. Just some cleanup:

void derive_flag(char *inp) {
  char x[32];
  char y[32];
  char z[32];
  char a[16];
  char b[64];
  /* canary setup */
  memcpy(x, xmmword_4B1190, 32);
  memcpy(a, xmmword_4B11B0, 16);
  memcpy(b, xmmword_4B11C0, 64);
  sub_402110(inp, z);
  for (int i = 0; i < 32; ++i) {
    y[i] = z[i] ^ x[i];
  }
  _fprintf(1, (unsigned int)"\nGood job! Here is the flag: ");
  for (int i = 0; i < 16; ++i) {
    _fprintf(1, (unsigned int)"%02x", a[i]);
  }
  _putchar(':');
  for (int i = 0; i < 64; ++i) {
    _fprintf(1, (unsigned int)"%02x", b[i]);
  }
  _putchar('\n');
  /* canary check */
}

And sub_402110:

__int64 __fastcall sub_402110(__int64 a1, _BYTE *a2)
{
  _BYTE *v3; // rdx
  int v5; // eax
  int v6; // r11d
  int v7; // r9d
  int v8; // r8d
  __int64 result; // rax
  char v10; // dl
  char v11; // bl
  char v12; // si
  char v13; // cl
  __int64 v14; // rsi

  v3 = a2;
  v5 = 49;
  do
  {
    *v3 = v5;
    v5 += 11;
    ++v3;
  }
  while ( (_BYTE)v5 != 0x91 );
  v6 = 0;
  v7 = 11;
  v8 = 3;
  result = 0;
  do
  {
    v10 = *(_BYTE *)(a1 + result);
    v11 = v6 ^ v10;
    v6 += 17;
    a2[result & 0x1F] = v11 + (v10 ^ a2[result & 0x1F]);
    v12 = v8;
    v8 += 7;
    a2[v12 & 0x1F] = (v10 + result) ^ __ROL1__(a2[v12 & 0x1F], 1);
    v13 = result++;
    v14 = v7 & 0x1F;
    v7 += 13;
    a2[v14] += __ROL1__(v10, v13 & 7);
  }
  while ( result != 81 );
  return result;
}

Just some cleanup:

void scramble(char *inp, char *out) {
  /* pow(11, -1, 256) * (0x91-49) % 256 = 32 */
  char x = 49;
  for (int i = 0; i < 32; ++i) {
    out[i] = x;
    x += 11;
  }
  char tmp = 0;
  char a = 0, b = 3, c = 11;
  for (int i = 0; i < 81; ++i) {
    char cur = inp[i];
    out[a] = (tmp ^ cur) + (cur ^ out[a]);
    out[b] = (cur + i) ^ rol(out[b], 1);
    out[c] = out[c] + rol(cur, i);
    tmp += 17;
    a = (a+1) % 0x20;
    b = (b+7) % 0x20;
    c = (c+13) % 0x20;
  }
}

Honestly, I don’t immediately clock a meaningful algorithm other than random deterministic scrambling that we can either run ourselves or retrieve the result dynamically.

Fitting back to the original “win” function, we could suppose this prevents directly retrieving y (or v17[2]) without solving the Sudoku.

However, perhaps perplexingly, y (or even z) is never actually printed to stdout. Let’s just see how it looks like, continuing from our earlier debugging session:

pwndbg> b *0x4af7f9
Breakpoint 3 at 0x4af7f9
pwndbg> c
# ...

Thread 1 "challenge" hit Breakpoint 3, 0x00000000004af7f9 in ?? ()
# ...
 ► 0x4af7f9    mov    esi, 0x4b1103     ESI => 0x4b1103 ◂— '\nGood job! Here is the flag: '
   0x4af7fe    mov    edi, 1            EDI => 1
   0x4af803    xor    eax, eax          EAX => 0
   0x4af805    call   0x44fd20                    <0x44fd20>
# ...
pwndbg> tele $rsp (4+2+1+4)*2
00:0000│ rsp 0x7fffffffdc50 ◂— 0xb6df00b86eba2547 # x
01:0008│-110 0x7fffffffdc58 ◂— 0x30d0e10d5ab3330d
02:0010│-108 0x7fffffffdc60 ◂— 0x11510877e6dee367
03:0018│-100 0x7fffffffdc68 ◂— 0xffd2bbeb5d4e0d71
04:0020│-0f8 0x7fffffffdc70 ◂— 0xfad4359b89c173fa # y
05:0028│-0f0 0x7fffffffdc78 ◂— 0xee434e8acce10d8c
06:0030│-0e8 0x7fffffffdc80 ◂— 0x98f4866b1012ad21
07:0038│-0e0 0x7fffffffdc88 ◂— 0x99c6fe5177360745
08:0040│ rdi 0x7fffffffdc90 ◂— 0x4c0b3523e77b56bd # z
09:0048│-0d0 0x7fffffffdc98 ◂— 0xde93af8796523e81
0a:0050│-0c8 0x7fffffffdca0 ◂— 0x89a58e1cf6cc4e46
0b:0058│-0c0 0x7fffffffdca8 ◂— 0x661445ba2a780a34
0c:0060│-0b8 0x7fffffffdcb0 ◂— 0x824645b34e6471af # a
0d:0068│-0b0 0x7fffffffdcb8 ◂— 0xac615fe3be96e123
0e:0070│-0a8 0x7fffffffdcc0 ◂— 0x62c0b7f6efbca887 # b
0f:0078│-0a0 0x7fffffffdcc8 ◂— 0xea2ffc072d5cd7b0
10:0080│-098 0x7fffffffdcd0 ◂— 0x7e16b1add0efca78
11:0088│-090 0x7fffffffdcd8 ◂— 0x55267963f7792c98
12:0090│-088 0x7fffffffdce0 ◂— 0x32bc05abc9d4d327
13:0098│-080 0x7fffffffdce8 ◂— 0x449c17962e8b4306
14:00a0│-078 0x7fffffffdcf0 ◂— 0xcc3923a9545da656
15:00a8│-070 0x7fffffffdcf8 ◂— 0xb54764b423349a7