Guess My Cheese (Part 1)

Challenge

Link	Difficulty	Status
https://play.picoctf.org/practice/challenge/473?category=2&originalEvent=74&page=1

Note

Description

Try to decrypt the secret cheese password to prove you’re not the imposter! Connect to the program on our server: nc verbal-sleep.picoctf.net 56466

Solution

On connecting to the server we get this. For this challenge I had to use the hint as I had no idea what was this cipher.

Note

Hint

Remember that cipher we devised together Squeexy? The one that incorporates your affinity for linear equations???

A quick google search for a cipher that is based on linear equations and we land on Affine cipher.

Looking at the image below, we know that there are two params A (slope) and B(intercept) that can be tuned to cipher and decipher the text. Now our goal is to figure out these two values used in the above challenge.

For this I am going to use the encrypt a cheese option to get a cipher text for the plaintext I enter which will help me figure out A and B as I can bruteforce A and B until I get the same plaintext/ciphertext.

I tried to encrypt Parmesan but it looks like it only know a certain set of cheese or only cheese in capital case. After a few tries I could get it to work with Pecorino and I got the cipher text like below. Now it’s time to bruteforce the values of A and B. I wrote this little helper script to bruteforce the ciphertext (with help from the Internet).

function areCoprime(a, m) {
 
  const gcd = (x, y) => {
 
    while (y) {
 
      const t = y;
 
      y = x % y;
 
      x = t;
 
    }
 
    return x;
 
  };
 
  return gcd(a, m) === 1;
 
}
 
function modInverse(a, m) {
 
  for (let i = 1; i < m; i++) {
 
    if ((a * i) % m === 1) {
 
      return i;
 
    }
 
  }
 
  return 1;
 
}
 
function charToNum(char) {
 
  return char.toUpperCase().charCodeAt(0) - 65;
 
}
 
function numToChar(num) {
 
  return String.fromCharCode((num % 26) + 65);
 
}
 
function decryptAffine(ciphertext, a, b) {
 
  const m = 26;
 
  let plaintext = "";
 
  const aInverse = modInverse(a, m);
 
  for (let i = 0; i < ciphertext.length; i++) {
 
    const char = ciphertext[i];
 
    if (!/[a-zA-Z]/.test(char)) {
 
      plaintext += char;
 
      continue;
 
    }
 
    const isUpper = char === char.toUpperCase();
 
    const charNum = charToNum(char);
 
    let decrypted = (aInverse * (charNum - b + m)) % m;
 
    if (decrypted < 0) decrypted += m;
 
    const decryptedChar = numToChar(decrypted);
 
    plaintext += isUpper ? decryptedChar : decryptedChar.toLowerCase();
 
  }
 
  return plaintext;
 
}
 
function bruteforceAffine(ciphertext) {
 
  const m = 26;
 
  for (let a = 1; a < m; a++) {
 
    if (!areCoprime(a, m)) continue;
 
    for (let b = 0; b < m; b++) {
 
      const plaintext = decryptAffine(ciphertext, a, b);
 
      if (plaintext === "PECORINO") {
 
        return {
 
          a,
 
          b,
 
          plaintext,
 
        };
 
      }
 
    }
 
  }
 
  return null;
 
}
 
function findPlaintext(ciphertext) {
 
  const result = bruteforceAffine(ciphertext);
 
  return result;
 
}
 
function main() {
 
  const ciphertext = process.argv[2];
 
  console.log("Attempting to bruteforce affine cipher...");
 
  console.log(`Ciphertext: ${ciphertext}`);
 
  console.log("-".repeat(50));
 
  const result = findPlaintext(ciphertext);
 
  const { a, b, plaintext } = result;
 
  console.log(`Keys (a=${a}, b=${b})`);
 
  console.log(`   Plaintext: ${plaintext}`);
 
  console.log("-".repeat(50));
 
}
 
main();

Running the script reveals A = 25 and B = 7. Let us use https://cryptii.com/pipes/affine-cipher to decipher the actual ciphertext. On guessing the cheese with the value from above we get the flag.