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] (0i<70\le i < 7) とします。また reg[0], reg[5], reg[6] はそれぞれ特殊な使われ方をするため、それぞれ eip, valflag と呼ぶことにします。命令は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] == valreg[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+rp)(q+rq),p=a4,q=b4n = (p + r_p)(q + r_q), p = a^4, q = b^4 となっており、 a,ba, b は256bits, rp,rqr_p, r_q は24bits程度となっています。 p+rp,q+rqp + r_p, q + r_q を求め RSA を復号すればフラグが手に入ります。

    leak(rp, rq) の情報から rpe+rqer_p^e + r_q^e の値が既知なので、 rpr_p について全探索をして rqr_q も24bits 程度になるかどうかを調べることで rp,rqr_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

    (a4+rp)(b4+rq)=(ab)4+rpb4+rqa4+rprq=n(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)^4 が他の項に比べて十分に大きく、 ab=n1/4ab = \lfloor n^{1/4}\rfloor が成り立ちます。これと nn の2式を使うことで整数上の1変数多項式ができ、これを解くことで a,ba, 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

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

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

    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}

      ;