picoCTF 2025 writeup (Crypto)

picoCTF 2025 の Crypto 問題の Writeup (medium 問題のみ)

Guess My Cheese (Part1)

サーバーに接続すると暗号文が渡される
こちらからチーズの種類名 (例: チェダーチーズ "cheddar") を与えると対応する暗号文が返される
最初に渡された暗号文を解読して送ればフラグが獲得できると考えられる
ヒントなどから Affine 暗号であることが推測される

Affine 暗号とは

各文字に対して線形変換を行う手法
$a, b$ を鍵, $x$ を平文, $E(x)$ を暗号文として以下の式で表現できる

$$E(x) \equiv (a \cdot x + b) \mod m$$

復号は以下

$$x = \equiv a^{-1} \cdot (E(x) - b) \mod m$$

$m$ はアルファベットの文字数 26 となるのが一般的
上記は $x, E(x), m$ が既知の組が二組以上あれば $a, b$ を特定できる

Exploit

一度 "cheddar" を送り, その返り値を元に鍵を特定し, 暗号を解読したらフラグを獲得した
コードは以下の通り

from pwn import *
from Crypto.Util.number import inverse

def affine_guess(enc1: int, enc2: int, plain1: int, plain2: int, m: int=26):
    a = inverse(plain1 - plain2, m) * (enc1 - enc2) % m
    b = (enc1 - a*plain1) % m
    return a, b

def affine_dec(a: int, b: int, enc: str, m: int=26):
    plain = ""
    for i in range(len(enc)):
        plain += chr(((ord(enc[i]) - ord("A") - b) * inverse(a, m)) % m + ord("a"))
    
    return plain
        
host = "verbal-sleep.picoctf.net"
port = 61921

cheese1 = "cheddar"

sh = remote(host, port)

prompt = sh.recvuntil("guess it:")
print(prompt.decode())

cipher = sh.recvline().decode().strip()
print("cipher: ", cipher)

prompt = sh.recvuntil("like to do?")
print(prompt.decode())

sh.sendline("e".encode())

prompt = sh.recvuntil("encrypt?")
print(prompt.decode())

sh.sendline(cheese1.encode())

prompt = sh.recvuntil("cheese:")
print(prompt.decode())

enc_cheese = sh.recvline().decode().strip()

a, b = affine_guess(enc1=ord(enc_cheese[0]) - ord("A"), enc2=ord(enc_cheese[1]) - ord("A"), plain1=ord(cheese1[0]) - ord("a"), plain2=ord(cheese1[1]) - ord("a"))
key = affine_dec(a, b, cipher)
print("key:", key)

prompt = sh.recvuntil("like to do?")
print(prompt.decode())

sh.sendline("g".encode())

prompt = sh.recvuntil("cheese?")
print(prompt.decode())

sh.sendline(key.encode())

sh.interactive()

Guess My Cheese (Part2)

今度はソルト (ハッシュにおいてパスワードの後に付加するセキュリティ用のバイト) が追加されたらしい
sha-256 暗号だがキーのリストが渡されているため, キー + ソルト (ヒントから 0x00 - 0xff のどれかのバイト) の組についてハッシュ値と平文の組を作っておくと解読できる
以下のコードでフラグ獲得

from pwn import *
import hashlib

rainbow = {}
with open("./cheese_list.txt", "r") as f:
    cheese_list = f.readlines()
    for cheese in cheese_list:
        for i in range(0x100):
            salty = cheese.strip().lower().encode() + bytes([i])
            rainbow[hashlib.sha256(salty).hexdigest()] = salty.strip()
            salty = bytes([i]) + cheese.strip().lower().encode()
            rainbow[hashlib.sha256(salty).hexdigest()] = salty.strip()

host = "verbal-sleep.picoctf.net"
port = 57464
sh = remote(host, port)

prompt = sh.recvuntil("guess it:")
print(prompt.decode())

cipher = sh.recvline().decode().strip()
print("cipher:", cipher)

print("hit:", rainbow[cipher])

prompt = sh.recvuntil("like to do?")
print(prompt.decode())

sh.sendline("g".encode())

prompt = sh.recvuntil("my cheese?")
print(prompt.decode())

sh.sendline(rainbow[cipher][:-1])

prompt = sh.recvuntil("my salt?")
print(prompt.decode())

print("key:", rainbow[cipher])
salt_int = int(rainbow[cipher][-1])
salt_hex = f"{salt_int:02x}"
print("salt hex", salt_hex)

sh.sendline(salt_hex.encode())

sh.interactive()

チーズ名をすべて小文字にしているのは試行錯誤の結果 (本来は大文字, 小文字, 原文ママなどすべての通りを一度に試すと楽だった?)