雑記

書きたいことを書く

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

まずこの括弧列(?)の生成規則について考えました。いろいろと睨みながら考えていましたが、括弧列の深さが深い方に浅い方が取り込まれる、同じであれば連結という結論に至りました。(Union-Findの併合とちょっと似てる)

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

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

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をします 解説が欲しかったら僕にリプを飛ばしてください。急いで書きます。

twitter.com

ソース:

gist.github.com

 

おまけ:asm-4

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

 感想

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

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

f:id:keymoon:20181029013432p:plain

 

CyberRebeat CTF Write-up 兼感想文

 概要

2018年9月8,9日にかけて開催された、CyberRebeatCTF2018のWriteUp 兼 感想文です。僕の所属しているチーム「生活習慣崩壊ズ(SeikatsuKowareru)」は10時間程度で5チーム目に全完し、同率一位となりました。僕は6問通しましたが、1問解けたのに通せなかったものや3問のなぞなぞ枠を鑑みて実質4完かなぁという気がします。

ということで、僕が解けた6+1問について書いていきます。

Monero

  • genre : Trivia
  • difficulty : 10
  • point : 116pts
  • solved : 127

通貨名は定かではなかったが、日本で、自身のウェブサイト上にこのソフトを設置した何人かのユーザが逮捕されている。とあったのでまぁcoinhiveだろうなと思った。あっていた。

Tweet

  • genre : Recon
  • difficulty : 10
  • point : 113pts
  • solved : 130

Let's check our official twitter account!とあるので、公式アカウントを見た。あった。

ここまでは出先だったので、スマホで解いた。

ここでエカスドクィナにPPCを全て解かれてしまい、PPC担当だった僕は意気消沈していた。そこで見るからに作業ゲーっぽいCrosswordをやることにした。

Crossword

  • genre : Trivia
  • difficulty : 100
  • point : 203pts
  • solved : 71

f:id:keymoon:20180909011447p:plain

ググり力が試される問題だと思った。ひたすらググってペイントで頑張った。よくよく見るとCyberRevertと誤字してしまっている。つらい(Iに入る”E”をエスパーできたのが個人的に嬉しいポイント)

Alpha

  • genre : Stegano
  • difficulty : 100
  • point : 218pts
  • solved : 65

画像でAlphaと言ったらまぁアルファ値だろうと思い、C#で画像を読み込む方法を調べる。

分かったので実装し、初めの方を回すと大体アルファが253だなぁという感想を持った。そこで場合分けしてピクセルを文字1つとしてテキストに出力し、いい感じで見てあげると文字が見えた。

gist.github.com

f:id:keymoon:20180909013652p:plain

ここで漁師もこの問題を解いていたらしく、フラグのテキストファイルを開いた瞬間に「解けたよw」って言われた。おもしろかった。(彼はGimpかなにかを使ったらしく、それのほうがスマートだなぁと思った)

f:id:keymoon:20180909013835p:plain

Last 5 boxes

  • genre : Stegano
  • difficulty : 200
  • point : 414pts
  • solved : 14

MP4の知識はあったので、まぁ最後のBoxを見たらヒントが書いてあるのかなぁと思って見た。そうすると怪しいのが5個本当にあったので、1つ目を見た。PNGシグネチャが見えたので、ファイルを繋げる系かなぁと思った。シグネチャがズレていることから考えるに、おそらくBoxにはオフセットがあるだろうな、と思った

大体同じ24byteのオフセットかな、と思ってオフセットを除いたファイルを5個作り、それをつなげて祈りながら拡張子を変えたらflagが出た。

f:id:keymoon:20180909014505p:plain

f:id:keymoon:20180909014631p:plainf:id:keymoon:20180909014826p:plain

Opening Movie

  • genre : Misc
  • difficulty : 100
  • point : 377pts
  • solved : 21

開始すぐに目を通したときは、sourceにwasmが見えたのでpwnかぁと思ってアセンブラ担当のぞへに投げようかと思っていた。しかし、よく見てみるとdllが落ちてきている。どうやらC#等をブラウザ上で実行できるライブラリのようだ。

