Codeforces Round #415 (Div. 1) C. Find a car

dpの遷移が複雑すぎるだろ。

問題概要

縦109, 横109の合計1018個のマス目があり、上からi番目, 左からj番目のマス目を(i, j)と表す。マス目に以下のルールで数を書き込んでいく:

  • マス(i, j)には、マス{(x, j) | 1 ≦ x < i}とマス{(i, y) | 1 ≦ y < j}に書かれている数全てを除いた上で、最小の自然数(0は含まれない)を書き込む。
  • つまり、マス(i, j)には、そのマスの左と上を見て、書かれていない数の内、最小のものを書く。
  • 当然(1, 1)は1とする

具体的には、以下のような形になる(問題文から引用)

f:id:potetisensei:20170521163405p:plain

以下の質問に対して Q回答えよ:

  • x1, y1, x2, y2, kが与えられるので、長方形区間{(x, y) | x1 ≦ x ≦ x2 ∧ y1 ≦ y ≦ y2}について、k以下の数が書かれているマスについて、それらのマスに書かれている数の総和を答える。
  • ただし総和はあまりにも大きな数になるので、109+7で割った余りを答えれば良い。

制約

  • 1 ≦ Q ≦ 104
  • 1 ≦ x1 ≦ x2 ≦ 109
  • 1 ≦ y1 ≦ y2 ≦ 109
  • 1 ≦ k ≦ 109

解法

まず求めたい値をcalc(x1, y1, x2, y2)とおくと、calc(x1, y1, x2, y2) = calc(1, 1, x2, y2) - calc(1, 1, x1-1, y2) - calc(1, 1, x2, y1-1) + calc(1, 1, x1-1, y1-1)に分解できるので、全て(1, 1)から考えて良いことがわかる。 ここから少し考察すると、(1, 1)を含む任意の長方形状のマス目は簡単な操作で2倍に拡大できる事に気づく。

つまり、

{ \displaystyle \left( \begin{array}{cc} A&B\\C&D \end{array} \right) \to \left( \begin{array}{cccc} 2A-1&2A&2B-1&2B\\2A&2A-1&2B&2B-1\\2C-1&2C&2D-1&2D\\2C&2C-1&2D&2D-1 \end{array} \right) }

こういうことで、 例えば

{ \displaystyle \left( \begin{array}{cc} 1&2\\2&1 \end{array} \right) \to \left( \begin{array}{cccc} 1&2&3&4\\2&1&4&3\\3&4&1&2\\4&3&2&1 \end{array} \right) }

この性質を用いれば、まあ倍倍にしていけば、{ \displaystyle O(log(max(x2-x1, y2-y1)))}ぐらいで計算できそうだな、というのは分かる。ここからが問題。 基本的にdpをするんだけど、dpの遷移が大変なので本当に辛かった。 やはり遷移を直で200行ぐらい書くよりは、悩んでもいいからループでちゃんと遷移をまとめる方が良いなという気持ちになった。 具体的な方針としては、1x1の1個のマス目から初めて、目的の長方形へ伸ばしていって、その際に必要な値をdpとして伝搬させて行く。この際、最終的な最大値kから逆算して、各過程に置いて許される最大値というものを前計算しておく。 つまり例えばk = 7だったとすれば、1つ前の長方形ではk' = 4である必要がある、これは長方形を2倍した時、マス目の値も2倍か2倍-1されるから。 まずdpとして持つ状態は、

  • どの部分のマス目を考えているか - 右端、下端、右下のマス、それ以外の4通りが必要になる
  • 最大値かどうか - 桁dp的な考え方をする必要がある。つまり、上記のように、マス目のに書かれている数が各過程において可能な最大値である場合、場合によっては2倍すると不適となる場合がある。
  • 例えば上記の例でマスの数が4であった場合、2倍すると8になるが、許される最大値が7である時、これは不適となる。

また、遷移の式は、dp[i+1][nj][nk] += dp[i][j][k]*2 - num[i][j][k]のようになるわけなので、実はマス目の総和だけでなくて、条件に適するマス目の個数というのも持っておく必要がある。ちなみに僕は誤読していて個数を求める問題だと思っていて200行直書き遷移を書き直す必要が出てきて詰んだ。

書いたコード

まあ本当に遷移は頑張るという感じで、こういう問題は嫌いですが、本番中に1発で通せるべきだよなあと思い反省の意を込めてこの記事を書いておきます

Codeforces Round #415 (Div. 1) C. Find a car

みんなのプロコン 2017 予選 D

みんなになれなかった。

 

問題概要

読んで: D: 工場 - 「みんなのプロコン」 | AtCoder

 

解法

正攻法はそのままこのクエリを実現しようとすれば結合則成り立つので値を2,3個持ってくださいというやつみたいです(たしかにね。)。

 

クエリの時系列と日数の時系列の2次元なので、こういう時はとりあえず日数の時系列でクエリをソートして、segment treeのインデックスをクエリのインデックスにすることを考える。

 

D = D1, D2, ... , Dqを順に代入しつつ以下の値を考える(ただしD1 ~ Dqは昇順にソートしたクエリの日付)。

 

num[qidx] := qidx番目までのクエリを考慮した時、D日目までに販売した賞品の数

 

これをセグ木によって持つことを考える。

Dqidx = Dとなるようなqidx番目のクエリを処理することを考える。

経理質問(回答クエリ)については、num[qidx]を答えられれば良いので、この値をセグ木で実現できるなら特に考える必要がない。

注文追加(更新クエリ)について考える。

qidx番目のクエリによる更新が反映されるべきなのは、num[qidx] ~ num[Q]であって、それぞれのi ∈ [qidx, Q]について、num[i] = max(num[i]+Aqidx, K*D)という更新を行う。

