dudidudida - HackTheBox Challenge Writeup

Challenge Information

Description

A software company claims to have invented a new way to protect their applications. They released a small binary as a proof of concept, confident that no one can break the secret. Your task is simple: make the program return Success.

The task ships a single Windows PE binary, dudidudida.exe, that reads a line of input, evaluates it against an internal “protection” scheme, and prints Success!, Failed!, or Timeout! depending on the outcome. The goal is to recover an input string that makes it print Success!.

Solution

1. Artifact recovery

The staged dudidudida.exe in the working directory was a 0-byte placeholder. The real ~1 MB PE binary was found inside the task’s .zip archive, protected with the standard HTB archive password.

# Locate the real archive (staged binary was 0 bytes)
find /out /tmp -maxdepth 3 -name "*.zip" 2>/dev/null

unzip -P hackthebox -o /out/<task-uuid>.zip -d work/

2. Fingerprinting the binary

Static inspection with pefile and strings revealed this wasn’t a typical C/C++ binary:

strings -n 5 dudidudida.exe | grep -inE "success|fail|wrong|timeout|enter"

Key strings found:

Enter flag:
Success!
Failed!
Timeout!

Section headers were unusual: ._deh, .minfo, .dp, .tp, .fptable — these are hallmarks of a binary compiled with the DMD (D programming language) compiler, not MSVC/GCC. This immediately explained why generic RE tooling struggled: the runtime layout (module ctors, .minfo module-info table, .tp/.dp TLS/data sections) is D-specific.

3. Mapping program structure

Using pefile + capstone to disassemble around the entry point and string cross-references:

import pefile
from capstone import *
from capstone.x86 import *

pe = pefile.PE('dudidudida.exe')
ib = pe.OPTIONAL_HEADER.ImageBase
data = pe.get_memory_mapped_image()

md = Cs(CS_ARCH_X86, CS_MODE_64)
md.detail = True
# Disassemble around main() and the module constructor
for i in md.disasm(data[0x1000:0x1600], ib + 0x1000):
    print(hex(i.address), i.mnemonic, i.op_str)

This revealed the flow:

1. main reads a line of stdin input.
2. It spawns a “state function” at 0x14000b180 (state index derived from the input).
3. It waits up to 3 seconds for a completion signal — hence Timeout! if the state machine never terminates.
4. It prints Success! only if a terminal state sends a 0 message and all 224 entries in a global results array at 0x1400d9aa0 have been marked visited.

Each of the 224 state functions followed an identical template:

// Pseudocode reconstructed per state function `i`:
if (results[i] != -1) {
    fail();           // no re-entry allowed — each state visited exactly once
}
results[i] = i;

// Accumulate into a global 256-bit BigInt
ACC += BigInt("0x" ~ toHexString(sha256([cast(ubyte) i])));

// Consume 2 bits of input, mapped through a global alphabet table
symbol = lookup_AA(input[pos .. pos+2]);   // AA: {"00","01","10","11"} initially
spawn_state(successor_table[i][symbol], pos + 2);

The global alphabet array AA was initialized by the module constructor at 0x140001000:

AA[0] = "00"
AA[1] = "01"
AA[2] = "10"
AA[3] = "11"

4. Deriving the real problem: a Hamiltonian path

Since:

• there are 224 states,
• each consumes exactly 2 bits,
• each state may be visited exactly once,
• and Success! requires all 224 to be visited before the run ends at the one state capable of emitting the terminating 0 message (state 195, function 0x140005860),

the required input is a 448-bit binary string = 56 ASCII characters, and finding it is equivalent to finding a Hamiltonian path through a 224-node directed graph, starting at state 203 (the state entered from main) and ending at state 195.

# Extracted per-state successor edges into states.json:
# { "0x14000b180": {"idx": 0, "succ": {"0":..., "1":..., "2":..., "3":...}}, ... }

import json, sys
sys.setrecursionlimit(100000)
S = json.load(open('states.json'))
a2i = {a: v['idx'] for a, v in S.items()}

def dfs(cur, depth, path, visited):
    if depth == 224:
        return path if cur == TARGET_IDX else None
    for sym in range(4):
        nxt = S[cur]['succ'][str(sym)]
        if nxt not in visited:
            visited.add(nxt)
            path.append((cur, sym))
            r = dfs(nxt, depth + 1, path, visited)
            if r:
                return r
            path.pop()
            visited.remove(nxt)
    return None

5. The real “protection”: checkpoint states with an accumulator constraint

A naive Hamiltonian-path search over 224 nodes is already expensive, but 28 of the 224 states were checkpoint states that made brute-force search intractable without extra insight:

