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つの数字が与えられ、 を復元するとフラグが得られる。
まず と を求める。
とすると、次のように計算できる。簡単のため は省略する。
ただし、 と は適当な整数。
つまり、 を計算すると の倍数が得られる。 と の最大公約数をとると が求められるので、 で も得られる
次に と を求める。
なので、 と の最大公約数をとると が求められ、 で が得られる。
(ここまで書いていて気付いたが、ごちゃごちゃやって を求めずに と の最大公約数をとって を求めたほうが良かった)
オイラーの定理より、 なので、 となる を求めると、次のようにして を得られる。
最後に、, , それぞれを modulus とした を求めた後、中国の剰余定理を利用して を復元できる。 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暗号の , とフラグ を暗号化した暗号文 、フラグ のビット数が与えられる。 くわえて、 のビット数を としたときに、上位 ビット目から見て 0b0011111111 となっているかの真偽値だけを返してくれる。
自体は分からないが、 に任意の数値 を掛けることはできるのでこれを利用する。
復号したときに、パディングがついているかどうかの判定を通る最も大きい値 (0b0011111111111..., 末尾は不明) となるようにすることを考える。 つまり、 となる を求める。 この解を とすると、 となりフラグが得られる。
を見つける際は、 のビット数が分かっているのでまず大まかに判定が true になる を探し、その後は二部探索で判定が切り替わる直前の を求めればよい。
▶ 最終的なソースコード(クリックで展開)
#!/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!}
でした