SECCON CTF 2022 Quals Writeup

SECCON CTF 2022 オンライン予選にチーム yharima で参加しました(およそ3年ぶりのCTF)。
全体では49位、domestic では14位でした。二日目に入って地蔵と化してしまったのが反省点です。鍛錬が足りませんでした。

web: skipinx, crypto: pqpq, crypto: this_is_not_lsb だけ解けたので、その writeup を書きます。

web: skipinx

8080番ポートをリッスンしているnginxにリクエストを送ると、リクエストパラメータに proxy=nginx を append した上で web サーバにリクエストが転送される。 web サーバ側では proxy=nginx の指定がなければフラグを表示されるよう実装されているが、web サーバがリッスンしている 3000 番ポートは外からは繋げないので、リクエストパラメータをいじって突破した。

結論から書くと下記のように1000個リクエストパラメータを指定した。

#!/usr/bin/env python3
import requests

url ='http://skipinx.seccon.games:8080/?' + 'a=1&' * 999 + 'proxy=foo'
res = requests.get(url)
print(res.text)

フラグ SECCON{sometimes_deFault_options_are_useful_to_bypa55} でした。

web サーバは express のデフォルトの設定で動いており、マニュアルによると query parser は qs のデフォルト設定が利用されるとありました。 そこで qs のドキュメントを読むと 1000 個までしかパラメータをパースしないと書いてあったので、1000 個パラメータを送り付けることにしました。

For similar reasons, by default qs will only parse up to 1000 parameters

適当なパラメータ 1000 個だと req.query.proxy.includes のところで includes が見つからずエラーとなってしまったので、proxy=foo の指定をそっと忍ばせてフラグを得ました。

crypto: pqpq

RSA 暗号的な p, q, r 3つの素数を使った暗号を解く問題。
この記事を書いていて途中でいろいろ計算を間違えていたことに気づいたが運よく解けていた。。。

次の5つの数字が与えられ、 m を復元するとフラグが得られる。


\begin{aligned}
e &= 2 \cdot 65537 \\
n &= pqr \\
c_1 &= p^e - q^e & (\mathrm{mod} \ n) \\
c_2 &= (p - q)^e & (\mathrm{mod} \  n) \\
c_m &= m^e & (\mathrm{mod} \ n)
\end{aligned}

まず  pq r を求める。

 t = 65537 とすると、次のように計算できる。簡単のため  \mathrm{mod} \ n は省略する。

 
\begin{aligned}
c_2 &= (p - q)^{2t} \\
&= ((p - q)^2)^t \\
&= (p^2 - 2pq + q^2)^t \\
&= p^e + q^e + pqX \\
c_2^2 &= p^{2e} + q^{2e} + pqX' \\
c_1^2 &= p^{2e} + q^{2e} - 2p^eq^e \\
c_2^2 - c_1^2 &= pqX' + 2p^eq^e
\end{aligned}

ただし、 X X' は適当な整数。

つまり、 {c_2}^2-{c_1}^2 を計算すると  pq の倍数が得られる。  n {c_2}^2-{c_1}^2 の最大公約数をとると  pq が求められるので、 n \cdot (pq)^{-1} r も得られる

次に  p q を求める。


\begin{aligned}
c_1 + c_2 &=(p^e - q^e) + (p^e + q^e + pqX) \\
&= 2p^e + pqX
\end{aligned}

なので、 c_1 + c_2 n の最大公約数をとると  p が求められ、 q = pq \cdot q^{-1} q が得られる。
(ここまで書いていて気付いたが、ごちゃごちゃやって  pq を求めずに  c_1 - c_2 n の最大公約数をとって  q を求めたほうが良かった)

オイラーの定理より、 a^{(p - 1)(q - 1)(r -1)} = 1 \ (\mathrm{mod} \  pqr) なので、 td = 1 \ (\mathrm{mod} \ (p - 1)(q - 1)(r - 1) ) となる  d を求めると、次のようにして  m^ 2 を得られる。


(c_m)^d = (m^{2t})^d = (m^2)^{td} = m^2 \ (\mathrm{mod} \ n)

最後に、 p,  q,  r それぞれを modulus とした  m を求めた後、中国の剰余定理を利用して  m を復元できる。 modulus が素数であれば、Modular square root - Prime-Wiki にあるような方法で平方根を求めることができるので、これを利用した。 平方根はそれぞれの modulus に対して二つ出てくるので、計8パターン全て試してフラグが出るものを探した。

最終的なソースコード(クリックで展開)

#!/usr/bin/env python3
from Crypto.Util.number import *
import random

e = 131074
n = 587926815910957928506680558951380405698765957736660571041732511939308424899531125274073420353104933723578377320050609109973567093301465914201779673281463229043539776071848986139657349676692718889679333084650490543298408820393827884588301690661795023628407437321580294262453190086595632660415087049509707898690300735866307908684649384093580089579066927072306239235691848372795522705863097316041992762430583002647242874432616919707048872023450089003861892443175057
c1 = 92883677608593259107779614675340187389627152895287502713709168556367680044547229499881430201334665342299031232736527233576918819872441595012586353493994687554993850861284698771856524058389658082754805340430113793873484033099148690745409478343585721548477862484321261504696340989152768048722100452380071775092776100545951118812510485258151625980480449364841902275382168289834835592610827304151460005023283820809211181376463308232832041617730995269229706500778999
c2 = 46236476834113109832988500718245623668321130659753618396968458085371710919173095425312826538494027621684566936459628333712619089451210986870323342712049966508077935506288610960911880157875515961210931283604254773154117519276154872411593688579702575956948337592659599321668773003355325067112181265438366718228446448254354388848428310614023369655106639341893255469632846938342940907002778575355566044700049191772800859575284398246115317686284789740336401764665472
cm = 357982930129036534232652210898740711702843117900101310390536835935714799577440705618646343456679847613022604725158389766496649223820165598357113877892553200702943562674928769780834623569501835458020870291541041964954580145140283927441757571859062193670500697241155641475887438532923910772758985332976303801843564388289302751743334888885607686066607804176327367188812325636165858751339661015759861175537925741744142766298156196248822715533235458083173713289585866

