Destruction Set

Platform: spbctf | Category: Reversing | Type: Challenge | Difficulty: Medium | OS: Linux | Author: XESXOR | Date: 2026-07-02 | Status: Solved Techniques: aeskeygenassist_reimplementation, docker_amd64_verification, invertible_state_mixing, meet_in_the_middle

Summary

Task: stripped x86-64 PIE crackme reads an octal disarm code, derives an init hash via an AES-NI aeskeygenassist instruction and mixes octal digits with add/xor/rol. Solution: reimplement aeskeygenassist in Python, invert the per-digit mixing, and use meet-in-the-middle to recover the 15-octal-digit code REDACTED.

Destruction Set — spbctf

Description

Quick! There's a bomb in the building! ... What is its disarm code?

File: destruction_set.elf (https://rev-kids20.forkbomb.ru/files/rev/new8/destruction_set.elf)

A stripped x86-64 crackme asks for a "bomb disarm code". The answer is not a FLAG{...} string — it is the octal number the program accepts. The goal is to recover that number.

Analysis

file / strings -a recon:

• Stripped x86-64 LSB PIE ELF, dynamically linked, Debian GCC 8.2.0.
• Key strings:
  • Enter bomb disarm code
  • This task uses Intel AES instruction set ← AES-NI hint
  • BOOOOOOOOOOOOOOOM! The bomb didn't like too many button presses
  • The bomb is disarmed, Bruce Willis himself
  • --skipintro argv option
• Imports: scanf, strcmp, alarm, usleep, putchar, printf. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

objdump -d -M intel on the main routine (.text offset 0x1195) reveals the full algorithm:

1. Octal input. scanf("%llo", &input) reads the disarm code into [rbp-0x28]. The %llo specifier means the input is parsed as octal — this single detail defines the entire input encoding.

2. AES-NI key seed. Two 64-bit constants are loaded and stored as a 16-byte block at [rbp-0x40]:

   • r12 = 0xf9fcf2842e28f4d3 (low qword)
   • r13 = 0x68a3e428351d1ae5 (high qword)

3. aeskeygenassist. movdqa xmm0, [rbp-0x40] then aeskeygenassist xmm1, xmm0, 0x7 (RCON = 7), and movdqa [rbp-0x40], xmm1 writes the full 16-byte result back — both qwords are overwritten. This is the AES-NI key-schedule assist instruction, not full AES encryption. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

   Reimplemented result:

   • new low qword (rdx = [rbp-0x40]) = 0x5f99b08e99b0895f
   • new high qword (rax = [rbp-0x38]) = 0x34450a6e450a6934

4. init_hash. imul rax, rdx → 0x34450a6e450a6934 * 0x5f99b08e99b0895f (mod 2^64) = 0x0b74acbe98e9de4c, stored at [rbp-0x18].

5. Digit loop (LSB-first, at most 16 iterations; a 17th prints "BOOOOOM"):

   d = input & 7; input >>= 3        # extract next octal digit
   hash += 0x1234567890abcdef
   hash ^= d
   hash = rol(hash, 12)              # rol qword [rbp-0x18], 0xc
   # continue while remaining input != 0
   

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

1. Final check. hash == 0xf656656e1a2efc8e → "Yaaaay! Congrats! The bomb is disarmed".

Solution

Reimplement aeskeygenassist

aeskeygenassist(xmm, rcon) on little-endian dwords X0..X3 returns [ SubWord(X1), RotWord(SubWord(X1))^RCON, SubWord(X3), RotWord(SubWord(X3))^RCON ], where SubWord applies the AES S-box byte-wise and RotWord is a rotate-right-by-8 on each dword. Feeding the seed gives init_hash = 0x0b74acbe98e9de4c.

Invertible mixing → meet-in-the-middle

Each per-digit step is invertible: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

• forward: hash = rol((hash + K) ^ d, 12)
• inverse: hash = (ror(hash, 12) ^ d) - K, with K = 0x1234567890abcdef

A naive 8^n brute force (up to 16 octal digits) is too large. Since digits are freely 0..7, use meet-in-the-middle: for each candidate length n, apply the first a = n//2 (LSB) digits forward from init_hash into a dict keyed by mid-state, then reverse the target 0xf656656e1a2efc8e for the remaining b digits and match mid-states. A solution appears at n = 15. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
MASK = 0xFFFFFFFFFFFFFFFF
K = 0x1234567890abcdef
target = 0xf656656e1a2efc8e

# ---- aeskeygenassist (AES S-box omitted here for brevity) ----
def rotword(w): return ((w >> 8) | (w << 24)) & 0xFFFFFFFF
def subword(w): return (sbox[w&0xff] | (sbox[(w>>8)&0xff]<<8)
                        | (sbox[(w>>16)&0xff]<<16) | (sbox[(w>>24)&0xff]<<24))
def aeskeygenassist(xmm, rcon):
    X1 = (xmm >> 32) & 0xFFFFFFFF; X3 = (xmm >> 96) & 0xFFFFFFFF
    R0 = subword(X1); R1 = (rotword(subword(X1)) ^ rcon) & 0xFFFFFFFF
    R2 = subword(X3); R3 = (rotword(subword(X3)) ^ rcon) & 0xFFFFFFFF
    return R0 | (R1<<32) | (R2<<64) | (R3<<96)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

xmm0 = 0xf9fcf2842e28f4d3 | (0x68a3e428351d1ae5 << 64)
res  = aeskeygenassist(xmm0, 0x7)
init_hash = (((res >> 64) & MASK) * (res & MASK)) & MASK   # 0x0b74acbe98e9de4c

def rol(x, r): return ((x << r) | (x >> (64 - r))) & MASK
def ror(x, r): return ((x >> r) | (x << (64 - r))) & MASK
def forward_step(h, d): return rol(((h + K) & MASK) ^ d, 12)
def reverse_step(h, d): return ((ror(h, 12) ^ d) - K) & MASK

found = None
for n in range(1, 17):
    a, b = n // 2, n - n // 2
    fwd = {}
    def gen_fwd(h, depth, ds):
        if depth == a: fwd.setdefault(h, []).append(tuple(ds)); return
        for d in range(8): gen_fwd(forward_step(h, d), depth+1, ds+[d])
    gen_fwd(init_hash, 0, [])
    def gen_bwd(h, depth, ds):
        global found
        if depth == b:
            if h in fwd:
                for fds in fwd[h]:
                    found = list(ds) + list(fds)[::-1]   # MSB..LSB
            return
        for d in range(8): gen_bwd(reverse_step(h, d), depth+1, ds+[d])
    gen_bwd(target, 0, [])
    if found:
        print("n =", n); break
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

octal = ''.join(map(str, found))
print(octal, "->", int(octal, 8))   # REDACTED -> 19712717238203

Verification

• Python forward simulation of REDACTED (octal) from init_hash reaches exactly 0xf656656e1a2efc8e in 15 iterations.
• Ground truth on the real binary. The solve host is Apple Silicon (arm64) with no qemu-x86_64, so the x86-64 AES-NI binary was run via Docker --platform linux/amd64 on debian:bullseye-slim:

   bash read-only • copy allowed Copy
  printf 'REDACTED\n' | docker run --rm -i --platform linux/amd64 \
    -v "$PWD":/w -w /w debian:bullseye-slim ./destruction_set.elf --skipintro

  Output ended with: "Yaaaay! Congrats! The bomb is disarmed, Bruce Willis himself". ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