keygenme-py picoCTF 2021 Solution

Description

1. Step 1

   Locate the validation logic in the script

   Observation

   I noticed the challenge provides a Python key generator script, which suggested the flag is computed rather than stored literally, so finding the validation function and its hash calls was the necessary first step.

   Grep for the key generator and validation routines. The check is usually shaped like expected == hashlib.<algo>(seed).hexdigest()[:N] or hashlib.<algo>(input).hexdigest()[:N] == expected.

   bash

   grep -nE 'def (generate_key|check|verify|validate)|hashlib\.|hexdigest' keygenme-py.py

   Copied!

   bash

   cat keygenme-py.py

   Copied!

   Expected output

   picoCTF{1n_7h3_|<3y_of_...}

   What didn't work first

   Tried: Running strings or grep for 'picoCTF{' directly on the script to extract the flag

   The full flag is never stored as a literal in keygenme-py.py. Only the static prefix and the index list are present; the suffix is computed at runtime from the SHA-256 digest of the username. grep for the flag pattern returns nothing useful, and you need to trace the actual computation to produce the correct value.

   Tried: Using grep -n 'key' or grep -n 'password' instead of targeting hashlib and hexdigest to find the validation function

   Generic keyword searches on 'key' or 'password' match variable names and comments throughout the file without pinpointing the digest comparison. Searching for 'hashlib.' and 'hexdigest' hits exactly the hash-construction lines, making the validation shape immediately visible and reducing manual reading.

   Learn more

   A keygen (key generator) challenge asks you to reverse-engineer the validation logic of a program to produce a value that passes the check - rather than recovering a stored secret. The key here is deterministic: it depends only on a hardcoded constant string, so there is exactly one valid answer.

   SHA-256 is a cryptographic hash function that produces a 256-bit (64 hex character) digest. The script uses specific character positions from the hex digest as nibbles of the dynamic portion of the key. Nibble selection at specific indices is a common obfuscation pattern in crackme challenges.

2. Step 2

   Compute the key from the SHA-256 hash

   Observation

   I noticed the script contains a hardcoded username constant and builds the flag suffix by selecting specific indices from a SHA-256 hexdigest, which suggested replaying that exact computation in Python was all that was needed to produce the correct key.

   The static prefix in the source is picoCTF{1n_7h3_|<3y_of_ and the suffix is built from the SHA-256 hexdigest of the username. Read the username constant from your copy of the script (it is set per-instance), hash it, extract hex-digest characters at indices [4, 5, 3, 6, 2, 7, 1, 8], and wrap with the prefix and closing brace.

   python

   python3 -c "
   import hashlib
   username = b'GOUGH'   # use the username constant from YOUR keygenme-py.py (per-instance)
   h = hashlib.sha256(username).hexdigest()
   suffix = ''.join(h[i] for i in [4, 5, 3, 6, 2, 7, 1, 8])
   print('picoCTF{1n_7h3_|<3y_of_' + suffix + '}')
   "
   # For username GOUGH this prints picoCTF{1n_7h3_|<3y_of_...}

   Copied!

   What didn't work first

   Tried: Using the username 'GOUGH' literally instead of reading the username constant from your own copy of keygenme-py.py

   The username is set per-instance, so different downloads assign different constants. Hardcoding GOUGH produces picoCTF{1n_7h3_|<3y_of_...} only for that specific instance; any other username yields a different SHA-256 digest and therefore a different suffix, causing the check to fail.

   Tried: Extracting all 64 characters of the SHA-256 hexdigest as the suffix instead of selecting characters at the specific indices [4, 5, 3, 6, 2, 7, 1, 8]

   The script does not use the full digest. It picks exactly eight characters at scrambled, non-consecutive positions from the 64-character hex string. Using the raw full digest or a consecutive slice produces a 64-character or arbitrarily-sliced string that will not match the eight-character expected suffix in the validation check.

   Learn more

   The indices [4, 5, 3, 6, 2, 7, 1, 8] are not consecutive - they are scrambled to make the pattern less obvious. By reading the source validation logic carefully and tracing each index access, you reconstruct the exact nibble order needed to form the correct suffix.

   This challenge illustrates why security through obscurity fails: once the source code is available (or reversible from a binary), any deterministic computation can be replicated. A truly secure key would involve an actual secret that is never stored in the program.

3. Step 3

   Brute force the digest-prefix check

   Observation

   I noticed that some keygen validations compare a hash of user-supplied input against a short target prefix rather than computing a key from a fixed seed, which suggested a brute force partial-preimage search as an alternative technique when the computation direction is inverted.

   If the validation is shaped like target == hashlib.md5(user_input).hexdigest()[:N] for small N (typically 4-8 hex chars), iterate candidate inputs until the digest prefix matches. For N=6 the expected work is roughly 16 million tries.

   python

   python3 - <<'EOF'
   import hashlib
   import itertools
   import string
   
   target = 'abcdef'  # the digest prefix from the script
   alphabet = string.ascii_letters + string.digits
   
   # Try lengths 4..8 until a match falls out
   for length in range(4, 9):
       for guess in itertools.product(alphabet, repeat=length):
           s = ''.join(guess)
           if hashlib.md5(s.encode()).hexdigest().startswith(target):
               print('match:', s)
               raise SystemExit
   EOF

   Copied!

   What didn't work first

   Tried: Applying this brute force loop to the actual keygenme-py.py challenge instead of reading the username and replicating the computation

   This challenge does not ask for a value that hashes to a target prefix - it computes the key deterministically from a known username constant. Brute forcing is unnecessary and far slower; reading the username from the script and running the eight-index extraction takes under a second and is the intended path.

   Tried: Searching only up to length 4 in the brute force loop when the target prefix is 6 or 8 hex characters

   A 4-character prefix has only 65,536 possible digests, so a length-4 input is likely found quickly - but if the script requires a 6 or 8 hex char prefix match, a length-4 candidate will almost certainly not collide unless you extend the search range. The expected work scales as 16^N_prefix, not as the input length, so prefix length drives the loop bound.

   Learn more

   Brute force vs invert. If the script computes the key from a fixed seed (this challenge's shape), no brute force is needed - just replicate the computation. If the script accepts your input and checks whether its digest matches a target prefix, you're looking at a partial-preimage search and brute force scales with 16^N for an N-hex-char prefix. For N ≤ 6 a single laptop core finishes in seconds; N = 8 needs hashcat (hashcat -m 0 -a 3 target ?a?a?a?a?a?a); beyond that the design is genuinely intractable and the challenge wants a different trick (algebraic shortcut, leak elsewhere in the binary).

Flag

The key is deterministic: static prefix picoCTF{1n_7h3_|<3y_of_ plus eight characters taken from the SHA-256 hexdigest of the username at indices [4,5,3,6,2,7,1,8]. The username is set per-instance (GOUGH gives ...f911a486; PRITCHARD gives ...54ef6292), so read it from your own script copy.