SECCON CTF 2021 作問者Writeup + 運営参加記
本記事はCTF Advent Calendar 2021 - Adventarの22日目の記事です。1つ前の記事はkam1tsur3さんが「CTFで出題されるmusl libc問あれこれ - 過密です」を時間跳躍して書いてくれました(前の記事でも1つ前の担当者に時間跳躍させた気がするな...)
今年のSECCON CTFですがなんと./Vespiaryに対して問題作成の打診を受けまして、私とArkの2名が参加しました。本記事では前半に私が作った問題のWriteup(とちょっとした小ネタや裏話等)を、後半に運営サイドに回って感じた事を書きます。
Table of Contents §
CCC §
次のようなスクリプトとその実行結果を用意しました。
from Crypto.Util.number import bytes_to_long, getPrime, getRandomInteger, isPrime
from secret import flag
def create_prime(p_bit_len, add_bit_len, a):
p = getPrime(p_bit_len)
p_bit_len2 = 2*p_bit_len // 3 + add_bit_len
while True:
b = getRandomInteger(p_bit_len2)
_p = a * p
q = _p**2 + 3*_p*b + 3*b**2
if isPrime(q):
return p, q
def encrypt(p_bit_len, add_bit_len, a, plain_text):
p, q = create_prime(p_bit_len, add_bit_len, a)
n = p*q
e = 65537
c = pow(plain_text, e, n)
print(f"{n=}")
print(f"{e=}")
print(f"{c=}")
print(f"{a=}")
if __name__ == "__main__":
encrypt(1024, 9, 23, bytes_to_long(flag))
いつものRSAですが、$p,q$の作り方が異常です。$p$に対して$q$が未知数$b$を用いて次のようになっています。
$$ q = (ap)^2 + 3apb + 3b^2 $$
また、$p$のbit数を$l_p$とおくと、$q$のbit数は$2l_p$、$q$のbit数は$\frac 23 l_p$となります。
通常のRSA問題同様に$N=pq$なのでこれを利用して上記の式をいい感じに変形出来ないかを考えると、$ap$を両辺に掛けてあげると次のようになります。
$$ apq = aN = (ap)^3 + 3(ap)^2b + 3apb = (ap + b)^3 - b^3 $$
この式から$p' \coloneqq ap+b$とおくと$p'^3 - b^3 = aN$の関係があります。$b$についてもbit数の見積もりを行うと、$\frac 23 l_p$程度なので$b^3$のbit数も$2l_p$程度になり、$p' \approx (aN)^{\frac 13}$のような近似が行なえます。
さて、歴戦のCryptoプレイヤーならこの形に見覚えがあるかもしれません。フェルマー法っぽさがあります(ありますよね...?)。ということは$\lceil (aN)^{\frac 13} \rceil$を1ずつ増やしていけば近いところで正しい$p'$に辿り着いてくれそうな予感がします。
これを$p_0 \coloneqq \lceil (aN)^{\frac 13} \rceil$とおいて、具体的に$b^3 \approx (p_0 + \delta)^3 - aN$を計算してみると$\delta$が1増える毎に右辺は$3p_0^2$のオーダーで増加する事がわかります。つまり、$p_0^3 - aN$と比べるとおよそ$3\delta p_0$だけ増えます。
前述の各値の見積もりから$b^3$のbit数が$2l_p$程度である事が判明しており、これは$3p_0^2$と近いことからそれなりに小さい$\delta$で$(p_0 + \delta)^3 - aN = b^3$を満たす事がわかります。
後はこれを通常のFermat法と同様に実装するだけです。$\delta$をインクリメントしながら$(p_0+\delta)^3 - aN$を計算し、これが立法数であるかを判定して、もしそうなら$p', b$が求まった事になり、そこから$p$を求める事が出来ます。
from math import ceil
from Crypto.Util.number import long_to_bytes
# return an integer less than or equal to pow(x, (1/n))
def int_nth_root(x, n):
b_length = x.bit_length()
ret_ceil = pow(2, ceil(b_length / n))
ret_range = [1, ret_ceil]
while True:
ret_half = (ret_range[0] + ret_range[1]) // 2
v = pow(ret_half, n)
if v < x:
if pow(ret_half + 1, n) > x:
return ret_half
ret_range[0] = ret_half
elif v > x:
ret_range[1] = ret_half
elif v == x:
return ret_half
def cubic_fermat_method(n, c):
a = int_nth_root(n, 3) + 1
cnt = 1
while True:
b3 = a**3 - n
_b = int_nth_root(b3,3)
if _b**3 == b3:
p = a - _b
assert n % p == 0
assert p % c == 0
p //= c
return p, n // p // c
a += 1
cnt += 1
def get_params():
n=748951371882130931802035658643190843137768069094997532951877004804355999097514221898028746065708192401137682993520394304990274249486640341029596290845019123501455018318510517909188939742845359945051314320563879373308724866109205523358039610245817247396545225688131777569595375742563435181638557077287922855820814595617783963660715574123873253353153278155760187284507960974463459267090974567641539244100051157552969986630824060742455310593820406102161092521387627538070667222153082596080511347819692755067747768139661729133034101802879625296211575691192743381543325874828909504875804787273331727742295091555122604114378761875904742058873698555585850827391696126140112636986993317927401429541856267367473445998581503501399623438736593768742981259154547976308900931109837309595997322935859631651669260030950617914529080413885891792411413957578026402435702642249422813870751911884533018455112305024443548612214695005687499093470313
e=65537
c=144917864074015511935922816857363231541337762967562770119947985253463317126444931330942327334877580469990487497385196884757450691512323490753332323130997570096503070353477774210372799245361349305977816855197674562476707717312608963647587926329578332695523741999417967833032897169784927673730478114998147220953244488180240589904915102081692892506680654490941335587101027728447612331673649345499892499229553504426795996533332373684883271169670391774715307364853681369400205428259656028822679426328606371637153322224619471527480606421420141488512534130932537599855407350411776431197722318883451482159889911162752057786419942877600817298455386249064465557840145113456791121193853697366914932529401387170474843621810340519604877328113389161648132892104521737590843609044323838717403840588506498097350784386251597640755764921923426609290805256930846775003488315671785785091516760625958052962992811477229394815825903218592357864607501
a=23
return n,e,c,a
if __name__ == "__main__":
n,e,c,a = get_params()
p,q = cubic_fermat_method(a*n, a)
assert n == p*q
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
flag = pow(c, d, n)
print(long_to_bytes(flag).decode("utf-8"))
フラグはSECCON{CCC_means_Cubic_root_and_the_CTF_I_learnt_a_lot_about_fermat's_factorization_method}です。
フラグ中のthe_CTF_I_learnt_a_lot_about_fermat's_factorization_methodはCircle City Conのことです。このCTFのNo Stone Left Unturnedという問題でフェルマー法の一般化について色々と学んだ事を思い出しながら3乗を上手く使って作問出来ないか考えていました。
Circle City Conと作問の打診を受けたのが結構近い時期だったので、この問題の原案(PoC書いただけ)は結構早い段階から出来上がってました。また、時が経つにつれて、多変数Coppersmithによる解法が心配になりましたが、未知数が$p$の時点で3次な上に、$N^{\frac 13}$程度であるので、これに$b$という未知数を入れたら解けないと判断しました。
というわけで、もし何らかのCoppersmith's Attackで解いたらそれは非想定解です、おめでとうございます。Writeupを書いてください。
レビュー等で運営の皆さんに解いて貰った反応は「なんでこれで解けるの?」というのが多かったです。実際、私も前述のNo Stone Left Unturnedで同じ事を思ったのでフェルマー法についてアルゴリズムだけでなくなんで動くのかを調べてみると納得いくかもしれません。
この問題は17チームに解いてもらいました。思ったより少なかったです。warmup程ではないにしても30 Solves近くはあるんじゃないかと思ってました。
ちなみにこの問題、最終的にeasy想定で出したんですが、当初はwarmupの予定でした。どうしてそうしたかの記憶があまり無いのですが、最近のCTFの難易度がぶっ壊れている(Intermediateレベルのチームがちょっと頑張ると解けるのがwarmup)影響を見事に受けているのと「フェルマー法を改造するだけだからwarmup」みたいな思考が働いたと思います。レビュアー各位からも「warmupで出たら泣いちゃう」等のお褒めの言葉を頂き最終的にeasy想定となりました。なお、参考にしたNo Stone Left Unturnedは解けなかったので「解けなかった問題を参考にしてwarmupで出す」というカスみたいな事をして、作問勢の皆様から怒られが発生しました。まったくもってその通りだと思いますし反省してます。
(mediumで良かったな...難易度表記が無くて助かりました)
Sign Wars §
次のようなスクリプトとその実行結果を用意しました。
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Util.Padding import pad
import random
from secret import msg1, msg2, flag
flag = pad(flag, 96)
flag1 = flag[:48]
flag2 = flag[48:]
# P-384 Curve
p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
a = -3
b = 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575
curve = EllipticCurve(GF(p), [a, b])
order = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
Z_n = GF(order)
gx = 26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087
gy = 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871
G = curve(gx, gy)
for b in msg1:
assert b >= 0x20 and b <= 0x7f
z1 = bytes_to_long(msg1)
assert z1 < 2^128
for b in msg2:
assert b >= 0x20 and b <= 0x7f
z2 = bytes_to_long(msg2)
assert z2 < 2^384
# prequel trilogy
def sign_prequel():
d = bytes_to_long(flag1)
sigs = []
for _ in range(80):
# normal ECDSA. all bits of k are unknown.
k1 = random.getrandbits(128)
k2 = z1
k3 = random.getrandbits(128)
k = (k3 << 256) + (k2 << 128) + k1
kG = k*G
r, _ = kG.xy()
r = Z_n(r)
k = Z_n(k)
s = (z1 + r*d) / k
sigs.append((r,s))
return sigs
# original trilogy
def sign_original():
d = bytes_to_long(flag2)
sigs = []
for _ in range(3):
# normal ECDSA
k = random.getrandbits(384)
kG = k*G
r, _ = kG.xy()
r = Z_n(r)
k = Z_n(k)
s = (z2 + r*d) / k
sigs.append((r,s))
return sigs
def sign():
sigs1 = sign_prequel()
print(sigs1)
sigs2 = sign_original()
print(sigs2)
if __name__ == "__main__":
sign()
フラグを2つに分割してそれぞれ前半、後半のECDSAの秘密鍵としています。使われている曲線はP-384曲線で今のところ楕円曲線自体に脆弱性はありません。
前半のECDSAではnonceである$k$に関して次のようにしました。
$$ k = k_1 + z_1 \cdot 2^{128} + k_3 \cdot 2^{256} $$
ここで$k_1, k_3$は署名ごとに異なる128bitのランダムな値で$z_1$は署名されるメッセージ(これも128bit)です。通常のECDSA問題であればこれは公開されている事が多いのですが、この問題で秘密となっています。結果として、$k$は384bit全部が不明な値となります。
このような変なnonceを用いて80個の署名を用意しました。
後半のECDSAではこんな変なnonceの作り方はせず、384bitの乱数を用意しています。
前半後半共に乱数はgetrandbitsを用いています。なんでこれをわざわざ明記したかと言うと問題に関わるからです。
前半部分は見覚えのある方もいるかもしれませんが、HNPをECDSAに応用させたBiased Nonce Attackをこの形にも適用できるように改造する問題です。具体的に式にしてみると$k_1,z_1,k_3$と署名$r,s$の間には次のような関係があります。
$$ (k_1 + z_1 \cdot 2^{128} + k_3 \cdot 2^{256})s \equiv z_1 + rd_1 \mod N $$
ここで$N$は楕円曲線の位数です。
これを次のように変形します。
$$ k_1 \equiv \left(\frac 1s - 2^{128} \right)z_1 - \frac{2^{256}}{s} k_3 + \frac rs d_1 \mod N $$
合同式を外して等式の形にすると整数$l$を用いて次のようになります。
$$ k_1 = \left(\frac 1s - 2^{128} \right)z_1 - \frac{2^{256}}{s} k_3 + \frac rs d_1 + Nl $$
ここで$k_1$が128bitなことと、右辺の既知の値がどれも384bit程度であることから、格子を利用して$k_1$を構成するような係数を求める事が出来そうな予感がします。具体的には次のような格子を組みます。但し、$n$はこの格子を使うのに必要な署名の数であって80個全て使うわけではありません。
$$ \begin{pmatrix} N \cr & \ddots \cr & & N \cr -2^{256}& & & 1 \cr & \ddots& & & \ddots \cr & & -2^{256}& & & 1 \cr \frac{r_1}{s_1} & \dots & \frac{r_n}{s_n} & & & & \frac 1{2^{256}} \cr \frac 1{s_1} - 2^{128} & \dots & \frac 1{s_n} - 2^{128} & & & & & 1 \end{pmatrix} $$
これに左から係数ベクトルとして$(l_1, \dots, l_n, k_{3,1}, \dots, k_{3,n}, d_1, z_1)$を掛けると$(k_{1,1}, \dots, k_{1,n}, k_{3,1}, \dots, k_{3,n}, \frac{d_1}{2^{256}}, z_1)$が現れます。$k_{i,j}$は$j$個目の署名で使われた$k_i$を意味します。
各行のノルムが256bit以上である一方で、出てくるベクトルのノルムは128bit程度であるため、基底を簡約すると出てきてくれそうです。後は$n$を決めます。
この基底の体積(full-rankなので行列式と同じ)は$N^n\times \frac 1{2^{256}}$になります。よってLLLで出てくる最も小さな基底のノルムは$\left(N^n\times \frac 1{2^{256}}\right)^{\frac 1{2n+2}} \approx 2^{\frac{384n - 256}{2n+2}}$になります。
一方出てきてほしい基底のサイズは128bitです。したがって$n$に関して次のような近似式が成り立ちます。
$$ 384n - 256 \approx (2n+2) \cdot 128 $$
これを解くと$n \approx 4$となるのでこの付近の数の署名を集めて格子を錬成します。幾つかやってみると$n=5$の時に上手くいきます(先頭$n$個の署名で試した結果)。
というわけで$n=5$でLLLを実行し、秘密鍵$d_1$を求めます。これでフラグの前半部分が手に入りました。
後半ですが、nonceを完全に乱数に頼っているので、前半のような攻撃は出来そうにありません。パット見不可能に見えますが、ここでgetrandbitsを使っている事が活きます。
getrandbitsはMT19937を用いる事から32bitの出力が624個あれば、以降の出力が完全に予測出来ます(話すと長くなるのでググってください)。32bitでなくても32bitより大きな値であれば32bitでの出力をバイト列としてみなして結合して出力するので32の倍数のbit数を要求してその出力を入手出来れば、32bitごとの出力を入手出来た事と同じになります。
今回は署名で128bitの乱数を2つ用いました。よって1つの署名で8個の出力が得られた事になります。これが80個あるので結果として640個の出力が得られた事になり、これは624より大きいです。
前半で秘密鍵を復元できたので各署名のnonceも全て求める事が出来ます。よってこのnonceを求めてバイト列にし、32bitごとに分割してgetrandbits内部のMT19937の出力を完全再現することで状態を復元し、以降の出力を予測出来ます。これで後半の3つのnonce全てを復元可能です。
nonceがわかってしまえばあとは$d_2,z_2$に関する一次式は2つあれば十分なので2つの署名を用いて解くだけです。
最終的なソルバは次のようになります。
import random
from binascii import unhexlify
from output2 import sigs1, sigs2
def long_to_bytes(x):
if x < 0:
x = -x
x = int(x)
if x == 0:
return b"\x00"
return x.to_bytes((x.bit_length() + 7) // 8, "big")
p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
a = -3
b = 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575
curve = EllipticCurve(GF(p), [a, b])
order = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
Z_n = GF(order)
gx = 26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087
gy = 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871
G = curve(gx, gy)
sig_cnt = 5
size = sig_cnt*2 + 2
mat = [
[0 for _ in range(size)] for _ in range(size)
]
for i in range(sig_cnt):
r,s = sigs1[i]
s_inv = inverse_mod(s, order)
mat[i][i] = order
mat[i+sig_cnt][i+sig_cnt] = 1
mat[i+sig_cnt][i] = -2^256
mat[-2][i] = r * s_inv % order
mat[-1][i] = (s_inv - 2^128)
mat[-2][-2] = 1/(2^256)
mat[-1][-1] = 1
l = matrix(QQ, mat)
llled = l.LLL()
for b in llled:
d1 = int(b[-2] * 2^256) % order
msg1 = b[-1]
valid_msg = True
for b in long_to_bytes(msg1):
if b < 0x20 or b > 0x7f:
valid_msg = False
if not valid_msg:
continue
# print("[+] Found!!")
# print(long_to_bytes(msg1))
# print(long_to_bytes(d1))
found = True
break
if not found:
print("?????????")
exit()
ks = []
for r, s in sigs1:
s_inv = inverse_mod(s, order)
k = (msg1 + r*d1) * s_inv % order
ks.append(int(k))
def untemper(x):
x ^^= (x >> 18)
x ^^= ((x << 15) & 0xefc60000)
x_bottom_14 = (x ^^ (x << 7) & 0x9d2c5680) # & ((1 << 14) - 1)
x_bottom_21 = (x ^^ (x_bottom_14 << 7) & 0x9d2c5680) # & ((1 << 21) - 1)
x_bottom_28 = (x ^^ (x_bottom_21 << 7) & 0x9d2c5680) # & ((1 << 28) - 1)
x ^^= (x_bottom_28 << 7) & 0x9d2c5680
x_top_22 = x ^^ (x >> 11)
x ^^= (x_top_22 >> 11)
return int(x)
def k_split(k):
ret = []
for _ in range(4):
ret.append(k & 0xffffffff)
k >>= 32
return ret
state = []
for k in ks:
k_bottom = k & (2^128 - 1)
k_top = (k >> 256)
s1 = list(map(untemper, k_split(k_bottom)))
s2 = list(map(untemper, k_split(k_top)))
state = state + s1 + s2
mt_state = tuple(state[:624] + [624])
mt_state = (3, mt_state, None)
random.setstate(mt_state)
assert random.getrandbits(128) == ks[-2] & (2^128 - 1)
assert random.getrandbits(128) == ks[-2] >> 256
assert random.getrandbits(128) == ks[-1] & (2^128 - 1)
assert random.getrandbits(128) == ks[-1] >> 256
k1 = random.getrandbits(384)
k2 = random.getrandbits(384)
r1, s1 = sigs2[0]
r2, s2 = sigs2[1]
rdiff = r1 - r2
d2 = (k1*s1 - k2*s2) * inverse_mod(rdiff, order) % order
# print(long_to_bytes(d2))
flag = long_to_bytes(d1) + long_to_bytes(d2)
print(flag.decode("utf-8"))
提出するソルバの都合上、依存ライブラリをへらすためにlong_to_bytesを時前実装していますが気にしないでください。
フラグはSECCON{New_STARWARS_Spin-Off_The_Book_Of_Boba_Fett_Will_Premiere_On_December_29-107c360aab}です。
1つぐらいフラグに自分の趣味を入れても怒られは発生しないだろうということでSTARWARSネタにしました、The Book of Boba Fett楽しみですね。皆さんも今からDisney+を契約して、EP1~6とローグ・ワンとクローン・ウォーズ 劇場版, シーズン1~7と反乱者たちとマンダロリアン シーズン1,2とバッドバッチを見ましょう(ハン・ソロとビジョンズとその他黒歴史はお好みで)。
前半でnonceを3つに分割してあるのも、後半で署名を3回作っているのもそれぞれプリクエル3部作とオリジナル3部作に対応させています(シークエル3部作ってなんですか? 公式による金のかかった同人作品のことですか?)。
この問題にも元になった問題があり、pbctf 2020のLeaKです。nonceの真ん中が未知な事以外はだいたい同じです。実は元になったというのは半分嘘で、作っていたら「あれ? これLeaKと同じじゃね?」という形になってしまったのでそれを避けるためにちょっとだけ改造しました。元になったというより影響を受けているというのが正しいです。
ところで、後半ではフラグを入手するだけならメッセージは不要で秘密鍵だけを求めれば良いのですが、メッセージの方も意味が通るようになっています。イースターエッグとして用意したのですが、幾つかのWriteupでは求められており、嬉しかったです。これを読んだ皆さんも復習する際には是非求めてみてください。
正直、前半が解けるぐらいCryptoをやっているチームにとっては後半は自明みたいなところがあるに留まらず、XXXと「楕円曲線 + HNP」というネタ被りもあり、こちらを遅くに出したのでレビューでrejectされることも覚悟していましたが、前者が議論にはなったもののrejectには至らず、寛大な皆様のおかげで無事に出題されました。
最終的にこの問題は8チームに解かれました。思ったより少なかったです(2回目)。というか有意な差を付けて1番解かれないCrypto問題になるとは思っていませんでした。
毎週のようにCTFに出てWriteupを読んでいると格子が当たり前の世界なのでそれが解けるチームばかりに思えてしまいますが、実際はそうでもなく、そもそも今回国内の格子を解ける人間の多くがCTF運営に回ったことで、日本人が多く出るSECCON CTFでは少なくなってしまったと思っています。
また、この問題のSolvesの推移も興味深く、序盤から中盤にかけてはまばらにSolvesが入って6 Solvesぐらいになったのですが、ある時点から8時間ぐらい全く解かれず終盤にちょっと入ったという動きをしていました。この事から、実力に応じてかかる時間が線形に減っていくのではなく、わかるチームなら瞬殺出来るが、そうでないと24時間で知識を揃えたり気合で解いたりするのが難しいという考察が出来ます。
そういう意味ではボス問にはなってしまいましたが、あまり相応しくないような気がしました。強い層でも歯応えのある問題がボス問題として相応しく、要素を段階的に用意して問題の体力増加を図っている(結果的にそうなっただけで意図はしてないです)この問題はボス問題らしくはないと思います(作者ということもあり嫌いではないです)。次もしなんらかの問題が作る機会があればボスに相応しい問題を作りたいです。
Writeupはここで終わりです。残りは非技術的な内容、俗に言うポエムなので興味ない人はタブを閉じましょう、ショートカットキーはだいたいのブラウザでCtrl + Wのはずです。果物のロゴが刻印されたMから始まる銀色のPCの場合は知りません。
他のCrypto問題 §
作った問題がそのまま出題されることは無く、他の作問者からレビューを受けて出すに足るクオリティかどうかのチェックが行われました。というわけでCryptoの他の問題について私が他のCryptoに対して抱いた感想を書きます。
pppp §
Warmup枠です。$N$の素因数分解が出来ることが問題を見てから3秒でわかるので、勘で$d = e^{-1} \mod \phi(N)$を求めて指数にして各行の要素でGCDしたらなんか解けました。対角成分以外はなんとなく何倍かになるのかと思ったら元に戻るらしいです、ふしぎ～。
意外と「$p$の倍数は$pq$で法をとっても$p$の倍数であることは維持される」という事実は気付きにくいのでそれを利用しつつ行列のべき乗で実現しているというのが綺麗でした。
また、「通常のRSAと同様にやってみると非自明だが何故か解ける」というのもビギナーズラック感があり、そういう意味でもwarmupらしい問題です。フラグにもある通り皆さんは元に戻る事が証明出来ましたか? 私は出来ませんでした。
最終的に70チームに解かれており、良いwarmupだったと思います。
XXX §
かなり好きな問題です。「プレイヤー側で解きたかった VS 人類最速で取り組む事が出来た」みたいな気持ちの戦いが生じています。
各式の差をとるといい感じにHNPに落とし込めるので後は典型です。格子経験者にとってはwarmupかもしれませんが、格子のエントリーレベルにちょうど良いんじゃないでしょうか? oOoOoOより解かれなかったのが不思議です。
theoremoonさんらしく、簡素な問題スクリプトとシンプルな解法でPlayer-Firstな問題です。
前述の通り、奇しくもSign Wars同様「楕円曲線+格子」という組み合わせの問題で解法も似ていたことから、遅れて出したSign Warsが被りでRejectされる事も危惧しましたが、寛大な皆様のおかげで無事に出題出来ました。そういう意味では1番脅威だった問題でもあります。
oOoOoO §
1週間ぐらい考えても解けなかった問題です。Crypto作問者以外も含めて十分なレビューが集まっており「俺の存在意義とは...?」となりました。
最初は格子に掛ける係数ベクトルの候補をord("O")とord("o")の2通りで考えていたのですがこの2つの差が大きいせいか、いい感じに出てくれませんでした。そこから上手く数の候補を減らしたり格子の大きさを変化させて解こうとしたのですが、それでも解けず、聞いたところにによるとBKZなら解けるらしいです。Flag is Win - TSGCTF 2021の反省が何も生きていないことが判明しました。
では、なんでそんな問題がここまでSolvesがあるのかというと、最近のCTFプレイヤーが全員BKZを知っていた...わけではなく、mod演算における法の商($a \equiv b \mod p$に対する$a-b = kp$の$k$のこと)が小さくなることからこれを総当りすればただのMerkle-Hellman Knapsack暗号に帰着出来るからです。Beginners CTFでも出ていたらしいのでその流れで解けた人が多いんじゃないでしょうか? そういう意味では普段から格子に触れているプレイヤー程、強引に解こうとしてドツボにはまる問題だと思います、決してレビューで解けなかった言い訳ではありません。
この問題、最初はeasy想定だったらしく、「魔女の考える事はわからない」という気持ちになりました。しかし、最終的に2番目にSolvesが多く、私がeasyも解けないクソザコナメクジである事が発覚しました。CCCはもちろんのこと、同じ格子を使う問題でもXXXやSign Warsの方が絶対簡単だと今でも思ってます。
cerberus §
PCBCモードのPadding Oracle Attackらしいです。ブロック暗号問題苦手で後回しにした結果、レビューに参加できなかったので特に言える事はありません...
レビュー総括 §
昨年のSECCONやzer0pts CTF等、数々のCTFで問題提供実績のあるtheoremoon先生と動画に付随する問題や記念Challengeで数々の良問を生み出しているkurenaif先生の問題を先行体験出来て良かったです。振り返るとあまりまともなレビューが出来ていたとは言えませんが、問題を解くだけでなく評価するという貴重な体験が出来ました。
今考えると実力実績共にあるこの2人に挟まれてCryptoの作問したの場違い過ぎて恐ろしいですね...他分野もネームバリューのある人が多いので私が最弱です。
Crypto所感 §
各問題の感想は上に書いた通りなので全体の感想を書きます。
不思議な力が働いて格子問題が半分を占めたので普段からCTF出てる勢が非常に有利になったと予想してます。書いてて思いましたがこれ小泉構文っぽさありますね(普段から出ていれば当然CTFは強いので。皆さんも国内CTFに留まらずCTFtimeを見て色々なCTFに出ましょう)。
他分野に比べるとSolvesの総和は多いんじゃないかと思います。また、分野内で最も小さいSolvesが他分野に比べると大きかったのが気になりました。実際開幕で海外強豪チームが物凄い勢いで解いてるのを眺めていたので「終わった...」なんて思ってました。特にNu1Lが開幕1時間ぐらいで3つも解いてて最終的に一番早くCryptoを全部解いたのでビビってました。記憶が定かではありませんが、最終的に6チームぐらいが全てのCryptoを埋めていました。
今度また作問する機会があれば、今回全部解いたチームでも唸るような問題を提供したいですが、それには大量のinputが必要で気が遠くなりそうです。実際CCCもSign Warsも過去に自分が体験した問題がベースになっています。
予想外だったのはSolvesの順番です。最終的に解かれた順に"pppp > oOoOoO > CCC > cerberus > XXX > Sign Wars"でしたが、私の予想は"pppp > CCC >= XXX > Sign Wars >= cerberus >> oOoOoO"だと思ってました。Solves順で賭けをしなくて本当に良かったです。もっともこの予想は自分が問題を作ったのとHNP型の格子問題の経験があるというのが一因になっていると思います。
このように作問者の予想と実際に解かれた数では隔たりがあることから難易度表記のあるCTFは信用出来ない事がわかりました。そもそも開催中もSolvesが表示される時点でこれがある程度難易度の指標となっている感じがしており、難易度表記は不要なんじゃないかと思ったりしてました。
ただ、Cryptoの話に限りますが、一般的なCryptoプレイヤーは公開鍵暗号問題のような数学が絡む問題を好むため、今回のcerberusのような問題は「解く実力や可能性はあるのに解かない or 後回しにするチームがいる」という事もあり、Solvesが当てにならないこともあります。実際、前半のSolvesはcerberusが1番少なかったです。このような事情もあって実際の難易度がどのような順番になるというのは非常に難しいと実感しました。
その他 §
話しても大丈夫そうな範囲で適当に書きます。
対話式問題 §
私の問題は2つともサーバーへの接続を要しない問題ですが、これは偶然では無く意図しています。理由の1つはプレイヤー側になった時に通信用のコードを書くのが苦痛に近い作業でプレイヤーとしてあまりやりたくないからです。
もう1つの理由はデプロイの際に面倒な作業がありそうな予感がしたからです。そういうのが面倒という単純な感情もありますが、ネットワーク関連の知識や経験が全然無いのにこういう問題を作って足を引っ張る事を恐れた方が強いです。
とは言いましたが、CCCを作って以降、Sign Warsを含めて3つの案を考えて実はそのうち2つは対話式の問題でした。結局Sign Warsが1番形にしやすかったので出題されましたが、もしかすると本番寸前で通信周りで修羅場になってた世界線が見られたかもしれません(実際Web問題担当とかはインフラチームと頻繁にやりとりしていて大変そうだった)。
なお、このお蔵入りになった問題に関してはレビューでRejectされたわけでも無く、詳細を他の作問者に話してもいないのでもしかするとどこかで提供する機会があるかも...? 嘘です、特に./Vespiary CTFのような予定はありません。
自チーム §
私が所属している./Vespiaryは今回2人が作問に回ったため、他のメンバーは縮小チームで出ていたらしいです。彼等が私の問題を解く事を期待しましたが、よく考えたら私以外にCrypto担当は居ない(たまにkurenaif先生が助っ人に来てくれるが、作問側にいる)上に、一応解く知識があるであろうチームメイトも24時間では自分の得意分野を解くので精一杯なのでその期待は見事に外れました。最近、Discord越しに話す機会がたまに発生するので、チームメイト達からの苦情を肉声で聞きたかったです。
結局、CTF終了後にCCCだけ解く会をしましたが、意外と苦戦してました(数時間の会で自力で解く事は叶わなかった)。非Crypto勢からするとやっぱり難しかったようです。
そういえば、TSGやzer0ptsも一部が作問、残りが競技者だったらしいので、作問者各位は直接感想とかチームメイトから貰えたんでしょうか?
開催中の暇潰し §
普段CTFをしている人間が問題作成側に回ると何をしだすのでしょうか? チーム開催とかならインフラの対応が主だとは思いますがSECCON CTFには素晴らしいインフラチームの皆様が居るので我々が担当することはありません。というわけで24時間何をしてたかを書きます。
開幕は「サーバートラブル大変そう」みたいな話を交えながら、welcome以外のフラグ提出状況を眺めながらDiscordでCTF関連の話を作問勢の皆様としていました。これで普段CTFで好成績を残している皆さんが少なくとも声帯を持っている事は判明しました(肉体の存在とCTF特化型AIでない事の証明はまだされていない)。この段階だとまだあんまりSolvesが増えてないのでどの問題が解かれやすい/解かれにくいというのは予想しにくいです。実際開幕はSign Warsよりcerberusの方が1 Solves差ぐらいで解かれていなかったのですが、最終的にcerberusは16 Solves、Sign Warsは8 Solvesと有意な差が現れました。序盤は"pppp > CCC > XXX = Sign Wars = oOoOoO > cerberus"ぐらいのSolvesだった気がします。
これも数時間もすると落ち着いて、食事等で離席する人も増えてテキストチャットに移行しました。何故かCCCが話題に上がったので解いてない人が解いて「なんでこれで解けるの」みたいな反応をされたりしました。そこから日付が回るぐらいまでは、当時ハマっていたBorderlands 3をしながらたまに自分の問題がどのぐらい解かれたかや./Vespiaryの部分集合がどのぐらい解いているかを確認していました。
日付が回る頃に急に「ボードゲームアリーナをしませんか?」という打診があり、まさかの作問者+運営が8人も集まってボドゲをすることになりました。多くのボドゲは8人用に出来ていないので、ニムトやUNOに追加のアクションカードとスピードバトルを入れたOne(だっけ?)というゲームをして盛り上がりました。どちらのゲームも押し付けられたカードの枚数が多いと不利になるので大量のカードを押し付けたり押し付けられたりで阿鼻叫喚の様相を呈していました。何故かzer0pts内で内紛が始まったり、./Vespiary内で順位格差が出来たりとチーム崩壊が起きていて面白かったです(Arkが妙に強かった)。
その後はピクトセンスやGartic Phoneをして遊びました。既に何名かが話題にしてましたが、前者で「カナリア」というお題が現れた時にスタックの様子を描いていたのが記憶に残っています。後者ではptr-yudai画伯を始めとして皆さんの画力に「すげ～」って言っていました。一方、私の代表作は次のとおりです(キャプションはお題(原文ママ))。
他にも「Githubのオクトキャット」や「JNDIな文字列を弾くWAFくん」や「中国人剰余定理」のような非人道的なお題が出て楽しかったです。私は「ハッシュ関数」や「CPU実験に苦しむ東大生」をリクエストしました。どちらも次の回答時には別物になっていました。
そんなこんなで夜明けが近くなると寝る人も増えてきて最終的に午前7時前ぐらいに解散になりました。その後はBorderlands 3のデイリーを消化して寝てから終了15分ぐらい前に起床しました。
だいたいこんな感じです。zer0ptsの2人はいつもこんな楽しい体験をしてるのかと思うと毎週CTFを開きたくなっ...ては来ませんが、声を掛けられたらボドゲ目当てでCTF運営について行ってしまいそうなぐらいは楽しかったです。
あとがき §
初のCTFの問題作成がまさかのSECCON CTFとなってしまい、非常にビビっていましたが、なんとか問題を提供できて良かったです。機会をくださったCTF運営チームの皆様、並びに快適なCTF環境を実現してくださったインフラチームの皆様、その他CTF運営に関わった全ての皆様、ありがとうございました。
そして何よりも、私の問題に取り組んでくださった参加者の皆様に最大限の感謝の意を表します。また、Writeupや復習記事を読むのを楽しみにしていますので「Xornetが書いたから書かなくていいや」というような愚かな事を言わず書いてください。私が読みたいという他に、Writeupを書く事で良い復習になるのでCTFプレイヤーとして成長できるというのもあります。そして良質なWriteupを書いて、私が終了後に解けなかった問題で苦しむ機会を減らしてください。
明日のCTF Advent Calendarはkusano_kさんで「SECCON CTF 2021作問者writeup＋作問した感想 - kusano_k’s blog」を書いてくれるそうです。Crypto以外の全分野に問題提供を行ったという「恐怖の作問マシーン」ぶりを見せてくれたのでWriteupを読むのが楽しみです(そういえば別の恐怖の作問マシーンもSECCON CTF 2021に居ましたね)。既に英語版は書かれているので、待ちきれない方はそちらもご覧ください。
CTF Advent Calendarは22日以降は全て埋まってしまいましたが、空いている日付はまだあります。RTACTF等ネタになるCTFもありましたし、時間跳躍して書いてみてはいかがでしょうか?
Links §
先日からAuthor勢がWriteupを公開し始めているので以下もご覧ください。他にも確認したら追加します。
- SECCON CTF 2021作問者Writeup - CTFするぞ: ptr-yudaiさん分
- XXX - SECCON CTF 2021 Author's Writeup - ふるつき: theoremoonさん分
- SECCON CTF 2021作問者writeup＋作問した感想 - kusano_k’s blog: kusanoさん分
- kusanoさん分(英語): 多いのでまとめツイートを掲載
- SECCON CTF 2021 Writeup (author's): kurenaifさん分
- SECCON CTF 2021 author writeup (4 web challenges) | XS-Spin Blog: Ark分
- SECCON 2021で作問し、運営中ボードゲームをしました。 - 欣快の至り: moraさん分、飛んだ先にWriteupリンクがある