Guess My Cheese (Part 1) picoCTF 2025 Solution

Description

1. Step 1

   Use the encryption oracle to identify the cipher

   Observation

   I noticed the service let me submit any cheese name and returned its encrypted form, which meant I had a chosen-plaintext oracle; submitting a known word like CHEDDAR and observing each letter's mapping was enough to identify the two-parameter Affine cipher structure.

   Submit a known cheese name (uppercase - the cipher only shifts A-Z, so anything else is dropped silently) and capture the ciphertext. The cipher is Affine: E(x) = (a*x + b) mod 26, A=0..Z=25. Two distinct plaintext-ciphertext pairs give you two equations - enough to solve for a and b.

   bash

   # At the oracle prompt, submit (uppercase):
   CHEDDAR
   
   # Oracle replies with something like:
   # CHEDDAR encrypts to: ADWLLEJ
   #   C(2) -> A(0):  0 = (a*2 + b) mod 26
   #   H(7) -> D(3):  3 = (a*7 + b) mod 26
   # Subtract: -3 = a*(-5) mod 26  ->  a = 3 * inv(5) mod 26
   # where inv(x) is the modular inverse of x mod 26.

   Copied!

   What didn't work first

   Tried: Submitting lowercase letters to the oracle to get plaintext-ciphertext pairs

   The cipher silently drops any character that is not an uppercase A-Z letter, so a lowercase submission returns an empty or mangled ciphertext with no usable pairs. You need to submit the cheese name in uppercase so every character survives the encoding step and maps to a ciphertext letter you can use in the equations.

   Tried: Trying to solve for a and b with a single plaintext-ciphertext pair

   One pair gives you one equation with two unknowns (a and b), which is underdetermined - infinitely many (a, b) combinations satisfy it. You need at least two distinct pairs to reduce the system to a unique solution modulo 26. Submit a plaintext with at least two different letters and capture both mappings.

   Learn more

   The Affine cipher is a monoalphabetic substitution cipher that maps each letter x (0 to 25) to (a*x + b) mod 26. The parameter a must be coprime to 26 to ensure the mapping is reversible; valid values are 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25 - only 12 possibilities. The parameter b is any value 0 to 25, giving 26 options. Combined, there are only 12 * 26 = 312 possible Affine keys, making brute force trivial even without a known plaintext.

   With two known plaintext-ciphertext pairs (p1, c1) and (p2, c2), you get two simultaneous equations modulo 26: c1 = a*p1 + b (mod 26) and c2 = a*p2 + b (mod 26). Subtracting eliminates b: c1 - c2 = a*(p1 - p2) (mod 26). Solving for a requires computing the modular inverse of (p1 - p2). Once a is known, b = c1 - a*p1 (mod 26).

   The encryption oracle provided by the service is what makes this challenge straightforward. Instead of brute-forcing all 312 keys, you derive the exact parameters algebraically from one well-chosen plaintext. Choosing a plaintext with letters that span a wide range of values (like CHEDDAR) maximises the information extracted per query.

