2022-04-11

nullcon HackIM CTF 2022 に参加しました

nullcon HackIM CTF 2022 に参加しました。解いた問題の writeup です。

Texnology (web)

問題は、 LaTeX のドキュメントをコンパイルし、 PDF を生成するウェブサイトです。ヒントとして、 /FLAG にフラグがあることが述べられています。

さて、このサイトの URL に /FLAG を付け加えてアクセスすると、なんとフラグが！

ENO\{L4T3x\_H4ck1Ng\_R3L04D3D\_OK!}

Texnology (Fixed) (web)

先ほどの問題は、設定ミスだったようです。というわけで、この問題では、同様のウェブサイトが与えられますが、フラグの場所が /FLAG.php に変更になっています。

先程のように /FLAG.php に直接アクセスしても、何も表示されません。きっと、 PHP コードの中に書かれているのでしょう。なので、細工をした LaTeX ドキュメントによって、フラグの内容が含まれるような PDF を生成できないか考えてみましょう。

\input{/FLAG.php}

これを渡してみると、 "BLACKLISTED commands used" と言われ、コンパイルをしてくれません。なので、16進数でエスケープをして送ってみます。

^^5c^^69^^6e^^70^^75^^74^^7b^^2f^^46^^4c^^41^^47^^2e^^70^^68^^70^^7d

すると、見事 PDF を生成することができました。 PDF にはフラグが書かれていました。

¡?php /* ENO{L4T3x_H4ck1Ng_R3L04D3D_OK_N0t_BugGy_!}*/ ?¿

cookie lover (crypto)

この問題では、 netcat でアクセスできるサーバーとソースコードが与えられます。サーバーには、2種類のコマンドを送ることができます。

$ nc 52.59.124.14 10301
Choose an option:
1:[text to sign]
2:[number - signature to check]

1番目のコマンドは、文字列を署名に変換して出力します。この実装は次のようになっていました。

def sign(msg: bytes):
    # I will not talk about cookies.
    if b"cookie" in msg:
        return 0
    # no control characters allowed in message
    if any([c < 32 for c in msg]):
        return 0
    return pow(bytes_to_long(msg), key.d, key.n)

このように、文字列を整数にデコードした後、秘密鍵を使って署名します。ただし、文字列に cookie が含まれていたり、制御記号が一文字でも含まれている場合には、署名を作らずに 0 を返します。

2つ目のコマンドは、署名の整数を公開鍵を使って復号し、それが所定の文字列の場合に、フラグを表示します。

msg = 'I love cookies.'

def verify(number : int):
    if str_to_int(msg) == pow(number, key.e, key.n):
        return flag
    else:
        return 'wrong signature'

この2つのコマンドを合わせて考えると、

"I love cookies." を sign し、署名を入手
その署名を verify し、フラグを入手

ということができそうですが、実際にはできません。この文字列は cookie を含んでいるため、前述の sign 処理の条件の部分で引っかかってしまうからです。そこで、この文字列を cookie 含まないようにうまく分割して、 verify コマンドでそれぞれの署名を得て、それらを合成してもとの文字列の署名を作ってみましょう。

sign の処理をもう一度見てみましょう。署名処理では、まず、文字列を整数に変換します。この値を $p$ をすると、署名は、 $p^{d} \pmod n$ となります。もし、 $p$ を $p = a \times b$ となるように $a$ と $b$ に分割した場合、それぞれの署名は、同様に $a^{d} \pmod n$ と $b^{d} \pmod n$ となります。これらを掛け合わせると、 $a^{d} \times b^{d} \equiv (a \times b)^{d} \equiv p^{d} \pmod n$ となり、元の文字列に対応する署名になることが分かります。

cookie も制御文字も含まない $(a, b)$ を見つけたら、サーバーに $a$ , $b$ それぞれを sign して、それらの署名 $a^{d} \pmod n$ と $b^{d} \pmod n$ を得ます。これをかけ合わせると $a^{d} \times b^{d} \equiv p^{d} \pmod n$ となるので、 "I love cookies." の署名が合成できます。さあ、あとはこの合成した署名を verify してフラグが返ってくるのを待つだけです。

#!/usr/bin/python3
import re
import subprocess
import telnetlib

def str_to_int(s):
    return 0 if s == "" else str_to_int(s[:-1]) * 256 + ord(s[-1])