K*DとAqidxは定数でnum[i]はiについて流石に単調増加なので、num[t] > K*D-Aqidxなる最小のtを二分探索で見つければ、t未満のインデックスについては区間に対してAを加算、t以上のインデックスについては区間に対してK*Dを代入をすればよく、これは、seg木にnum[i]の代わりにnum[i]-num[i-1]をもたせれば、Lazy Propagationによる区間代入をサポートした、区間和を求めるseg木によって実現できるので解ける。めちゃくちゃバグる。

CTFのpoteti問題まとめ

どうも、binjaリーダーのpotetiです。あまりしたくはありませんが、Twitterを見ていて必要性を感じたのでCTFの話をします。

 

CTFのExploitation(Pwnable)ジャンルで、過去にpotetiが作問した問題はいくつかあって、通称bataリスト(だっけ?)と呼ばれる例のあれにも数問載っています。

しかし、それらの問題を提供したED CTFやburning CTFは公開を終了してしまっていて問題を参照しづらいのと、起動時に注意が必要な問題が数問あるんですが、その問題に関する注意書きがどこにも存在していないので、このブログを使ってまとめておくことにしました。

なんか自分で言うのも何ですが、一部を除いて良問なのでやって損はないと思います。

 

My Sandbox おすすめ度: ★★★

www.dropbox.com

なんかそこそこ初期に作った問題で、かなり簡単なはず(作問者の実力が低いので)。村人Bが解ける人はおそらく十分に挑戦する資格があるのでやってみると良いかもしれません。ちなみに想定解は4つあって、4つとも典型テクなので考えてみると良いです。

もうちょっと難しく出来るしbinja CTFが開催できるなら改題を出したいなあ。

 

Heap is a tomodachi of mine おすすめ度: ★★

www.dropbox.com

分かる人には分かるかもしれないんだけど、これ途中までは全く別の方針で解けるようにしようとして作っていたんだけど、最終的に上手くまとまらなかったから適当にごまかしてしまってこの形に至ってしまったので、個人的にはクソ問の部類に入ります。ですが、一応今時のheap問題に比べると特殊なテクニックが必要なく極々典型的なテクニックで解くことが出来るため、入門には良いかもしれないということでおすすめ度を2にしました。が、まあやはりやらなくていいと思います。

 

Local Only 64 おすすめ度: ★★★★★

www.dropbox.com

個人的に、Local Onlyシリーズは多分僕が今まで公開した問題の中だと最も難しくて面白いと思っています。

 

で、「起動時に注意が必要な問題」というのは、Local Onlyシリーズのことです。まず1つには、これらは起動時に大量のopenシステムコールを発行するので、ulimit -nコマンド等で1つのプロセスが開くことの出来るfdの最大数をunlimitedなどにしておいてください。また、この問題には、ローカルから接続することが想定されています。意味不明な状況かもしれませんが、問題サーバー上のxinetdで問題が動いていて、更に問題サーバーにはssh接続が出来るという状態でした(だから"Local" Onlyという名前なんですよね)。これは、他の問題を解いた人間にしか挑戦権がないという意図でした(まあこの問題は難しいので)。

 

また、この問題に限りlibcの配布がありませんが、これは意図的です。何故かというと、libcが配布されてない状況に対処するのも問題の一部だからです。実際にこれがED CTFで稼働している時は、この問題に限り、自前ビルドしたlibcで動いていました。想定解は頑張って特定をするとかそういうクソ解法ではないので、ちゃんと考えましょう。

 

裏話としては、元々自分の研究課題として、Windows側でExploitを書いていた時期があったんですが、一定の成果が出たので、同じことをLinuxでやらせるような問題を作ろうと考えた結果この問題になりました。当時は僕がゴミだったので、「カーネルのコンフィグなどを適切にいじれば、returnするfdの番号をランダムに出来る」ということを知らなかったため、このようなランダム回数/dev/nullを開いて連番のfdを消費するというゴミ実装になっています。ごめんね。

 

Local Only 32 おすすめ度: ★★★★★★

www.dropbox.com

これもLocal Onlyシリーズです。32や64というのはbitを表していて、つまり、Local Only 32はx86の問題です。注意事項は64と同様です。

 

一般的にROPは呼び出し既約などの観点からx86_64上の方がx86上よりも難しいと考えられていますが、Local Only 64よりLocal Only 32の方が難しいという皮肉が、この問題の面白いところです。

 

このシリーズが解ければROPに関しては不安はないと言っていいでしょう。まあ本番でこれだけのROPを思いつけるかは保証できないけど。

発展課題としては、SECCONのいつぞやの予選に、ROP:Impossibleという良問があって(これにはとても面白い別解としてめちゃくちゃ楽な解き方があるんですが)、正攻法で解いてみるのがROPの実力を試すには良いと思います。個人的には大会中数時間で解けるレベルなのでやるだけです。それぐらいの時間で解けなければ反省すべきです。

 

Under Debugging おすすめ度:

www.dropbox.com

おすすめ度はバグではありません。0です。これはクソ問なのでやらなくて良いです。

どれぐらいクソ問かというと、解いてくれたint03さんやbataさんやhorityさん(解いてたか怪しい)には土下座しないといけないレベルのゴミカス問です(bataさんはポジティブな評価をくれた覚えがあって、聖人か?みたいな気持ちになった気がする。int03さんにはボロカスに言われましたが、それが正しい評価だと思う)。

 

言い訳すると、これもHeap is a tomodachi of mineと同様で、作問案はあったんだけど、思うように実装が出来ず妥協した結果、ゴミ面倒なだけの問題になりました。まあ面倒なExploitationの問題はたまに出るので、練習には良いかもしれない?俺はやりたくない。

 