1. They rewrite the global 2-bit alphabet AA to a new permutation of {"00","01","10","11"} — meaning the meaning of each subsequent input bit-pair changes mid-stream.
2. They assert a modular constraint on the running accumulator:

   assert(ACC % K == T[checkpoint_id]);
   ACC = 0;   // reset after checking

   where K is a fixed 256-bit constant stored at 0x1400d9e40, and each T[checkpoint_id] is a distinct 76–77-digit decimal constant living in .rdata.

Since ACC accumulates sha256(byte(state_index)) as a BigInt for every visited state since the last checkpoint, the order in which states are visited between two checkpoints is constrained by a modular sum condition — not just graph reachability. This transforms the puzzle from “any Hamiltonian path” into “a Hamiltonian path whose accumulated-hash sums satisfy 28 independent modular equations,” which is what made brute-force naive search alone insufficient and required combining graph traversal with the modular checks as pruning constraints.

import hashlib

def state_hash_int(i):
    h = hashlib.sha256(bytes([i])).hexdigest()
    return int(h, 16)

K = 990890843036155646042991645774678752016205603...  # 256-bit constant from .rdata

def check_checkpoint(acc, checkpoint_id, T):
    return acc % K == T[checkpoint_id]

6. Solving

The final solver combined:

• DFS over the 224-node successor graph (Hamiltonian path search, start=203, end=195),
• pruning any branch that reaches a checkpoint state without satisfying ACC % K == T[id],
• tracking the live alphabet permutation (AA) as checkpoints rewrote it, so the correct 2-bit symbols could be translated back into the actual input[pos..pos+2] substring at each step.

# Core search loop (simplified)
def dfs2(cur, depth, aa, ssum, path):
    if depth == 224:
        return path if cur == TARGET else None
    for sym in range(4):
        nxt, is_ckpt = S[cur]['succ'][str(sym)]
        new_sum = (ssum + state_hash_int(nxt)) % MOD
        if is_ckpt and not check_checkpoint(new_sum, nxt):
            continue  # prune — modular constraint fails
        aa2 = rotate_alphabet(aa) if is_ckpt else aa
        r = dfs2(nxt, depth + 1, aa2, 0 if is_ckpt else new_sum,
                 path + [aa[sym]])
        if r:
            return r
    return None

Once a valid path of 224 states (448 bits / 56 characters) was found, the bit-pairs were translated through each active AA permutation segment to reconstruct the literal 56-character ASCII string that must be piped into the binary’s Enter flag: prompt. Feeding that string to dudidudida.exe produced:

Enter flag:
> <56-character solution string>
Success!

Extracting the printed value yielded the flag:

HTB{REDACTED}

Tools Used

• pefile — PE parsing, section/import inspection, image mapping
• capstone (x86-64 disassembly engine) — manual disassembly of state functions and the module constructor
• Python (hashlib, json) — SHA-256 accumulator modeling, graph extraction, Hamiltonian-path/DFS solver with modular-constraint pruning
• strings — initial triage for embedded prompts/output strings
• Standard Unix toolchain (unzip, bash) for artifact recovery

Key Learnings

• Identify the compiler/runtime before diving into disassembly. The unusual section names (._deh, .minfo, .dp, .tp, .fptable) were the tell for a DMD-compiled D binary — recognizing this early explains otherwise-confusing module constructor and runtime init code.
• “No one can break the secret” claims often hide a graph/constraint problem, not raw crypto. The real protection here was structural: a Hamiltonian-path requirement over 224 states combined with 28 modular-arithmetic checkpoints on a running SHA-256-based accumulator — cryptographic primitives used as constraints, not as an unbreakable cipher.
• State machines with “visit-once” semantics reduce to Hamiltonian path search. Recognizing the results[i] != -1 re-entry guard was the key insight that reframed 224 independent-looking functions as nodes in a single directed graph problem.
• Checkpoints that mutate global state (the alphabet permutation) must be tracked stateful during search. Treating the checkpoints as simple boolean gates would have been insufficient — their side effects change how subsequent input bits are interpreted, so the alphabet state had to be threaded through the DFS itself.
• Pure brute-force Hamiltonian-path search is infeasible at this scale (224 nodes). The modular accumulator checks doubled as powerful pruning constraints, and pruning on partial sums as soon as a checkpoint state was reached avoided wasted search deep in the tree.
• Recover the real artifact before analyzing. The staged binary was 0 bytes; the actual PE was inside the standard-password-protected task archive — always confirm you’re working against the real file before spending analysis time on a placeholder.