angstrom CTF 2022

TL;DR

提出した数値を復号して(秘密鍵を指数としてべき乗する)、AESで暗号化するスクリプトが動いている
AESで暗号化する際にパディングが施され、PKCS#7であることからバイト数が16の倍数なら、暗号文が16バイト伸びる
これをOracleにしてOAEPに対するPadding Oracle Attackの1つであるManger's Attackが出来る

Prerequisite

Manger's Attack(下で軽く解説)

Writeup

次のようなスクリプトが動いている

from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Util.Padding import pad
from Crypto.Random import get_random_bytes
from Crypto.Cipher import AES
from secret import flag, d

assert len(flag) < 256

n = 0xbb7bbd6bb62e0cbbc776f9ceb974eca6f3d30295d31caf456d9bec9b98822de3cb941d3a40a0fba531212f338e7677eb2e3ac05ff28629f248d0bc9f98950ce7e5e637c9764bb7f0b53c2532f3ce47ecbe1205172f8644f28f039cae6f127ccf1137ac88d77605782abe4560ae3473d9fb93886625a6caa7f3a5180836f460c98bbc60df911637fa3f52556fa12a376e3f5f87b5956b705e4e42a30ca38c79e7cd94c9b53a7b4344f2e9de06057da350f3cd9bd84f9af28e137e5190cbe90f046f74ce22f4cd747a1cc9812a1e057b97de39f664ab045700c40c9ce16cf1742d992c99e3537663ede6673f53fbb2f3c28679fb747ab9db9753e692ed353e3551
e = 0x10001
assert pow(2,e*d,n)==2

enc = pow(bytes_to_long(flag),e,n)
print(enc)

k = get_random_bytes(32)
iv = get_random_bytes(16)
cipher = AES.new(k, AES.MODE_CBC, iv)

while 1:
	try:
		i = int(input("Enter message to sign: "))
		assert(0 < i < n)
		print("signed message (encrypted with military-grade aes-256-cbc encryption):")
		print(cipher.encrypt(pad(long_to_bytes(pow(i,d,n)),16)))
	except:
		print("bad input, exiting")

最初にフラグをRSAで暗号化したものが与えられる。その後、次のような署名(なのか? 検証が出来ない気がするので)サービスが特に使用回数の制限無く動いている。

数値$i$を受け取る
$i^d \mod n$を計算する、ここで$d$はRSAの秘密鍵である
2の結果をバイト表現にし、PKCS#7によるパディングを施してAESで暗号化した結果を渡す

注目すべきはAESによる暗号化を行う際にパディングが施されるところで、これによって暗号文を受け取った際に平文の大きさがある程度推測出来る。

PKCS#7は暗号文の長さが16の倍数で無い時は足りない分のバイトを末尾に足すことで補うが、16の倍数の時は何もしないのでは無く、\x10を16個並べたものを末尾に付与する。よって、もしpow(i,d,n)が2040bit(255バイト)より大きく、バイト表現にした際に256バイトとなるなら、返ってくる暗号文は272バイトとなる。

これをオラクルとするのがManger's Attackで、正確にはRSA公開鍵$N$の「バイト」長を$k$とした時にRSAの復号結果が$2^{8(k-1)}$以下か、それより大きいかが判定出来るオラクルが存在する時に、平文の候補を区間を狭める形で$O(\log N)$程度で探索出来る。

現実のケースではあるOAEPの仕様で先頭に識別子を埋め込む都合上、そこが壊れている場合はエラーを吐くという実装になっている場合がこのオラクルに相当する。

なおManger's Attackの詳しい動作原理や実装に関してはこのWriteupの最後に様々なリンクを貼っておくのでそちらを参照して頂きたい。

というわけでこのオラクルを利用してManger's Attackを実装し¹、スクリプトを走らせるとだいたい15分ぐらいでフラグを入手出来る。

Code

from pwn import remote
import sys
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes, bytes_to_long
from xutil.misc import conn_info


