ACTF 2022 Writeup

Tue Jun 28 2022

6/25-6/27 で開催していた ACTF 2022 に参加しました。結果は 31st/310 でした (得点のあるチームのみカウント)。

最近は7月末にある ISUCON に向けてあれこれ勉強していて CTF から離れていたのですが、来週に Google CTF があることからリハビリがてら参加しました。 Crypto をやるつもりでしたがいつの間にか Rev をやっていました… 解いた問題について writeup を書きます。

Crypto

retros

3 solves

この問題は前半部分と後半部分に分かれていて、前半は Crypto、後半は Rev になっています。

前半部分の Crypto パートは AES CBC モードで padding oracle attack をする典型問題ですので省略します。注意点としては \n を入力するとヌル終端されてしまうため、 \n が生じないように工夫する (祈る) 必要があります。 PKCS#7 の padding として適切かつヌル終端されている復号結果になれば前半部分突破です (しかしこの条件を満たせば何でもいいわけではないということが後半部分でわかります)。

後半部分は AES で復号した結果のバイト列を使った VM が実装されています。0から31までの数字を含んでいる長さ32の配列 (以下 table と呼びます) がランダムに生成されるので、これらの数字を入れ替えるなどしてソートができればフラグが手に入ります。こういう動作をするようなバイト列に復号される入力を作れればクリアです (DEFCON で似たようなことやったな)。

レジスタに相当するものが7つあります。これを reg[i] ( $0\le i < 7$ ) とします。また reg[0], reg[5], reg[6] はそれぞれ特殊な使われ方をするため、それぞれ eip, val と flag と呼ぶことにします。命令は10種類あり、それぞれ以下のような動作をします。

0 (0args) table が sort されているかチェックする
1 (2args) reg[i] += val (i != 3, 4)
2 (2args) reg[i] -= val (i != 3, 4)
3 (3args) reg[i] = table[reg[j]] (i = 3, 4, j = 1, 2)
4 (3args) table[reg[i]] = reg[j] (i = 1, 2, j = 3, 4)
5 (3args) val = 16 * x + y (x, y は入力値)
6 (3args) if flag != 0: val = 16 * x + y (x, y は入力値)
7 (1arg ) flag = table[reg[2]] <= table[reg[1]]
8 (2args) flag = val <= reg[i] (0 <= i < 7)
9 (2args) val = reg[i] (0 <= i < 7)

これらの命令を駆使して table のソートをします。1つの命令、1つの引数に4bit使われるのと、復号結果は最大30bytes使われることから、60個の命令・引数を使えます。

4の命令を見ると table への代入は reg[3] か reg[4] からしかできない上 reg[3], reg[4] には3の命令からしか代入できないため、 table 内での値を入れ替えていく必要があります。バブルソートや挿入ソートが使えそうだなと思ってあれこれ作ってみましたが、60個以内に抑えることが出来ませんでした… (※作ろうとしていたとき、 reg[5] == val や reg[6] == flag であることに気づいていなかったため、いい方法を見逃していたかも)

そこで、確率的に成功するのでもいいかなということで、 table[0] と table[table[0]] を入れ替えていき、 table[0] が0になったら終了するというアルゴリズムに方針転換しました。こうすることで for 文は前述したソートアルゴリズムでは2個必要だったのが1個だけで済むようになり、60個以内の制約を難なく満たせました。成功確率はだいたい1/32だと思います。このアルゴリズムをそれっぽく書くと以下のようになります。

label: first
    reg[3] = table[reg[1]]
    val = 1
    flag = val <= reg[3]
    val = 0
    if flag == 1: val = offset_to_continue
    reg[0] += val

label: last
    check

label: continue
    reg[3] = table[reg[1]]  # 省略可
    val = reg[2]
    reg[2] -= val
    val = reg[3]
    reg[2] += val

    reg[4] = table[reg[2]]
    table[reg[2]] = reg[3]
    table[reg[1]] = reg[4]

    val = 1
    reg[5] += val
    val = offset_to_first
    reg[0] -= first

これを数字に置き換え、バイト列に変換すると以下のようになります。

payload = [
    3, 3, 1,
    5, 0, 1,
    8, 3,
    5, 0, 0,
    6, 0, 4,  # 次の命令で1個先に飛ぶ
    1, 0,

    0,

    3, 3, 1,
    9, 2,
    2, 2,
    9, 3,
    1, 2,

    3, 4, 2,
    4, 2, 3,
    4, 1, 4,

    5, 0, 1,
    1, 5,
    5, 11, 12,  # 次の命令で47個上に戻る
    2, 0,
]

