OTP Implementation picoCTF 2020 Mini-Competition Solution

Description

1. Step 1

   Analyze the binary in Ghidra

   Observation

   I noticed the challenge provided a compiled binary with no source code, which suggested static reverse engineering in Ghidra to reveal the validation logic, the jumble transformation, and the hardcoded target string that the input is checked against.

   Load otp in Ghidra and look at main. The program takes a command-line argument, validates that each character is a lowercase hex digit (a-f or 0-9), applies a custom jumble transformation, and compares the result to a hardcoded 100-character string. The transformation and the target string are visible in Ghidra's decompiler view.

   Learn more

   Ghidra is a free, open-source reverse engineering framework developed by the NSA. Its decompiler converts raw machine instructions back into readable C-like pseudocode. Here it reveals the validation pattern: apply a jumble() function to each character, then call strncmp() against a fixed expected string.

   The key insight is that you do not need to algebraically invert the jumble math. The comparison is done with strncmp(), which you can observe at runtime. There are only 16 possible input characters (hex digits), so you can test each one at each position empirically.

2. Step 2

   Set a GDB breakpoint at strncmp to observe both arguments

   Observation

   I noticed from the Ghidra decompiler that the validation ends with a strncmp call comparing the jumbled input to a fixed target, which suggested setting a GDB breakpoint there to read both string pointers from RDI and RSI and directly see whether a candidate character position matches the expected byte.

   Run the binary under GDB with a 100-character test input and set a breakpoint at the strncmp call. When the breakpoint hits, inspect the RSI and RDI registers: one holds your jumbled input, the other holds the expected target. On a 64-bit machine, strncmp arguments are passed in registers. This lets you see whether any character position matches the target.

   bash

   gdb ./otp

   Copied!

   bash

   (gdb) break strncmp

   Copied!

   bash

   (gdb) run $(python3 -c "print('6' + '0'*99)")

   Copied!

   bash

   (gdb) x/s $rsi

   Copied!

   bash

   (gdb) x/s $rdi

   Copied!

   What didn't work first

   Tried: Reading the jumbled output from RAX instead of RDI/RSI after strncmp returns

   After strncmp returns, RAX holds the integer comparison result (0 for match, nonzero for mismatch), not a pointer to either string. The actual string pointers are only live in RDI and RSI at the moment the function is entered, so the breakpoint must be set at the call site or at the function entry, not at the return.

   Tried: Using 'info registers' to find the expected target, then reading all 100 characters from memory at once

   The full 100-character expected string is in memory, but RDI and RSI each point to different strings depending on argument order - which one is the expected target vs. the jumbled input can vary by compiler. Reading the wrong pointer gives you your own jumbled input back, which looks like a match for every position. Verifying which register holds the hardcoded bytes (constant across runs) vs. the dynamic jumbled input (changes with input) is required before trusting the read.

   Learn more

   Martin manually tested one character to understand the mapping: putting in 'a' produced 'c', going up by two each step, so 'b' produces 'e', 'c' produces 'g', and so on. Since the first expected byte was 'M' and the mapping increments by 2, he calculated that '6' maps to 'M' and confirmed it with GDB. Once he saw the first character matched, he moved on to automating the rest.

   On x86-64, the first two arguments to any function are passed in rdi and rsi. Inspecting them at the strncmp breakpoint shows both the jumbled version of your input and the hardcoded expected string side by side, without modifying the binary.

