Reverse Checksum

Full solution below. Spoilers ahead.

Task description

Surely you can’t recover anything based on a one-byte checksum…

The handout is checksum_v3.tar.gz, which unpacks to one Linux executable called checksum. Run it and it prints marketing copy for a “proprietary one-byte checksum algorithm” named SFSN161, from a fictional “TrustMeBro Ltd”, and dares you not to bother trying to recover anything. It offers to checksum three named variables. A fourth, FLAG, is accepted but never listed, and recovering its value is the task.

What the binary is

file reports a 64-bit PIE ELF (a position-independent executable, the normal shape of a modern Linux program) that is not stripped:

checksum: ELF 64-bit LSB pie executable, x86-64, ... dynamically linked,
          ... for GNU/Linux 3.2.0, ... not stripped

The readable strings mention rustc and library/std/src/..., so it is a Rust binary. The symbol table is the interesting part. Almost every entry is a function named checksum_<40 hex digits>, mangled in the Rust style as _ZN8checksum50checksum_<40hex>_17h<16hex>E. Parsing .symtab with pyelftools counts exactly 5030 of them, plus one ordinary checksum::main (_ZN8checksum4main..., at 0x40ed0). Leaving the symbols in place is the first gift to a reverser: each node of the structure below has a name and a size, so a disassembler can be pointed straight at it.

I did the whole analysis statically in Python, parsing the ELF with pyelftools and disassembling with capstone (a disassembly library). No debugger was involved, and the challenge binary was never executed; everything here comes from reading the code at rest.

The program’s own help text sets up the premise it gets wrong:

The checksum is only one byte however due to the nature of the algorithm this […] Only the checksum is ever stored in memory so it is absolutely impossible to recover the original secret.

What main does

main reads a line of input and compares it against the strings FLAG, AZURE_API_KEY, DB_PASSWORD and MANS_BEST_FRIEND. On a match it zeroes a single byte on the stack, calls that variable’s root checksum_* function with rdi (the first-argument register) pointing at the byte, and prints Checksum: <byte>. Only one byte of state exists for the whole computation.

Every function is one XOR and some calls

Disassembling the checksum_* family shows a startlingly narrow instruction set. Across the whole family only four operations do any work:

call  <child>                 13893x
xor   byte ptr [rdi], imm8     4983x
not   byte ptr [rdi]             25x
ret

Each function applies one operation to the shared byte, either an XOR with a constant or a not (which is XOR with 0xff), and then calls its children in order, keeping the byte’s address in rbx across the calls:

push rbx
mov  rbx, rdi
xor  byte ptr [rdi], 0x7f      ; this node's constant
call <child0> ; mov rdi,rbx
call <child1> ; mov rdi,rbx
call <child2>
pop  rbx ; ret

So each variable is a call tree of a few thousand nodes, and every node XORs one constant into the same byte. The 13893 figure above is the number of parent-to-child call edges inside the family, which is what makes it a tree rather than a flat list.

The secret lives in the tree, not the byte

Because every node XORs into one shared byte and XOR is commutative, the final printed byte is just the XOR of all the constants in the tree. Reorder the nodes and the byte comes out the same. On that count the marketing is right: the output byte on its own tells you almost nothing about the secret.

It is wrong about everything else, because the order the constants are applied in is recorded in the shape of the tree, and that order is a function of the secret. A function runs its own XOR first and only then recurses into its children left to right, so the tree executes in pre-order (parent, then each subtree in turn). The generator spends a fixed budget of nodes per secret character, laid out one character after another in that pre-order sequence. If I keep a running XOR of the byte while walking the tree in pre-order, then at the end of the k-th character’s block the running value equals the XOR of the first k characters of the secret. Differencing two neighbouring boundaries gives one character:

secret[k] = cum[boundary_k] ^ cum[boundary_{k-1}]

The program never prints these intermediate values; it only ever prints the final byte. They are recoverable because the code that would compute them is sitting in the file, so the pre-order walk can be replayed offline.

Why the running output still only leaks one byte at runtime

The prefix XORs are intermediate states of the single stack byte during the computation. At runtime nothing observes them: the program recurses through the whole tree and prints the byte once, at the end. The leak is entirely static. It exists because the generated code can be read and its exact pre-order execution reconstructed without running it, not because the running program reports anything beyond the one byte it claims to.

Calibrating on the dog

MANS_BEST_FRIEND is the obvious joke variable, and it is the calibration I trusted the rest of the method on. Its checksum is 0x6c. Man’s best friend is a dog, and 'd' ^ 'o' ^ 'g' is 0x6c. Its tree walks to exactly 484 nodes, which is 3 * 161 + 1, so the budget is roughly 161 to 162 nodes per character. Walking it in pre-order and cutting at boundaries near round(k * N / L) (with N nodes and L characters) reads back dog exactly. That confirmed both the pre-order rule and the per-character budget before I pointed anything at FLAG.

