ReM3 Again

Platform: knightctf | Category: Reversing | Type: Challenge | Difficulty: Medium | OS: Linux | Author: XESXOR | Date: 2026-01-21 | Status: Solved Techniques: angr, data_extraction, static_analysis, symbolic_execution

Summary

Task: Reverse a bloated 500MB ELF binary with decoy checks and Fisher-Yates permutation-based transformation. Solution: Used angr symbolic execution with flag format constraints to find the correct input that passes the real check.

ReM3 Again — KnightCTF

Description

Reverse me again if you can...

Given an ELF 64-bit executable rem3_again.ks. File size is 524MB, but the actual code occupies only ~2KB (the rest is null bytes to hinder analysis).

Analysis

Initial Reconnaissance

 bash read-only • copy allowed Copy
$ file rem3_again.ks
rem3_again.ks: ELF 64-bit LSB executable, x86-64

$ ls -lh rem3_again.ks
-rwxr-xr-x 1 user user 500M Jan 20 04:44 rem3_again.ks

# Actual code size
$ objdump -h rem3_again.ks | grep -E "\.text|\.rodata"
  .text         00000800  ...
  .rodata       00000200  ...

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

Program Structure

Disassembly revealed the following key functions:

Main Logic

1. Reads user input (exactly 38 characters)
2. Generates permutation table via function p (seed: 0xf5a4ada5)
3. Performs 3 checks with chk_first using decoy data:
   • x_g0/g1/g2 — should return 0 (not equal)
   • x_f0/f1/f2 — should return 0 (not equal)
   • x_d0/d1/d2 — should return 0 (not equal)
4. Final check: eq(input, t(cat3(x_r0, x_r1, x_r2))) should return 1 ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

Function p — Permutation Generation

Uses Fisher-Yates shuffle algorithm with xorshift PRNG:

 c read-only • copy allowed Copy
void p(uint8_t* perm, uint32_t seed) {
    uint32_t state = seed;  // 0xf5a4ada5
    
    // Initialization
    for (int i = 0; i < 256; i++) {
        perm[i] = i;
    }
    
    // Fisher-Yates shuffle
    for (int i = 255; i > 0; i--) {
        // xorshift32
        state ^= state << 13;
        state ^= state >> 17;
        state ^= state << 5;
        
        int j = state % (i + 1);
        // swap
        uint8_t tmp = perm[i];
        perm[i] = perm[j];
        perm[j] = tmp;
    }
}

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

Function t — Transformation

Complex transformation using:

• XOR with constant 0x6a124de908b17733
• ROR (rotate right) operations
• Lookup table from permutation
• Feedback through state

Data in .rodata

x_d0, x_d1, x_d2  — decoy data
x_f0, x_f1, x_f2  — decoy data
x_g0, x_g1, x_g2  — decoy data
x_r0, x_r1, x_r2  — real flag data

Solution

Approach 1: Manual Implementation (Static Analysis)

1. Extract data x_r0, x_r1, x_r2 from .rodata section
2. Implement permutation generation function p
3. Implement transformation function t
4. Compute t(cat3(x_r0, x_r1, x_r2), inv_perm) to obtain the flag ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

Approach 2: Symbolic Execution (angr)

 python read-only • copy allowed Copy
import angr
import claripy

# Load binary
proj = angr.Project('./rem3_again.ks', auto_load_libs=False)

# Flag length is 0x26 = 38 characters
FLAG_LEN = 38

# Create symbolic input
flag = claripy.BVS('flag', FLAG_LEN * 8)

# Create initial state
state = proj.factory.entry_state(stdin=flag)

# Add constraints for printable ASCII
for i in range(FLAG_LEN):
    byte = flag.get_byte(i)
    state.solver.add(byte >= 0x20)
    state.solver.add(byte <= 0x7e)

# Add constraint for KCTF{ prefix
state.solver.add(flag.get_byte(0) == ord('K'))
state.solver.add(flag.get_byte(1) == ord('C'))
state.solver.add(flag.get_byte(2) == ord('T'))
state.solver.add(flag.get_byte(3) == ord('F'))
state.solver.add(flag.get_byte(4) == ord('{'))
state.solver.add(flag.get_byte(FLAG_LEN - 1) == ord('}'))
‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

# Create simulation manager
simgr = proj.factory.simulation_manager(state)

# Find address that prints "Success! Real flag accepted."
# Avoid address that prints "Failed!" or "Success! ...but you won't get points"
find_addr = 0x124e  # "Success! Real flag accepted."
avoid_addrs = [0x1229, 0x1177]  # "Failed!" and decoy success

print(f"[*] Starting exploration...")
simgr.explore(find=find_addr, avoid=avoid_addrs)

if simgr.found:
    found_state = simgr.found[0]
    solution = found_state.solver.eval(flag, cast_to=bytes)
    print(f"[+] Found flag: {solution.decode()}")
else:
    print("[-] No solution found")

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

Key Observations

1. Bloated binary — file is padded to 500MB with nulls to hinder loading in disassemblers
2. Decoy checks — three checks with fake data distract from the real check
3. Fisher-Yates + xorshift — deterministic permutation generation by seed
4. Fixed length — flag is exactly 38 characters (0x26)

References

• Fisher-Yates shuffle
• Xorshift PRNG
• angr documentation ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