ILSpyに入れていろいろ見ていると、300回以上のときにFlagを描画する機能がついた関数を見つけた(BuildRenderTree())。これはframeを生成し、そのsrcに変数txtを指定する、というソースのようだ。txtは文字列をmd5でハッシュ化したものなので、同様にハッシュ化してあげてそこにアクセスすれば終了。

f:id:keymoon:20180909015327p:plain

f:id:keymoon:20180909015719p:plain

Signature

  • genre : Crypto
  • difficulty : 200
  • point : 419pts
  • solved : 13

ユーザー名Kanaとしてログインさせる問題。guestのログイン枠が与えられている。

始めはソースを見逃していた。それで10分位溶かしてしまった。単純にsaltつきのmd5とログイン情報を一致させているようで、どこにもWeb的な脆弱性を見つけることはできなかった。(Cryptoだしそれはそう)

gist.github.com

 

Cookieのlogged_inが0以外であれば受け付けるようなので、そこを弄ってハッシュを合わせるという検討はついたが、それ以上は何もわからなかった。

Cryptoしそうなところといえばmd5脆弱性ということで、漁師が伸張攻撃なるものを見つけてきた(天才)。kを未知変数(この場合はSalt)、mを既知としたときに、md5(k+m),|k|(kの長さ)が分かっている場合、任意のaに対してmd5(k+m+b+a)が分かるbがあるという。

この後の文章で謎の英字一文字が出てきた場合は、上の伸張攻撃の説明に出てくるものだと思って欲しい。

kの長さは分かっていないが、今回はSaltがFlagと一緒という制約もあり、高々50以下なので余裕で探索ができる。

なので、bの部分をlogged_inの後部につけ、aは&id=Kanaにするのかなぁと思った。

logged_in=0となる非ログイン状態でもHashが与えられていることに気が付き、mをlogged_in=0として、logged_in=0{b}&id=Kanaとすればうまくいきそう、と思った、しかしなぜか上手く行かなかった。なぜ上手く行かなかったかはわからない…。

途方にくれているうちに、えかすどがlogged_in=1&id=guestをmにすればいいのでは?と提案してきた。後から&id=KanaとするとidはKanaになる上、guestログインでのHashは与えられているので行けると思った。しかし、HashはCookieからそのまま取っているわけではなく、"logged_in={$parse["logged_in"]}&id={$parse["id"]}"と整形した後の文字列から取っていた。そのため、愚直にlogged_in=1&id=guest&id=Kanaを送るだけでは上手くいかない。

少し工夫をして、logged_inの値を1&id=guestとするといい感じで行きそうだと感じる。なので1&id=guestをURLエンコードし、送信cookieはlogged_in=1%26id%3dguestとした。

しかしどうにも上手くいかないのでいろいろ考えてみたところ、Cookieを受け取るところとparse_strの部分で二回URLエンコードに対するデコードが掛かっているよう。なので、エンコードされた%に対して更にエンコードをした。それによって、ついに通すことができた。

伸張攻撃を行うのに使ったツールはHashPumpというツール。以下のソースはHashPumpでハッシュとbを生成するシェルスクリプト、それを鯖に投げてログインを確認するC#プログラムに分かれている。C#で参照されているdata-signature.txtはシェルスクリプトのアウトプット。ファイルはソースコードの下に添付した。

gist.github.com

data-signature.txt - Pastebin.com

感想

ラストの問題を通して全完したので喜びはとても大きかったです。

チーム全員のバランスがよく、分散して問題が解けていたのでやっていて楽しかったです。全く自分がわからない分野(Cryptoやrev)をチームメイトが通しているのを見ると「天才だなぁ」という気持ちになりました。また、最後の問題は総力戦みたいな感じがあって、チーム戦特有の「相手の天才考察の上に考察を構築する気持ちよさ」みたいなものがあり、ゾクゾクしました。

今回はILやMP4と言った自分の知識範囲のものが偶然複数出てくれたので個人で満足の行く成績が残せましたが、PPCTCPコネクションで苦戦したりなどと基礎部分ができていないという印象が残りました。体系的に過去問を解くなどの勉強をしていきたいです。

