Guess My Cheese (Part 1) picoCTF 2025 Solution

Description

1. Step 1Use the encryption oracle to identify the cipher
   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!
   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 2Brute-force or solve for a and b
   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!
   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 3Decrypt the target cheese and submit
   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!
   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.