binja CTFではこれも改題を出したいなあ。一応当時考えていた作問案は実現したし、いい感じで綺麗になったので。

 

Ninja no Aikotoba おすすめ度:★★★★

www.dropbox.com

burning CTFのExploitationの300pt(3問あった問題の内真ん中の難易度)だった問題です。これはかなり非典型というか、ad-hocで、しかも解法にはExploitationらしいExploitationテクニックは全く必要ないので、個人的には好きな問題です。現実性はかなり低いし途中のパートはうざいけど。

 

まあネタバレになるのであまり裏話とか意図は言うべきじゃない気がするんだけど、僕のポリシーとして、「Exploitationに関しては、初心者はまず仕様に強くなれ」というのがあって、それを体現した問題です。皆さん仕様には詳しくなろうね。

 

craSH(実際には2問として出題されフラグは2つある) おすすめ度:★★★

www.dropbox.com

これは完全に名前から作問に入った問題なんですが、かなり完成度は高くて、きれいな問題に仕上がったという自負を持っています。

一応、burning CTFの問題の中では最も難しい問題だったのですが、個人的にはこの程度は解けないと今時のCTFではやっていけないですし、今時のCTFにこの問題が出たらボーナス問題の部類です。

 

この問題の面白いところは、SEGVなどを引き起こすと片方のflagは取得することが出来るという点です。これは、burning CTFの運営の人から、作問の注文として「初心者でも解けるようなめちゃくちゃ簡単な問題を作って欲しい」と言われて考えた結果、この形式になりました。実際、普通のExploitationの問題は脆弱性を見つけるだけでは全く点数にならず、初心者にとってはどちらかといえばExploitを書くことが難しいわけなので、こういった形で部分点を設けるのはとても良いと思うし、もっとこの形で問題を作る大会は多くてもいいのになと思います。

 

以上が僕はExploitationジャンルでまともに作問した問題集でした。

解いてくれると、作った甲斐があったなと感じるので、もちろん嬉しいですし、感想や質問などは歓迎です。

CTFとの向き合い方 ~CTFで消耗しているすべての人へ~

この記事はCTF Advent Calendar 2016の25日目の記事になる予定だったのですが、タイムリーな議論が起きているため早い内に公開したいという気持ちと、3日目担当のBo Wangさんが記事を書かれていないように思えるので、3日目兼25日目の記事として足して2で割って14日目に公開したいと思います。この文章は1年以上僕の恨みつらみを込められて作成された文章です。

 

序文

近年、CTFがある程度人権を得て情報系の競技としてポピュラーになった気がしています。しかし、それにともなってCTFで消耗してる人が多くなった気がしましたので、僕も昔から消耗してきた身として、個人的なCTFとの向き合い方をポエムしようかなと思いこの記事を作成しました。

 

お前誰

最近はCTFを現役でやるだけの体力がなくなってきていて、もしかすると最近始めた皆さんは僕や僕のチームのことを存じ上げないかもしれないので、一応自己紹介を初めにしておきましょう。

筆者のCTF戦績の一部

  • SECUINSIDE 2014 Finals 4位
  • DEFCON 2014 Finals 13位
  • CODEGATE 2015 Junior 優勝
  • HITCON 2015 Finals 9位
  • DEFCON 2016 Finals 8位

 

一応CTFは5年ほどやっていることになり、おそらくこれを読んでいる皆さん以上か同じ程度には近年のCTFを理解しているつもりでいます。

一方でまだ学生の身分である私は、現実のセキュリティ、いわゆる業務などに関しては少し疎い面があります。勘違いしてそうな所はまたコメントなり個人的になり教えていただけると嬉しいです。あ、でも脆弱性報告とかはたまにしています。そのお金でデコンパイラ全部付いているIDA Pro買ったり更新しているので。

 

それでは僕が実際に見かけたいくつかの消耗パターンの、原因と思われるものに言及していきましょう。

1. CTFを語る時はジャンルと想定する参加者側のレベルに気をつけよう

当たり前な気はしますが、CTFにおける何かしらの主張というのは、ジャンルによって当てはまったり当てはまらなかったりすることがあります。何に関する話なのか(例えばバイナリを扱うジャンルに関してなのかなど)を明確にしましょう。

そして、参加者のレベルに気をつけましょう。こんなことはあまり言いたくないですが、どれぐらい出来る人間に関して言ってるのかによって、主張が正しいかどうか違ってくる場合があります。例えば次の主張は多分正しいです。「世界の有名なCTFの決勝に安定して参加しているようなチームは、実際のセキュリティの世界においても何かしらの偉大な功績を残していることが多い」。PPPやShellphishなどをみるとこれらのチームがアカデミックな世界においても類稀なる進捗を生み出しているのは明らかで、あるいはgeohotや韓国のチームは著名なアプリケーションの重大な脆弱性を報告している例がたくさんあります。逆にそうでないチームも含めて、言及の対象を「CTFを少しでもやっている人間」に広げると、さっきの主張は全く的外れになるでしょう。

 

2. 出るCTF、解く問題を正しく選んで消耗しないようにしよう

CTFを新しく始めた知り合いの話なんかを聞いていると、どの大会や問題に手を出せば良いのかということが分からず、適当にやってみた結果、何も分からなくてCTFの面白さに気づけないまま諦めるみたいな状態に陥っている人がいるように見受けられます。

このような人に送るアドバイスとしては以下のようなものがあります。

自分の出来る事、ジャンルを見極めましょう

