Obfuscated State Machine Explained: When Your Verifier Turns Into a Maze

Imagine entering the correct secret, only for the program to refuse to compare it directly. Instead, it turns every character into bits, sends those bits through hundreds of junctions, changes the rules at some of them, and occasionally asks you to satisfy a 256-bit arithmetic equation.

That is roughly what some custom binary verifiers are doing.

From the outside, the program looks harmless. It reads input and prints Success or Failed. Internally, it can be a large state machine hidden behind dozens or hundreds of handlers, dictionary lookups, lazy initialization, and extra arithmetic constraints designed to make brute force miserable.

This article walks through the whole process: finding the states, rebuilding the transition graph, dealing with mutable dictionaries, handling BigInt constraints, and turning the solved path back into input.

What Is an Obfuscated State Machine, Anyway?

A normal state machine is simple:

State A + input 0 -> State B
State A + input 1 -> State C

You know the current state, read the input, and follow the matching edge.

An obfuscated verifier does the same thing while hiding the pieces behind runtime machinery.

Instead of:

if (input[i] == 'A')
    state = 12;
else
    state = 57;

you may get something more like:

input bytes
   ↓
bit string
   ↓
2-bit chunk
   ↓
AA lookup
   ↓
dispatcher
   ↓
next handler
   ↓
state update
   ↓
another handler

The program is no longer telling you “the answer is X.” It is effectively saying, “prove that your input can walk through my entire machine.”

The core idea

A common pattern uses a result array whose entries start with a sentinel such as:

0xffffffff

Each handler updates the corresponding slot when that state is reached.

At the end, the verifier inspects the array to determine whether the required states were visited.

That gives you a very useful reverse engineering clue: instead of searching for a hidden secret, look for the place where state visitation is recorded.

Why Should You Care?

This design changes the reverse engineering strategy completely.

• Hunting for strcmp may get you nowhere.
• Searching .rdata for a complete secret may find nothing.
• The visible branches may be correct while their key ordering is hidden in runtime data.
• A Success! string does not imply that a matching secret string exists.
• Some states may impose arithmetic constraints before allowing the next transition.

In other words, you are not trying to “find the secret.” You are reconstructing the rules that decide which input can traverse the verifier successfully.

Worked Example: Turning a Hostile Binary Into a Graph

Suppose our synthetic verifier contains 224 states.

Each handler has a prologue resembling:

cmp dword ptr [result_array + index*4], 0xffffffff

That index matters. Once you identify the result array and the index used by each handler, you can map functions to states.

1. Locate the result array

Start by looking for repeated comparisons against:

0xffffffff

Once the result array is located, entries such as:

[result_array + 0*4]
[result_array + 1*4]
[result_array + 2*4]
...

can be interpreted as:

State 0
State 1
State 2
...

That one step turns hundreds of anonymous functions into named graph nodes.

2. Map every state to its handler

With the array address known, look for instructions such as:

cmp dword ptr [rip+disp32], 0xffffffff

Resolve the RIP-relative displacement and check whether the target lands inside the result array.

If it does:

slot = (target - array_va) // 4

You can build a mapping like:

slot 0   -> handler_0
slot 1   -> handler_1
slot 2   -> handler_2
...
slot 223 -> handler_223

Now you have a state inventory.

3. Discover the input alphabet

The verifier may not consume bytes directly.

A common design converts the input into a bit string and then consumes small chunks. With 2-bit chunks, the alphabet becomes:

00
01
10
11

A state may therefore have up to four possible outgoing transitions:

State 17
 ├── 00 -> State 81
 ├── 01 -> State 9
 ├── 10 -> State 143
 └── 11 -> State 52

There is, however, a nasty trap.

The Dictionary Trap

The 2-bit values are not necessarily tied to the same key forever.

The program may use an AA or dictionary lookup and replace the mapping while it runs.

For example, the initial mapping could be:

0 -> 00
1 -> 01
2 -> 10
3 -> 11

Later, another state may load:

0 -> 10
1 -> 11
2 -> 00
3 -> 01

If you assign transition numbers according to branch order in the disassembly, you can build a perfectly plausible graph that is completely wrong.

The fix is to track the key itself.

Conceptually:

current_ecx = key
        ↓
AA lookup
        ↓
transition target

not:

first branch = 0
second branch = 1
...

This is one of the easiest ways to waste hours. The bad graph still looks reasonable, which makes the mistake harder to notice.

4. Reconstruct the Graph

Once the keys and lookup calls are tracked correctly, the verifier becomes a graph:

graph = {
    0: {0: 14, 1: 72, 2: 19, 3: 41},
    1: {0: 91, 1: 10, 2: 33, 3: 77},
    # ...
}

At that point, you can stop treating the binary like a pile of assembly and start treating it like a graph problem.

A design that requires visiting every state without invalid revisits is closely related to a Hamiltonian path.

5. The Second Layer: BigInt Constraints

This is where the verifier gets mean.

Some states do more than select the next edge. Before continuing, they update a large accumulator.

A common pattern is conceptually:

accumulator += SHA256(state_byte)

with the hash interpreted as a 256-bit integer.

Selected states then apply an additional condition:

accumulator mod M == expected_constant

Now the correct path must satisfy two independent layers:

Graph constraint
+
Arithmetic constraint