payload += [0] * (62 - len(payload))
payload += [0, 1]
target = b""
for i in range(0, 64, 2):
    target += bytes([payload[i] * 16 + payload[i+1]])
# b'3\x15\x01\x83P\x06\x04\x10\x031\x92"\x93\x124$#AE\x01\x15[\xc2\x00\x00\x00\x00\x00\x00\x00\x00\x01'

復号結果がこれになるように padding oracle attack が上手くいくのを祈り、ソートも上手くいくのを祈ると、フラグが手に入りました。

ACTF{AES_Padding_Orcale&Sorting_Algorithm|Any_bugs_in_program?}

secure connection

22 solves

通信のプロトコルが実装されており、送受信されているバイト列が与えられています。後半部分の送受信パケットは暗号化されているのでそれを復号する問題です。

プロトコルの実装を見ると、 AES CCM モードで暗号化されています。この AES の key は乱数列を事前に共有されている鍵 (numeric_key_bytes) で暗号化したもので生成されます。この事前に共有されている鍵が実は脆弱でパターンがかなり少ないため、全探索で探すことができます。配布ファイルでいうと以下の場所です。

    numeric_key = int(input("Shared numeric key > "))
    numeric_key = numeric_key % 0x1000000
    state.numeric_key = numeric_key
    state.numeric_key_bytes = (numeric_key).to_bytes(16, "little")

パケットの値と整合性の取れる numeric_key を以下で全探索します。

for numeric_key in tqdm(range(0x1000000)):
    numeric_key_bytes = numeric_key.to_bytes(16, "little")
    tmp = secure_confirm(numeric_key_bytes, MRandom, b"\x00" * 16, b"\xff" * 16)
    if tmp[:14] == MConfirm:
        print(numeric_key, numeric_key_bytes)
        break

これさえわかれば後半のパケットもすべて復号でき、最後のほうのやり取りでフラグを見つけられました。

ACTF{[email protected]}

※余談ですが、 AES CCM モードを知らず、これを使った問題だと最初勘違いしており、実装をだいぶ追ってしまっていました…ここで供養しておきます。

# CCM mode の確認
import struct
from pwn import xor
from Crypto.Util.number import long_to_bytes

key = b"\x00" * 16
nonce = int(4).to_bytes(13, "little")
msg = b"hogetarofugafuga"
cipher = AES.new(key=key, mode=AES.MODE_CCM, nonce=nonce)
expected = cipher.encrypt(msg)

cipher = AES.new(key=key, nonce=struct.pack("B", 15 - len(nonce) - 1) + nonce, mode=AES.MODE_CTR)
s_0 = cipher.encrypt(b"\x00" * 16)
assert cipher.encrypt(msg) == expected

cipher = AES.new(key=key, mode=AES.MODE_ECB)
assert xor(msg, cipher.encrypt(b"\x01" + nonce + long_to_bytes(1, 2))) == expected

RSA LEAK

37 solves

task.py
from sage.all import *
from secret import flag
from Crypto.Util.number import bytes_to_long


def leak(a, b):
    p = random_prime(pow(2, 64))
    q = random_prime(pow(2, 64))
    n = p*q
    e = 65537
    print(n)
    print((pow(a, e) + pow(b, e) + 0xdeadbeef) % n)


def gen_key():
    a = randrange(0, pow(2,256))
    b = randrange(0, pow(2,256))
    p = pow(a, 4)
    q = pow(b, 4)
    rp = randrange(0, pow(2,24))
    rq = randrange(0, pow(2,24))
    pp = next_prime(p+rp)
    qq = next_prime(q+rq)
    if pp % pow(2, 4) == (pp-p) % pow(2, 4) and qq % pow(2, 4) == (qq-q) % pow(2, 4):
        n = pp*qq
        rp = pp-p
        rq = qq-q
        return n, rp, rq
    
n, rp, rq = gen_key()
e = 65537
c = pow(bytes_to_long(flag), e, n)
print("n =", n)
print("e =", e)
print("c =", c)
print("=======leak=======")
leak(rp, rq)

$n = (p + r_p)(q + r_q), p = a^4, q = b^4$ となっており、 $a, b$ は256bits, $r_p, r_q$ は24bits程度となっています。 $p + r_p, q + r_q$ を求め RSA を復号すればフラグが手に入ります。

