先週土日に開催されていたCircle City Con 2021に出たので自分が解いた問題(OSINTを除く)と、終了後に復習した問題についてのWriteupを書きます。

なお、問題はこちらのリポジトリで公開されています。Writeup付きなので復習や参加していない人もどうぞ。

Table of Contents §

Guardian §

Babyタグが付いているRevだったので簡単な解説に留めます。

フラグを1文字ずつ先頭からチェックし、合っていたらチェックマークを表示、異なっていたところで終了というプログラムが動いている。ということは先頭から文字を決定出来るのでそれをするだけのコードを書いただけ。

問題の性質上「文字種数 x フラグの長さ」の時間がかかるのだが、アホみたいにフラグが長いのがちょっとだけ気に食わなかった。

Flag: CCC{let_m3_thr0ugh!_let_me_p4ss!_d0_y0u_th1nk_y0u_c4n_h3lp_h3r?}

Lonk §

フラグを表示してくれるPythonスクリプトとそれを動かす為のライブラリが与えられる。

じゃあ動かして終わりじゃん...という事はなく、最初の6文字は直ぐ出るものの残りはかなり時間がかかる。

フラグ開示用のスクリプトは長過ぎるので割愛するが、ライブラリの方は次のようになっている

class :
    def __init__(self, n=None):
        self.n = n


def (a):
    h = ()
    c = h
    while a > 0:
        c.n = ()
        c = c.n
        a -= 1
    return h.n


def (a):
    i = 0
    while a:
        i += 1
        a = a.n
    return i


def (a):
    h = ()
    b = h
    while a:
        b.n = ()
        b = b.n
        a = a.n
    return h.n


def (a, b):
    h = (a)
    c = h
    while c.n:
        c = c.n
    c.n = (b)
    return h


def (a, b):
    h = (a)
    c = h
    d = b
    while d:
        c = c.n
        d = d.n
    return c


def (a, b):
    h = ()
    c = a
    while c:
        h = (h, b)
        c = c.n
    return h.n


def (a, b):
    r = (b)
    c = r
    while c.n:
        c = c.n
    c.n = r

    d = r
    c = a
    while c.n:
        d = d.n
        c = c.n

    if id(d.n) == id(r):
        r = None
    else:
        d.n = None

    return r


def (a, b):
    h = ()
    c = b
    while c:
        h = (h, a)
        c = c.n
    return h


def (a, b, m):
    return ((a, b), m)


def (n):
    print(chr((n)), end="", flush=True)

まず注目すべきは一番上のである。内部では最初にhというclassを作りその中に別のを追加している形になる。よって次のような構造になっている

c.n.n.n.n ... .n = 我()

を更に読んでみると最後の空の我()に辿り着くまでの回数が引数で与えたaになっているようである。

残りの関数を読んでみるとはこの回数を返し、は与えられたと同じ長さのを返す。そして以降の関数も解析しようと思ったところで、フラグ開示用のスクリプトの上部だけを抜粋すると次のようになっている

((67))
(((34), (33)))
((((105), (58)), (20)))
(((3), (41)))
(((811), (234)))
(((3), (5), (191)))

