keygenme-py picoCTF 2021 Solution

Description

1. Step 1Locate the validation logic in the script

   Observation

   The challenge provides a Python key generator script, so the flag is computed rather than stored literally. Finding the validation function and its hash calls comes first.

   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 a literal in the script. Only the static prefix and the index list are there; the suffix is computed at runtime from the SHA-256 digest of the username. Grepping for the flag pattern finds nothing, so trace the computation instead.

   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 2Compute the key from the SHA-256 hash

   Observation

   The script holds a hardcoded username constant and builds the flag suffix by picking specific indices out of a SHA-256 hexdigest. Replaying that same computation in Python produces the 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 whole digest. It takes exactly eight characters from scrambled, non-consecutive positions in the 64-character hex string. Use the full digest, or a consecutive slice, and you get something that never matches the eight-character suffix the validation expects.

   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 3Brute force the digest-prefix check

   Observation

   Some keygen validations compare a hash of your input against a short target prefix instead of computing a key from a fixed seed. When the computation runs that direction, a brute-force partial-preimage search is the alternative.

   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 want a value that hashes to a target prefix; it computes the key deterministically from a known username constant. Brute force is both unnecessary and far slower. Read the username from the script and run the eight-index extraction, which takes under a second.

   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 short input is usually found fast. But if the script demands a 6- or 8-character prefix match, a short candidate almost certainly will not collide without extending the search. The expected work scales with 16 to the power of the prefix length, not with the input length, so the prefix 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.