Skip to content

ljagiello/ctf-skills / ctf-reverse

ctf-reverse

Flagged

Provides reverse engineering techniques for CTF challenges. Use when the main job is to understand how a compiled, obfuscated, packed, or virtualized target works before exploiting or solving it, including binaries, APKs, WASM, firmware, custom VMs, bytecode, game clients, malware-like loaders, and anti-debug or anti-analysis logic. Do not use it when the vulnerability is already understood and the remaining task is exploitation; use pwn instead. Do not use it for pure web workflows, log or disk forensics, or standalone crypto problems unless reversing the implementation is the real blocker.

FileKindSize
SKILL.mdskill md15.6 KB
anti-analysis-ctf.mdmarkdown10.7 KB
anti-analysis.mdmarkdown23.3 KB
field-notes.mdmarkdown31.9 KB
languages-compiled.mdmarkdown26.9 KB
languages-platforms.mdmarkdown28.3 KB
languages.mdmarkdown22.9 KB
mba-simplification.mdmarkdown4.5 KB
patterns-ctf-2.mdmarkdown18.8 KB
patterns-ctf-3.mdmarkdown37.9 KB
patterns-ctf.mdmarkdown30.0 KB
patterns-runtime.mdmarkdown12.0 KB
patterns.mdmarkdown19.9 KB
platforms-hardware.mdmarkdown15.9 KB
platforms.mdmarkdown22.5 KB
radare2-r2pipe.mdmarkdown17.1 KB
tools-advanced-2.mdmarkdown14.5 KB
tools-advanced.mdmarkdown12.1 KB
tools-dynamic.mdmarkdown25.4 KB
tools-emulation.mdmarkdown12.7 KB
tools-mcp.mdmarkdown42.7 KB
tools.mdmarkdown16.1 KB
unicorn-emulation.mdmarkdown48.3 KB

mba-simplification.md

View on GitHub
# CTF Reverse - MBA Simplification with msynth

## MBA Simplification with msynth

Mixed Boolean-Arithmetic (MBA) obfuscation rewrites simple operations (e.g. `x + y`) as tangled combinations of bitwise and arithmetic ops. Typical MBA shape in decompiler output:

```c
// MBA-obfuscated addition — spot the (x ^ y) + 2 * (x & y) pattern
out = (x ^ y) + 2 * (x & y);   // == x + y
```

**Key insight:** `(x ^ y) + 2*(x & y) == x + y` — the XOR carries the sum bits without carry, the AND-shifted term restores the carry. Detection heuristic: decompiler output mixing `^`, `&`, `|` with `+`, `*` and small constants (especially `* 2`) on the same variables is MBA until proven otherwise.

### Install

```bash
uv pip install "msynth @ git+https://github.com/mrphrazer/msynth.git" z3-solver
uv pip install "miasm @ git+https://github.com/cea-sec/miasm.git@1dc5fa9"
```

> Note: msynth is not on PyPI (`uv pip install msynth` fails with "not found in the package registry") — install from the git URL. Pin miasm to commit `1dc5fa9`: the PyPI miasm release imports the long-dead `imp` module and breaks on Python 3.12+. Smoke test: `python -c "from msynth import Simplifier, Synthesizer"`.

### Simplifier Path (Oracle Lookup)

The `Simplifier` looks up unified subexpressions in a precomputed oracle of I/O equivalence classes. The oracle is not shipped ready-made: the msynth checkout's `database/` directory holds a `3_variables_constants_7_nodes.txt.zip` expression table (1,293,020 combinations), and you build the oracle from it (10+ minutes) or fetch the precomputed `oracle.pickle` linked from the msynth README:

```bash
git clone https://github.com/mrphrazer/msynth.git
unzip -d msynth/database -q msynth/database/3_variables_constants_7_nodes.txt.zip
python msynth/scripts/gen_oracle.py msynth/database/3_variables_constants_7_nodes.txt oracle.pickle
```