# 2 * t = e
t = e // 2

# p^2e + q^2e - 2p^eq^e
c1s = (c1 * c1) % n

# p^2e + q^2e + pqX
c2s = (c2 * c2) % n

# pqX + 2p^eq^e
y = c2s - c1s

pq = GCD(y, n)
r = n // pq

# c1 = p^e + q^e + pqX
# c2 = p^e - q^e
# c1 + c2 = 2p^e + pqX
w = c1 + c2

p = GCD(c1 + c2, n)
q = pq // p

phi = (p - 1) * (q - 1) * (r - 1)
d = inverse(t, phi)

m2 = pow(cm, d, n)

def shanks_sqrt(a, p):
    s = p - 1
    e = 0
    while s % 2 == 0:
        e += 1
        s //= 2
    q = s

    x = 1
    while True:
        x += 1
        z = pow(x, q, p)
        if pow(z, 2 ** (e - 1), p) != 1:
            break

    y = z
    r = e
    x = pow(a, (q - 1) // 2, p)
    v = (a * x) % p
    w = (v * x) % p

    while w != 1:
        k = 0
        ww = w
        while ww != 1:
            ww = pow(ww, 2, p)
            k += 1
        d = pow(y, 2 ** (r - k - 1), p)
        y = pow(d, 2, p)
        r = k
        v = (d * v) % p
        w = (w * y) % p
    return v, p - v

rps = shanks_sqrt(m2, p)
rqs = shanks_sqrt(m2, q)
rrs = shanks_sqrt(m2, r)

ip = inverse(q * r, p)
iq = inverse(r * p, q)
ir = inverse(p * q, r)
kp = ip * q * r
kq = iq * r * p
kr = ir * p * q

for rp in rps:
    for rq in rqs:
        for rr in rrs:
            rcm = (kp * rp + kq * rq + kr * rr) % n
            flag = print(long_to_bytes(rcm))

フラグは SECCON{being_able_to_s0lve_this_1s_great!} でした

crypto: this_is_not_lsb

RSA暗号 n,  e とフラグ  mを暗号化した暗号文  c 、フラグ  m のビット数が与えられる。 くわえて、 n のビット数を  b としたときに、上位  b ビット目から見て 0b0011111111 となっているかの真偽値だけを返してくれる。

 m 自体は分からないが、 m に任意の数値  x を掛けることはできるのでこれを利用する。


\begin{aligned}
c &= m^e \ (\mathrm{mod} \ n) \\
(cx^e)^d &= (mk)^{ed} = mx \ (\mathrm{mod} \ n) 
\end{aligned}

復号したときに、パディングがついているかどうかの判定を通る最も大きい値 (0b0011111111111..., 末尾は不明) となるようにすることを考える。 つまり、 mx \lt 2^{b-2} となる  x を求める。 この解を  x^* とすると、 \lfloor 2^{b-2} /x^ * \rfloor = m となりフラグが得られる。

 x^* を見つける際は、 m のビット数が分かっているのでまず大まかに判定が true になる  x を探し、その後は二部探索で判定が切り替わる直前の  x を求めればよい。

最終的なソースコード(クリックで展開)

#!/usr/bin/env python3
from Crypto.Util.number import *
import socket
import random
import re

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('this-is-not-lsb.seccon.games', 8080))

conf = s.recv(1024).decode('utf-8')
print(conf)

def parse_conf(conf):
    m = re.search(r'n = (\d+)', conf)
    n = int(m.group(1))
    m = re.search(r'e = (\d+)', conf)
    e = int(m.group(1))
    m = re.search(r'flag_length = (\d+)', conf)
    flag_length = int(m.group(1))
    m = re.search(r'c = (\d+)', conf)
    c = int(m.group(1))
    return n, e, flag_length, c

n, e, flag_length, c = parse_conf(conf)

def my_judge(x):
    y = (c * pow(x, e, n)) % n
    s.send(f'{y}\n'.encode('utf-8'))
    d = s.recv(1024).decode('utf-8')
    return d.startswith('True')

def calc_bounds():
    b = 1024 - flag_length - 10

    found = False
    for i in range(1, 1024):
        x = i * (2 ** b)
        print(f'iter {i}: {x}')

        judge = my_judge(x)
        if not found and judge:
            print(i)
            found = True
        elif found and not judge:
            print(i)
            break

    l = (i - 1) * (2 ** b)
    r = i * (2 ** b)
    return l, r

def binary_search(l, r):
    while l + 1 < r:
        mid = (l + r) // 2
        print(f'binary search: {mid}')
        judge = my_judge(mid)
        if judge:
            l = mid
        else:
            r = mid
    return l

l, r = calc_bounds()
x = binary_search(l, r)
padding_pos = n.bit_length() - 2
flag = long_to_bytes((0x100 << (padding_pos - 8)) // x)
print(flag)

フラグは SECCON{WeLC0me_t0_tHe_MirRoR_LaNd!_tHIs_is_lSb_orAcLe!} でした