← Back to Writeups
CUSTOMMediumReversing
Bookmark

First Mark

XESXOR9/10/20266 min read
#reversing#custom#medium#riscv_custom_insn_decode#rtype_field_decode#gf256_multiply_recognition#byte_rotation_inversion#xor_carry_feedback_inversion#witness_gate_reasoning

First Mark

Platform: CACTF2026 | Category: Reversing | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-07-27 | Status: Solved Techniques: riscv_custom_insn_decode, rtype_field_decode, gf256_multiply_recognition, byte_rotation_inversion, xor_carry_feedback_inversion, witness_gate_reasoning

Summary

Task: stripped bare-metal RISC-V (rv32i) firmware crackme that validates a 16-byte flag with four undocumented custom R-type instructions. Solution: manually decode the .insn opcodes, recognize the prime operand table as a GF(2^8) multiply and the permutation table as byte rotation, then invert the XOR-with-carry feedback stage and the two byte transforms to recover the input.

First Mark — CACTF2026 (HTB Cyber Apocalypse 2026)

Description

A lore-heavy narrative about "Veylen Marr" building a stone that "witnesses" the First Mark and answers "true, or nothing at all." The stone has FOUR undocumented instructions ("four runes ... left undocumented on purpose ... no key ... learn what those four runes do from the company they keep"). A partial key is given for the THIRD rune: "The third rune is not a plain XOR. Each round it computes out = a0 ^ state ^ carry, then updates the hidden carry as carry = old_a0 & state. The carry starts at 0, and the state starts at 0xA5 and becomes the rune's output each round." ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

English summary: We are given a stripped, statically-linked, bare-metal RISC-V 32-bit firmware ELF. It reads a 16-byte flag from a fixed buffer and validates each byte through four custom (non-standard) RISC-V instructions. Three of the four runes are undocumented; the narrative gives a partial spec of the third. Goal: reverse the four custom ops, invert the pipeline, and recover the 16-byte "First Mark", wrapped in HTB{...}.

Analysis

Recon

  • The download is a zip containing first-mark.elf.
  • file reports: ELF 32-bit LSB, UCB RISC-V (rv32i2p1_m2p0_zmmul1p0), soft-float, statically linked, stripped.
  • strings gives narrative anchors: the stone witnesses. it does not bargain. read the four marks or be cast out., ACCEPTED: The First Mark was cut in steel., keep your steel.
  • Standard objdump cannot target riscv32; use riscv64-unknown-elf-objdump -d -M no-aliases. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The verify loop (0x200000d0)

Bare-metal firmware: sp=0x80010000, input buffer at 0x80000000 (bss, externally provided 16-byte flag). The check function loops i = 0..15:

a0 = input[i]
a1 = tab1[i] & 7          ; RUNE_A operand
RUNE_A: a0 = f(a0,a1)     ; opcode 0x0b funct3=0 -> .insn 4, 0x00b5050b
a1 = tab2[i]              ; RUNE_B operand
RUNE_B: a0 = f(a0,a1)     ; opcode 0x0b funct3=1 -> .insn 4, 0x00b5150b
RUNE_C: a0 = f(a0,a2)     ; opcode 0x2b funct3=0, rs2=a2=state -> .insn 4, 0x00c5052b
a2 = a0                   ; state <- output
a3 = tab3[i]
RUNE_D: f(a0,a3)          ; opcode 0x2b funct3=1 funct7=1 rd=zero -> .insn 4, 0x02d5002b (witness/compare)

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

The custom instructions appear as .insn 4, 0x.... Manually decoding the R-type fields (opcode / rd / funct3 / rs1 / rs2 / funct7) tells which registers each rune consumes and produces. "ACCEPTED" is printed unconditionally in this firmware; rune D is the real gate — it traps / answers nothing on mismatch. So the pipeline A→B→C must reproduce tab3 byte-for-byte.

