Checkpass picoCTF 2021 Solution

Description

1. Step 1Understand the vulnerability: early-exit comparison

   Observation

   The binary prints the flag only for a correct password, and it looks like it exits early on a mismatch. That is a timing side-channel: each correct character makes the loop run more instructions before it stops.

   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{AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}' 2>&1 | grep 'I   refs'

   Copied!

   bash

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

   Copied!

   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 swings with system load, scheduling jitter, and branch prediction warmup. The per-character difference is a handful of nanoseconds, far under the noise floor of a shell timer. Cachegrind sidesteps that by counting instructions on a deterministic emulated CPU, giving a stable delta of exactly 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 never calls C strcmp or memcmp; it compares inline, as a byte loop compiled from Rust iterator code. ltrace only intercepts dynamic library calls and shows nothing, and strace captures syscalls rather than user-space comparisons. Neither exposes the byte-by-byte logic behind 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 2Automate character recovery with a Python script

   Observation

   Cachegrind confirms a detectable instruction-count delta for each correct character. So a Python script can walk all printable characters at each of the 32 inner positions and greedily lock in whichever 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]   # 94 printable characters, no whitespace
   
   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 the later positions go wrong. Once several characters are locked in, a partially correct guess already scores high, and a new correct character may beat the original all-wrong run by a margin small enough for noise to swallow. Carry the best count forward, so each new character is measured against the current best rather than the first baseline.

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

   Running many Valgrind processes at once saturates the cores and spreads emulation overhead unevenly, which makes the I-refs counts non-deterministic under contention, so the highest count may not be the right character. Parallelize across positions once the previous one is solved, or run candidates sequentially 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 94 times, so the total number of cachegrind invocations is at most 32 x 94 = 3,008 rather than the 94^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 3Verify the recovered password

   Observation

   The script converges on a candidate string, one position at a time. Running the binary with that string confirms whether the side-channel actually recovered the 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.