CTF Writeup: Intmod | RE | SunshineCTF 2026

Description

IntMod?? Do you mean integer modulus??

"No. I do not mean that."

"Then what, pretell, could it mean?"

"Just put the agent on the ghidra dawg"

Flag format: sun{flag_content}

We're given: intmod

---

Overview

intmod is a non-PIE x86-64 Linux ELF that reads a 33-byte line and runs it through a small custom virtual machine. The VM scrambles the input using 64-bit add, XOR, multiply, rotate and swap operations, then verifies the result with 40 polynomial-hash checks taken modulo 65521. Instead of brute-forcing, the plan is to turn those 40 checks into a linear system, solve it for the VM's final state, and then run every scrambling operation backwards to get the original input.

---

Solution

1. Find the input format in Ghidra

I opened intmod in Ghidra and let auto-analysis run. Since the binary is non-PIE, the addresses are stable:

Address	What it does
0x400470	Reads input with fgetc and validates it
0x401110	Copies the input into the VM state and pads it
0x400ae0	The VM instruction interpreter
0x400fa0	Polynomial hash
0x400e40	Subtraction modulo 65521

The program accepts exactly 0x21 = 33 bytes before the newline, copies them into a 40-byte state, and appends seven 0x07 padding bytes. The state is treated as five little-endian 64-bit words:

input[0:33] || 07 07 07 07 07 07 07

This matters: the flag is 33 bytes, but the VM works on 40. Solving for 40 arbitrary printable bytes gives the wrong model.

2. Understand a single VM instruction

Each decoded instruction record starts with 16 bytes that matter:

Offset	Size	Meaning
0	4	opcode
4	1	destination word d
5	1	source word a
6	1	check slot m
7	1	rotate count sh
8	8	immediate v

The interpreter at 0x400ae0 works on five 64-bit registers r[0..4], with all arithmetic wrapping modulo 2^64:

Opcode	Effect
0	r[d] = r[d] + rol64(r[a], sh)
1	r[d] = r[d] XOR rol64(r[a], sh)
2	r[d] = r[d] * v
3	r[d] = rol64(r[d], sh)
4	swap(r[d], r[a])
5	hash the 40 state bytes, subtract the high 32 bits of v mod 65521, store in check slot m
6	compare check slot m against v; a mismatch sticks
7	stop

One gotcha: opcode 5 writes to a separate check slot at state offset 0x28 + 8*m. It does not overwrite r[m]. Mixing those up makes the later hashes unsatisfiable.

3. Dump the decoded instructions with GDB

The VM program is built at runtime, so I captured it by breaking on the interpreter and reading the instruction pointer from RSI (second argument in the System V x86-64 calling convention).

First, a 33-byte probe line just to reach the VM:

printf 'sun{aaaaaaaaaaaaaaaaaaaaaaaaaaaa}\n' > probe.txt

Then capture.gdb:

set pagination off
python
import gdb
from pathlib import Path
records = []
class CaptureInstruction(gdb.Breakpoint):
    def stop(self):
        ptr = int(gdb.parse_and_eval('$rsi'))
        records.append(bytes(gdb.selected_inferior().read_memory(ptr, 16)))
        return False
CaptureInstruction('*0x400ae0')
end
run < probe.txt
python
Path('intmod_instructions.bin').write_bytes(b''.join(records))
print('captured', len(records), 'instruction records')
end

gdb -q -batch -x capture.gdb ./intmod

A good dump has 203 records (3248 bytes), with 40 opcode-5 records, 40 opcode-6 records, and opcode 7 as the last one. Quick sanity check on a few records:

index 0:   00000000000100070000000000000000
index 103: 050000000000000029270000b6d60000
index 202: 07000000000000000000000000000000

4. Turn the 40 checks into equations

The first opcode 5 is at record 103, and records 103 to 201 hold the 40 hash/check pairs. Reading 0x400fa0, the hash walks the state bytes from index 39 down to 0, which is just a polynomial evaluation. For base x and state bytes s[0..39]:

H_x(s) = (s[0] + s[1]*x + s[2]*x^2 + ... + s[39]*x^39) mod 65521

For an opcode-5 immediate v, the base is x = low32(v) and subtract = high32(v). The matching opcode-6 immediate is the wanted value, so each pair gives:

H_x(s) = (wanted + subtract) mod 65521

Worked example from record 103: v = 0x0000d6b600002729, so x = 10025 and subtract = 54966. Its check expects 33635, giving H_10025(s) = 23080. The first three equations come out as (10025, 23080), (22888, 61195), (23294, 13565).

A detail that tripped me up when scripting this: the 5s and 6s come in groups of three (5 5 5 6 6 6), so each opcode 6 has to be matched to its opcode 5 by check slot m, not simply by "the previous opcode 5".

5. Solve the linear system mod 65521

All 40 bases are distinct, so the 40 x 40 Vandermonde matrix is invertible over the field mod 65521. Row i is [1, x_i, x_i^2, ..., x_i^39 | target_i]. Gaussian elimination with every operation reduced mod 65521 works (use pow(p, -1, 65521) for pivot inverses). The solution column is the 40-byte VM state, and every value lands in 0 to 255:

6cafc8323d654776a8dd07eb9952338b9195bea30295dd826fa3c4066f926ed6f2df257bbf94a177

As five little-endian words:

r0 = 7647653d32c8af6c
r1 = 8b335299eb07dda8
r2 = 82dd9502a3be9591
r3 = d66e926f06c4a36f
r4 = 77a194bf7b25dff2

The wrinkle: some opcode-0 records have d = a = 0 and sh = 0. Read literally, that would double r0, and the 40 equations then become inconsistent. Treating those records as no-ops reproduces every check and recovers exactly the single state above. This is where the challenge name earns itself: the static decompilation alone doesn't show how the interrupt / self-modifying path treats these records at runtime, so I found the correct behavior by checking which interpretation keeps the system consistent.

6. Reverse the first 103 operations

Walking records 102 down to 0 and skipping the special no-op records, each opcode inverts cleanly:

Forward	Reverse
r[d] += rol64(r[a], sh)	r[d] -= rol64(r[a], sh) (when d != a)
r[d] ^= rol64(r[a], sh)	same XOR (when d != a)
r[d] *= v	r[d] *= inverse(v, 2^64)
r[d] = rol64(r[d], sh)	r[d] = ror64(r[d], sh)
swap(r[d], r[a])	swap again

The multiplication immediates are all odd, so each has an inverse mod 2^64, available as pow(v, -1, 1 << 64).

Here is the full solver I used, which reads the 16-byte records from intmod_instructions.bin:

import struct, sys

P = 65521
M = (1 << 64) - 1
rol = lambda x, n: ((x << n) | (x >> (64 - n))) & M if n % 64 else x
ror = lambda x, n: rol(x, (64 - n) % 64)

raw = open(sys.argv[1], 'rb').read()
recs = [raw[i:i + 16] for i in range(0, len(raw), 16)]
ins = []
for r in recs:
    op, d, a, m, sh = struct.unpack('<IBBBB', r[:8])
    v = struct.unpack('<Q', r[8:])[0]
    ins.append((op, d, a, m, sh, v))

# 1) Build the 40 hash equations (pair each opcode 6 with its opcode 5 by slot)
eqs, slots = [], {}
for op, d, a, m, sh, v in ins[103:]:
    if op == 5:
        slots[m] = (v & 0xffffffff, v >> 32)
    elif op == 6:
        x, sub = slots[m]
        eqs.append((x, (v + sub) % P))

# 2) Gaussian elimination mod P
n = 40
A = [[pow(x, j, P) for j in range(n)] + [t] for x, t in eqs]
for c in range(n):
    p = next(r for r in range(c, n) if A[r][c] % P)
    A[c], A[p] = A[p], A[c]
    inv = pow(A[c][c], -1, P)
    A[c] = [x * inv % P for x in A[c]]
    for r in range(n):
        if r != c and A[r][c]:
            f = A[r][c]
            A[r] = [(x - f * y) % P for x, y in zip(A[r], A[c])]
state = bytes(A[i][n] for i in range(n))

# 3) Undo the first 103 word operations
r = list(struct.unpack('<5Q', state))
for op, d, a, m, sh, v in reversed(ins[:103]):
    if op == 0 and d == a and sh == 0:
        continue  # special state-preserving record
    if op == 0:   r[d] = (r[d] - rol(r[a], sh)) & M
    elif op == 1: r[d] ^= rol(r[a], sh)
    elif op == 2: r[d] = r[d] * pow(v, -1, 1 << 64) & M
    elif op == 3: r[d] = ror(r[d], sh)
    elif op == 4: r[d], r[a] = r[a], r[d]

out = struct.pack('<5Q', *r)
print(out[:33].decode())  # drop the 7 padding bytes

Reversing all 103 records and serializing the words little-endian gives the original 40 bytes:

sun{I_L0v3_Int3rrupts&SelfMod!!!}\x07\x07\x07\x07\x07\x07\x07

Drop the seven 0x07 padding bytes and the first 33 bytes are the flag. As a final check, the flag can be fed straight to the binary on a Linux machine:

printf '%s\n' 'sun{I_L0v3_Int3rrupts&SelfMod!!!}' | ./intmod

---

Flag

sun{I_L0v3_Int3rrupts&SelfMod!!!}

---

Key Takeaways

• Know the real input model. The flag is 33 bytes but the VM runs on 40 (33 plus seven 0x07 padding bytes). Solving for 40 free bytes would have been the wrong problem.

• Hash checks can be linear equations. A polynomial hash modulo a prime is linear in the input bytes, so 40 checks with distinct bases form an invertible Vandermonde system. No brute force needed.

• Check slots are not registers. Opcode 5 writes to its own slot at offset 0x28 + 8*m, and confusing it with r[m] makes everything unsatisfiable.

• Decompiler output isn't the whole story. The "double r0" reading of the d = a = 0 records looks right in Ghidra but contradicts the embedded checks. When static analysis and the data disagree, trust the data and test both hypotheses.

• Invert every operation, not just the easy ones. Odd multipliers are invertible mod 2^64, rotates reverse with the opposite rotate, and swaps undo themselves.

• Capture, don't reimplement. Dumping the runtime-built instruction stream with a GDB breakpoint was far easier than reconstructing it statically.

---

Tools Used

Tool	Purpose
Ghidra	static analysis, function identification, and understanding the VM interpreter
GDB (with Python scripting)	capturing the 203 decoded VM instruction records at runtime
Python 3	modular Gaussian elimination, opcode reversal, and flag recovery