チームメイトのWriteUpは以下↓

kobaryo222912.hatenablog.com

ecasd-qina.hatenablog.com

CyberRebeatCTFの参戦記とwriteup

SuperCon2018参加記~本選篇~

はじめに

SuperConってなに?とかは以前の記事で説明しました。

keymoon.hatenablog.com

結果

落ちました。

感想

予選篇とか書いてるけど本選なかったらクソザコですよね、まあ通ると信じてこうしましたが

SuperCon2018参加記~予選篇~ - 雑記

しょぼすぎる。ひゃ

通った人はおめでとうございます!落ちた人の分まで本選で戦ってきてください。

えーなんか、Twitterは割と荒れてましたね。(去年優勝のWA_TLEさんも落ちてたり、前回二位のチームメイトを擁する僕たちも落ちてたり。)

僕はそんなに文句を言うつもりはないので、適当に燃えてたところを纏めてみたいと思います。

審査が遅延した!地震はどうせ言い訳だろ!

 

こういうことなので普通に地震のせいでしょう。

10ミリ秒単位での改善は本質的なのか?

これは思わないでもないですが、細かい枝刈りをさせるのが出題者の意図だったのではないか、要するにこれが本質だったのでは?と感じます。

ジャッジが不透明!

テストケースもそのうち公開される気がします。(そのときに明らかに早い/遅い等があったら別ですが。)

境界外参照が発生しうるコードが通っている。

単純に非本質的なところで落としたくはないという意図だった気がします。知らんけど

サイレントお祈り

予選落ちメールは同時に送ってほしかったです(一日経っても送られてきていない気がする)

なんでこんなまとめしたの?

精神を安定させたいからです

さいごに

来年は真面目に取り組むぞい

 

SuperCon2018参加記~予選篇~

はじめに

 SuperCon2018の予選に出ました。僕は提出コードにほぼ手を加えてないので実質マスコットですが、キーボードが打てるマスコット*1としての仕事はしたのでここに記します。

ところで

予選篇とか書いてるけど本選なかったらクソザコですよね、まあ通ると信じてこうしましたが

6/20 更新しました

keymoon.hatenablog.com

SuperConってなんやねん

 高校生がチームで参加できるプログラミングコンテストです。予選、本選ともに長期間*2で一問を解きます。スコアで競う場合もありますが、今回の予選は特定の解を出すための実行時間で競います。

 チームは2,3人で、本選出場者は関東・関西でそれぞれ10チームずつです。

 本戦だとスーパーコンピューターを使って問題を解きますが、予選は普通のパソコンで解ける程度の問題です。

問題概要(PDF)

 予選に関係する1級認定問題のみ説明します。*3

 端的にいうと、

格子上で(0,0)を始点とする閉路のうち、交差しない(同じ点は1度しか通らない)かつ特定の点を通らないような閉路の総数を求めなさい

という問題です。*4(分からなかったらPDFを見るなりすると雰囲気が掴めます)

僕がしたこと(概要)

ひたすらテストした 以上。*5

詳細

C++が書けないので、C#でexeを実行してランダムにテストケースを実行させ、ベンチマークを取ったり愚直解と比較したりするテストを書きました。ログはJsonで吐き出して解析しやすくしました*6

愚直解ですが「絶対に間違いでないと保証されている解」が欲しいとのことで最低限の枝刈りを*7行ったDFS*8で解を出しました

最高320万くらいで、6分くらいで終わります(平均3分程度。遅い)

失敗一覧

人の失敗って見てて面白いですよね。教訓にしてください

  • めんどくさがり性のせいでtesterを書くのが1日遅れた*9
  • コンパイルオプションの-Oを-oとしていてコンパイルオプションがかかっていなくて、遅い奴で動かしていた*10
  • パフォーマンスを比較する時に別実行ファイルを比較しているつもりでいたら同じ実行ファイルを比較していた*11
  • Seedからの復元性がなかった*12
  • そもそもこれを書いてる時にまだ提出が済んでいない。

経過

5/30

SuperCon、組めたら組もうね~ってKMCodeと話した