情報セキュリティというのは他の情報系技術があって初めて、副次的に考える必要が生じる分野なわけです。つまり、何らかの分野のセキュリティを考えたいとなった時に、そのベースとなる技術の知識がない状態では考えようがないでしょう。それは情報セキュリティが競技化したCTFにおいても当てはまる話です。当たり前ですが、何の知識もない状態で問題を解ける人間なんているはずがありません。自分が何が得意なのか、どういった種類の問題なら解けるのかなどを見極めることが、CTFに参加し問題を解く第一歩になることは明らかです。この記事はCTF初心者に向けたものではないので、詳しく扱うことはありませんが、最近だとちゃんとそういったことを解説している記事とかはあるんじゃないでしょうか。よく知りません。

過去問を見てCTFの形式や傾向を見ましょう(例えばDEFCONにはWebは出ません)

常設型CTFサイトに関しては、自分の好きな時間に好きな問題を解けるわけですから特に言うことはありませんが、競技時間のあるCTF(常設型CTFのしっくりくる対義語欲しいんですけど誰か作って欲しい)に関してはそうもいきません。大抵のコンテストは24時間以上開催されるものが多いので、真剣にやろうと思うと、健康的な日常生活の時間を犠牲にしたり、社会人や忙しい学生の方であれば、参加するために事前から予定をあけるなどの労力がかかるわけで、参加コストが中々高いことは否定できないでしょう。そのように参加コストが高いコンテストにせっかく参加したにも関わらず、自分の解ける問題が一切でなくて時間溶かしたアビャ~となってしまっては、全くもって骨折り損のくたびれ儲けです。このような事態を避けるために有効な手立てとしては、出ようと考えている大会の過去問を眺めてみることです。大体どのようなジャンルの問題が、どのような難易度で出るのかということがはっきりします。もちろん年度によって多少の難易度のブレがあったり、例えばCODEGATEなどは数年に一度運営が変わってしまって何もかもが変化してしまうことだってありますが、特に初心者の方など、初めのうちは参加する前に自分の丈にあった大会なのかということは考えてもいいのではないでしょうか。知り合いの方を例に取ると、DEFCONはWebが出ません...

評判を見て出るCTFを選びましょう

悲しいことですが、大会の品質は常に保証されているわけではありません。一般に、実力の伴っていないチーム、運営が企画した大会というのは概して経験者からはクソCTFと呼ばれるものが多いのが現状でしょう。初心者の方からすると、何がクソで何がクソでないかというのは判断しかねると思いますが、大雑把に説明してしまえば、「問題の解法に論理的妥当性があるか」と「どのような立場の人間でも公平に解けるような解法が存在するか」ということです。後は個々人の感覚によるものになってしまいますが、「問題(解法に必要とされる発想)が面白いか」、「問題の典型性が低いか(既出でないか、ツールゲーでないかなど)」、「問題の現実性は高いか」なども、クソかどうかという判定において良く考慮される要素です。後半の要素に関しては、個人の好みとして割り切ってしまえるものが多いですが、解法の論理性と公平性に関しては、欠かしてはいけないものだと思っています。あなたは「URLを推測します。どこにも公開していませんが、ctf.shit.net/shit_problem_exampleというURLがあるので接続できれば答えが出ます」(もっと分かりやすい例では「僕はカレーが好きなので答えはカレーでした」)と言われて納得できますか。また、そんな問題から何を学べるんでしょうか。強いて言うならそんな大会には二度と出ないでおこうということでしょう。おそらく何がクソで何がクソでないかをそこまで判断出来ない初心者の方でも、このような問題には理不尽さやつまらなさというものを感じてしまうのではないでしょうか。そして、数多のコンテストが開かれている今日では、このような問題を平気で出してしまうような、全くもって考えが浅い運営がいるという現実があります。これは別に実力がないから運営をするなという話ではないのですが(まあ実力がなくて面白いコンテストができるのかには疑問がありますが)、せめて論理性だけは欠かないようにして欲しいことです。というかなんでこんな問題を出してしまうのでしょうか。このような理不尽を経験したことが、怒りを覚えたことがないのでしょうか。それは概してCTFに参加したことがないということで、だから僕はしきりに運営をする人間はCTFに参加すべきだというわけです。

 こんな当たり前に見える、一般に批判なしに受け入れるしかなさそうことを、いちいち言ってもらわないと分からない人が、問題を作ってるんでしょうか...(こみ上げる怒り)

学びは面白さとは少し独立してしまっているので、どちらかといえば競技として、僕は学びより面白さを優先すべきだと思いますが、どちらにしても学びがあるということは良いことですネ。

 

まあということで、参加者側は、CTFTimeやTwitterでの評判など、色々参考にして参加を検討する姿勢があって良いと思います。クソCTFに時間を吸われるのは時間の無駄です(一方で、中々この世からなくならないクソ問題を解くためにクソCTFに出て耐性をつけるべきという一理ある意見もありますが。一般にクソ問題を解く能力はなぜかクソ問題に費やした時間に比例する傾向が経験則上あります)。

 

3. CTFと実際のセキュリティと比較して消耗しないようにしよう

色々な運営などに携わることもあって、「セキュリティ関係の仕事をしているから」、「セキュリティに関連する技術を高めたいから」という理由でCTFに出ようとする人が多く見受けられるように感じます。あるいは、運営側もしかり。

ですが、僕は楽しむという目的がなく、義務や使命感のためにCTFに参加しているのであれば、すぐにやめるべきだと思います。それはなぜか。

実世界においてセキュリティに関連する何かをする時にCTFをする必要は一切ない

一例を上げましょう。

