Translation

This post is also available in Simplified Chinese.

Notice

This article was originally published on Anquanke: original article

Introduction

With tremendous help from my teammates, we won the Rising Star division of the TCTF 2021 Finals. The challenge from which I learned the most was 0bf, a ten-round cipher hidden beneath extensive code obfuscation. The official post-event solution deobfuscated it first, but during the competition we lacked time to study the obfuscation pattern and had to analyze it directly. This was also my first use of Unicorn to emulate function logic.

Program Logic

Obfuscation inflated the function enormously, so first raise IDA’s function-size limit. Open IDA installation\cfg\hexrays.cfg, set MAX_FUNCSIZE to a large value, and reanalyze the encryption function sub_11C9. After Hex-Rays finishes several minutes later, copy the result into a file and reformat it to place each assignment on its own line. I uploaded the decompiled code.

VS Code’s minimap then makes the repeated regions obvious. For example, the function begins with:

1
2

  v2 = 12 * (*a1 & 0x4138B65C) + 8 * ~(*a1 & 0xBEC749A3) + (*a1 & 0xBEC749A3) + 1 - 6 * (*a1 ^ 0xBEC749A3) + 8 * ~*a1 + *a1 + 1 - 2 * (*a1 | 0xBEC749A3) - 4 * ~(*a1 | 0xBEC749A3) - 4 * ~(*a1 | 0x4138B65C) + 5 * (*a1 & 0xBEC749A3) + 1688020449;
  v3 = 2636545543LL * v1;

The second round begins with:

1
2

  v106 = 12 * (v103 & 0x70E38EE0) + 8 * ~(v103 & 0x8F1C711F) + (v103 & 0x8F1C711F) + 1 - 6 * (v103 ^ 0x8F1C711F) + 8 * ~v103 + v103 + 1 - 2 * (v103 | 0x8F1C711F) - 4 * ~(v103 | 0x8F1C711F) - 4 * ~(v103 | 0x70E38EE0) + 5 * (v103 & 0x8F1C711F) + 1583631427;
  v107 = 4225108746u * v105;

And the third with:

1
2

  v209 = 12 * (v206 & 0xEEE7AAAE) + 8 * ~(v206 & 0x11185551) + (v206 & 0x11185551) + 1 - 6 * (v206 ^ 0x11185551) + 8 * ~v206 + v206 + 1 - 2 * (v206 | 0x11185551) - 4 * ~(v206 | 0x11185551) - 4 * ~(v206 | 0xEEE7AAAE) + 5 * (v206 & 0x11185551) + 1862844314;
  v210 = 3734538576u * v208;

Following these patterns divides the encryption function into ten rounds, with two 32-bit values passed between rounds. Round one consumes the eight bytes at a1; round two takes v103 and v105 from round one, and so forth. The tenth round’s two results form the encrypted eight-byte block.