def int_to_bytes(n):
    return b"" if n == 0 else int_to_bytes(n // 256) + bytes([n % 256])

def find_divisors(n):
    output = subprocess.check_output(["factor", str(n)]).decode()
    # (Result) factors = [2, 5, 6673, 189344417922901, 30051184098398543]
    factors = [int(x) for x in output.split()[1:]]
    for i in range(2 ** len(factors)):
        d = 1
        for j in range(len(factors)):
            if i & (1 << j):
                d *= factors[j]
        yield d

def is_good_text(n):
    b = int_to_bytes(n)
    return b"cookies" not in b and not any(x < 32 for x in b)

def send_command(command):
    tn = telnetlib.Telnet("52.59.124.14", 10301)
    tn.read_until(b"2:[number - signature to check]\n\n")
    tn.write(command + b"\n")
    _, _, b = tn.expect([re.compile(b"(.+)\n")])
    return b.decode()

def get_signature(n):
    return int(send_command(b"1:" + int_to_bytes(n)).strip())

def main():
    p = str_to_int("I love cookies.")
    for a in find_divisors(p):
        b = p // a
        if is_good_text(a) and is_good_text(b):
            print(f"{a=}, {b=}")
            a_signature, b_signature = get_signature(a), get_signature(b)
            signature = a_signature * b_signature
            print(f"{signature=}")
            print(send_command(b"2:" + str(signature).encode()))
            return

main()

a=12634953007995183730, b=30051184098398543
signature=67808480752096882249536890417271527142627613650491087661725471919971867955944582924477862606827704344233136001974798815599611141917764508558605210785616800943049588190688360228813427917737623160286185879758208429399327406671416512364422044545949511826290061550101320413848719720537928999458050974184073535139191336296769044679913457014170619008611266188768078578799420634454920122179248074879797193419007860957081995036602650836481729131071134252091588077338994405341109209907633423859402452208912697420356395617569736417967636112535440182905756469627577588341779330083160901013528054035251438405221686660468080640176423454584160789716288974882647721714810303217749405951251170426141701994820549471717843959824969233544689564749464414207707178423044784307361627020990780948084308592823684509498197706848765150061735201967736471705418022613733940059013582699742556194377633571057940431199901531958572646609700948588832990688196060658043001559094901354421322536435804998571004245175847588788171233273863104539370035921203128300441639774220624093786752675323463167095440339285020658839857281338867534871208143283538189316041162027737767059377580921758562540282259065905064706387516496222891114787286170247366010295213961327233365185408193131464458806310283469636091529194795229325269803461018862050674944092619832036525171235235699127720683584072977114008399069674966168803702742501205846961256226743460612166606969195980385385616265321098154236955701536431706137445922719772477646386937596133145696881048908326176103488852469284492234632025608795723288074387134053440377467973163779129670639479786518649949887439504867527321628437729821034523240635779040054100951251048017255851585461952717498282664643126096190010745857067757603775132759124036440226523288733174582280408151176440137773216739713778656007131671124626526335686000056927450923366468344730767097527542965136065862805377662675788432060830035192257319158186668276350657700959162506545155478612719489682371475721110792404318822560283619704328998062129750080860184897746410424784044088519179038243004915261724792793357266347774701745650725509932010969289210425840500177233047937319262792609113102884057001912561513353097360766923317315087014837407682061011961901390200511288636154810071539171188167958371874861160014530811526823260553587941537345110544937642927310735046621449504368521498083518766481227683324427530240319988542878274294284121019487050037099475734804066934272569406411305200755991820552919750
ENO{F4ct0r_and_Conqu3r!}

Shuffle (crypto)

プログラムのソースコードと、その出力結果が与えられます。ソースコードの主要部分は次のとおりです。

# p は [0, 1, 2, ..., 65535] をシャッフルしたもの
p = generate_base(1<<16)

# a, b は 2つのランダムな 256 bit 整数
a = random.randint(0, 1<<256)
b = random.randint(0, 1<<256)

# A は p と同じ長さの配列
# A[i] は p[p[p[...[p[i]]]]] のように p を a 回ネストさせたもの
# B[i] も A[i] と同様
A = pow(p,a)
B = pow(p,b)

# p, A, B を出力
# 出力されたファイルも問題の一部として与えられる
writer = open('output','w')
writer.write('p = %s\nA = %s\nB = %s\n' % (str(p), str(A), str(B)))

# A[A[A[...[A[i]]]]] のように A を b 回ネストさせたものを作り、
# その配列をシリアライズしたものが key_Alice
# key_Bob も同様に B を a 回ネストさせたものをシリアライズしたもの
key_Alice = pow(A,b).to_key()
key_Bob = pow(B,a).to_key()
assert key_Alice == key_Bob

# key_Alice を鍵として flag を AES 暗号化し、その結果を出力する
# enc_flag も問題の一部として与えられる
cipher = AES.new(key_Alice, AES.MODE_CBC, bytes(16))
code = cipher.encrypt(flag.encode() + b'\x00' * (16 - len(flag) % 16))
writer.write('enc_flag = %s' % code.hex())
writer.close()

ここで、出力結果の情報だけから、もし a と b を求めることができれば、 key_Alice を計算することが可能になり、復号が可能になります。したがって、 p, A から a を求めることを考えてみましょう。愚直に、 x を 1 ずつ増やしながら pow(p, x) を計算し、 A と一致するかチェックしていく方法が考えられますが、これだと一生計算が終わりません。なので、もう少し効率のよい方法を考える必要があります。

考察のための簡単な例として p = [1, 2, 0, 4, 3, 5] という順列を考えてみます。これを順にネストさせていくと、

pow(p, 1) = [1, 2, 0, 4, 3, 5]
pow(p, 2) = [2, 0, 1, 3, 4, 5]
pow(p, 3) = [0, 1, 2, 4, 3, 5]
pow(p, 4) = [1, 2, 0, 3, 4, 5]
pow(p, 5) = [2, 0, 1, 4, 3, 5]
pow(p, 6) = [0, 1, 2, 3, 4, 5]
pow(p, 7) = [1, 2, 0, 4, 3, 5]
pow(p, 8) = [2, 0, 1, 3, 4, 5]
pow(p, 9) = [0, 1, 2, 4, 3, 5]
...

というように、6回周期で同じものが現れていることがわかります。さらによく見ると、 $(0, 1, 2)$ で構成される巡回置換のグループは、 [1, 2, 0] → [2, 0, 1] → [0, 1, 2] → [1, 2, 0] →… というように、3回周期で元に戻っています。同様に、 $(3, 4)$ で構成される巡回置換は2回周期、そして $5$ で構成される巡回置換は1回周期となっていることが確認できます。この6回周期というのは、つまり、それぞれの巡回置換の長さの最小公倍数 $LCM(3, 2, 1)$ なのです。

もし A = [2, 0, 1, 4, 3, 5] である場合、 a の解は $5 + 6m$ （ $m$ は任意の正整数）となります。この $5$ というがどこから出てくるのか考えてみましょう。さて、巡回置換 $(0, 1, 2)$ を見ると、対応する [2, 0, 1] というパターンは、 $2 + 3m_1$ 回目（ $m_1$ は任意の正整数）のときに現れていることがわかります。また、巡回置換 $(3, 4)$ の [4, 3] は $1 + 2m_2$ 回目のとき（ $m_2$ は任意の正整数）、巡回置換 $(5)$ は $m_3$ 回目のとき（ $m_3$ は任意の正整数）です。つまり、 a の解は次の方程式を満たせばよいことになります。

$a \equiv 2 \pmod 3$
$a \equiv 1 \pmod 2$
$a \equiv 0 \pmod 1$

この問題は中国剰余問題として知られており、ユークリッド互除法を使った効率的なアルゴリズムも存在します。

さて、ここまでの内容をまとめると、 p と A から a を求めるには次のことをすればよいことがわかります。

p を巡回置換に分解する
それぞれの巡回置換に対応する A の部分列を見て、 $a \equiv r_i \pmod {m_i}$ となる $r_i$ を探す（ $m_i$ は巡回置換の長さ）
得た $(r_1, m_1), ..., (r_c, m_c)$ で中国剰余問題を解く

p と B から b を求める手順も同様です。さあ、これを実装するとこんな感じになります。

#!/usr/bin/python3
import codecs
import hashlib
import Crypto.Cipher.AES
import output  # p, A, B, enc_flag

def decomposite_to_cycles(perm):
    is_visited = [False] * len(perm)
    cycles = []
    for idx in range(len(perm)):
        if is_visited[idx]:
            continue
        size = 0
        idx2 = idx
        while not is_visited[idx2]:
            is_visited[idx2] = True
            idx2 = perm[idx2]
            size += 1
        cycles.append((idx, size))
    return cycles

def extgcd(a, b):
    if b != 0:
        d, y, x = extgcd(b, a % b)
        y -= (a // b) * x
        return d, x, y
    return a, 1, 0

def solve_chinese_remainder(m1, r1, m2, r2):
    d, x, y = extgcd(m1, m2)
    r = (m2 * y * r1 + m1 * x * r2) // d
    m = m1 * (m2 // d)
    return m, r % m

def find_exponent(perm1, perm2):
    cycles = decomposite_to_cycles(perm1)
    period, remainder = 1, 0
    for cid, csize in cycles:
        ax = cid
        for k in range(csize):
            if ax == perm2[cid]:
                period, remainder = solve_chinese_remainder(period, remainder, csize, k)
                break
            ax = perm1[ax]
        else:
            raise Exception(f"Reached to the limit, {cid=}")
    return remainder

def perm_mul(x, y):
    return [y[x[idx]] for idx in range(len(x))]

def perm_pow(perm, k):
    res = list(range(len(perm)))
    base = list(perm)
    while k > 0:
        if k & 1:
            res = perm_mul(base, res)
        base = perm_mul(base, base)
        k >>= 1
    return res

def get_key(perm):
    b = next(b for b in range(len(perm)) if 256**b > len(perm))
    return hashlib.sha256(b"".join(x.to_bytes(b, "big") for x in perm)).digest()

def main():
    flag = codecs.decode(output.enc_flag, "hex")
    a = find_exponent(output.p, output.A)
    b = find_exponent(output.p, output.B)
    alice = get_key(perm_pow(output.A, b))
    cipher = Crypto.Cipher.AES.new(alice, Crypto.Cipher.AES.MODE_CBC, bytes(16))
    print(f"{a=}, {b=}")
    print(cipher.decrypt(flag).decode())

main()

この出力は次のようになりました。

a=672989656291771592391205967, b=208588402018547701153476749
ENO{maybe_y0u_shou1d_use_an0ther_group_for_DH}