あなたは業務でマルウェアを読まないといけなくなりました。あなたはマルウェアマルウェア解析に関する知識が皆無です。この時、CTFに出て技術を磨くのは最善の方法でしょうか?

おそらくCTFは役に立たないことはないでしょうが、CTFでマルウェアを読まずとも、仕事場に読む環境があるのだからそちらで経験を積めばいいのではないでしょうか?そもそも問題で常にマルウェアが出るとは限りませんし、どの程度現実に即しているのかということは保証、判断しかねるでしょう。もちろんステップアップ的な面でCTFを使いたくなるモチベーションもあるのですが、それはCTFでなくても代用できる方法はいくつかあるはずです。

もう一例出すと、脆弱性を探すという行為に関しては、CTFだとexploitを書く必要がありますが、実際の脆弱性調査ではPoCを書かなければならないことは稀でしょう。怪しいなと思った部分は攻撃できるできないに関わらず全て修正すればいいのですから。

CTFは全く役に立たないか?

一方で、CTFに出ている人間が実際のセキュリティ関係の何かでは役に立たないというのも間違いです。たまにそういう主張をしている人がいるように思えます。ああ、勘違いしてほしくないのは、これは、「CTFに出ている人間が絶対に現実でも役に立つ」といってるわけではありません。相関がないと言っているのです。また、先ほども書いた通り、その人間のCTFの実力、つまり参加者のレベルにもよって、「役に立つ」かは変わるのではないですか。極端な例では、CTFに興味があって最近初めてみましたという人に、何も知らない上司が「君はセキュリティに強いのか、じゃあこれをやってみてくれ」と実務を与えて「役に立たなかった」と喚いているようなものです。そもそもCTFをやったことがない人はCTFをやったことがある人のCTFの実力を判定することは絶対に不可能なので、こういうレッテル貼りは良くないのではと思います。

CTFも強くて実世界でも強い人、CTFには出ていなくて実世界で強い人、CTFは強くて実世界ではあまり関係ない仕事をしている人、これらの3種類の人々がたくさんいる時点で、CTFと実世界の何かの相関を測ろうというのはありえないことだと思うのです。

 

しかし、これもまた一方で、CTFをやっている人間が実務では役に立たないという主張をする人の気持ちもよく理解できます。僕はこの文章から分かる通り、CTFを批判から庇護したいという気持ちは少々ありますが、どちらかというと実際のセキュリティにおいては全く役に立たないかあるいはする必要が無いという主張に賛同出来るところが多いです。

まず、大きな前提として「CTFは解けるように作られている」のです。もっと言えば開催期間の24~48時間以内に解けるようなサービスしか登場しないのです。それは非現実的でしょう。そもそも現実では解法があるのかどうかすら分からない"問題"を何日も掛けて調査するんですから。所詮CTFは箱庭のお遊びであって、結局現実の業務において必要なスキルや能力全てを問えるものではないということです。

 

しかし、これも、これもまた、一般には言えても僕個人からするとまだ例外があると思えます。

CTFはExploitationの技術を学ぶには最適なゲームです。

現実でexploitを、それもとても高度な代物を書く必要がある境遇にある人というのはとても少なくて、PoCを示すことで報奨金の金額が変わったり、顧客に脆弱性の深刻度を説明する際の説得力が上げられたり、jailbreakや諜報活動をしているなどで実際に攻撃する必要がある場合(これはよろしくないですが)ぐらいしかないので、ほとんどの人には当てはまらないのかもしれないです。

しかし、僕個人としてはこのような状況に陥ることがたまにありえるというのと、実際に陥るような仕事をしている人がいるということです。

例えばGoogleのProject Zeroは、今まで任意のコード実行が不可能だと思われていた脆弱性に対して、任意のコード実行を獲得する手法を公表することがしばしばあり、The Poisoned NUL Byte 2014 editionもその1つです。これは簡単に言うと、「heapのメタデータを1byteだけNULL文字で書き換えられるという脆弱性で、任意のコード実行は可能か」という未解決だった問題で、答えはyesだったという話です。上記のURLにも書かれている通り、これは非常に攻撃可能か疑わしいぐらいにとても小さな脆弱性で、クラッシュ以外引き起こすことが出来ないと判定されて修正の優先度を下げられる可能性すらあるようなものなのです。そして書かれている通りこれはとてもwargame、CTFらしい状況というわけです(ということもあって、少なくともExploitationの問題に関しては、現実性という指標を持って測ろうとするのは良くないのではないかと思います。"CTFらしい状態"に、現実のExploitationがなっているのですから、問題の現実性もクソもないです)。

なぜCTFらしいのでしょうか。まず1つは、CTFは如何なる問題設定もし得るという時点で、色々な場合においてどうexploitを書くかということを練習できるわけです。これは教科書的なROPの攻撃方法だけ知っているというのでは対応出来ない問題が出題されても対応できるような、攻撃手法やheapなどのexploit対象に対する本質的な理解が深まることを意味しています。

もう1つは、CTFでは攻撃に必要な最小の条件を考えやすいということです。これは出題側の話になりますが、例えばExploitationの問題を出すとして、どこまで使える脆弱性や環境に制限を付け加えても解くことが出来るのかというのを考えることによって、難しい問題を作ることができます。poisoned NUL byteも「脆弱性の中でもcriticalになりづらいoffbyoneでかつNULL文字でしかbuffer overflowしない」という時点でその一例であって、PPPは自身の主催するPlaid CTFにおいて、これを本質とした問題Plaid DBを出題し、一時期騒がれました。数年前までのCODEGATEにも、とても解けるようには見えない問題に対して知られていない攻撃方法を考えされる様な形で高得点問題を出す傾向がありました。

 