That explains a common reverse engineering failure mode: the graph looks solvable, yet every candidate path eventually dies.

Mind the endianness

Do not assume that the SHA-256 bytes are being interpreted arbitrarily.

The binary may construct a value through something like:

bytes
   ↓
hex string
   ↓
"0x..."
   ↓
BigInt parser

The exact representation matters.

A single endianness or formatting mistake can make every arithmetic constraint appear impossible when the real problem is simply that the model is wrong.

6. Search the Path

Once the graph and constraints are extracted, do not brute-force the original byte string.

Search the state graph first.

A basic DFS with backtracking looks like:

def dfs(state, visited, path):
    if len(visited) == total_states:
        return path

    for key, nxt in graph[state].items():
        if nxt in visited:
            continue

        if violates_constraint(nxt, path):
            continue

        result = dfs(
            nxt,
            visited | {nxt},
            path + [(nxt, key)]
        )

        if result:
            return result

    return None

For larger graphs, use heuristics such as trying low-degree nodes first.

The important shift is that the graph itself eliminates huge portions of the search space.

7. Convert the Path Back to Input

After solving the graph, you have a sequence of transition keys.

For a 2-bit alphabet:

pairs = {
    0: "00",
    1: "01",
    2: "10",
    3: "11",
}

bits = "".join(pairs[key] for key in path_keys)

Then pack the bits back into bytes:

data = bytes(
    int(bits[i:i+8], 2)
    for i in range(0, len(bits), 8)
)

If the dictionary changes between chunks, you must apply the correct mapping at each chunk instead of using one global dictionary.

This is an important detail. You can have the correct state path and still generate the wrong input because the final bit-to-key conversion ignored a runtime permutation.

8. Validation

Do not call the solver finished just because it produced a long candidate.

Validate all of these:

✓ correct entry state
✓ valid transition key at every step
✓ no forbidden state revisits
✓ every arithmetic constraint satisfied
✓ correct dictionary mapping for every chunk
✓ reconstructed input reproduces the same path
✓ verifier reaches Success

The strongest validation is to feed the generated input back into the original verifier.

Vulnerable Code Examples

This is not a traditional one-line memory corruption bug. The weakness is a verifier design that can be fully reconstructed from the client binary.

Weak version: the entire decision process is shipped to the client

def verify(user_input):
    state = 0
    visited = set()

    for chunk in split_into_chunks(user_input):
        key = lookup_key(chunk)
        state = transitions[state][key]

        if state in visited:
            return False

        visited.add(state)

    return len(visited) == TOTAL_STATES

Why is this dangerous? Because the transition graph and its rules are available to anyone who can reverse the binary.

Better version: keep the decisive secret server-side

def verify(server, user_input):
    proof = build_minimal_proof(user_input)
    return server.verify(proof)

The client can still be reverse engineered. That is fine. The important part is that the information required to forge a successful verification is not entirely present on the attacker-controlled machine.

Defense / How to Fix

1. Do not treat obfuscation as your primary security boundary. If the full verifier is on the client, assume it can eventually be understood.

2. Keep secret material outside the binary. Server-side verification or hardware-backed secrets are appropriate when the design requires them.

3. Avoid exposing a complete reusable success graph. Obfuscation increases analysis cost but does not create secrecy.

4. Reduce useful static artifacts. Clear symbol names, debug metadata, and descriptive strings can make reconstruction dramatically easier.

5. Use cryptographic verification when authenticity matters. If a value must be proven without revealing a secret, a cryptographic protocol is usually stronger than a client-side puzzle.

6. Red-team your verifier. Open your own binary in IDA, Ghidra, or Binary Ninja and ask a simple question: “How much of the acceptance logic can I recover without the server?”

Testing / Audit Points

When reviewing a similar verifier, look for:

What to look for	Why it matters
Arrays filled with 0xffffffff or similar sentinels	Possible visited-state tracking
Hundreds of similarly shaped functions	Generated state handlers
Repeated AA/map lookups	Transition dispatch
2-bit or N-bit chunks	Encoded input alphabet
BigInt or 256-bit arithmetic	Extra path constraints
SHA-256 inside the verifier	Hash-derived state updates
Success without an obvious secret string	Success may be traversal-based
Lazy initialization guards	Useful for mapping slots to handlers

Common Myths

“More Obfuscation means the secret is unrecoverable”

No.

Obfuscation raises the cost of analysis. It does not change the fact that the client contains the verification logic.

“If the secret is not in the strings, it must not exist”

Not necessarily.

There may be no stored secret at all. The required input can be the sequence that drives the machine through an accepted path.

“A huge graph automatically makes brute force impossible”

Not always.

A large graph with strong constraints can be easier than byte-level brute force because the constraints eliminate massive portions of the search space.

“Branch order is the transition key order”

Not when the verifier uses a mutable dictionary or AA permutation.

Track the actual key reaching the lookup.

Final Thoughts

This style of verifier teaches one of the most useful reverse engineering habits: stop staring at individual instructions and start looking for the system they implement.

Functions become states.

AA lookups become transitions.

Bit chunks become the alphabet.

BigInt checks become guard conditions.

Once the binary is transformed into a graph, the monster becomes much less impressive.

Obfuscation can make the road longer. It cannot change the mathematics of the road.