Kumbhakarna: The Machine Beneath Lanka

By Team Cryptonite · 4 min read

About the CTF: Pinaka CTF

kumbha is a stripped x86-64 binary that turns out to be a tiny 24-bit virtual machine with its ROM embedded in the ELF. The validator wants four 24-bit input words (the "invocation") and the resulting TAG. Rather…

Kumbhakarna: The Machine Beneath Lanka

**Pinaka CTF 2026** · Reverse engineering · Team Cryptonite · All 44 Pinaka write-ups

Category: reverse engineering

Flag: PINAKA{kumbhakarnawakeswheny0umodelthemachinenotbrute_it}

Overview

kumbha is a stripped x86-64 binary that turns out to be a tiny 24-bit virtual machine with its ROM embedded in the ELF. The validator wants four 24-bit input words (the "invocation") and the resulting TAG. Rather than brute-forcing, the check can be run backwards.

Files:

Each trace lists the invocation, the result (DORMANT), the final tag, and the PC/R0 pair for every step. They act as an oracle: any VM model that doesn't reproduce them is wrong.

Analysis

Finding the ROM. The binary copies 0x410 bytes from .rodata offset 0x2200 into a VM struct in BSS at 0x4080. That's 260 little-endian dwords, one per ROM word:


import struct
b = open("kumbha", "rb").read()
rom = list(struct.unpack("<260I", b[0x2200:0x2200+0x410]))

rom.bin is the same data as 3-byte big-endian values. The interesting words:


ROM[0x000] = 0x3c0400
ROM[0x001] = 0x00000e
ROM[0x008] = 0x088400    # interrupt service routine
ROM[0x100] = 0xc3b014    # encrypted multiplier 0
ROM[0x101] = 0xa0b682
ROM[0x102] = 0x16ea82
ROM[0x103] = 0xfea221
ROM[0x048] = 0x6e1a93    # comparison constant 0
ROM[0x05e] = 0x69ad85    # comparison constant 1
ROM[0x074] = 0x387eda    # comparison constant 2
ROM[0x08a] = 0xa30740    # comparison constant 3

the memcpy of 0x410 bytes from .rodata 0x2200 into the VM struct

VM architecture:

I/O ports used by this ROM:

Instruction encoding. A 24-bit word w decodes as:


op = (w >> 18) & 0x3f   # 6-bit opcode
A  = (w >> 15) & 7      # destination / first register
B  = (w >> 12) & 7      # source / second register
f  = (w >> 10) & 3      # immediate mode
r9 = w & 0x3ff          # 10-bit immediate or small offset

If f != 0, the next ROM word is a 24-bit immediate. The next-PC rule that matches the binary is nxt = pc + 2 + (1 if (w & 0x800) else 0).

Opcodes that matter:

Two of these aren't what they look like:


s = a + b
carry = s >> 24
r = ((s & 0xffffff) + carry) & 0xffffff

the shift-and-reduce loop at 0x15C0 with the 0x100001B reduction

Boot and DMA. Boot code programs a four-word DMA (source = ROM[0x100], destination = 0x10, length = 4, seed = 0xC0DE). The DMA decrypts each word with the same LCG constants used elsewhere:


seed = (seed * 0x19660D + 0x3C6EF3) & 0xffffff
word = ROM[src + i] ^ seed

Decrypting ROM[0x100..0x103] gives the four multipliers 0x0F1E2D, 0x3C4B5A, 0x678869, 0xA5B4C3. DMA completion raises the interrupt, which runs the ISR at ROM[0x08] and starts the main check.

The four-block check. The main routine reads four 24-bit input words from port 0x40 and starts with R0 = 0x4B554D ("KUM"). Then it runs four identical blocks. For block i:

  1. R0 = R0 + input[i] with end-around carry.
  2. R0 = R0 * mem[0x10 + i] in GF(2^24), polynomial 0x100001B.
  3. R0 = R0 ^ lcg_i.
  4. R7 = R7 | (R0 ^ const_i).

The LCG starts at 0x9A1337 and steps with state = state * 0x19660D + 0x3C6EF3 mod 2^24, giving the per-block values 0x1652BE, 0xE45699, 0x46CAB8, 0x920A4B. The comparison constants are 0x6E1A93, 0x69AD85, 0x387EDA, 0xA30740.

The ROM signals AWAKE only when R7 == 0, so every block must finish with R0 == const_i. That makes the four equations independent once R0 is carried forward.

the four-block loop in the ROM disassembly or an annotated emulator trace

Solution

Work each block backwards:


target = const_i ^ lcg_i
q      = target * inverse(mem[i])     in GF(2^24)
input  = q - R0                       modulo 2^24 - 1

R0 for the next block is const_i. The GF inverse is a^(2^24 - 2), and subtraction undoes end-around-carry addition. Because the addition is mod 2^24 - 1, b = (q - R0) mod (2^24 - 1) is unique in range, with the usual edge case at 0 / 0xFFFFFF.

Worked values as target -> q -> input:

The solver doesn't need the emulator:


M = 0xffffff
POLY = 0x100001b

def gfmul(a, b):
    a &= M
    b &= M
    r = 0
    for _ in range(24):
        if b & 1:
            r ^= a
        b >>= 1
        a <<= 1
        if a & 0x1000000:
            a ^= POLY
    return r & M

def gfpow(a, e):
    r = 1
    while e:
        if e & 1:
            r = gfmul(r, a)
        a = gfmul(a, a)
        e >>= 1
    return r

def gfinv(a):
    return gfpow(a, (1 << 24) - 2)

def add(a, b):
    s = a + b
    carry = s >> 24
    return ((s & M) + carry) & M

def sub_inv(r, a):
    # find b with add(a, b) == r
    for b in ((r - a) % M, (r - a - 1) % M, (r - a + 1) % M):
        b &= M
        if add(a, b) == r:
            return b
    return None

mem = [0x0f1e2d, 0x3c4b5a, 0x678869, 0xa5b4c3]

lcg = []
s = 0x9a1337
for _ in range(4):
    s = (s * 0x19660d + 0x3c6ef3) & M
    lcg.append(s)

const = [0x6e1a93, 0x69ad85, 0x387eda, 0xa30740]

R0 = 0x4b554d
inputs = []
for i in range(4):
    target = const[i] ^ lcg[i]
    q = gfmul(target, gfinv(mem[i]))
    inp = sub_inv(q, R0)
    inputs.append(inp)
    print(i, hex(inp))
    R0 = const[i]

print(" ".join("%06X" % x for x in inputs))


0x574b31
0x4e6752
0x41533a
0x6f6d21
574B31 4E6752 41533A 6F6D21

The TAG is a cycle hash over the machine state, so rather than reproduce it in a custom emulator, run the real binary on the recovered input (on macOS, via Docker):


docker run --rm --platform linux/amd64 \
  -v "$PWD":/w -w /w ubuntu:24.04 \
  sh -c './kumbha 574B31 4E6752 41533A 6F6D21'


AWAKE
TAG d1ddfd42

Submission


curl -s -X POST https://pinaka-kumbhakarna-validator.onrender.com/verify \
  -H 'Content-Type: application/json' \
  -d '{"invocation":"574B31 4E6752 41533A 6F6D21","tag":"d1ddfd42"}'


{"flag":"PINAKA{kumbhakarna_wakes_when_y0u_model_the_machine_not_brute_it}","message":"Kumbhakarna stirs. The machine beneath Lanka awakens.","ok":true}

Notes

Read this post on CyberHx →