論旨を正しく抑えられる文章を読む力のある人であれば、「こいつここに来て主張が二転三転しているぞ」と思ったかもしれませんが、結局の所全体を通して、僕が「CTFと現実を結びつけること」に関して言いたかったのは、様々な主張があることも、そう主張する理由も理解できますが、無限に例外を考えられるので、不毛だからマジでやめろということです。

 

結局CTFとはどう向き合うべきか?

CTFはつまるところ、「やれば少しは学びがあるのでそこそこ美味しい遊び」という認識を持つべきです。正直当たり前の結論だと思うのですが、それでも時たま物議を醸すことがあるということは、この認識が出来ていない人が多いのでしょう。趣味でトライアスロンをしたりするのとあまり変わりません。

個人的な話をすると、僕はCTFの本質はパズルであると思っています。受験における有機化学がパズルであると主張されるように、CTFも必要な単調作業、知識をすべて取り除いた時、本質として残るのはパズルでしかないと思っています(もしかすると、「パズルになっていない問題は、面白くない問題やクソ問である」と言ってしまえるかもしれません。流石に過激かな)。パズルは好きな人がやるものです。数独が嫌いな人は、数独の大会に無理して出るものではないし、または数独の問題を作るべきでもないでしょう。スリザーリンクに面白さを感じない人は、スリザーリンクを面白いと思う人が、どういう問題のどういう所に面白さを感じるか分からないでしょう。その状態で"面白い"問題を作れるわけがないでしょう。よく周りのCTFプレイヤーが"脳汁が出た"という表現を使いますが、パズルを解くことによって生まれる、そのようなアハ体験を経験したことがないのであれば、あなたはCTFを理解していないのかもしれません。

もう一度引用しましょう

 僕たちは超能力者になりたいわけでも、スクリプトキディになりたいわけでもなく、頭を使ってパズルを解きたいだけなのです。学びを求めてCTFをしてる人には反感買うかもしれませんが、上に書いたように僕はその場合CTFじゃなくても大丈夫だと思っているので、なぜCTFか、CTFでないといけないか、CTFに何を求めているのかといえば、頭を使うことだと考えます。

 

まとめ

1. 3. では、CTFについて一般論を語るのは難しいということを説明したつもりです。

そして2.では、特に初心者の人がなにで詰まっているように見えるかということとCTFの腐敗について紹介しました。流石にたくさんの人々全員は相手していられないので、親切に色々解説する気力はもう僕には残っていませんが、後は皆さんで考え、なんとかしてくれることを祈っています。

 

以上が僕のCTFに対する距離の取り方、考え方であり、皆さんの参考になればと思いこの記事を作成しました。意見、質問、反論等はこのブログのコメント欄に書いてもらうのが一番良いと思います。よろしくお願いします。炎上だけは怖いのでやめてください。

heap exploitationテク走り書き

これはCTF Advent Calenderの記事でもなんでもありません。

 

なんか最近CTFから退いていたので、色々とglibcのheap allocator周りのpwnテクに発展があったりしたかなあと思い眺めてたんですけど、面白いものはほとんどなかったと共に人の書き方があまりにも辛い感じになっていて、ボケが入っていて良く過去の記事を参照してexploitを書く僕からすると当てにならなくて辛かったので自分用に少しメモっておく。後皆雑にExploitationテクに名前つけすぎ。

 

House of *系

前々からあったテクだしよく使いはするんだけど他人のWriteup見てて名前が出てきてもどのテクがどれを指してるのかよく分からなくなるのでメモっとく

House of Mind

arena forgeして任意のアドレスをheapのアドレスで書き換えてるだけ。

sploitfunのブログ書き方が悪いから一目で何が本質なのかマジで分からんし勘弁して欲しい。GOTとかに制限している意味もないし、もっと言うと実はHouse of Mindはまだ弱い。

結構内部で複雑な動きするから条件は書くのめんどい。自分の過去のコードパクるといい。

House of Force

topのサイズを無限大に飛ばすことで任意のアドレスをtopからのoffsetで表して返せるようにするやつ。

House of Lore

Shellphishのgitlabに改良版?っぽいの上がってるけど、smallbinに入るようなfreed chunkの、bkを書き換えるという自明なことをしているだけだし、当然assert抜けるのにheapのアドレス知らないといけないのでクソ弱い。まあアドレス知ってたら大体のbinで任意のアドレス登録出来るよってだけ。当然fastbinsの方が強い。

よく分からないのはfastbinsの方はHouse of Loreと呼ぶの?ということで、とりあえず皆さんに言いたいのは、テクニックに名前付けたりする時は、ちゃんと責任持って、何をどうした時にそう呼ぶのかをちゃんと明確に記述して欲しい。smallbin限定なのかどうかとか(しかも仮にsmallbin限定なら弱すぎるでしょという話で、それはそれで嫌)。後下にtopあっちゃダメとか、topあろうがなかろうがいけるとか、全部書けと。heapはコード量多いからどこでどう引っかかるかはコード読みながらやらないと分からないし、テクニックとしてある程度脊髄反射的に使わせたいのであれば、それぐらいはすべきでしょう。

House of Spirit

sploitfunのコードはいちいち理解に不必要な要素が多くて読みづらいな

fastbinsはアドレスの整合性チェックしてないのでbssとかのアドレスも余裕で登録できるというだけ。というかここら辺のテクニックは全部大体同じ性質から来る手法の亜種なのに、わざわざ別に扱ってるのが理解できない。fastbinsはn重にfree出来る話とかも全部本質は同じなんだけど、こいつら理解せずに使ってるんじゃないかという気持ちになる。