The same budget holds for the other two listed variables, which I did not need to decode but did count as corroboration: AZURE_API_KEY walks to 5817 nodes (about 36 characters, checksum 0x0b) and DB_PASSWORD to 2748 nodes (about 17 characters, checksum 0x21). Every tree is the same construction at a different length.

Decoding FLAG

The solver loads the ELF, disassembles each checksum_* function to pull its XOR constant and its child call targets, then walks a chosen root in pre-order and records the running XOR after every node. The core of the walk is small:

def cumulative(node, root):
    out, x = [], 0
    def go(a):
        nonlocal x
        op, kids = node(a)
        x ^= op          # this node's constant, applied first
        out.append(x)    # running XOR after this node
        for c in kids:
            go(c)
    go(root)
    return out

FLAG’s tree walks to 4850 nodes, which is 30 * 161.67, so the secret is 30 characters. The per-character blocks all land between 160 and 163 nodes, the boundaries sum to the node count exactly, and the last running value is 0x39, the checksum the program would print. The real boundary table (character, prefix XOR px, pre-order index, and block size) begins:

 k  ch  px   boundary size
 1 'F'  0x46   160  161
 2 'o'  0x29   322  162
 3 'r'  0x5b   484  162
 4 't'  0x2f   645  161
 5 'I'  0x66   807  162
 6 'D'  0x22   969  162
 7 '{'  0x59  1131  162
 8 'c'  0x3a  1293  162
 ...
30 '}'  0x39  4849  162
final boundary == n-1 ? True   checksum 0x39

The first seven characters land on FortID{, which is the flag format and the first independent confirmation that the model is right.

Why one reading and not another

Here is the honest limit of the method, and it is worth being plain about. Because 161.67 is not an integer, the per-character boundary has a little slack. At a few positions more than one nearby running value is a printable character, so the tree structure alone admits several charset-valid decodings, and all of them share the same final byte 0x39. The structure narrows the answer to a small set; it does not hand over a single string.

Three constraints together pin it. The FortID{...} format fixes the first seven characters and the closing brace. The plaintext has to read as a sentence rather than noise. And the XOR of all 30 characters has to equal 0x39. The near-miss readings differ from the right one in only one or two leetspeak choices, and that is exactly enough to break the last test:

candidate (clipped)	XOR of bytes	why it fails
FortID{cH3ck5um...	0x39	matches the checksum and reads cleanly
FortID{ch3ck5um...	0x19	lowercase h, parity wrong
FortID{cH3cksum...	0x7f	plain s instead of 5, parity wrong

The capital H and the 5-for-s substitution are both forced by the parity coming out to 0x39. So the solver does not decode the flag blind. It takes the candidate string I proposed from the format and the readable text, and it verifies that the string is consistently encoded in the tree: it checks that every prefix XOR of the candidate appears as a running value at a strictly increasing pre-order index near k * N / L, that the last of those indices is the final node, and that the overall XOR matches the printed byte. The decode function returns true or false for a given string; it never enumerates. The flag is pinned by format, readability and the one-byte checksum together, with the tree supplying the per-character evidence.

Running the solver

The included solve.py carries the candidate and runs all three checks against the handout binary. It needs pyelftools and capstone. The assertions inside it are the proof: the dog sanity check, the consistency of the flag’s encoding in the tree, and the parity match.

$ python -I solve.py extracted/checksum
[*] sanity: MANS_BEST_FRIEND = "dog"  (checksum 0x6c)
[*] FLAG checksum byte = 0x39
[+] FLAG = FortID{cH3ck5um...

The recovered string is 30 bytes, opens with FortID{, reads as a short phrase about the checksum not being secure, and its bytes XOR to 0x39 (sha256 prefix abd2d2a27755). There is no remote service: the flag is the FLAG variable’s secret, recovered from the static call graph, and I did not submit it to the platform, so the evidence is the solver’s three consistency checks rather than a scoreboard tick.

What the design got wrong

SFSN161’s runtime output genuinely is one byte, and because XOR is commutative that byte really does hide the order the constants were applied in. The mistake is that the generator writes the secret, in order, into the control flow it emits, so the whole input survives in the program at rest even though it collapses to a byte at runtime. Shipping the binary unstripped made it worse, since the 5030 named functions and their sizes let a linear disassembler recover every node without any guessing about function boundaries. If a secret has to be checkable without being stored, the tool for that is a keyed MAC or a password hash such as argon2, with only the digest shipped. A bespoke routine whose structure is a function of the plaintext is not storage-free, it is storage in a different shape.