IntMod — sunshinectf2026

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

English summary: an ELF64 binary reads up to 33 bytes on stdin and prints Correct or Nope. The title is a red herring — "IntMod" is not the C integer-modulus operator but modular arithmetic over the prime field GF(65521), and the real mechanic (revealed by the flag text) is Interrupts + Self-Modification: a VM whose instruction dispatch is a SIGTRAP handler. Goal: find the 33-byte input that yields Correct. Flag format sun{...}.

Analysis

Binary shape

• ELF64, non-PIE, stripped, dynamically linked, x86-64. md5 = 0169799f7f6f1309ebc1e50af8f59811.
• Input read one byte at a time via fgetc (stops on \n/EOF), capped at 33 bytes; argv ignored.
• Import list is the tell: alongside malloc/calloc/free/mmap/munmap/sysconf there are sigaction, sigaltstack, sigemptyset, sigaddset. Signal machinery in a "keygen"-style rev challenge is the key hint — the interpreter lives in a signal handler.

Data model

• The 33 input bytes get PKCS#7 padding (7 bytes of 0x07) to 40 bytes → five 64-bit registers = a 320-bit VM state.
• All arithmetic is over GF(65521) (0xfff1, a prime), implemented with Barrett reduction. This is what "IntMod" actually refers to.

Embedded encrypted program

• At .rodata 0x4055c0 sits a serialized "module" (ITM6 magic 0x364d5449): 203 instructions, 16 bytes each, layout op:u32, a, b, c, d (bytes), imm:u64.
• Encryption is XTEA (32 rounds, delta 0x9e3779b9) wrapped in CBC:
  • Key derived from header +0x1c (SHA-256 round constants).
  • IV derived from header +0x30 (Blowfish P-array / digits of π).
  • Per-instruction keystream tweak mixes wyhash const 0xa0761d6478bd642f and splitmix64 const 0xbf58476d1ce4e5b9. Decrypt/mix logic is spread across 0x401780 / 0x4014d0 / 0x401570 / 0x401ac0 / 0x401b50 / 0x401bf0.

Opcodes (8 total)

• id, add, xor, rol, swap, mul — the mixing set. All are invertible; mul requires an odd multiplier so it has a modular inverse mod 2^64.
• op5 = polynomial hash: H(state40, x) = Σ_{j=0..39} S[j]·x^j mod 65521 (Horner). It is linear in the state bytes.
• op6 = check: compares against a constant; mismatches are OR-ed into ctx[0x48]. The win function at 0x400dd0 returns 1 iff ctx[0x48] == 0.
• Return-status table at 0x408880: 0 ok, 1 invalid arg, 2 out of range, 3 invalid state, 4 unsupported, 5 system error, 6 integrity error.

The core obfuscation — an interrupt-driven self-modifying VM

• main runs validators V1..V7 that pass for any input. V2 (fcn.402690) mmaps an RWX arena; V7 (fcn.404040) installs SIGSEGV/SIGILL/SIGTRAP handlers on an alternate stack (sigaltstack). V8 (fcn.0x4042f0) is the real check.
• The VM runner at 0x4042f0 loads VM registers into r8..r12, executes an int3 at 0x404394, and the SIGTRAP handler executes each opcode by editing the ucontext. On return, code at 0x404395 syncs r8..r14 back into ctx via xmm registers.
• So int3 / SIGSEGV / SIGILL are the interpreter dispatch, not anti-debug decoration. That is precisely the meaning of the challenge and the flag: interrupts + self-modification.

Why standard tools fail (important guidance)

• angr: fault-based control flow plus HashMap-like structures aren't symbolic-friendly; exploration only reaches validator-failed states.
• gdb: software breakpoints are int3, which collide with the program's own int3 dispatch.
• qemu-user gdbstub: breaks guest signal delivery. Even handle SIGTRAP/SIGSEGV nostop pass kills the process, because the guest handler isn't effective under the stub. The exact same binary runs fine without a debugger.
• Lesson: when a debugger keeps breaking on the target's own signals, that is the loudest possible hint that the signals ARE the mechanic — instrument from inside the process instead.

