Checkpass picoCTF 2021 Solution

Description

1. Step 1

   Understand the vulnerability: early-exit comparison

   Observation

   I noticed the binary prints the flag only for a correct password and presumably exits early on a mismatch, which suggested a timing side-channel where each correct character causes the loop to execute more instructions before stopping.

   Run the binary under Valgrind with cachegrind and compare the instruction reference count (I refs) for a clearly wrong input versus an input that gets the first character right. You will see a higher I-refs count when the first character matches, because the loop runs one more iteration before exiting.

   bash

   valgrind --tool=cachegrind --cachegrind-out-file=/dev/null ./checkpass 'picoCTF{AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}' 2>&1 | grep 'I   refs'

   Copied!

   bash

   valgrind --tool=cachegrind --cachegrind-out-file=/dev/null ./checkpass 'picoCTF{tAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}' 2>&1 | grep 'I   refs'

   Copied!

   Expected output

   picoCTF{t1mingS1deChann3l_...}

   What didn't work first

   Tried: Use wall-clock time (time ./checkpass ...) instead of cachegrind to detect the timing difference per character.

   Wall-clock time varies too much with system load, CPU scheduling jitter, and branch prediction warmup. The per-character difference is only a handful of nanoseconds, far below the noise floor of a shell timer. Cachegrind sidesteps this by counting instructions in a deterministic emulated CPU, giving a stable delta of exactly the instructions added by one extra loop iteration.

   Tried: Run ltrace or strace to observe strcmp or memcmp calls and recover the password from the arguments.

   The Rust binary does not call a C strcmp or memcmp; it performs the comparison inline as a byte loop compiled from Rust's iterator code. ltrace only intercepts dynamic library calls, so it shows nothing useful. strace captures syscalls, not user-space comparisons. Neither tool exposes the byte-by-byte logic that creates the timing difference.

   Learn more

   Why cachegrind? Cachegrind counts every CPU instruction the process executes. Because the Rust binary compares the password character by character and returns as soon as one character does not match, a correct character forces the loop to advance one step further, executing a handful of additional instructions. That small difference is detectable and stable, unlike real wall-clock timing which varies with system load.

   Flag format constraints. The binary validates the input length (41 characters total), confirms it starts with picoCTF{ and ends with }, and then checks the 32 inner characters one at a time. You are searching for those 32 characters.

2. Step 2

   Automate character recovery with a Python script

   Observation

   I noticed the manual cachegrind approach confirmed a detectable instruction-count delta per correct character, which suggested writing a Python script to iterate all printable characters at each of the 32 inner positions and greedily lock in whichever candidate scores highest.

   Write a script that iterates over all printable characters for each of the 32 unknown positions. For each candidate, run cachegrind and parse the I refs line. The character that produces the highest instruction count is correct. Repeat for every position until the full password is recovered.

   python

   python3 checkpass_solve.py

   Copied!

   import subprocess, string
   
   BINARY = "./checkpass"
   CHARS = string.printable[:-6]   # ~95 printable characters
   
   def i_refs(password: str) -> int:
       result = subprocess.run(
           ["valgrind", "--tool=cachegrind",
            "--cachegrind-out-file=/dev/null", BINARY,
            f"picoCTF{{{password}}}"],
           capture_output=True, text=True
       )
       for line in result.stderr.splitlines():
           if "I   refs:" in line:
               return int(line.split(":")[1].strip().replace(",", ""))
       return 0
   
   flag = ["A"] * 32
   best = i_refs("".join(flag))
   
   for pos in range(32):
       for c in CHARS:
           guess = flag[:]
           guess[pos] = c
           count = i_refs("".join(guess))
           if count > best:
               best = count
               flag[pos] = c
               print(f"pos {pos}: {c}  ->  picoCTF{{{''.join(flag)}}}")
               break
   
   print("Flag:", f"picoCTF{{{''.join(flag)}}}")

   What didn't work first

   Tried: Iterate positions using a greedy break on the first character that gives any increase over the previous run, without tracking a running best baseline.

   Without an updating baseline, later positions regress: once several correct characters are locked in, the instruction count for a partially-correct guess is already high, and a correct character at a new position may only beat the very first all-wrong run by a tiny margin that noise obscures. The script must carry the best count forward across positions so each new correct character is measured against the current best, not the original baseline.

   Tried: Parallelise all 95 character candidates for a given position by launching cachegrind runs simultaneously with multiprocessing.Pool.

   Running many Valgrind processes at once saturates CPU cores and causes them to share emulation overhead unevenly. The resulting I-refs counts become non-deterministic under contention, so the highest-count winner may not be the correct character. Parallelism is safe only across positions (after the previous position is fully solved), or by running candidates sequentially within each position on isolated cores.

   Learn more

   How the loop works. At each position the script tries every candidate character, keeps the highest I-refs count seen so far as the baseline, and locks in the first character that beats it. Because the comparison is sequential and exits on the first wrong character, each correct character you fix extends how far into the loop the binary reaches, which always increases the instruction count relative to the previous best. The outer loop runs 32 times and the inner loop runs at most ~95 times, so the total number of cachegrind invocations is at most 32 x 95 = 3,040 rather than the 95^32 brute-force search space.

   Performance note. Each cachegrind run takes roughly 2-10 seconds because Valgrind emulates the CPU. The full script therefore takes several hours to complete. Running it in a screen or tmux session is recommended. Some solvers parallelise the inner loop across multiple cores to cut the wall time.

   Parsing the output. The line of interest looks like: I refs: 490,589. Strip commas and convert to an integer for easy comparison.

3. Step 3

   Verify the recovered password

   Observation

   I noticed the script printed a candidate flag string after converging on each character position, which suggested running the binary directly with that string to confirm the side-channel recovery produced the actual correct password.

   Once the script finishes, run the binary directly with the recovered flag string. It should print a success message.

   bash

   ./checkpass 'picoCTF{t1mingS1deChann3l_...}'

   Copied!

Flag

The flag is static. The password is recovered character by character using cachegrind instruction counts as a timing oracle.