Why not login to Qiita and try out its useful features?

We'll deliver articles that match you.

You can read useful information later.

0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

1日1CTFAdvent Calendar 2024

Day 8

ARES (SECCON Beginners CTF 2024) WriteUp

Last updated at Posted at 2024-12-07

はじめに

この記事は 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}

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up

Qiita Advent Calendar is held!

Qiita Advent Calendar is an article posting event where you post articles by filling a calendar 🎅

Some calendars come with gifts and some gifts are drawn from all calendars 👀

Please tie the article to your calendar and let's enjoy Christmas together!

0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?