leak(rp, rq) の情報から $r_p^e + r_q^e$ の値が既知なので、 $r_p$ について全探索をして $r_q$ も24bits 程度になるかどうかを調べることで $r_p, r_q$ が求まります。

leak_n = 122146249659110799196678177080657779971
leak_c = 90846368443479079691227824315092288065
leak_p = 8949458376079230661
leak_q = 13648451618657980711
leak_c -= 0xdeadbeef

leak_phi = (leak_p - 1) * (leak_q - 1)
leak_d = int(pow(e, -1, leak_phi))

# pow(rp, e, leak_n) + pow(rq, e, leak_n) == leak_c
for rp in range(2**24):
    rq = pow(int(leak_c - pow(rp, e, leak_n)), leak_d, leak_n)
    if rq <= 2**24:
        print(rp, rq)
        break
# rp, rq = 405771, 11974933

$(a^4 + r_p)(b^4 + r_q) = (ab)^4 + r_p b^4 + r_q a^4 + r_p r_q = n$ となりますが、 $(ab)^4$ が他の項に比べて十分に大きく、 $ab = \lfloor n^{1/4}\rfloor$ が成り立ちます。これと $n$ の2式を使うことで整数上の1変数多項式ができ、これを解くことで $a, b$ が求まります。

solve.sage
n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
e = 65537
c = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840

# (a^4 + rp) * (b^4 + rq) == n
# (ab)^4 + rp b^4 + rq a^4 + rp rq = n
ab = int(n ** (1 / 4))

PR.<a4, b4> = PolynomialRing(ZZ)
f = ab**4 + rp * b4 + rq * a4 + rp * rq - n
g = a4 * b4 - ab**4
I = PR.ideal([f, g])
basis = I.groebner_basis()

PR.<b4> = PolynomialRing(ZZ)
b4, _ = PR(basis[1]).roots()[0]
b = b4 ** (1 / 4)
assert ab % b == 0
a = ab // b
pp = a ** 4 + rp
qq = b4 + rq
phi = (pp - 1) * (qq - 1)
d = int(pow(e, -1, phi))
print(long_to_bytes(int(pow(c, d, n))))

ACTF{lsb_attack_in_RSA|a32d7f}

impossible RSA

114 solves

server.py
from Crypto.Util.number import *
from Crypto.PublicKey import RSA

e = 65537
flag = b'ACTF{...}'

while True:
    p = getPrime(1024)
    q = inverse(e, p)
    if not isPrime(q):
        continue
    n = p * q;
    public = RSA.construct((n, e))
    with open("public.pem", "wb") as file:
        file.write(public.exportKey('PEM'))
    with open("flag", "wb") as file:
        file.write(long_to_bytes(pow(bytes_to_long(flag), e, n)))
    break

$q$ の生成方法が特殊で、 $q = e^{-1} \mod p$ となっている RSA です。 $p, q$ を求めて復号すればフラグが手に入ります。

問題より $eq = kp + 1$ が成り立ちますが、両辺に $p$ を掛けると $en = kp^2 + p$ となります。左辺は既知なので $k$ の値さえわかれば $p$ を求められます。ここで $k$ は $e$ と同程度の大きさであることを使うと全探索可能なことがわかります。

solve.sage
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes

with open("public.pem", "r") as fp:
    pubkey = fp.read()

with open("flag", "rb") as fp:
    enc = fp.read()


rsa = RSA.import_key(pubkey)
n = rsa.n
e = rsa.e
# eq = kp + 1
# en = kp^2 + p

PR.<p> = PolynomialRing(ZZ)
for k in range(1, 100000):
    f = k * p^2 + p - e * n
    roots = f.roots()
    if len(roots) > 0:
        print(k, roots)
        break
# 46280 [(150465840847587996081934790667651610347742504431401795762471467800785876172317705268993152743689967775266712089661128372295606682852482012493939368044600366794969553828079064622047080051569090177885299781981209120854290564064662058027679075401901717932024549311396484660557278975525859127898004619405319768113, 1)]

p = 150465840847587996081934790667651610347742504431401795762471467800785876172317705268993152743689967775266712089661128372295606682852482012493939368044600366794969553828079064622047080051569090177885299781981209120854290564064662058027679075401901717932024549311396484660557278975525859127898004619405319768113
assert n % p == 0
q = n // p
phi = (p - 1) * (q - 1)
d = int(pow(e, -1, phi))
print(long_to_bytes(int(pow(bytes_to_long(enc), d, n))))

ACTF{F1nD1nG_5pEcia1_n_i5_nOt_eA5y}