HITCON CTF Quals 2017 - Seccomp

ELF x64 reversing challenge.

1. The main function

It is a small program. This program hides its core logic inside the seccomp syscall filter rule, and requires us to figure out the correct syscall arguments.

The filter rules stored at 0x201020 can be easily decoded using seccomp-tools. I have used bpftools for the decoding purpose, but outputs from seccomp-tools are more human-readable.

int __cdecl main(int argc, const char **argv, const char **envp)
{
  int result; // eax@7
  __int64 v4; // rcx@7
  signed int i; // [rsp+Ch] [rbp-54h]@1
  sock_fprog v6; // [rsp+10h] [rbp-50h]@1
  _QWORD v7[7]; // [rsp+20h] [rbp-40h]@1
  __int64 v8; // [rsp+58h] [rbp-8h]@1

  v8 = *MK_FP(__FS__, 40LL);
  v6.len = 4059;
  v6.filter = &filter_201020;
  memset(v7, 0, 0x30uLL);
  for ( i = 0; i <= 4; ++i )
    _isoc99_scanf("%llu", &v7[i]);
  prctl(PR_SET_NO_NEW_PRIVS, 1LL, 0LL, 0LL, 0LL);
  if ( prctl(PR_SET_SECCOMP, 2LL, &v6) )
  {
    perror("prctl");
    exit(1);
  }
  syscall(0x1337LL, v7[0], v7[1], v7[2], v7[3], v7[4], v7[5]);
  printf("Excellent! flag: hitcon{""%s""}\n", v7);
  result = 0;
  v4 = *MK_FP(__FS__, 40LL) ^ v8;
  return result;
}

2. Reverse the filter

The filter is 4000 lines long. I first skimmed through the instructions and discovered recurring patterns.

Below piece of code splits a 64-bit argument into four 16-bit integers and store them at M[0]..M[3]. Note that BPF has following 32-bit registers:

  • A: The most frequently used register.
  • X: Also frequently used register.
  • M[0] .. M[15]: Sixteen index-addressed registers, sometimes referred as “mem”.
 0003:  A = args[0]
 0004:  X = A
 0005:  A &= 0xffff
 0006:  mem[3] = A
 0007:  A = X
 0008:  A >>= 16
 0009:  mem[2] = A
 0010:  A = args[0] >> 32
 0011:  X = A
 0012:  A &= 0xffff
 0013:  mem[1] = A
 0014:  A = X
 0015:  A >>= 16
 0016:  mem[0] = A

This code calculates (M[0] * 0x6761) % 65537 with some edge case handling. With the edge cases removed, this operation is invertible.

 0017:  A = mem[0]
 0018:  if (A != 0) goto 0020
 0019:  A = 65536
 0020:  A *= 0x6761
 0021:  X = A
 0022:  A /= 0x10001
 0023:  A *= 0x10001
 0024:  A = -A
 0025:  A += X
 0026:  if (A != 65536) goto 0028
 0027:  A = 0
 0028:  mem[0] = A

And this code adds two 16-bit integers.

 0033:  A = mem[2]
 0034:  A += 0x5f65
 0035:  A &= 0xffff
 0036:  mem[2] = A

This is how resulting values are checked.

 0797:  X = 4919
 0798:  A = mem[3]
 0799:  A ^= X
 0800:  if (A == 2695) goto 0802
 0801:  return KILL
 0802:  A = mem[2]
 0803:  A ^= X
 0804:  if (A == 6003) goto 0806
 0805:  return KILL
 0806:  A = mem[1]
 0807:  A ^= X
 0808:  if (A == 45409) goto 0810
 0809:  return KILL
 0810:  A = mem[0]
 0811:  A ^= X
 0812:  if (A == 44702) goto 0814
 0813:  return KILL

There are a few more patterns such as register swap and XOR.

3. Simplify the filter

I simplified the filter program with a pattern matching algorithm.

import re

def get_opcode(code):
    if ' = ' in code: return 'mov'
    elif '+=' in code: return 'add'
    elif '&=' in code: return 'and'
    elif '^=' in code: return 'xor'
    elif '>>=' in code: return 'shr'
    elif '*=' in code: return 'mul'
    elif '/=' in code: return 'div'
    elif 'if' in code: return 'if'
    elif 'return' in code: return 'ret'
    else: return 'other'

all_lines = []
all_ops = []
content = open('disas').read()
content = re.sub('mem\[(\d)\]', 'M\\1', content)
for idx, line in enumerate(content.splitlines()):
    line = line[8:]
    op = get_opcode(line)
    all_lines.append(line)
    all_ops.append(op)
return all_lines, all_ops