def sign(msg):
    sc.recvuntil(b"Enter message to sign: ")
    sc.sendline(str(msg).encode())
    sc.recvuntil(b"encryption):\n")
    sig = sc.recvline().strip().decode()
    sig = eval(Rf"{sig}")

    return sig


# ceil(numerator / denominator)
def frac_ceil(numerator, denominator):
    if numerator % denominator == 0:
        return numerator // denominator
    return numerator // denominator + 1


L = 256
B = 2**(8*255)

# return c^d mod n < B
def oracle(c):
    sig = sign(c)

    if len(sig) > L:
        return False

    return True


def attack(c, pubkey):
    # prepare parameters
    n, e = pubkey
    # k = len(long_to_bytes(n))
    # B = 2**(8*(k-1))

    if n < 2*B:
        raise ValueError("Failed...")

    # step1
    print("[+] Step1")
    f1 = 2
    while True:
        x = pow(f1, e, n) * c % n
        if oracle(x):
            f1 = 2*f1
        else:
            break

    print("[+] f1 =", f1)

    # step2
    cnt = 0
    print("[+] Step2")
    f2 = (n+B) // B * f1 // 2
    while True:
        if cnt % 1000 == 0:
            print(cnt)
        cnt += 1
        x = pow(f2, e, n) * c % n
        if oracle(x):
            break
        else:
            f2 = (f2 + f1 // 2)
            print(f2)

    print("[+] f2 =", f2)

    # step3
    print("[+] Step3")
    m_max = (n+B) // f2
    m_min = frac_ceil(n, f2)

    cnt = 0

    while True:
        cnt += 1
        f_tmp = 2*B // (m_max - m_min)
        i = f_tmp * m_min // n
        f3 = frac_ceil(i*n, m_min)
        x = pow(f3, e, n) * c % n
        if oracle(x):
            m_max = (i*n + B) // f3
        else:
            m_min = frac_ceil(i*n + B,f3)

        print(f"[{cnt}] width of m:", m_max - m_min)
        if m_max - m_min == 0:
            break

    print(cnt)

    return m_max


n = 0xbb7bbd6bb62e0cbbc776f9ceb974eca6f3d30295d31caf456d9bec9b98822de3cb941d3a40a0fba531212f338e7677eb2e3ac05ff28629f248d0bc9f98950ce7e5e637c9764bb7f0b53c2532f3ce47ecbe1205172f8644f28f039cae6f127ccf1137ac88d77605782abe4560ae3473d9fb93886625a6caa7f3a5180836f460c98bbc60df911637fa3f52556fa12a376e3f5f87b5956b705e4e42a30ca38c79e7cd94c9b53a7b4344f2e9de06057da350f3cd9bd84f9af28e137e5190cbe90f046f74ce22f4cd747a1cc9812a1e057b97de39f664ab045700c40c9ce16cf1742d992c99e3537663ede6673f53fbb2f3c28679fb747ab9db9753e692ed353e3551
e = 0x10001


if len(sys.argv) > 1 and sys.argv[1] == "-l":
    LOCAL = True
else:
    LOCAL = False


if LOCAL:
    host = "localhost"
    port = 13337
else:
    host, port = conn_info("nc challs.actf.co 31500")


sc = remote(host, port)
if LOCAL:
    sc.recvuntil(b"n=")
    n = int(sc.recvline())
enc = int(sc.recvline())

_m = attack(enc, (n, e))
print(long_to_bytes(_m))

"""
[+] Opening connection to challs.actf.co on port 31500: Done
[+] Step1
[+] f1 = 7770675568902916283677847627294075626569627356208558085007249638955617140820833992704
[+] Step2
"""

Flag

actf{the_letters_in_rsa_and_aes_form_aries_if_you_throw_in_the_letter_i_because_that_represents_yourself_or_something_anyway_aries_is_a_zodiac_sign_which_means_that_the_two_cryptosystems_are_mutually_compatble_i_think??}

Resources

実際には1年ぐらい前に実装していたのでそれをコピペして改良しただけだが