The first round has roughly this structure:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

  v1 = (unsigned int)a1[1];
  v2 = 12 * (*a1 & 0x4138B65C) + 8 * ~(*a1 & 0xBEC749A3) + ...;
  v3 = 2636545543LL * v1;
  if (2636545543LL * v1) {
    ...
    v10 = 6 * ~((HIDWORD(v9) - 1) | ~(_DWORD)v9 | 0x9D267E07) + 2 * (v9 & ((HIDWORD(v9) - 1) | 0x9D267E07)) - ...;
  } else {
    ...
    v10 = 4 * (~((v1 - 1) | 0x9D267E05) - 3 * ~((v1 - 1) | 0x62D981FA)) - ...;
  }
  v12 = 300216365LL * (21 * (v10 & ~v2 & 0xEE1B0FD2) + 10 * ~(v10 | ~v2 | 0xEE1B0FD2) + ...;
  if (v12) {
    v1222 = -4 * (-(__int64)HIDWORD(v12) ^ (unsigned int)v12);
    v1182 = 6 * (v12 | (HIDWORD(v12) - 1)) + 5 * (~(unsigned __int64)(unsigned int)v12 & (v12 | (HIDWORD(v12) - 1)) ^ -(__int64)HIDWORD(v12));
    ...
  } else {
    v20 = 2 * ~((21 * (v10 & ~v2 & 0xEE1B0FD2) + 10 * ~(v10 | ~v2 | 0xEE1B0FD2) + ....;
    v21 = v20 - (-(21 * (v10 & ~v2 & 0xEE1B0FD2) + 10 * ~(v10 | ~v2 | 0xEE1B0FD2) + ...;
    ...
  }
  ...
  v103 = 4 * (v2 & v93 & v101) - 21 * (v2 & v93 & ~(_DWORD)v101) + ...;
  v105 = 26 * (v10 & v101 & ~v97) + ((unsigned int)v101 & v10 | v97 ^ v101) + ...;

One round can therefore be summarized as follows:

  1. Briefly transform the inputs *a1 and a1[1] into v2 = s(*a1) and v10 = t(a1[1]), then compute v12 = r(v2, v10).

  2. All subsequent computation depends only on v12. After it is computed, later uses of v2 and v10 have exactly the same form as v12, namely 21 * (v10 & ~v2 & 0xEE1B0FD2) + ...; the expression is simply another representation of v12.

  3. Calling step two’s result f(v12), the two 32-bit outputs v103 and v105 are g(v2, f(v12)) and h(v10, f(v12)).

The exact operations performed by r, s, t, f, g, and h remain unknown.

Analysis

Without deobfuscation, treat each code segment as a black box and infer its logic by varying inputs and observing outputs.

Definitions for IDA macros such as _DWORD, LOWORD, and __CFADD__ are available in IDA installation\plugins\defs.h. To analyze s in v2 = s(*a1), convert the decompilation back into C:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "defs.h"

void f(unsigned int* a1) {
  unsigned int v2 = 12 * (*a1 & 0x4138B65C) + 8 * ~(*a1 & 0xBEC749A3) +
                    (*a1 & 0xBEC749A3) + 1 - 6 * (*a1 ^ 0xBEC749A3) + 8 * ~*a1 +
                    *a1 + 1 - 2 * (*a1 | 0xBEC749A3) - 4 * ~(*a1 | 0xBEC749A3) -
                    4 * ~(*a1 | 0x4138B65C) + 5 * (*a1 & 0xBEC749A3) +
                    1688020449;
  printf("%x %x\n", *a1, v2);
}

int main() {
  srand((unsigned)time(NULL));
  unsigned int a, x;
  for (a = 0; a < 256; a++) {
    x = a;
    f(&x);
  }
  for (a = 0; a < 256; a++) {
    x = rand();
    f(&x);
  }
  return 0;
}

Testing every input from 0 through 255 plus random values reveals s(x) = x + 0x6e62d8bf. Similar experiments establish r(x, y) = g(x, y) = h(x, y) = x ^ y and t(x) = (x*0x9d267e07-((x*0x9d267e07)>>32))&0xFFFFFFFF. The remaining function f is too complex to infer directly. A round is therefore:

1
2
3
4
5
6
7

Input: 32-bit values `a`, `b`
Output: 32-bit values `x`, `y`
v1=(a*C1-((a*C1)>>32))&0xFFFFFFFF
v2=b+C2
v3=v1^v2
x=v1^f(v3)
y=v2^f(v3)

Solution

Without deobfuscation, f is the only non-invertible component, but XOR can eliminate it. Given ciphertext x, y, choose v1'=x^y, v2'=0. Then v3'=x^y, x'=x^y^f(x^y), and y'=f(x^y). Thus the new ciphertext’s y' equals the original invocation’s f output; XORing y' with x and y recovers the original v1 and v2.

Next choose a'=0, b'=1, producing v1'=C1, v2'=C2. Together with the recovered v1 and v2, these constants reveal the original a and b. Decryption therefore requires no inverse of f.

Unicorn conveniently emulates selected code regions. The key is choosing suitable start and end points so the intervening black box depends on as little external state as possible.

The beginning of sub_11C9 is:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

.text:00000000000011C9                   ; __unwind {
.text:00000000000011C9 F3 0F 1E FA                       endbr64
.text:00000000000011CD 55                                push    rbp
.text:00000000000011CE 48 89 E5                          mov     rbp, rsp
.text:00000000000011D1 41 57                             push    r15
.text:00000000000011D3 41 56                             push    r14
.text:00000000000011D5 41 55                             push    r13
.text:00000000000011D7 41 54                             push    r12
.text:00000000000011D9 53                                push    rbx
.text:00000000000011DA 48 89 7D C0                       mov     [rbp+var_40], rdi
.text:00000000000011DE 48 8B 45 C0                       mov     rax, [rbp+var_40]
.text:00000000000011E2 8B 00                             mov     eax, [rax]
.text:00000000000011E4 41 89 C5                          mov     r13d, eax
.text:00000000000011E7 48 8B 45 C0                       mov     rax, [rbp+var_40]
.text:00000000000011EB 48 83 C0 04                       add     rax, 4
.text:00000000000011EF 8B 00                             mov     eax, [rax]
.text:00000000000011F1 41 89 C4                          mov     r12d, eax
.text:00000000000011F4 B8 A3 49 C7 BE                    mov     eax, 0BEC749A3h
.text:00000000000011F9 4C 31 E8                          xor     rax, r13
.text:00000000000011FC 48 89 C2                          mov     rdx, rax
.text:00000000000011FF 48 89 D0                          mov     rax, rdx
.text:0000000000001202 48 C1 E2 02                       shl     rdx, 2
.text:0000000000001206 48 29 D0                          sub     rax, rdx
.text:0000000000001209 48 01 C0                          add     rax, rax
.text:000000000000120C 48 89 C1                          mov     rcx, rax
.text:000000000000120F 4C 89 E8                          mov     rax, r13

Use 0x11F4 as the emulation start, where r12 and r13 hold the first-round inputs. The round ends at 0xF7AD, with its results again in r12 and r13. We must also control v3 and inspect v1 and v2, so choose 0x241A as an intermediate point where r12 and r13 contain those values:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void solve(uint64_t start,
           uint64_t middle,
           uint64_t end,
           uint64_t x,
           uint64_t y,
           uint64_t* ox,
           uint64_t* oy) {
  uint64_t z, w, s, t;
  uint32_t a, b;
  do_emulation(binary, start, middle, 1, 0, &s, &t);
  do_emulation(binary, middle, end, x ^ y, 0, &z, &w);
  printf("z=%lx w=%lx s=%lx t=%lx\n", z, w, s, t);
  b = (w ^ y) - t;
  uint64_t m, n;
  assert(exgcd(0x100000001, s, &m, &n) == 1);
  a = ((x ^ w) * n) % 0x100000001;
  if (n & (1UL << 63)) {
    a -= 1;
  }
  printf("n=%lx a=%x b=%x\n", n, a, b);
  *ox = a;
  *oy = b;
}

do_emulation executes a code region with Unicorn. First start with a=1, b=0 and run to the midpoint; the analysis predicts r12=C2, r13=C1, saved as s and t. Then begin at the midpoint with v1=x^y, v2=0 and run to the end, producing r12=x^y^f(x^y), r13=f(x^y), saved as z and w. Recover the original values with v1=w^x, v2=w^y, then compute b=v2-C2 and a=(v1*n)%0x100000001, where n is the multiplicative inverse of C1 modulo 0x100000001.

Using Unicorn

Here is the implementation of do_emulation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

void do_emulation(FILE* fp,
                  uint64_t start,
                  uint64_t end,
                  uint64_t r12,
                  uint64_t r13,
                  uint64_t* x,
                  uint64_t* y) {
  uc_engine* uc;
  uint64_t size = end - start;
  uint64_t rsp = 0x280000, rbp = 0x2c0000;

  assert(uc_open(UC_ARCH_X86, UC_MODE_64, &uc) == UC_ERR_OK);
  assert(uc_mem_map(uc, 0x1000, 0x100000, UC_PROT_ALL) == UC_ERR_OK);
  assert(uc_mem_map(uc, 0x200000, 0x100000, UC_PROT_ALL) == UC_ERR_OK);
  assert(fseek(fp, start, SEEK_SET) == 0);
  assert(fread(buf, size, 1, fp) == 1);
  assert(uc_mem_write(uc, start, buf, size) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_RSP, &rsp) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_RBP, &rbp) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_R12, &r12) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_R13, &r13) == UC_ERR_OK);
  assert(uc_emu_start(uc, start, end, 0, 0) == UC_ERR_OK);
  assert(uc_reg_read(uc, UC_X86_REG_R12, x) == UC_ERR_OK);
  assert(uc_reg_read(uc, UC_X86_REG_R13, y) == UC_ERR_OK);
  uc_close(uc);
}

The challenge is PIE. To avoid relocation, map .text directly at 0x1000, allocate an empty stack, point rsp and rbp into it, load the inputs into r12 and r13, and call uc_emu_start.

Download and build Unicorn. Avoid installing self-built software into system directories with make install, where it may conflict with existing packages. Many online OpenSSL guides install directly into /usr/lib, causing system programs to load an incompatible libssl and fail.

Static linking with a local include path makes self-built third-party libraries easy to use without polluting the environment, especially for one-off programs. Link Unicorn with:

1

gcc solve.c -I /xxx/download/unicorn/include/ /xxx/download/unicorn/libunicorn.a -lm -lpthread

-I selects the header search directory. Pass libunicorn.a directly to the linker, then add libm and libpthread to produce a standalone emulator.

The complete code follows:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#include <unicorn/unicorn.h>

unsigned char buf[0x100000];
FILE* binary;

uint64_t exgcd(uint64_t a, uint64_t b, uint64_t* x, uint64_t* y) {
  if (b == 0) {
    *x = 1;
    *y = 0;
    return a;
  }
  uint64_t r = exgcd(b, a % b, x, y);
  uint64_t t = *y;
  *y = *x - (a / b) * (*y);
  *x = t;
  return r;
}

void do_emulation(FILE* fp,
                  uint64_t start,
                  uint64_t end,
                  uint64_t r12,
                  uint64_t r13,
                  uint64_t* x,
                  uint64_t* y) {
  uc_engine* uc;
  uint64_t size = end - start;
  uint64_t rsp = 0x280000, rbp = 0x2c0000;

  assert(uc_open(UC_ARCH_X86, UC_MODE_64, &uc) == UC_ERR_OK);
  assert(uc_mem_map(uc, 0x1000, 0x100000, UC_PROT_ALL) == UC_ERR_OK);
  assert(uc_mem_map(uc, 0x200000, 0x100000, UC_PROT_ALL) == UC_ERR_OK);
  assert(fseek(fp, start, SEEK_SET) == 0);
  assert(fread(buf, size, 1, fp) == 1);
  assert(uc_mem_write(uc, start, buf, size) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_RSP, &rsp) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_RBP, &rbp) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_R12, &r12) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_R13, &r13) == UC_ERR_OK);
  assert(uc_emu_start(uc, start, end, 0, 0) == UC_ERR_OK);
  assert(uc_reg_read(uc, UC_X86_REG_R12, x) == UC_ERR_OK);
  assert(uc_reg_read(uc, UC_X86_REG_R13, y) == UC_ERR_OK);
  uc_close(uc);
}