Solution

The solve has four phases: instrument from inside → recover the 203-instruction program → solve the checks as linear algebra → run the program backward.

1. Instrument from inside via LD_PRELOAD inline hooks

A constructor mprotects a .text page RWX, writes a jmp rel32 at the hook site into a trampoline, and the trampoline logs then runs the stolen prologue and jumps back.

• Allocate the trampoline via mmap near 0x30000000 so a 32-bit rel32 reaches the (non-PIE, low) .text, and so it's outside brk/heap ASLR.
• Trampoline: save volatile regs → call a C logger → restore → execute the relocated stolen prologue → jmp back.
• Stack-alignment gotcha: hooks placed mid-function where rsp % 16 == 0 must manually build an aligned frame, otherwise glibc memcpy/memmove movaps will SIGSEGV:

  push rbp
  mov  rbp, rsp
  and  rsp, -16
  sub  rsp, 128
  ; ... call C logger ...
  mov  rsp, rbp
  pop  rbp

Three hook sites:

Site	What it captures	Notes
0x400ae0	step fn: 16-byte instruction + temp ctx	partial/unreliable ctx (~126 records)
0x400fa0	hash fn: 40-byte state buffer + base x	40 calls over a single finalized state
0x404415	before int3: the real 0x80-byte ctx	reliable trace: 171 executed instrs, pc 0..202, identical control flow across all inputs

Because control flow does not depend on the data, the 0x404415 trace is stable — data only changes the values, not the path.

2. Recover the 203-instruction program from state deltas

Run three different inputs, capture the ctx before each int3, and infer each opcode from the register transition:

• two registers exchanged → swap
• single reg a changed and new == rol(old, d) → rol
• new - old == rol(R[b], d) → add
• new ^ old == rol(R[b], d) → xor
• new == old * imm where imm = new * modinv(old, 2^64) and old is odd → mul
• nothing changed → id / hash / check

Collect candidate ops over the union of runs, then verify every candidate against all runs. This yields a unique program (counts e.g. id 81, add 18, xor 18, mul 18, rol 18, swap 18). Sanity: the forward model reproduces the final state, and the backward model reproduces the initial state, on all runs.

3. Solve the checks as a Vandermonde linear system over GF(65521)

The 40 op5/op6 pairs all hash the same finalized state (mixing is finished by then — confirmed by the 0x400fa0 log showing 40 calls over one buffer). Each pair is one linear equation over GF(65521):

Σ_{j=0..39} S[j] · x_i^j ≡ (imm_check_i + imm_hash_hi_i)  (mod 65521)

With 40 equations, 40 unknown state bytes, and pairwise-distinct bases x_i, the coefficient matrix is a Vandermonde matrix (non-singular). Gaussian elimination over GF(65521) recovers the 40-byte target state.

4. Run the recovered program backward

Run the 171-step program backward from the recovered target state to get the initial registers → the 40 state bytes; the first 33 are the flag. The 7-byte 0x07 PKCS#7 tail falls out correctly on its own (it is never constrained by any equation) — an independent confirmation of both the program model and the linear solve.

#!/usr/bin/env python3
# Solver skeleton (solution-only; flag output redacted).
# 1) Trace via LD_PRELOAD inline hooks -> per-step ctx before each int3, plus 40 hash bases.
# 2) Recover the invertible program from state deltas across >=3 runs.
# 3) Solve the polynomial-hash checks as a Vandermonde system over GF(65521).
# 4) Run the program backward from the target state to the input bytes.

P = 65521  # GF(65521), the real meaning of "IntMod"
MASK64 = (1 << 64) - 1

def rol(x, d):            return ((x << d) | (x >> (64 - d))) & MASK64
def ror(x, d):            return ((x >> d) | (x << (64 - d))) & MASK64
def modinv64(a):          # a must be odd; inverse mod 2^64
    inv = 1
    for _ in range(6):
        inv = (inv * (2 - a * inv)) & MASK64
    return inv