pzipの時に、本質的にこれと同じことを使って、chunk内にfastbinsのchunkを作って入れ子にすることで、外側のデータをいじる時にfastbinsのchunkをいじれるというものを使うんだけど、これは逆に中々に汎用性が高くかつ忘れがちなテクニックなので名前付けたほうが良いんじゃないのという感じがする(pzipはこれ使っても他に色々あってしんどかったと思う、解いた問題いちいち覚えてないので忘れた)。

 

Unsafe Unlink

shellphishの所に一応コードはあるが、これも正直マジで理解しづらい。どうやったらこんなに分かりづらく書けるのか本当に疑問。多分printfがうざいのも一員。別に実行時に確認したい情報じゃないんだから説明はコメントで良いんだよ。

見るならinazさんのコードが良いと思う。

既知のアドレスAを持つメモリ内にheapのアドレスBが入っていれば、A+定数をBの中に入れておくことで、B周りは矛盾なくunlinkが出来るので昔懐かしのunlink attackでA周りの値をA周りのアドレスに書き換えられるというだけ(基本的にexploitationにおいて大事なのは、どの領域をcontrol出来るか、つまり各アドレスはどの領域に属するかということなので、定数を無視すれば、概ね*A=Bであったとき、*A=Aとなるような操作が起こると思えばよい、条件式と起こる操作の式を考えるとまあそうなるよねということが分かる)。

shellphishのコードとinazさんのコードはかなりテクいことをしているけど、本質はunlinkなので、サイズとprev_inuseを消さないと発生しないということはないが、あのやり方はかなり汎用的でコードを深く潜って起こる操作ではないので、基本あれでいいと思う。HITCONの2014のstkofか何かを解いた方が多分理解しやすそう。

 

chunk size overwrite attack

なんか何故かこれは名前がないのでinazさんの呼び方を引用する。連続する3つのchunk、A, B, Cを考えた時、Bをfreeした上で、脆弱性によりそのsizeをより大きいものに書き換えた場合、BとCを重ねられる。本質的にsizeのみ書き換えられfd, bkとかはノータッチなこととunsorted_bin周りのチェックが雑なことによって、unsorted_binの処理に矛盾しないことによる。

 

Poisoned NULL Byte

これも本質は同じunsorted_binの整合性にあって、今度は逆にsizeを小さくした時、どうすればexploit出来るかを考えたものと捉えるとよい。

(なんか昔いくつかのPlaidDBのwriteupを眺めていると、他にもoverlapさせる手順があったように思うんだけど覚えてないんで誰か調べて欲しい。とりあえず一番有名な奴を下に書く)

上と同じ状況を考えた時、Bのsizeの下位1byteが0でなければ、NULL byteによるoverwriteは、sizeを小さくすることを意味する。上と同様に、これによる矛盾を検出する機構は今の所glibcには存在しないので、そのままBはunsorted_binにあり動き続ける。小さいsizeのallocationを行って2個chunkを返させる。もちろんよほど小さくない限りはunsorted_binからのallocateが優先されるので、Bがsplitされて2つの領域に別れて返される(B1, B2としよう)。allocationでunsorted_bin内のchunkからsplitした領域を返す時、隣り合うchunkの整合性を保つために次のchunkのprev_sizeを書き換える処理があるが、今回の場合においては、B1やB2のサイズすなわちBのサイズを元に計算するので、Cのprev_sizeではなく、もう少し手前がprev_sizeと認識され書き換えられてしまう。つまりCのprev_sizeは書き換わらないので、Cのprev_sizeを判断基準とする処理では、Cの前にあるchunkはB1のままである。この状態でB1, Cを順にfreeするとconsolidate backwardによりB1がconsolidateされるのでB2がoverwrapする。

 (追記:

 

 

 )

 

unsorted_bin Attack

これもまたunsorted_binの処理の甘さに着目すると分かる手法。unsorted_bin内のchunkのサイズにjust fitなallocationが来た場合、特に整合性のチェックなど無しにchunk->bk->fd = unsorted_chunks (av)した上でchunkを返す処理がある。よってunsorted_bin内のchunkのbkを書き換えておけばmain_arena内のアドレスなどが任意のアドレスに書き込まれる。

 

これぐらいかなあ。直近で驚いたものといえばHITCONのhouseoforangeのsysmalloc内の_int_freeぐらいなんだけど、今の所作問案が消費されていなくて安心という気持ちしかない。というか早く公開したい気持ちしかないんだけどbinja CTFの予定立たなさすぎて辛い。

 

Codeforces Round #176 (Div. 1) D. Tourists

JOIerお家芸感。なんかこれはJOIerは結構見た瞬間簡単だなあと思う気がする。おそらくDではない。

 

原点にある点がn個あり、i個目の点は時刻q[i]に原点を出発し、x軸の正方向に沿って速さ1で進む。また、それとは別にm個の線分が存在して、i番目の線分は時刻t[i]に区間[l[i], r[i]]を覆うように一瞬の内に出現する。各点について、点が線分に覆われながら移動している時間の長さを求めよ。

 

