TSG CTF 2020 作問感想

博多市が作問した問題に関する雑記です。ちゃんとしたWriteupは後ほど投げます。

Beginner's Crypto (Crypto)

配布ファイルが単純だし解くのに複雑な式変形も必要ないのでBeginner。

レビュー中にsatos (@satos___jp) が下の桁から合わせていく面白い別解で解いていた。

Sweet like Apple Pie (Crypto)

「こんな問題できないかな～」って投げたらナン氏 (@naan112358) が秒で解いてくれた。すごい。sin(x) = sin(π - x) に関しては博多市も作問する際にめっちゃ悩んだのでみんなにもこの苦しみを味わってもらいたいと思いそのまま出題。

Rubikrypto (Crypto)

CTFにルービックキューブ問は何度も出てるけど、ちゃんと暗号暗号してる良問ってないな～と思っていたので、ちゃんと群と暗号に絡めた形の問題を作りたかった。想定解は Pohlig-Hellman ではなくルービックキューブ群の元の位数がたかだか1260であることを利用する。

Modulus Amittendus (Crypto)

原案はcookies (@kcz146) の「Nの代わりにΦ(N)が与えられたらpとqを復元できないかな～」という発言。その過程で「そういえばHITCONに Lost Modulus Againなんて問題があったね～」ってなって、試しにこの問題から係数を一つ落とした問題をナン氏 (@naan112358) に投げてみたら秒で解いてくれたので出題。

今年もRSA問が出せてよかった。係数一つ落としただけなのにもとの問題と解き方が全く違ってくるのが面白いですね～。

Beginner's Web (Web)

object[key](hoge, fuga) みたいなやつで key がいじれるシチュエーションなら、CTFerでなくても Object.prototype を疑うのが自然かな～と思います。

で、想定ムーブは Object.prototype 以下のメソッド一覧をドキュメントなりなんなりで確認し、(String, Function) という引数を取る関数が __defineSetter__ と __defineGetter__ しか無いことを見つけ、で __defineGetter__ はフィルタの [FLAG] に引っかかるので __defineSetter__ 一択に絞れる。あとは一直線。

Slick Logger (Web)

いや～Side-channel問の作問って難しい。つばめ先生の Blind Regexp Injection の記事にあるとおり、Golangはオートマトンを用いたいい感じのRegExpエンジンを実装しているのでexponentialな計算量のReDoSが難しいわけですね。ただオートマトンを用いるConsとしてオートマトンの状態数に比例した時間計算量が必要になり、GolangのRegExpには状態数に対する制限がないので重めの線形ReDoSが構築できます。あとはApacheのCGIのTimeout設定が1sなのを確認して status code が504か200かで判別できるようにパラメータを調整すれば勝ちです。

Beginner's Misc (Misc)

Base64もUTF-8も全人類知ってるしソースコードが実質3行なのでBeginner。

Base64に変換したあと[0-9/+]だけで構成されるようなUTF-8文字列を手で構成するなり全探索するなりしたあと分数にして上の桁から合わせていく。

Poor Stego Guy (Misc)

めっちゃ頑張って作ったのに一行で解かれて泣いちゃった。想定解はJPEGのDCTの係数離散化がそのまま格子と見なせることを利用し、LLLを用いてCVP問題を解きます。

BlindCoder (Misc)

「こんな問題できないかな～」って投げたらCoiL氏 (@coil_kpc) が秒で解いてくれた。すごい。