Guess My Cheese (Part 1) picoCTF 2025 Solution

Description

1. Step 1Use the encryption oracle to identify the cipher

   Observation

   The service encrypts any cheese name you submit, which makes it a chosen-plaintext oracle. Send a known word such as CHEDDAR, watch how each letter maps, and the two-parameter Affine structure is visible.

   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 anything that is not an uppercase letter, so a lowercase submission comes back empty or mangled with no usable pairs. Submit in uppercase and every character maps to a ciphertext letter.

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

   One pair is one equation in two unknowns, which many key combinations satisfy. Two distinct pairs pin the solution down modulo 26, so submit a plaintext with at least two different letters.

   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

   Observation

   An Affine cipher has 12 valid multipliers and 26 shifts, so 312 keys in total. Testing all of them against the oracle's known pair is faster than solving the equations by hand.

   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 multiplier of 1 is legitimate; it just reduces the cipher to a Caesar shift, and it matches if that is the real key. A multiplier of 13 is not, because it shares a factor with 26, and the mapping stops being one-to-one: several plaintext letters collide on one ciphertext letter and the loop finds a false match that decrypts to garbage. The coprimality guard is required.

   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 key is randomized per session, so any values shown here are illustrative. Capture the ciphertext your own oracle returns, run the brute force against it, and use whatever key the loop prints.

   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

   Observation

   With a and b known, the formula inverts directly: subtract b and multiply by the modular inverse of a, which Python computes with pow(a, -1, 26).

   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

   Running the forward formula over the ciphertext just encrypts it a second time. Decryption needs the inverse: subtract b, then multiply by the modular inverse of a rather than a itself. Computing that inverse is what separates the two directions.

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

   Modular arithmetic has no division, so you cannot divide through by a to isolate the plaintext. With a multiplier of 11 and a value of 15, dividing gives 1, but the real inverse of 11 is 19, and 19 times 15 reduces to 25 mod 26, a different letter entirely. Integer division throws away the modular structure.

   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.