1. はじめに
2022/3/19(土)09:00JST ～ 3/20(日)21:00:00JSTに開催された「zer0pts CTF 2022」にチーム「N30Z30N」でソロ参加しました。この記事はその参戦記*1です。
2. 開戦前
競技時間は36時間なので、睡眠・食事・休憩を除き24時間程度はフル稼働できるよう、週前半から体調を調整・・・出来ませんでした。サーセン。実態としては、
- 3/16 Warmupを兼ねてpicoCTF2022を始めた矢先に地震を食らう。ツラ。※幸い物的被害はほぼナシ。
- 3/17 睡眠障害発生、競技中のもぐもぐタイム用に準備した「どらやき」を先行して食してしまう。
- 3/18 前日の反動で寝落ち。しかし夜中に覚醒してしまい体力回復に失敗。
- 3/19 8:30くらいからからパソコン前に座ってドキドキワクワクするつもりが起床事故で8:55に。
という具合にgdgdでした。まぁ、いつものことなのですが。
3. 順調な？滑り出し（Crypto:Anti-Fermat）
Crypto全完を目標（出来るとは言っていない）に、まずはWarmup問から着手。
I invented Anti-Fermat Key Generation for RSA cipher since I'm scared of the Fermat's Factorization Method.
ファイル：「task.py」
from Crypto.Util.number import isPrime, getStrongPrime from gmpy import next_prime from secret import flag # Anti-Fermat Key Generation p = getStrongPrime(1024) q = next_prime(p ^ ((1<<1024)-1)) n = p * q e = 65537 # Encryption m = int.from_bytes(flag, 'big') assert m < n c = pow(m, e, n) print('n = {}'.format(hex(n))) print('c = {}'.format(hex(c)))
ファイル：「output.txt」
n = 0x1ffc7dc6b9667b0dcd00d6ae92fb34ed0f3d84285364c73fbf6a572c9081931be0b0610464152de7e0468ca7452c738611656f1f9217a944e64ca2b3a89d889ffc06e6503cfec3ccb491e9b6176ec468687bf4763c6591f89e750bf1e4f9d6855752c19de4289d1a7cea33b077bdcda3c84f6f3762dc9d96d2853f94cc688b3c9d8e67386a147524a2b23b1092f0be1aa286f2aa13aafba62604435acbaa79f4e53dea93ae8a22655287f4d2fa95269877991c57da6fdeeb3d46270cd69b6bfa537bfd14c926cf39b94d0f06228313d21ec6be2311f526e6515069dbb1b06fe3cf1f62c0962da2bc98fa4808c201e4efe7a252f9f823e710d6ad2fb974949751 c = 0x60160bfed79384048d0d46b807322e65c037fa90fac9fd08b512a3931b6dca2a745443a9b90de2fa47aaf8a250287e34563e6b1a6761dc0ccb99cb9d67ae1c9f49699651eafb71a74b097fc0def77cf287010f1e7bd614dccfb411cdccbb84c60830e515c05481769bd95e656d839337d430db66abcd3a869c6348616b78d06eb903f8abd121c851696bd4cb2a1a40a07eea17c4e33c6a1beafb79d881d595472ab6ce3c61d6d62c4ef6fa8903149435c844a3fab9286d212da72b2548f087e37105f4657d5a946afd12b1822ceb99c3b407bb40e21163c1466d116d67c16a2a3a79e5cc9d1f6a1054d6be6731e3cd19abbd9e9b23309f87bfe51a822410a62
「q = next_prime(p)」であればFermat法が適用できますが・・・という問題です。
しかし悲観することはなく、q≒2の1024乗-pなので、qは
x**2 - 2**1024*x + n = 0
の解x（のうちの小さいほう）で近似できることがわかります。zer0pts CTFにしては優しめ*2の問題で、Warmupとしていい感ということになります。
実際、以下のソルバを使ってフラグをゲットできました。
ソルバ：
from Crypto.Util.number import * import gmpy2 n = 0x1ffc7dc6b9667b0dcd00d6ae92fb34ed0f3d84285364c73fbf6a572c9081931be0b0610464152de7e0468ca7452c738611656f1f9217a944e64ca2b3a89d889ffc06e6503cfec3ccb491e9b6176ec468687bf4763c6591f89e750bf1e4f9d6855752c19de4289d1a7cea33b077bdcda3c84f6f3762dc9d96d2853f94cc688b3c9d8e67386a147524a2b23b1092f0be1aa286f2aa13aafba62604435acbaa79f4e53dea93ae8a22655287f4d2fa95269877991c57da6fdeeb3d46270cd69b6bfa537bfd14c926cf39b94d0f06228313d21ec6be2311f526e6515069dbb1b06fe3cf1f62c0962da2bc98fa4808c201e4efe7a252f9f823e710d6ad2fb974949751 c = 0x60160bfed79384048d0d46b807322e65c037fa90fac9fd08b512a3931b6dca2a745443a9b90de2fa47aaf8a250287e34563e6b1a6761dc0ccb99cb9d67ae1c9f49699651eafb71a74b097fc0def77cf287010f1e7bd614dccfb411cdccbb84c60830e515c05481769bd95e656d839337d430db66abcd3a869c6348616b78d06eb903f8abd121c851696bd4cb2a1a40a07eea17c4e33c6a1beafb79d881d595472ab6ce3c61d6d62c4ef6fa8903149435c844a3fab9286d212da72b2548f087e37105f4657d5a946afd12b1822ceb99c3b407bb40e21163c1466d116d67c16a2a3a79e5cc9d1f6a1054d6be6731e3cd19abbd9e9b23309f87bfe51a822410a62 e = 0x10001 r = gmpy2.iroot(2**2046-n,2)[0] x = 2**1023 - r for i in range(-10000,10000): q = x + i if n % q == 0: p = n // q break d = inverse(e, (p-1)*(q-1)) print(long_to_bytes(pow(c,d,n)).decode())
zer0pts{F3rm4t,y0ur_m3th0d_n0_l0ng3r_w0rks.y0u_4r3_f1r3d}
range(-10000,10000)はいささか広めですが、大勢に影響ないのでヨシ！
この時点では（多少もたつきましたが）、まぁ順調な滑り出しかなぁ、と思っていました。
4. 行き詰まり、Idleモードに切り替え
競技開始時点で、他にCrypto問は
- Karen
- CurveCrypto
が公開されていましたが、
- Karen => 行列問なのでLLLっぽいことするのかなー
- CurveCrypto => 既視感があるけど何処で見たか思い出せないぞ。。。
という具合でボンヤリしていたので、思考を切り替えるため休憩をとってＴＶをつけることに。
しかし、今週こそ新作が放映されるであろうと期待した「ダイの大冒険」はまたしてもベストセレクション。サイバー攻撃許すまじ。ツヨツヨになったら悪・即・BANだ！果たしてレオナ姫のご尊顔を拝することができず、MP切れ。他のことをやりながら解法をゆるゆる考える「アイドリングモード」に移行。
Karenを見ているうちに辻褄が合わないことに気づき、discordを見ると何人か運営にDMしている方がいたのでスコアサーバを確認すると修正版が出ておりDL。
しかし1問も解けないままそのまま時間だけが溶けて行き、夕方以降
- OK
- EDDH
が追加されたのを確認。「OK」を見てみると・・・
「server.py」
from Crypto.Util.number import isPrime, getPrime, getRandomRange, inverse import os import signal signal.alarm(300) flag = os.environ.get("FLAG", "0nepoint{GOLDEN SMILE & SILVER TEARS}") flag = int(flag.encode().hex(), 16) P = 2 ** 1000 - 1 while not isPrime(P): P -= 2 p = getPrime(512) q = getPrime(512) e = 65537 phi = (p-1)*(q-1) d = inverse(e, phi) n = p*q key = getRandomRange(0, n) ciphertext = pow(flag, e, P) ^ key x1 = getRandomRange(0, n) x2 = getRandomRange(0, n) print("P = {}".format(P)) print("n = {}".format(n)) print("e = {}".format(e)) print("x1 = {}".format(x1)) print("x2 = {}".format(x2)) # pick a random number k and compute v = k**e + (x1|x2) # if you add x1, you can get key = c1 - k mod n # elif you add x2, you can get ciphertext = c2 - k mod n v = int(input("v: ")) k1 = pow(v - x1, d, n) k2 = pow(v - x2, d, n) print("c1 = {}".format((k1 + key) % n)) print("c2 = {}".format((k2 + ciphertext) % n))
x1、x2の偶奇が一致していれば、v=(x1+x2)//2と指定することでkey+ciphertextを得ることができます。・・・とここまでは分ったのですが、その先に至ることは出来ませんでした。結果は「NG」。OKなのにNGなんですよ。残念。
5. 既視感により救われた（Crypto:EDDH）
そんなこんなで（仕切りなおすため夜はしっかり寝て）2日目に突入。EDDHに着手しました。
I heard about that EdDSA is more secure than ordinal ECDSA. So ECDH on Edwards Curve too?
「server.py」
from random import randrange from Crypto.Util.number import inverse, long_to_bytes from Crypto.Cipher import AES from hashlib import sha256 import ast import os import signal n = 256 p = 64141017538026690847507665744072764126523219720088055136531450296140542176327 a = 362 d = 1 q = 64141017538026690847507665744072764126693080268699847241685146737444135961328 c = 4 gx = 36618472676058339844598776789780822613436028043068802628412384818014817277300 gy = 9970247780441607122227596517855249476220082109552017755637818559816971965596 def xor(xs, ys): return bytes(x^y for x, y in zip(xs, ys)) def pad(b, l): return b + b"\0" + b"\xff" * (l - (len(b) + 1)) def unpad(b): l = -1 while b[l] != 0: l -= 1 return b[:l] def add(P, Q): (x1, y1) = P (x2, y2) = Q x3 = (x1*y2 + y1*x2) * inverse(1 + d*x1*x2*y1*y2, p) % p y3 = (y1*y2 - a*x1*x2) * inverse(1 - d*x1*x2*y1*y2, p) % p return (x3, y3) def mul(x, P): Q = (0, 1) x = x % q while x > 0: if x % 2 == 1: Q = add(Q, P) P = add(P, P) x = x >> 1 return Q def to_bytes(P): x, y = P return int(x).to_bytes(n // 8, "big") + int(y).to_bytes(n // 8, "big") def send(msg, share): assert len(msg) <= len(share) print(xor(pad(msg, len(share)), share).hex()) def recv(share): inp = input() msg = bytes.fromhex(inp) assert len(msg) <= len(share) return unpad(xor(msg, share)) def main(): signal.alarm(300) flag = os.environ.get("FLAG", "0nepoint{frog_pyokopyoko_3_pyokopyoko}") assert len(flag) < 2*8*n while len(flag) % 16 != 0: flag += "\0" G = (gx, gy) s = randrange(0, q) print("sG = {}".format(mul(s, G))) tG = ast.literal_eval(input("tG = ")) # you should input something like (x, y) assert len(tG) == 2 assert type(tG[0]) == int and type(tG[1]) == int share = to_bytes(mul(s, tG)) while True: msg = recv(share) if msg == b"flag": aes = AES.new(key=sha256(long_to_bytes(s)).digest(), mode=AES.MODE_ECB) send(aes.encrypt(flag.encode()), share) elif msg == b"quit": quit() else: send(msg, share) if __name__ == '__main__': main()
「問題文、sage使わずに演算独自実装してるけど、シンプルなコードが売りのzer0ptsがどうした？」と違和感を覚えつつDLPの解法を調べていくうちに、「曲線外の点についても計算できる場合、GF(p)のDLPに帰着できる場合がある」に至り*3、なるほどと納得。
・・・で、解法はおそらく他の正解者の方々と同じです。(0, y)をセットして(0, yのs乗)を得られるようなyを見つけてサーバに投げます。p-1の素因数は小さい数なので、GF(p)でのDLPに帰着してsを計算できます。
競技中に得られた値は
sG = (58318174546957056169432032056343059934884742163892755006813686598775591148016,822219344460106439560681399389425143876696976177303814906846974164092345893)
でしたので、tGには
(0,4) をセットしました。
さらに、メッセージ「flag」（666c616700ffffffffffffffffffffff）を送ります。
返ってきた値は以下のものでした。
15507b447675922a3d17b98162c415e0b7c8a184e4d03b7e254e60f5c17bd8471cd81b6e96df5104ebee44cf176fe232fbc068c30f12694c7c9ec955e7f587d6
また、メッセージとして00000000000000000000000000000000を送ります。
返ってきた値は以下のものでした。
00000000000000000000000000000000fffffffffffffffffffffffffffffffffabd4bbc34327fafc0fa0b5909fd423f04c068c30f12694c7c9ec955e7f587d6
以上をもとに、フラグの値を計算しました。
ソルバ（SageMath）：
from Crypto.Util.number import * from Crypto.Cipher import AES from hashlib import sha256 def xor(xs, ys): return bytes(x^^y for x, y in zip(xs, ys)) p = 64141017538026690847507665744072764126523219720088055136531450296140542176327 L = 256 #sG = (58318174546957056169432032056343059934884742163892755006813686598775591148016, 822219344460106439560681399389425143876696976177303814906846974164092345893) #tG = (0,4) #666c616700ffffffffffffffffffffff #15507b447675922a3d17b98162c415e0b7c8a184e4d03b7e254e60f5c17bd8471cd81b6e96df5104ebee44cf176fe232fbc068c30f12694c7c9ec955e7f587d6 #00000000000000000000000000000000 #00000000000000000000000000000000fffffffffffffffffffffffffffffffffabd4bbc34327fafc0fa0b5909fd423f04c068c30f12694c7c9ec955e7f587d6 #7175697400ffffffffffffffffffffff _m = "00000000000000000000000000000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" _s = "00000000000000000000000000000000fffffffffffffffffffffffffffffffffabd4bbc34327fafc0fa0b5909fd423f04c068c30f12694c7c9ec955e7f587d6" _f = "15507b447675922a3d17b98162c415e0b7c8a184e4d03b7e254e60f5c17bd8471cd81b6e96df5104ebee44cf176fe232fbc068c30f12694c7c9ec955e7f587d6" _share = xor(bytes.fromhex(_s), bytes.fromhex(_m)) enc_flag = xor(bytes.fromhex(_f), _share) F = GF(p) a = F(bytes_to_long(_share[(L//8):])) g = F(4) s = discrete_log(a,g) aes = AES.new(key=sha256(long_to_bytes(s)).digest(), mode=AES.MODE_ECB) flag = aes.decrypt(enc_flag) print(flag)
zer0pts{edwards_what_the_hell_is_this}
サーバ繋ぐところまで自動化したソルバの方が美しいけど、フラグゲットできたのでヨシ！
この時点で3/20 17:45。
6. 「まだだ、まだ終わらんよ！」
競技終了まであと3時間でしたので、OKやCurveCryptoに取り組みました。
いろいろ試行錯誤し、CurveCryptoはCoppersmithも試しました*4が正解には至らず。時間だけが溶けていくシリーズパートn。21:00、オワタ！
7. 結果
Welcome/Surveyのほか、2問（Warmupを含む）を解き393点を獲得、得点を得た632チーム中93位でした。Warmup+2問くらいは解きたかったのでちょっと残念な感じです。もぐもぐタイムのどら焼きを先に食してしまい逸したことが原因と考えられるため悔やまれます。
8. おわりに（お気持ち表明）
ほとんどCrypto問しか見ていませんが、CTF TIMEでの宣言通りguessyな問題は皆無、コードも洗練されていて作問する際のお手本にしたいものばかりでした。
問題スクリプトの差し替えも対応迅速に行われたようですし、スコアサーバや各問題サーバへの不快感も皆無でしたので、総合的に見ても文句をつける要素が思いつきません。
ここ最近参加したClosedなCTFでは散々な目に逢っていた*5のですが、同じ「解けない」でも最後には清々しさが残る*6極めて良い大会であったと思います。
来年開催されれば、万難を排して出場します。あと、今年もCakeCTFの開催が楽しみです。
*1:今回は（今回も？）Warmup問を含め2問しか解けておらず、特に画期的な解き方をしたわけではなく、勉強のためWriteupを読まれる方は公式やツヨツヨな人達のWriteupを読んだ方がよいので、今回は「参戦記」という形で残すことにしました。なお、CTF参戦記としてはzer0ptsのメンバーでもあるYoshikingさんの SECCON Beginners CTF 2021 参加記 | yoshikingのへや が極めて秀逸で、参考とさせていただきました。
*2:「易しめ」の誤記ではありません。
*3:過去に類題を解いたことがあり、至ることができたというわけです。
*4:xが小さいことに着目。しかし、yが小さいことを失念していたので刺さりませんでした。まぁ当てずっぽうでやったものですから。うーん、ダメダメですね。。。
*5:例１：チームで１台しか解くためのパソコンが使えない。しかもツール類の事前準備はNG。公平性と予算の問題らしいけど、ちょっとね・・・例２：半日くらいの大会で最後の1時間になるまで重たい問題（面白い問題）がオープンされない。運営の悪意すら感じた。※いずれもSurveyでお気持ち表明してしまったので、おそらく今後は出禁でしょう。
*6:もちろん、終了直後はだいぶ落ち込みますが。
