はじめに

この記事は 1日1CTF Advent Calendar 2024 の 8 日目の記事です。

問題

ARES (問題出典: SECCON Beginners CTF 2024)

ARES stands for Advanced RSA Encryption Standard.

リポジトリ: https://github.com/SECCON/SECCON_Beginners_CTF_2024/tree/main/crypto/ARES

問題概要

server.py

#!/usr/local/bin/python
import os
from Crypto.Util.number import getStrongPrime
from Crypto.Cipher import AES

N_BITS = 1024

class ARES(object):
    """ARES: Advanced RSA Encryption Standard"""
    def __init__(self, key: bytes, p: int, q: int, e: int):
        self.key = key
        self.n = p * q
        self.e = e
        self.d = pow(self.e, -1, (p-1)*(q-1))

    def encrypt(self, m: int):
        iv = os.urandom(16)
        c1 = int.to_bytes(pow(m, self.e, self.n), N_BITS//8, 'big')
        c2 = AES.new(self.key, AES.MODE_CBC, iv).encrypt(c1)
        return iv + c2

    def decrypt(self, c: bytes):
        iv, c2 = c[:16], c[16:]
        c1 = AES.new(self.key, AES.MODE_CBC, iv).decrypt(c2)
        m = pow(int.from_bytes(c1, 'big'), self.d, self.n)
        return m

if __name__ == '__main__':
    key = os.urandom(16)
    p = getStrongPrime(N_BITS//2)
    q = getStrongPrime(N_BITS//2)
    n = p * q
    e = 65537

    FLAG  = os.getenv("FLAG", "ctf4b{*** REDACTED ***}").encode()
    FLAG += os.urandom(16)
    assert len(FLAG) < N_BITS//8
    m = int.from_bytes(FLAG, 'big')
    c = pow(m, e, n)
    print("enc_flag:", int.to_bytes(c, N_BITS//8, 'big').hex())

    ares = ARES(key, p, q, e)

    print("1. Encrypt with ARES" "\n"\
          "2. Decrypt with ARES")
    while True:
        choice = int(input('> '))
        if choice == 1:
            m = int(input('m: '))
            assert m < n, "Plaintext too big"
            c = ares.encrypt(m)
            print("c:", c.hex())

        elif choice == 2:
            c = bytes.fromhex(input('c: '))
            assert len(c) > 16 and len(c) % 16 == 0, "Invalid ciphertext"
            m = ares.decrypt(c)
            print("m:", m)

        else:
            break

RSA → AES_CBC で暗号化、AES_CBC → RSA で復号化できるオラクルが与えられるので、RSA 単体を解読すればフラグが得られる。また、RSA の公開鍵 $n$ は不明。

考察

暗号化の際、

assert m < n, "Plaintext too big"

と平文が $n$ 以下かを調べているが、下限は設定されていないので負の数を暗号化できる。
よって、$-1$ を暗号化して、その暗号文を復号化すれば $n - 1$ が分かるので、$n$ も分かる。

$n$ がわかった事により、decrypt() 関数の出力 $m$ がわかれば、関数内の $c_1$ を $c_1 \equiv m^e \pmod{n}$ より逆算できる。
理由: $m \equiv {c_1}^d \pmod{n}$ なので、$ed \equiv 1 \pmod{\phi(n)}$ を考えれば $m^e \equiv ({c_1}^d)^e \equiv {c_1}^{de} \equiv c_1 \pmod{n}$

def decrypt(self, c: bytes):
    iv, c2 = c[:16], c[16:]
    c1 = AES.new(self.key, AES.MODE_CBC, iv).decrypt(c2)
    m = pow(int.from_bytes(c1, "big"), self.d, self.n)
    return m

これで任意の出力に対し AES 単体での復号化が可能となる。

あとは Wikipedia の AES_CBC の図を眺めながら、 AES で復号化すると enc_flag となるような暗号文を後ろの方のブロックから順に求めてあげればよい。

solver

from pwn import *
from Crypto.Util.strxor import strxor
from Crypto.Util.number import long_to_bytes

io = process(["python3", "server.py"])

io.recvuntil(b"enc_flag: ")
enc_flag = bytes.fromhex(io.recvline().decode().strip())

print(f"enc_flag: {enc_flag}")


def encrypt(m):
    io.recvuntil(b"> ")
    io.sendline(b"1")
    io.recvuntil(b"m: ")
    io.sendline(str(m).encode())
    io.recvuntil(b"c: ")
    enc = bytes.fromhex(io.recvline().strip().decode())
    return enc


def decrypt(c):
    io.recvuntil(b"> ")
    io.sendline(b"2")
    io.recvuntil(b"c: ")
    io.sendline(c.hex().encode())
    io.recvuntil(b"m: ")
    dec = int(io.recvline().strip())
    return dec


n = decrypt(encrypt(-1)) + 1

print(f"n: {n}")

blocks = [enc_flag[i : i + 16] for i in range(0, len(enc_flag), 16)]

c = b"\xde\xad\xbe\xef\xca\xfe\xba\xbe" * 2  # 16 バイトなら何でもいい
for i in range(len(blocks)):
    m = decrypt(b"\x00" * 16 + c)
    c1 = pow(m, 65537, n)
    c1 = long_to_bytes(c1, len(c))
    c = strxor(c1[:16], blocks[-i - 1]) + c

print(f"c: {c}")

m = decrypt(c)

try:
    print("flag:", long_to_bytes(m)[:-16].decode())
except:
    print("flag:", long_to_bytes(m + n)[:-16].decode())

flag: ctf4b{bl0ck_c1pher_is_a_fun_puzzl3}