# ---- (2) infer one opcode from an observed register transition ----
def infer_op(old, new):
    diff = [i for i in range(5) if old[i] != new[i]]
    if not diff:
        return ("id",)                      # or hash/check (no state change)
    if len(diff) == 2:                       # swap
        i, j = diff
        if old[i] == new[j] and old[j] == new[i]:
            return ("swap", i, j)
    if len(diff) == 1:
        a = diff[0]
        for d in range(1, 64):
            if new[a] == rol(old[a], d):
                return ("rol", a, d)
        for b in range(5):
            for d in range(64):
                if (new[a] - old[a]) & MASK64 == rol(old[b], d):
                    return ("add", a, b, d)
                if (new[a] ^ old[a]) == rol(old[b], d):
                    return ("xor", a, b, d)
        if old[a] & 1:                       # mul needs odd multiplier
            return ("mul", a, (new[a] * modinv64(old[a])) & MASK64)
    raise ValueError("unresolved op")

# ---- (3) Gaussian elimination over GF(65521) on the Vandermonde system ----
def solve_gf(rows, rhs):
    n = len(rhs)
    M = [row[:] + [rhs[i]] for i, row in enumerate(rows)]
    for c in range(n):
        piv = next(r for r in range(c, n) if M[r][c] % P)
        M[c], M[piv] = M[piv], M[c]
        inv = pow(M[c][c], P - 2, P)
        M[c] = [(v * inv) % P for v in M[c]]
        for r in range(n):
            if r != c and M[r][c]:
                f = M[r][c]
                M[r] = [(M[r][k] - f * M[c][k]) % P for k in range(n + 1)]
    return [M[r][n] % P for r in range(n)]

# ---- (4) invert the program: run each opcode backward ----
def step_back(regs, ins):
    regs = regs[:]
    op = ins[0]
    if op == "swap":  i, j = ins[1], ins[2]; regs[i], regs[j] = regs[j], regs[i]
    elif op == "rol": a, d = ins[1], ins[2]; regs[a] = ror(regs[a], d)
    elif op == "add": a, b, d = ins[1], ins[2], ins[3]; regs[a] = (regs[a] - rol(regs[b], d)) & MASK64
    elif op == "xor": a, b, d = ins[1], ins[2], ins[3]; regs[a] ^= rol(regs[b], d)
    elif op == "mul": a, m = ins[1], ins[2]; regs[a] = (regs[a] * modinv64(m)) & MASK64
    # id/hash/check: no state change
    return regs

def recover_flag(program, target_regs):
    regs = target_regs[:]
    for ins in reversed(program):
        regs = step_back(regs, ins)
    state = b"".join(r.to_bytes(8, "little") for r in regs)   # 40 bytes
    flag  = state[:33]                                          # PKCS#7 tail = 7x 0x07
    assert state[33:] == b"\x07" * 7                            # independent check
    return flag  # -> feed to untouched binary; prints "Correct" (value redacted)

Key Indicators

Use this approach when:

• A stripped rev binary imports sigaction + sigaltstack + sigemptyset/sigaddset and you see int3 immediately followed by register-sync code — the SIGTRAP handler is the VM dispatcher, not anti-debug.
• gdb or qemu-user gdbstub die on the target's own SIGTRAP/SIGSEGV even with nostop pass, but the binary runs fine bare → stop debugging, instrument from inside with LD_PRELOAD inline-hook trampolines.
• You spot GF(65521) / modulus 0xfff1 with Barrett reduction — "int mod" wordplay pointing at a prime field, not the % operator.
• Crypto constants: XTEA delta 0x9e3779b9, splitmix64 0xbf58476d1ce4e5b9, wyhash 0xa0761d6478bd642f, SHA-256/Blowfish-P/π tables used as key & IV → an XTEA-CBC-wrapped embedded program.
• The final check is a polynomial hash Σ S[j]·x^j compared against constants at distinct bases → set up a Vandermonde system and solve with Gaussian elimination.
• Every mixing op is invertible (rol/swap/add/xor and odd-multiplier mul) → recover the program by op-inference from state deltas across a few runs, then run it backward from the solved target state.