5/31

部でいろいろ聞いて回ったけど確定した1チームしか観測できなかった

~~(僕は)虚無~~

6/10

SuperConに出るっぽい流れになったので取り組むことに。

いきなり1000msが来て、その少し後に600msのソースが降ってくる。

僕がテスターを作る感じになったけど、サボる(クズ)

6/11

テスター今日中にできる?って5時くらいに聞かれる。焦って適当に書いた

6/12

一晩寝かせて400ケースくらい調べたけどWAが出なかった。

いろいろと改善が降ってきて試したが、漏れ/被りがちらほら出て怖かったのでやめた(1/1500くらい)。

オーバーフローに気がつく。ソースコードへの唯一の貢献!

テストケースをいっぱい錬成して試すことに。テストケースはハッシュ値から再生成ができるようにする

6/13

解析したデータをスプレッドシートとかに起こした

最適化オプションの指定漏れに気がつく。死

指定し直して適当に解析したら400ms程度を出す。このまま提出用のコードを書いて後はテストするだけ

あれ?????テストケースの再生成できなくない?????→テストケース5000個くらいが無に帰す

引数自体を愚直に保存すればいいのに。って思ってそうする

チーム名を適当に考えるも何も思いつかない*13

ここらへんで英字8字縛りに気がつく→何も思い浮かばずに死

6/14

パソコンの自動スリープをオフにして持ち運び中もテストケースを錬成できるようにした。ThinkPadのぬくもりを感じて「これが彼女か…」ってなった。*14

昼休み(12:20頃)に提出準備*15。その頃にテストケースが4000個くらい生成できたので並行してテストする。

WAが0だったので満を持して提出。

テスターを公開すればコンテスト後に情報が迅速に集まる可能性があるな~って思ってテスターを改修。

あとテストケースが10000個くらいあると嬉しいかもしれないと思ったのでマイニングを継続

6/15

334のがしたけどテスターの改修が終わった ガバガバだけど動く

みんなの報告を全裸待機 それだけ*16

感想

つかれた。僕がポンコツで相方さんに迷惑がかかるので割と申し訳のなさみりてぃが高い。

なんかね、本選に行けたらいいねって感じです。*17*18

ということで

なんか最後の方にも書いたけどテスターを公開します。情報が欲しいです*19

一応コマンドラインでヘルプとかは完結するようにしましたが、readmeを読むと使い方がより詳細に書いてます。

ダウンロードリンクは以下です*20

ダウンロード

*1:SuperCon、マスコットとしてついていくとは言ったけどキーボードが打てるマスコットとしての作業程度はする()

*2:予選は15日くらい、長い。

*3:肩慣らしみたいなのがついてますが、それはどうでもいいです

*4:自己回避ループ (Self-Avoiding Loop、略して SAL) と呼ぶらしい

*5:というとちょっと嘘で、一箇所オーバーフローを見つけた えへへ

*6:区切りのカンマを忘れて死んだりとかした

*7:マンハッタン距離が残りターン数より少なければ切る,スタート地点の近傍が埋まったら切る

*8:いつもBFSなのでなにげに書くのは初めて

*9:謝罪しか無いです。懺悔of懺悔

*10:バカすぎる

*11:差が出ないしWAがも出ないしで喜んでいたら死んだ

*12:後述しますが、クソ致命的だった

*13:候補案:Tourist抗酸化物質国務長官,スーパー皆伝68

*14:電車で発熱するPCが入ったケースを抱いて壁にもたれていた時に、PCケースとお布団の類似性を見出した。

*15:準備室のパソコンがポンコツでむっちゃ固まった。

*16:Keidarooさんが提出できるかが割とヒヤヒヤでした

*17:正直どんくらいのタイムなのか、高速化の方針があってるかとかが無茶苦茶不安でマジで不安です

*18:というか恣意的に落とすコーナーケースとかをあまり検討しなかったので結構怖い

*19:解析したら是非、というかTwitterでつぶやいてくれ~~~~

*20:ソースは本選で使えそうな気がするので一応非公開です。たった100行くらいだけど。