Source: SECCON Beginners CTF 2024
Author: ptr-yudai

自由に暗号化と復号化が可能なサーバーがある。

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で暗号化している。復号化はその逆。

    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

RSAで暗号化されたflagが与えられている。RSAの公開鍵とAESの鍵は未知。

サーバーでは暗号化の入力に対してm<nしか見ていないので負数も入力可能。よって、-1を暗号化して復号化することでn-1が取得できる。nが分かったので、任意の平文をRSAで暗号化することが可能に、すなわちAESで暗号化される前の値が分かるようになった。

AES-CBCにおける暗号化と復号化はwikipediaから拝借したこの画像の通り。

enc_flagをAES-CBCで暗号化した値が得られればそれをオラクルに投げることでflagが得られる。つまり、後ろのブロックから順にenc_flagがplaintextとなるようなciphertextを求め、最後に辻褄が合うivを求めれば良い。

具体的には、ある平文と暗号文の組に対して一番最後(k番目)のブロックの復号結果がenc_flagと一致するように暗号文のk-1番目のブロックの値を操作する。そのブロックをAESで復号化した値は入手できるので、それを元にk-2番目のブロックの値を操作する。これを繰り返して最初のブロックの値が分かれば辻褄が合うivを求められる。

これらをsolverに書き起こすとこうなる。

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

def encrypt(m):
    p.sendlineafter('> ', '1')
    p.sendlineafter('m: ', str(m))
    p.recvuntil('c: ')
    return bytes.fromhex(p.recvline().strip().decode())

def decrypt(c):
    p.sendlineafter('> ', '2')
    p.sendlineafter('c: ', c.hex())
    p.recvuntil('m: ')
    return int(p.recvline().strip())

def chunks(data, size):
    return [data[i:i+size] for i in range(0, len(data), size)]

def xor_bytes(data1: bytes, data2: bytes) -> bytes:
    return bytes(a ^ b for a, b in zip(data1, data2))


p = remote('localhost', 5000)

# enc_flag
p.recvuntil('enc_flag: ')
enc_flag = bytes.fromhex(p.recvline().strip().decode())
print('enc_flag:', enc_flag.hex())

# n
n = decrypt(encrypt(-1)) + 1
print('n:', n)

# solve
blocks = chunks(enc_flag, 16)
plain = bytes_to_long(b'A'*16)
rsa = chunks(long_to_bytes(pow(plain, 0x10001, n)), 16)
ares = chunks(encrypt(plain), 16)

for i in range(1, len(blocks)):
  ares[-i-1] = xor_bytes(xor_bytes(ares[-i-1], rsa[-i]), blocks[-i])
  m = pow(decrypt(b''.join(ares)), 0x10001, n)
  rsa = chunks(long_to_bytes(m), 16)

iv = xor_bytes(xor_bytes(ares[0], rsa[0]), blocks[0])
c = b''.join(ares[1:])
flag = decrypt(iv + c)
print(long_to_bytes(flag)[:-16])

理由はよく分からないが、flagが得られたり得られなかったりする。
ctf4b{bl0ck_c1pher_is_a_fun_puzzl3}