3. Step 3

   Automate character-by-character recovery with a Python GDB script

   Observation

   I noticed that the 100-position key allows only 16 valid hex characters per position and that the strncmp oracle confirms matches one byte at a time, which suggested automating the 1,600 GDB invocations with a Python script rather than repeating the manual process for all 100 positions.

   Write a Python script that calls GDB in a loop. For each of the 100 positions, try all 16 hex characters. At the strncmp breakpoint, compare RSI and RDI. When they match at the current position, that character is correct. Record it and move to the next position. After all 100 positions the full key is recovered.

   python

   python3 solve_proc.py

   Copied!

   What didn't work first

   Tried: Trying to invert the jumble math algebraically from the Ghidra pseudocode instead of using the GDB oracle

   The Ghidra decompiler sometimes misrepresents integer widths, sign extension, and modular arithmetic in ways that produce a subtly wrong inverse formula. Applying a wrong inverse formula recovers a 100-character key that, when run through the binary, still fails strncmp. The GDB oracle approach sidesteps this entirely because it never needs to understand the math - it only needs to observe which input produces a matching first N bytes.

   Tried: Running the GDB script with the candidate character appended at the end rather than at position N with '0' padding after it

   The jumble function is applied per character but strncmp checks the full string from byte 0. If the known-good prefix plus the candidate are placed at positions 0..N but the remaining bytes are wrong, strncmp still returns nonzero even when position N is correct. The script must pad positions N+1 through 99 with a fixed neutral character (like '0') so that only positions 0..N are being evaluated against the target.

   Learn more

   The script runs the binary under GDB with the prefix of known-good characters, then the candidate character, then 99 minus the current position '0' characters to pad to 100. At the strncmp breakpoint it reads RSI and RDI. If the first N+1 bytes match, the candidate character is correct.

   This reduces the brute force from 16^100 (completely infeasible) to 16 * 100 = 1,600 GDB invocations. Each check is independent per position because the jumble function is applied per character. Martin demonstrates running the script and watching it fill in the key character by character: it starts with the '6' he found manually, then recovers all 100 characters automatically.

4. Step 4

   XOR the recovered key with flag.txt

   Observation

   I noticed the challenge name explicitly references OTP (One-Time Pad) and the binary produced a 100-character hex key, which suggested decoding that hex string to 50 bytes and XORing it with flag.txt to reverse the encryption and recover the plaintext flag.

   The recovered key is a hex string. Decode it to bytes and XOR it byte-by-byte with the contents of flag.txt. The result is the plaintext flag. Martin uses an online XOR tool for this step, first pasting the hex key and flag.txt bytes, then converting the hex output to ASCII.

   python

   python3 -c "
   key = bytes.fromhex('<recovered_100_char_key>')
   flag_enc = open('flag.txt','rb').read()
   print(''.join(chr(a^b) for a,b in zip(key,flag_enc)))
   "

   Copied!

   Expected output

   picoCTF{cust0m_jumbl3s_4r3nt_4_g0Od_1d3A_...}

   What didn't work first

   Tried: Treating the recovered key as ASCII text rather than a hex string and XORing it directly with flag.txt

   The 100-character key is a hex-encoded byte sequence where two characters represent one byte. Passing it directly to XOR as a 100-byte ASCII string doubles the effective key length and misaligns every byte, producing garbage output. bytes.fromhex() must be called first to convert the hex string into its 50-byte binary representation before XORing.

   Tried: XORing the full flag.txt file length against the key without checking that the lengths match

   If flag.txt is longer than the decoded key (50 bytes), zip() silently truncates to the shorter length and the tail of the flag is lost. If flag.txt is shorter, some key bytes are unused but the output appears correct. Using zip() without a length check masks mismatches - itertools.zip_longest or an explicit length assertion reveals when the key and ciphertext are misaligned.

   Learn more

   The One-Time Pad (OTP) XORs each plaintext byte with the corresponding key byte to produce ciphertext. XORing the ciphertext with the same key recovers the plaintext because XOR is its own inverse: (plaintext XOR key) XOR key = plaintext.

   The challenge's title is ironic: this is a broken OTP. A real OTP requires a key generated from a cryptographically secure source. Here the key is recoverable because the validation logic leaks one character at a time through GDB observation. The flag message confirms this: custom jumbles are not a good idea.

Flag

The trailing hex suffix (e.g. 15e89ca4 or 33ead16f) is generated per instance. GDB with a breakpoint at strncmp lets you observe both the jumbled input and the expected target in RSI/RDI. Testing all 16 hex characters per position (1,600 total checks) recovers the full 100-character key, which is then XORed with flag.txt.