なんか本当に簡単で、div1Dにしては簡単だと思うんだけど、1つの線分(l, r, t)に注目した時、q[i] >= t-lであるような点iはその線分によって、r-l秒覆われていることになる。そして、これはどう見てもqに関して単調性がある、すなわち、q[j] >= q[i] >= t-lであれば、点jもr-l秒覆われることになるから、点をq[i]で昇順にsortしておけば、二分探索により、r-l秒覆われる点が全て分かる上、imos法を用いれば、全ての線分について考えたときの具体的な秒数の合計も一瞬で分かる。ここで少し怖くなるのは、t-r+1 <= q[i] < t-lであるような点iについては、点が移動している途中で線分が出現するので、具体的には、q[i]+r-t秒だけ微妙に覆われることになる。しかしこれも同様に二分探索とimos法によって対応可能で、どうするかというと、二分探索でt-r+1 <= q[i] < t-lを満たすiの範囲を求めた上で、定数r-tを普通のimos法で計算(A[i]にi番目の点のこの定数に関する累積和が入るとする)、定数1をimos法で計算する(P[i]にこの累積和が入るとする)と、微妙に覆われた時間の累計はP[i]*q[i] + A[i]で求まる。1次関数の累積を求めているイメージ。基本的にはこれだけなんだけど、後は線分に重複があるところだけ解決しないといけない。これは、各座標において、その座標を覆う線分の内、tが最小であるものを求めればよい。これは結構明らかだと思う(tが最小であるような線分以外を無視すれば重複は解決され、かつ最も覆われる点が多い)。実際に各座標についてやると当然計算量がやばいが、これは簡単なイベント走査で解決できる。線分(l, r, t)についてイベント(l, t)とイベント(r, t)を作成し、イベントの集合を1つ目の要素に関してソート。multisetを1つ使って(l, t)が来たらtをinsert、(r, t)が来たらtをeraseしていけば、連続する2つのイベント(x1, t1), (x2, t2)について、区間[x1, x2]におけるtの最小値は、イベント(x1, t1)を処理し終わった後のmultisetの最小値となる。これも多分典型。なので各イベントの処理後に新しい線分の集合に、それらの値を追加してやれば、重複を取り除いた線分が全て求められて、解ける。このやり方ではどうやっても、重複を取り除いた線分は流石に自明にO(m)個しか存在しないので、かなり適当に追加しても問題ない。

 

ちなみに初め誤読して、「点は線分に覆われなくなったらその場で止まる。」という条件があると思っていたんだけど、それでも解けるので考えてみてください。

Codeforces Round #176 (Div. 1)

codeforces.com

はいサイアクの1完。

Bが分からない時は本当に辛いンゴねえ

 

A. nが与えられる。1~nの順列P[1]~P[n]が「∀i(1 <= i <= n) P[P[i]] = n+1-i」を満たす。このようなPを1つ出力せよ。そのようなPがなければ-1と出力すること。

順列なのでグラフではdirected "cycle"(cyclicではない) graphの集合と対応する。グラフにおいては、上の条件は、頂点iから有向辺を2本辿った先の頂点が常にn+1-iであることを表している。頂点n+1-iから2本辿った先が頂点iにならないといけないから、そのような条件を満たす順列は、大きさ1または4のdirected cycle graphのみで構成されている(ただしnが奇数でかつ頂点(n+1)/2についてのみ大きさ1は許される)。

よって与えられたnをまず4で割って、剰余が2, 3であればそのようなPはない。

後は適当にやればよくて、nが奇数であれば、ans[(n+1)/2] = (n+1)/2にだけ気をつけて、(k)→(k+1)→(n+1-k)→(n-k)→(k)みたいな閉路を考えて答えを構成してやればよい。

なんかめっちゃバグった。アホ。

 

B. 1~nの順列P[1]..P[n]と自然数kをとって、P[2]P[3]...P[k]P[1], P[k+2]P[K+3]...P[2k]P[k+1], ...を新しい順列として返す写像f(P, k)を定義する(つまり順列をk個ごとで区切って、区切った中で先頭の数を最後に移動させる)。L[1] = [1, 2, 3, ..., n]として、L[k] = f(L[k-1], k)と置く。L[n]を求めよ。

まず最後に移動させる操作の回数は、Σ[i=2..N]ceil(N/i) = O(NlogN)であるから、L[1][1] ~ L[n][n]のn^2個の数の内、いい感じに最後に移動させる数だけを処理することが出来れば、つまり1つの区間内のシフトをO(1)で出来ればO(NlogN)が達成できることはわかる。

ここからが問題で、僕はL[n]におけるi番目の数がL[1]においてどこにあったかというのを独立に考えようとしたのでドツボにハマった。つまり、L[1] ~ L[n]を正方形に並んだn^2個の数だというイメージで見た時、僕は縦に区切って処理しようとしてしまったんだけど、横に区切らないといけなかった。横に区切る、つまりL[k]からL[k+1]を一度に求めようという気持ちでいくとちゃんと出来て、これは、最後に移動させられる数を無視してみると、左に1個ずつズレていくだけだから、このズレを実際にはズラさずに固定してやると良い。どういうことかというと、配列L[k]から配列L[k+1]を作る時、本来ならL[k+1][i-1] = L[k][i]とやるわけだけど、定数1分ずつ全てがズレるのだから、i' = i-1と置いてやれば、L[k+1][i'] = L[k][i]と出来て、L[k+1]を新しく生成するのではなく、L[k]をinplaceに置き換えることにすると(dpのメモリ削減みたいなもん)、1ズレる数に関しては値を参照したりコピーする必要がなくなる。後は、最後に移動させる必要のある数だけ、L[k+1][i+k-1] = L[k][i]みたいな感じにする必要があるから、i'とinplaceを考えると、後ろからL[i'+k] = L[i]で更新していくだけでよく、上の評価式からこの更新の回数はO(NlogN)であるから解ける。

 

ちなみにL[n][i]がL[1]においてどこにあるかという考え方だと、O(NlogN(logN+loglogN))は達成できるんだけど、N=10^6でしかも旧版の問題に対する処置としてTLEが1/2の1秒だから普通に間に合わない。

 

自分用メモ: 流石にどっちで対処するかぐらいちょっと考えましょう、というか結構dpの変数置き換えはよくやるし好きなんだからこれぐらい思いつくべき