keygenme-py picoCTF 2021 Solution

Description

1. Step 1Locate the validation logic in the script
   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!
   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
   Hash the string GOUGH with SHA-256. Extract nibbles at indices [4, 5, 3, 6, 2, 7, 1, 8] from the hex digest. Concatenate the static prefix, the extracted nibbles, and the closing brace.
   python

   python3 -c "
   import hashlib
   h = hashlib.sha256(b'GOUGH').hexdigest()
   suffix = ''.join(h[i] for i in [4, 5, 3, 6, 2, 7, 1, 8])
   print('picoCTF{...}')
   "

   Copied!
   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
   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!
   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 - sha256 of a hardcoded constant, with specific nibbles extracted in a fixed order.