これらはCCC{m4に対応する。は与えられたの長さのchrを出力する関数である。ここからそれっぽい演算を(Guessingで)逆算出来ないか試みたところ加算、減算、乗算、余り、法の下でのべき乗である事がなんとなくわかる。

というわけでを引数aを格納するだけのクラスに改造し、残りの関数もそれに対応させたライブラリを作って差し替えたら無事にフラグが出力された。最終的に出来たライブラリは次の通り。

class Structure2:
    def __init__(self, n):
        self.n = n


# a階層の構造を作る
def create(a):
    return Structure2(a)


# 構造が何階層かを返す
def calc(a):
    return a.n


def cp(a):
    return create(calc(a))


def add(a, b):
    return Structure2(a.n + b.n)


def sub(a, b):
    return Structure2(a.n - b.n)


def mul(a, b):
    return Structure2(a.n * b.n)


def mod(a, b):
    return Structure2(a.n % b.n)


def normalpow(a, b):
    return Structure2(pow(a.n, b.n))


def modpow(a, b, m):
    return Structure2(pow(a.n, b.n, m.n))


def dump(n):
    print(chr(calc(n)), end="", flush=True)

※一応断っておくと、加算は自分で解析して、残りも四則演算だろうと当たりを付けたので完全にGuessingで解いたわけではないです。

Flag: CCC{m4Th_w1tH_L1Nk3d_l1$t5}

Poison Prime §

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

import Crypto.Util.number as cun
import Crypto.Random.random as crr
import Crypto.Util.Padding as cup
from Crypto.Cipher import AES
import os
import hashlib


class DiffieHellman:
    def __init__(self, p: int):
        self.p = p
        self.g = 8
        self.private_key = crr.getrandbits(128)

    def public_key(self) -> int:
        return pow(self.g, self.private_key, self.p)

    def shared_key(self, other_public_key: int) -> int:
        return pow(other_public_key, self.private_key, self.p)


def get_prime() -> int:
    p = int(input("Please help them choose p: "))
    q = int(
        input(
            "To prove your p isn't backdoored, "
            + "give me a large prime factor of (p - 1): "
        )
    )

    if (
        cun.size(q) > 128
        and p > q
        and (p - 1) % q == 0
        and cun.isPrime(q)
        and cun.isPrime(p)
    ):
        return p
    else:
        raise ValueError("Invalid prime")


def main():
    print("Note: Your session ends in 30 seconds")

    message = "My favorite food is " + os.urandom(32).hex()
    print("Alice wants to send Bob a secret message")

    p = get_prime()
    alice = DiffieHellman(p)
    bob = DiffieHellman(p)

    shared_key = bob.shared_key(alice.public_key())
    assert shared_key == alice.shared_key(bob.public_key())

    aes_key = hashlib.sha1(cun.long_to_bytes(shared_key)).digest()[:16]
    cipher = AES.new(aes_key, AES.MODE_ECB)
    ciphertext = cipher.encrypt(cup.pad(message.encode(), 16))

    print("Here's their encrypted message: " + ciphertext.hex())

    guess = input("Decrypt it and I'll give you the flag: ")
    if guess == message:
        print("Congrats! Here's the flag: " + os.environ["FLAG"])
    else:
        print("That's wrong dingus")


if __name__ == "__main__":
    try:
        main()
    except ValueError as e:
        print(e)

どうやらDH鍵共有が行われていて、それで共有された値から鍵を決定し、メッセージを暗号化した結果をくれる。これを復号した結果がメッセージと一致すればフラグが表示される。

普通のDH鍵共有問題と異なるのは法である素数pをこちらから指定出来ることである。但し、次の条件がある。

  • pは素数
  • p - 1の素因数で128bit以上の素数qも同時に与える

この問題の鍵となるのはDH鍵共有の際に開示される公開鍵が公開されていないことである(は秘密鍵)。ということは離散対数問題を解けるようなpを提出しても特に使い所は無い。

となると考えられるのはにおけるg (= 8)の位数が小さくなるようなpを提出することである。gの位数が小さいのであればDH鍵共有で共有される値が取りうる範囲も少なくなり、鍵を総当り出来る。

というわけでとなるが小さくなるようなの導出を目指す。

右辺を移項してから左辺を因数分解すると次のようになる。ここでであることを利用した。

$$ (2^e - 1)((2^e)^2 + 2^e + 1) \equiv 0 \bmod p $$

これよりとなるのでを計算し、素因数に大きなが現れるものを探す。FactorDB等を利用しても良かったのだが、面倒なので10000000までの素数で雑に割って出てきた因数の内、一番大きい数が素数であるかを判定して探した。

こうやって求めたの中からが大きな素因数を持つものを探した。これは見つかったの数がそこまで多くなかったのでFactorDBに突っ込んで判定した。

これでの時のが条件を満たす事がわかったので素因数であるqと一緒に提出して暗号文を総当りで復号した。

使用したスクリプトは次の通り

import Crypto.Util.number as cun
import Crypto.Random.random as crr
import Crypto.Util.Padding as cup
from Crypto.Cipher import AES
import os
import hashlib
from pwn import remote
from xcrypto.prime import create_sieve, is_prime

sieve = create_sieve(10000000)
primes = []
for i, is_p in enumerate(sieve):
    if is_p:
        primes.append(i)
print("[+] primes are created")


def easy_factorize(n):
    factors = []
    for p in primes:
        while n % p == 0:
            n //= p
            factors.append(p)

        if n == 1:
            return factors

    return factors + [n]


def get_largest_factor(n):
    return easy_factorize(n)[-1]


def has_large_factor(n):
    large_factor = get_largest_factor(n)
    if large_factor.bit_length() > 128 and is_prime(large_factor):
        return True, large_factor

    return False, None


def search_primes():
    factors = []
    exponent = 128
    two_exp = pow(2, exponent)
    for i in range(1000):
        term = two_exp - 1
        res, p = has_large_factor(term)
        if res:
            print("[+] found:", exponent, p)
            factors.append((p, exponent))
        two_exp *= 2
        exponent += 1

    return factors


# from `search_primes` and factordb.com
def get_params():
    p = 609975771894476528674847741770477550690431975984816508022169315752408668993737964630175742325288277204552613243684812253451253427056346412559151033770967839107719594288877646641877521578455691636766459660797203894013905167748331753651455643293131241572177344321
    e = 881
    q = 15138363943702743414985849001110688007893252776119878248055700358370333679110882929900173580454870111418797892031803506068105088295467180152699913928496417418117370927810699181181027547022238296846731688545530752594436880185320372547

    return p, e, q


if __name__ == "__main__":
    host = "35.224.135.84"
    port = 4000
    sc = remote(host, port)

    p, e, q = get_params()
    sc.recvuntil(b"choose p: ")
    sc.sendline(str(p))
    sc.recvuntil(b"(p - 1): ")
    sc.sendline(str(q))

    sc.recvuntil(b" message: ")
    ct = bytes.fromhex(sc.recvline().strip().decode())
    print(ct)

    for i in range(e):
        shared_key = pow(8, i, p)
        aes_key = hashlib.sha1(cun.long_to_bytes(shared_key)).digest()[:16]
        cipher = AES.new(aes_key, AES.MODE_ECB)
        pt = cipher.decrypt(ct)
        if pt[:11] == b"My favorite":
            print("[+] Found!!")
            pt = cup.unpad(pt, 16)
            print(pt)
            break


    sc.recvuntil(b"the flag: ")
    sc.sendline(pt)

    sc.interactive()

Flag: CCC{sm0l_subgr0up_w1th_a_m3rs3nn3_pr1m3}

4番目に解いたので惜しくも3rd Bloodを逃した、Web勢とPwn勢が1st~3rd Bloodを取っていたのでCryptoも取りたかった。

No Stone Left Unturned §

この問題は解けませんでしたが、終了後にCTFのDiscordからWriteupを回収して復習しました

次のようなスクリプトとその実行結果が与えられる。

from gmpy2 import next_prime, is_prime
import random, os, sys

if __name__ == "__main__":
    random.seed(os.urandom(32))
    p = next_prime(random.randrange((1<<1024), (1<<1024) + (1<<600)))
    pp = (p * 7) // 11
    q = next_prime(random.randrange(pp - (1<<520), pp + (1 << 520)))
    with open(sys.argv[1], "rb") as f:
        flag = int.from_bytes(f.read(), "big")
    assert is_prime(p)
    assert is_prime(q)
    N = p * q
    assert flag < N
    e = 0x10001
    c = pow(flag, e, N)
    with open("out.txt", "w") as f:
        f.write(f"N = {hex(N)}\n")
        f.write(f"e = {hex(e)}\n")
        f.write(f"c = {hex(c)}\n")


RSAだがとなっている(ここでである)。

今回はどちらも如何にもな近似が出来るのだが、使うのはの方でとなり、が520bitとそこまで大きくない事からとすることが出来る。

ということはは近い2数の積となっている事からフェルマー法が適用出来る。

※一見この2数の差であるは520bit程度と大きいように見えるが、実はフェルマー法は有効(と因数分解を試みた時にの増加に対してぐらい増加するため)。これに引っかかって当日はチームメイトと共にフェルマー法を棄却してしまった。

使用スクリプトは次の通り

from Crypto.Util.number import long_to_bytes
from xcrypto.rsa import dec_pq
from xcrypto.prime import fermat_method
from math import isqrt


if __name__ == "__main__":
    N = 0xa2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba93f56d1e890d1827d8ae8d40172a2dfafaa73523dd318c608bd4169d702442e6d153ae0637766f635255f4c1ee6bc694589b2708ae9061fb84f9db9da7199996c519635decfb53b4ccfde2bf9e89f70de9172bd370be887e8e1009b278774ee2449ce3ea3b76428506b4a98beda6e3c9aabbf1164e088f27554282d7909ef2ae61fb5316e705e3ea72cba9df06af06e54c3ee898dab8ed245e26290f59feeec9f58e61c4a2051086234fe48b42399a74452b87829da28f3e88a5a4b01b72d045b296297a3da34b9a5c20cb
    e = 0x10001
    c = 0x2d1f77201435e00d3355246cc4de54b3c98a801f688500ff1e824d985f225f95415019188af01c39c80393e648e5e51bab80e1abfda82a74490fe58ef82afde4bed2999b10ac71f241f20564f5d2461cd57b50033c0fe64319b246ad241846b2ab37328f83d0a77fe5c3564cec18dbc577fdacad417925d208735d8b916779f567ef863dba594d9d035c99e6210db9397797c10e900a1d4a3bce2f87502c23f2e909808c10ac675affb41b3e0769360c959289338ce2877813c723524718d84a75b2209ba4f3560fcbc82da69d6b2f86c32970b325ec034a060fc62f6b3a97ae01cdfc8aeb35df03d92af88a7b60831254095fb66ce73b2c5941440721899dc1

    _n = 7*11*N
    p, q = fermat_method(_n)
    print(p, q)
    if p % 7 == 0:
        p //= 7
        q //= 11
    else:
        p //= 11
        q //= 7

    assert p*q == N
    print(long_to_bytes(dec_pq(c, p, q, e)))

Flag: CCC{b4d_j0k3s_4b0ut_ferm4t's_f1rst_n4m3}

ちなみに解いていた時は未知数が小さいので多変数Coppersmithだと思っていた。式変形をしまくっていたが結局上手くいかずに12時間無駄にした。

感想 §

個人的に簡単すぎず難しすぎずちょうど良い難易度のCTFでした。最近は難しいCTFが多くて辛いです。