idx = 0
irs = []
while idx < len(all_lines):
    lines = all_lines[idx:idx+20]
    ops = all_ops[idx:idx+20]

    if ops[:14] == 'mov mov and mov mov shr mov mov mov and mov mov shr mov'.split():
        irs.append(('INPUT',))
        idx += 14
    elif ops[:12] == 'mov if mov mul mov div mul mov add if mov mov'.split():
        src = lines[0].split()[-1]
        dst = lines[11].split()[0]
        num = int(lines[3].split()[-1], 16)
        irs.append(('MUL', dst, src, num))
        idx += 12
    elif ops[:5] == 'mov mov add and mov'.split():
        src1 = lines[0].split()[-1]
        src2 = lines[1].split()[-1]
        dst = lines[4].split()[0]
        irs.append(('ADDV', dst, src1, src2))
        idx += 5
    # (continued

This script produces following output.

// Repeat 5 times for each argument
    ('INPUT',)

    // Repeat 8 times with different numbers
        ('MUL', 'M0', 'M0', 26465)
        ('ADDC', 'M1', 'M1', 27750)
        ('ADDC', 'M2', 'M2', 24421)
        ('MUL', 'M3', 'M3', 27489)
        ('XORV', 'M4', 'M0', 'M2')
        ('XORV', 'M5', 'M1', 'M3')
        ('MUL', 'M4', 'M4', 26207)
        ('ADDV', 'M5', 'M4', 'M5')
        ('MUL', 'M5', 'M5', 24927)
        ('ADDV', 'M4', 'M4', 'M5')
        ('XORV', 'M0', 'M0', 'M5')
        ('XORV', 'M1', 'M1', 'M4')
        ('XORV', 'M2', 'M2', 'M5')
        ('XORV', 'M3', 'M3', 'M4')
        ('SWAP', 'M1', 'M2')

    ('MUL', 'M0', 'M0', 6551)
    ('ADDC', 'M1', 'M1', 55642)
    ('ADDC', 'M2', 'M2', 55385)
    ('MUL', 'M3', 'M3', 38872)
    ('CHECK', 4919, [2695, 6003, 45409, 44702])

4. Find the flag

The argument checking routine is an 8-round encryption. One round looks like this:

def mul(x, y):
    if x == 0: x = 65536
    x = (x * y) % 65537
    if x == 65536: x = 0
    return x
def add(x, y):
    return (x + y) & 0xffff

def forward(m, p):
    m0, m1, m2, m3 = m
    p0, p1, p2, p3, p4, p5 = p
    # p0..p6 are constant numbers appears in the code.

    # Step 1
    m0 = mul(m0, p0)
    m1 = add(m1, p1)
    m2 = add(m2, p2)
    m3 = mul(m3, p3)

    # Step 2
    m4 = m0 ^ m2
    m5 = m1 ^ m3

    # Step 3
    m4 = mul(m4, p4)
    m5 = add(m4, m5)
    m5 = mul(m5, p5)
    m4 = add(m4, m5)

    # Step 4
    m0 ^= m5
    m1 ^= m4
    m2 ^= m5
    m3 ^= m4

    # Step 5
    m1, m2 = m2, m1
    return (m0, m1, m2, m3)

It may look complicated because m4 and m5 are modified back and forth.

However, m0 ^ m2 after step 4 is equal to m0 ^ m2 after step 2, which is eventually equal to m4 after step 2. Similarly, we can find the m5 after step 2. Subsequently, we can write inverse round function.

def inv_mul(x, y):
    if x == 0: x = 65536
    x = (x * modinv(y, 65537)) % 65537
    if x == 65536: x = 0
    return x
def inv_add(x, y):
    return (x - y) & 0xffff

def backward(m, p):
    m0, m1, m2, m3 = m
    p0, p1, p2, p3, p4, p5 = p

    m1, m2 = m2, m1

    m4 = m0 ^ m2
    m5 = m1 ^ m3
    m4 = mul(m4, p4)
    m5 = add(m4, m5)
    m5 = mul(m5, p5)
    m4 = add(m4, m5)

    m0 ^= m5
    m1 ^= m4
    m2 ^= m5
    m3 ^= m4

    m0 = inv_mul(m0, p0)
    m1 = inv_add(m1, p1)
    m2 = inv_add(m2, p2)
    m3 = inv_mul(m3, p3)
    return (m0, m1, m2, m3)

Find the correct arguments args[0]..args[4] to get the flag.

hitcon{w0w_y0u_are_Master-0F-secc0mp///>_w_<///}

Other posts (list)


Building custom kernel
HITCON CTF Quals 2017 - Impeccable Artifact
HITCON CTF Quals 2017 - Seccomp
Cross compiling Linux ARM kernel modules