void solve(uint64_t start,
           uint64_t middle,
           uint64_t end,
           uint64_t x,
           uint64_t y,
           uint64_t* ox,
           uint64_t* oy) {
  uint64_t z, w, s, t;
  uint32_t a, b;
  do_emulation(binary, middle, end, x ^ y, 0, &z, &w);
  do_emulation(binary, start, middle, 1, 0, &s, &t);
  printf("z=%lx w=%lx s=%lx t=%lx\n", z, w, s, t);
  b = (w ^ y) - t;
  uint64_t m, n;
  assert(exgcd(0x100000001, s, &m, &n) == 1);
  a = ((x ^ w) * n) % 0x100000001;
  if (n & (1UL << 63)) {
    a -= 1;
  }
  printf("n=%lx a=%x b=%x\n", n, a, b);
  *ox = a;
  *oy = b;
}

void decrypt(uint32_t xx, uint32_t yy, uint32_t* a, uint32_t* b) {
  uint64_t x = xx, y = yy;
  solve(0x83A25, 0x84C19, 0x92756, x, y, &x, &y);
  solve(0x75467, 0x76695, 0x83A25, x, y, &x, &y);
  solve(0x66ED9, 0x680D2, 0x75467, x, y, &x, &y);
  solve(0x58191, 0x5938A, 0x66ED9, x, y, &x, &y);
  solve(0x4949C, 0x4A68D, 0x58191, x, y, &x, &y);
  solve(0x3AF70, 0x3C19B, 0x4949C, x, y, &x, &y);
  solve(0x2CA30, 0x2DC24, 0x3AF70, x, y, &x, &y);
  solve(0x1E4DE, 0x1F70E, 0x2CA30, x, y, &x, &y);
  solve(0xF7AD, 0x109DB, 0x1E4DE, x, y, &x, &y);
  solve(0x11F4, 0x241A, 0xF7AD, x, y, &x, &y);
  *a = x;
  *b = y;
}

int main() {
  uint32_t x[] = {0xc94dac3e, 0xb2d4f81d, 0xd9c808c2, 0x483a21f1,
                  0x4e9d5687, 0xa3c64916, 0xa7459ba4, 0x6ff8306e};
  uint32_t *a, *b;
  char plain[33];
  int i;
  assert((binary = fopen("./chall", "rb")) != NULL);
  for (i = 0; i < 4; i++) {
    a = (uint32_t*)(plain + 8 * i + 4);
    b = (uint32_t*)(plain + 8 * i);
    decrypt(x[i * 2 + 1], x[i * 2], a, b);
  }
  fclose(binary);
  plain[32] = '\0';
  printf("flag{%s}\n", plain);
  return 0;
}

flag: flag{0o0..MBA_0bF_1s_S0_1ntEresT1ng!!}

Conclusion

Because I did not understand deobfuscation, this challenge required considerable effort. In the end, the XOR structure let us cleverly reuse the existing binary code. I still need to broaden my knowledge and learn proper deobfuscation techniques.