```python
from pathlib import Path
from msynth import Simplifier, parse_infix_expr

simp = Simplifier(oracle_path=Path("oracle.pickle"))
out = simp.simplify(parse_infix_expr("(x ^ y) + 2*(x & y)"))
print(out)  # x + y
```
With `oracle_path=None` the oracle branch always misses and only SimBA rewriting applies — still useful for light MBA, but the oracle carries most of the load on hard inputs.

### Synthesizer Path (From-Scratch Search)

Without an oracle, `Synthesizer(use_smir=True).simplify` searches candidate rewrites from scratch via `iterated_local_search`. Slower (seconds to minutes per expression) and stochastic — a hard MBA ran 61 s unchanged in prior smoke testing, so budget time and retries:

```python
from msynth import Synthesizer, parse_infix_expr

orig = parse_infix_expr("(x ^ y) + 2*(x & y)")
out = Synthesizer(use_smir=True).simplify(orig, num_samples=10, timeout=60)
print(out)  # x + y (observed in 0.9 s on this input)
```

### Equivalence Check (Mandatory)

Never trust a simplifier blindly — synthesis is stochastic and a wrong "simplification" silently breaks the solve. Evaluate both sides on N random 64-bit inputs, assert equality, and treat any mismatch as synthesis failure (retry with a longer timeout or fall back to manual analysis):

```python
import random
import z3
from miasm.ir.translators.z3_ir import TranslatorZ3

def check_equivalent(a, b, n=2000, seed=0xC7F):
    """Random differential test over 64-bit inputs. Returns True iff all N agree."""
    rng = random.Random(seed)
    names = sorted({str(x) for x in a.get_r()} | {str(x) for x in b.get_r()})
    t = TranslatorZ3()
    za, zb = t.from_expr(a), t.from_expr(b)
    zvars = {v: z3.BitVec(v, 64) for v in names}
    for _ in range(n):
        sub = [(zvars[v], z3.BitVecVal(rng.getrandbits(64), 64)) for v in names]
        va = z3.simplify(z3.substitute(za, *sub)).as_long() & (1 << 64) - 1
        vb = z3.simplify(z3.substitute(zb, *sub)).as_long() & (1 << 64) - 1
        if va != vb:
            return False
    return True

assert check_equivalent(orig, out, n=2000), "synthesis failure: outputs differ"
```

### Miasm Integration

msynth expressions are miasm `Expr` objects, so results plug directly into miasm-based tooling such as `miasm/expression/simplifications.py` (`ExpressionSimplifier` / `expr_simp`) for further reduction or SMT-backed reasoning.

### Ecosystem Map

- msynth — <https://github.com/mrphrazer/msynth>
- GAMBA: "Automated MBA Deobfuscation" (<https://arxiv.org/abs/2209.06335>) and follow-up (<https://arxiv.org/abs/2305.06763>)
- SiMBA (simplifier inside msynth's default pipeline) and mba-blast/Arybo — consult only if citable for the target at hand
rea-analysis-optimizationmorluto/reaOptimize REA providers and shared analysis workflows for agent context, latency, CPU, and memory while preserving correctness and Evidence. Use for analysis bottlenecks and cache or query design; CI/test-suite optimization belongs to rea-ci-tests-audit.Stars: 472kUpdated Claude CodeCodexVerifiedInstall
rea-ci-tests-auditmorluto/reaAudit REA CI and test suites for correctness, fixture drift, false passes, and measured performance; use for suite or workflow investigations and efficiency changes, rather than ordinary feature testing or a single test failure.Stars: 472kUpdated Claude CodeCodexVerifiedInstall
rea-tool-designmorluto/reaAudit, investigate, design, or change REA investigation tools, CLI/MCP contracts, provider capabilities, and Evidence semantics.Stars: 472kUpdated Claude CodeCodexVerifiedInstall
ponytail-auditDietrichGebert/ponytailQuality audit of the whole repo: bugs, security, real load, missing tests, speed, and what to delete. Most important first.Stars: 194kUpdated Claude CodeCodexVerifiedInstall