2. Step 2

   Brute-force or solve for a and b

   Observation

   I noticed the Affine cipher has only 12 valid multipliers coprime to 26 and 26 additive shifts, giving a total keyspace of 312 combinations, which suggested that brute-forcing all (a, b) pairs against the known plaintext-ciphertext pair from the oracle was faster than solving algebraically.

   Brute-force is faster to write; the algebraic solve is more elegant. For the actual exploit, brute-force. Iterate over all 12 valid a values and 26 b values, encrypt the known plaintext under each key, and find the pair that matches the oracle output.

   python

   python3 - <<'PY'
   from math import gcd
   
   def affine_encrypt(text, a, b):
       result = []
       for ch in text.upper():
           if ch.isalpha():
               x = ord(ch) - ord('A')
               result.append(chr((a * x + b) % 26 + ord('A')))
           else:
               result.append(ch)
       return ''.join(result)
   
   plaintext  = 'CHEDDAR'
   ciphertext = 'ADWLLEJ'  # replace with actual output from the service
   
   for a in range(1, 26):
       if gcd(a, 26) != 1:
           continue
       for b in range(26):
           if affine_encrypt(plaintext, a, b) == ciphertext:
               print(f'Found: a={a}, b={b}')
   PY

   Copied!

   Expected output

   Found: a=11, b=4

   What didn't work first

   Tried: Including a=1 or a=13 in the brute-force range without filtering by gcd

   a=1 is a valid multiplier (it is coprime to 26) but it reduces the cipher to a pure Caesar shift, which may still match if the real key happens to be a=1. a=13 is NOT coprime to 26 (gcd(13,26)=13), so including it produces a non-bijective mapping where multiple plaintext letters collide on the same ciphertext - the brute-force loop would find a spurious match that decrypts to garbage. The gcd(a, 26) != 1 guard in the loop is required, not optional.

   Tried: Hardcoding the example values a=11, b=4 from this page into the decrypt script without running the brute-force against the actual service output

   The service randomises the key each session, so a=11 and b=4 are illustrative values that will not match a live instance. You must capture the actual ciphertext returned by the oracle for your session, run the brute-force against that ciphertext, and use whichever (a, b) the loop prints before moving to the decryption step.

   Learn more

   The constraint that a must be coprime to 26 ensures that the cipher is a bijection - every letter maps to a unique ciphertext letter and the mapping is reversible. If gcd(a, 26) != 1, multiple plaintexts would map to the same ciphertext, making decryption impossible. Python's math.gcd function checks this efficiently.

   The brute-force only needs to check 312 combinations, which takes milliseconds. But for two known pairs you can solve analytically: subtract the two equations to isolate a, compute the modular inverse with pow(p1 - p2, -1, 26), then find b. The three-arg pow(x, -1, m) form requires Python 3.8+; on older Pythons use the extended Euclidean algorithm (see the Python for CTF guide for the snippet). Both approaches give the same answer; brute-force is more readable for short code.

3. Step 3

   Decrypt the target cheese and submit

   Observation

   I noticed the encryption formula E(x) = (a*x + b) mod 26 is algebraically invertible once a and b are known, which suggested applying the decryption formula D(y) = a_inv * (y - b) mod 26 using Python's pow(a, -1, 26) to recover the plaintext cheese name.

   With a and b known, compute the decryption formula: D(y) = a_inv * (y - b) mod 26 where a_inv is the modular inverse of a modulo 26. Apply this to every letter of the encrypted challenge cheese to recover the plaintext, then submit it.

   python

   python3 - <<'PY'
   a, b = 11, 4          # example values; use your discovered a and b
   a_inv = pow(a, -1, 26)
   
   target = 'ENCRYPTED_CHEESE_HERE'  # paste the challenge output
   
   result = []
   for ch in target.upper():
       if ch.isalpha():
           y = ord(ch) - ord('A')
           result.append(chr(a_inv * (y - b) % 26 + ord('A')))
       else:
           result.append(ch)
   print(''.join(result))
   PY

   Copied!

   What didn't work first

   Tried: Using the encryption formula D(y) = (a*y + b) % 26 to decrypt instead of the inverse formula

   Applying the forward Affine formula to the ciphertext just re-encrypts it, producing a doubly-encrypted string that is not the original cheese name. Decryption requires the inverse: multiply by a_inv (the modular inverse of a, not a itself) and subtract b before reducing mod 26. Using pow(a, -1, 26) to get a_inv is the critical step that distinguishes decryption from encryption.

   Tried: Applying integer division instead of modular inverse to undo the multiplier

   In modular arithmetic, division does not exist - you cannot simply divide both sides by a to isolate the plaintext. For example, if a=11 and the target value mod 26 is 22, then 22/11=2 looks correct, but the actual inverse is pow(11,-1,26)=19 and 19*22 mod 26=10, which is a completely different letter. Integer division discards the modular structure and produces wrong plaintexts for most letters.

   Learn more

   The decryption formula for the Affine cipher is the algebraic inverse of the encryption: D(y) = a_inv * (y - b) mod 26, where a_inv is the modular multiplicative inverse of a modulo 26. For example, if a = 11, then a_inv = 19 because 11 * 19 = 209 = 8 * 26 + 1 ≡ 1 (mod 26). Python's pow(a, -1, 26) computes this directly.

   One subtlety: the modulo operation in Python on negative numbers always returns a non-negative result (e.g., -1 % 26 == 25), so (y - b) % 26 handles the case where y < b correctly without any special-casing. In languages where modulo can return negative values (like C), you need to add 26 before taking the modulo when the result might be negative.

   After recovering the plaintext cheese name, type or paste it into the running netcat session when the service prompts for your guess. The server compares it to the secret and, on a match, prints the flag.

Flag

Encrypt CHEDDAR (or any known cheese), recover a and b by brute-force or algebra, then apply D(y) = a_inv * (y - b) mod 26 to the target ciphertext.