Data tables (.rodata)

  • tab1 @0x200001f4 = 03 07 01 05 02 06 04 00 (repeated) → after &7 a permutation of 0..7 (hint: rotate/shift amounts). → Rune A is a byte rotation.
  • tab2 @0x20000204 = 03 02 03 02 05 07 02 03 05 07 02 03 05 07 02 03 → only primes {2,3,5,7} ("the company they keep"). → Rune B is a GF(2^8) multiply.
  • tab3 @0x20000214 = 11 7a 35 90 7e 88 b0 59 79 7f 56 6a 3a 10 e9 05 → the expected outputs rune D checks against. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

  1. Invert rune C using the given spec. Forward: out = a0 ^ state ^ carry, carry_new = old_a0 & state, carry0 = 0, state0 = 0xA5, state <- out each round. Inverting per round recovers the value entering rune C (afterB): afterB[i] = tab3[i] ^ state[i] ^ carry[i], with state[0]=0xA5, state[i]=tab3[i-1], carry[0]=0, carry[i]=afterB[i-1] & state[i-1].
  2. Recover rune B — simple xor/add/sub/rol/ror for A and B yielded no printable input. Breakthrough: tab2 is all primes ⇒ B is gmul(a0, tab2[i]) in GF(2^8) with the AES polynomial 0x11b. Invert by multiplying by the GF-inverse of tab2[i].
  3. Recover rune A — out = ror8(a0, tab1[i] & 7). Invert by rol8.
  4. Applying gf_inverse-multiply then rol8 to afterB yields the clean, printable leetspeak 16-byte First Mark. Wrapping it in HTB{...} gives the flag. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solver (inversion + forward verification)

 python 
#!/usr/bin/env python3
# First Mark - CACTF2026 - RISC-V custom-instruction crackme solver

def gmul(a, b, poly=0x11b):
    r = 0
    for _ in range(8):
        if b & 1:
            r ^= a
        b >>= 1
        hi = a & 0x80
        a = (a << 1) & 0xff
        if hi:
            a ^= (poly & 0xff)
    return r

def gf_inv(x):
    if x == 0:
        return 0
    for y in range(256):
        if gmul(x, y) == 1:
            return y
    return 0
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def ror8(v, n):
    n &= 7
    return ((v >> n) | (v << (8 - n))) & 0xff

def rol8(v, n):
    n &= 7
    return ((v << n) | (v >> (8 - n))) & 0xff

tab1 = bytes([0x03,0x07,0x01,0x05,0x02,0x06,0x04,0x00] * 2)          # rotate amounts (&7)
tab2 = bytes([0x03,0x02,0x03,0x02,0x05,0x07,0x02,0x03,
              0x05,0x07,0x02,0x03,0x05,0x07,0x02,0x03])              # GF multipliers (primes)
tab3 = bytes([0x11,0x7a,0x35,0x90,0x7e,0x88,0xb0,0x59,
              0x79,0x7f,0x56,0x6a,0x3a,0x10,0xe9,0x05])              # expected rune-C outputs
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# --- invert rune C (the documented XOR-with-carry feedback) ---
afterB = [0] * 16
state = 0xA5
carry = 0
for i in range(16):
    afterB[i] = tab3[i] ^ state ^ carry
    carry = afterB[i] & state   # carry uses old_a0 (= afterB[i]) & state
    state = tab3[i]             # state becomes this round's rune-C output

# --- invert rune B (GF multiply) then rune A (rotate right) ---
recovered = bytearray(16)
for i in range(16):
    x = gmul(afterB[i], gf_inv(tab2[i]))   # undo rune B
    x = rol8(x, tab1[i] & 7)               # undo rune A (ror -> rol)
    recovered[i] = x
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# --- forward verification: does A->B->C reproduce tab3 exactly? ---
def forward(inp):
    out = []
    state = 0xA5
    carry = 0
    for i in range(16):
        x = ror8(inp[i], tab1[i] & 7)   # rune A: rotate RIGHT
        x = gmul(x, tab2[i])            # rune B: GF(2^8) multiply
        o = x ^ state ^ carry           # rune C
        carry = x & state
        state = o
        out.append(o)
    return bytes(out)

assert forward(recovered) == tab3, "forward mismatch"
# recovered is the 16-byte inner First Mark; flag = HTB{ + recovered + }
print("verified: A->B->C reproduces tab3 byte-for-byte")

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

The forward pass reproduces tab3 exactly, confirming the recovered 16 bytes. The leetspeak inner value reads "cut for the PINT", matching the "cut in steel" / "keep your steel" narrative. The final flag is that inner value wrapped in HTB{...}. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