Category Archives: 日記

ISUCON8で準優勝しました

(書きかけ)

これまで予選3回、本戦3回と参加させていただいているISUCONですが、今回のISUCON8でようやくランクインすることができました。
うまくやれば優勝できていたと思われるだけに悔しいーー!
まだまだ精進しないと…という感じです。

感想はともかく、何をしたか、何をしていれば優勝できたか、他に何をやることがあったかまとめておきたいと思います。

メンバーはいつもの3人、 @__math @misodengaku @chibiegg
SECCONで一緒に出てる @aki33524 は前回と同様釣りに出かけていました。

明確に決めてるわけではないのですが、役割分担としては以下のような感じです。

  • @__math (まーす先生) アルゴリズム、コーディング
  • @misodengaku (みそでん) データベース、エスパー
  • @chibiegg 取りまとめ、インフラ、お茶汲み係、雑用

時系列順に

まずは時系列にやったこととその効果をスコアで振り返りたいと思います。

競技中はソースコード、設定ファイル全てをGitHubで管理しています。
ブランチ毎に作業をして、切り替えながらベンチマークを実行し、バグ無く実装できたものをmasterにマージする方法でやっていました。

そのため、スコアのグラフはところどころ複数の機能実装を交互にテストしているため、実装と効果の関係を誤って記載しているかもしれない点についてはご了承ください。

事前準備 (こたまご)

GitHubにプライベートリポジトリを作成し、二人を招待しておく。
SlackのチャンネルにGitHub連携を設定しておく。

10:00 開始直後 (こたまご)

c351a44 ansible

2人にマニュアルとソースコードを見てもらっている間に作業効率化のための準備をしました。
簡単なAnsibleのplaybookを書いて、基本的な設定を行います。

Ansibleでやる必要もないのですが、やっておくとあとで一括作業が必要になった時に慌てずにできるので良いです。が、今回はあんまり使いませんでした。

  • SSH公開鍵の登録 (authorized_keys)
  • わかりやすいホスト名の設定
  • sudoをパスワードなしで実行できるように

4c9dad7 initial

それから、初期実装や設定ファイルとうのディレクトリ (/home/isucon/isucon2018-final) にあるファイルをリポジトリに登録します。

Nginx LTSV logs #1

Nginxのアクセスログをalpで解析できるようにLTSVフォーマットでファイルに出力するように設定。

とりあえず、この状態で初期スコアをベンチマークで測定しました。
この時点で把握した状況は以下の通り。

  • ネットワークの帯域は余裕、ピークで数Mbpsいくぐらい
  • アプリケーションとMySQLがCPUを食い合ってる
  • 静的ファイルへのアクセスは多く無い
  • 全体の応答時間のうち、 /info /orders へのリクエストが支配的
  • スコアは500点強

top

Pasted_image_at_2018-10-20__10_38_AM

 11:00 DBとアプリケーションサーバを分離 (みそでん、こたまご)

01のDBを02に接続 #4

MySQLとアプリケーションがCPUを食い合ってるのはよくないので分離。
サーバ01をアプリケーションに、サーバ02をMySQLに使うようにしました。

全サーバで共通のdocker-compose.ymlが利用されていましたが、これでは各サーバで動かすコンテナを変更できないので、サフィックスをつけて管理することに。

slowlog出したい気持ち #3

みそでんにスロークエリのログを吐いてもらうように設定して、再度ベンチマークでスコア測定。

  • スコアは800強
  • 2つ遅いクエリが見つかる
    • SELECT * FROM trade ORDER BY id DESC
    • SELECT m.t, a.price, b.price, m.h, m.l FROM (SELECT … FROM trade WHERE … GROUP BY t) m JOIN …..

11:20 明らかに遅くて不要なSQLを修正 (まーす先生)

add limit 1 #5

スロークエリを出すまでも無く、遅いクエリのうちの一つが、コードを見るとLIMIT 1で良いことにまーす先生がぱっと見で気づく。LIMIT 1を適用してベンチマーク。

  • スコアが10倍近い5000点強に

この時点で何チームか4000点から5000点代になっており、同様の対応をしたと想定されます。

limit1

11:50頃 /info の高速化のための下準備 (まーす先生)

まーす先生が /info を高速化すべく、いくつかのプルリクエストに分けて動作確認しつつ改修を進める。

add sec,min,hou #7
add indexes #9

ロウソク足の計算がしやすいように、tradeテーブルに秒まで、分まで、時までのカラムを追加し、インデックスを張った。

カラムを追加したのみで、利用はしていないためスコアへの影響はなし。

12:00頃 ロードバランスできるように準備 (こたまご)

ロードバランス #6

データベースを使い続ける方針にしたので、使っていない残り2台もアプリケーションサーバとして利用できるように設定。
この時点でサーバ01でNginx+App、サーバ02でMySQL、サーバ03と04でApp、という構成に。

ただし、Initializeが全台に対して行われるための仕組みを作っていなかったので、いつでもロードバランスできる状態にはしておきつつ、一旦サーバ01だけで処理するようにしておきました。

staticファイルをnginxから配信 #8

また、あんまり効果はないと思われたが、精神衛生上、静的ファイルはできるだけNginxから応答されるように設定しました。

案の定スコアへの影響はなし。

13:20頃 isuloggerへの送信にバルクリクエストを採用 (こたまご)

isulogerへの送信をバルクリクエストに変更 #10

isuloggerへのログ送信は秒間リクエスト数に制限がありました。
仕様書を見ると、バルクリクエストがあったためこちらを利用することにしました。

  1. ログの発生時は実際には送信せずchanに突っ込む
  2. バックグラウンドでchanからログを収集
  3. 定期的にまとめて送信

という挙動を実装しました。

実装とついでに吐いたログからわかったことは以下の通りです。

  • スコアが1000程上がって、6000弱になった
  • 今の所秒間リクエスト数を超えるようなログは発生していない

ログの送信がバックグラウンド処理になった影響で少しだけスコアが上昇します。

この時点では秒間リクエスト数の制限にかかるほどではなかったのであまり大きな効果になっていませんが、この実装をしておかないとこの後詰まることになります。

14:00頃 ロードバランスできるように初期化機能を実装 (まーす先生、こたまご)

初期化を全ノードに実行できる準備 #11
ロードバランスを再度有効化 #12

ベンチマーカーは実行開始前に一度だけ /initialize を実行します。
ロードバランスするとこの初期化リクエストは1つのアプリケーションプロセスにのみ届きます。

その時点で、全てのアプリケーションプロセスを初期化する必要があるため、内部APIを用意し (/internalInitialize) 全てのサーバの初期化を行うように実装しました。

また、設定をsettingテーブルから都度参照するようになっていたのをやめ、グローバル変数に持つように改修することでDBへのアクセスを減らしています。

ちゃんと動作はするようになったものの、数百程度のスコア上昇しかおきませんでした。

14:10頃 不要な行ロックを削除 (まーす先生)

remove lock #13

コード上に怪しい SELECT * FROM user WHERE … FOR UPDATE があったので、不要じゃないかとFOR UPDATEを削除。

この時点ではスコアに大きな影響はなかったが、残していた場合この後で困っていたと思われる。

14:30頃 SNSでの拡散を開始 (こたまご)

【暫定対応】確率的にSNSでシェア #14

みそでんがSNSシェアを有効にするフラグがあると発言。(さすがエスパー担当)

それを聞いた私が、もしかしてtrueにするとアクセスが増えるようにベンチマークができているのではと気づく。
ドキュメントを読み返すと同様の趣旨が書いてあった。(読んだけどなんのことかわからずその時はスルーしてしまっていたと思われる)

あまりにもtrueを返しすぎると、ユーザー増加に耐えられずタイムアウトが増えてしまうので、とりあえず1/8の確率でtrueを返すようにする。

  • スコアが1万点を超える
  • リクエストが増えたことでボトルネックがわかりやすくなった

47251873-77bdf500-d475-11e8-9313-1ccd4bd5799b
このあたりで1万5000点の特別賞をチームNaruseJunが獲得。
このフラグに気づくのがあと10分早かったらーーと悔やまれます(笑)。

15:20頃 /infoのローソク足をキャッシュ (まーす先生、こたまご)

雑な /info キャッシュ #15
雑じゃないロウソク足のキャッシュ #16

  • ローソク足は、直近のものは変化するが過去のものは変化しない
  • ローソク足は、秒単位で更新されれば良い

という性質もと、私が雑にレスポンス丸ごとメモリにキャッシュする実装、まーす先生が丁寧にロウソク足をメモリにキャッシュする方法をそれぞれ実装しました。

私の雑なキャッシュでも特に問題はなく、一気に25000点弱に。

まーす先生の丁寧なキャッシュもバグ無く動作したため、両方をマージしました。

ロックなくても動くやろ #17

丁寧にロックまでしてキャッシュを管理していたものの、ロックをしない私の雑キャッシュでも問題なく動作したためロックを削除した結果、28000点ぐらいまで上昇しました。

47252455-6201fd00-d480-11e8-973a-2f9192d06f39

 

15:50頃 約定条件のチェックが不要だった (まーす先生)

remove some checks #18

前々から処理が冗長だと気づいていた RunTrade 関数にメスを入れ始める。

初期実装では、注文があるたびにRunTrade関数を利用して約定可能なものを全て約定してから応答を返していた。

その際に、RunTrade関数を呼ぶ前に約定する可能性があるかどうかを確認するロジックがあったが、このロジックが重く不要だったため、小手始めにごっそり削除。

少しスコアが上がり、3万点弱に。

16:10頃 ユーザーの情報をメモリにキャッシュ (こたまご)

Userをキャッシュ #20

settingテーブルと同様、リクエストの度にデータベースを参照しにいくようになっていたユーザー情報をメモリにキャッシュするように修正。

DEBUGログを削除 #19

ついでに吐きすぎていた不要なログを削除。

ついに3万点を超える。

47252627-d9389080-d482-11e8-9f6c-f5ac305466a1

16:50頃 RunTrade (約定処理) をシリアルにバックグラウンドで実行するように (まーす先生)

async runTrade #21

上記の通り、注文処理が来る度に実行されていた約定処理を、約定処理要求だけフラグにもち、実際の約定処理はバックグラウンドでシリアルに実行されるように修正。

これによりスコアが37000程度に上昇。

17:30頃 /info 内の注文価格情報をキャッシュ (まーす先生)

ache lowest/highest value (GET /info Only) #22

もっとも安い売り注文と、もっとも高い売り注文の価格の計算を求めるSQLが重く、キャッシュすることに。

これにより5万点を超える。競技中4万点を超えたチームはtakedashiだけだった。

47253438-8dd7af80-d48d-11e8-8661-44be55083fa8

17:30頃 再起動試験や最後の調整を行う (こたまご、みそでん)

データベースやアプリケーションがサーバ再起動時にちゃんと上がって来るように設定されているかみそでんにチェックしてもらいました。

並行して再起動試験を行い、どの程度スコアが下がるか調査。
この時点でサーバ自体を再起動する勇気がなかったのがこの後の敗因の一つとなります。

また、Nginxのアクセスログや、スロークエリを出さないように設定したことで競技中最高得点の51,834点を記録。

maxscore2

時系列外 (みそでん)

みそでんにはデータベース周りの細かいチューニングを行ってもらっていました。

今回はDBのダンプファイルが提供されていなかったためバックアップを取っておいてもらったり、コネクション数を調整してもらったり、バッファサイズを調整してもらったり…

試行錯誤が必要なので、githubのコミットには細かくは残っていません…

最終計測

48000点ほどのリクエストを捌いたものの、33件のリクエストを落としてしまった (400エラーを返していた) ため、減点により31939点に。

ステータスコードが400なのがちょっときになるが、OS起動後でデータベースのファイルがOSのページキャッシュに載っておらず十分なおパフォーマンスが出せなかったことが原因と思われます。

また、SNSシェア率を100%にしてたため、パフォーマンスが追いつかなくなった時にエラーが頻発してしまう問題も抱えていました。

ほんとはやるべきだったこと、まだまだあるやるべきこと

この先も書こうと思っていますが、明日はU-22プログラミング・コンテストの審査会のため続きは明日終わってから書きます。
おやすみなさい…

第三回さくらの聖夜速報

さくらインターネット Advent Calendar 2015 24日目

こんばんは!さくらインターネットのこたまごです。
本日は、毎年のクリスマスイブ恒例「さくらの聖夜」でした。

詳しい内容は後日、オウンドメディアのさくらのナレッジに掲載されると思いますので、写真を交えて速報をお届けしますっ♪

事前打ち合わせ

事前打ち合わせ

ちゃっかり撮られてた

ちゃっかり撮られてた

「お宝写真大放出!さくら創業20年の歴史を振り返る」

創業20年に突入する節目に、社長の田中と研究所所長の鷲北が、写真で創業からを振り返りました。

社長と所長

社長と所長

ユーザの皆様

ユーザの皆様

「14年ぶりに復帰した理由、今後の構想~インフラ側から支えるIoT~」

後半は、創業メンバで、フェローの小笠原と、Cerevoの岩佐社長による、IoT Platformの発表でした。

なぜ小笠原がさくらインターネットに帰ってきたか、これから何をやるのかについて語るという内容だったのですが、勢い余ってさくらのIoT Platformを発表してしまいました。

具体的にはさくらが3G/LTEの通信モジュールを提供する、さくらのクローズドなネットワークに接続されており、センサの値をさくらのプラットフォーム上に記録したり、モジュールに対してデータを送信したりすることができる、という内容です。
送信するところから、貯めるところまでをハードウエア込みで一貫して提供することによって、IoTへの敷居をぐっと下げることが目的です。

モジュール構成

モジュール構成

システム構成

システム構成

ユーザーイベントだと思っていたのに、びっくりされた方もいらっしゃったかと思います笑

締め

ということで、お越しくださった皆様、ネット中継でご覧くださった皆様、本日はありがとうございました!
変わり続けるさくらインターネットを来年もどうぞよろしくおねがいします♪

最後の最後に、社長の田中も想定価格などを話始めるので、プレッシャーを感じている図。

TrendMicro CTFのオンライン予選をちょっとだけ解いた

実はこの土日にはISUCON5と同時にTrendMicro CTFのオンライン予選もやっていました。

こちらにもチーム竹田氏の以下の四人でメンバー登録して参加していました。

が、きひろちゃん以外はISUCONの方で体力をもっていかれていてあまり参加できなかったのが申し訳なかったです…きひろちゃんごめん…

わたしは、3問着手して、2問だけ答え出しました。

Click on the Different Color

ブラウザでアクセスすると、箱が幾つが含まれる画像が表示される。一箇所だけ違う色のがあるのでクリックすると次に進む。というページでした。最近SNSでも見かけたやつですね。

手でやっていては埒があかないので、Pythonで自動化していくと、最後にフラグが返ってきました。

下の動画を見るとおもしろいですが、最後の方は小さくて到底人間にはクリックできません笑

なので、答えは TMCTF{U must have R0807 3Y3s!} (You must have robot eyes!) でした!

Captcha

こちらはログインするとCaptchaが出てきて、連続で500回正解すると良い感じ。こちらも手でやっていては埒があかないので、Pythonで自動化しました。

画像からノイズを除去して、二値化。それからtesseract-ocrで文字列にして、簡単なチェックに通った場合のみ送信することで自動化できました。

captcha

ところが、大文字小文字や、数字の0とアルファベットのOを誤認識するなど、一部の文字を含む場合にはスキップするようにすると全然すすまなくて、学習させないとだめかなぁと思った時に、これはもしや、と、画像ファイルにアクセスしないようにして同じ答えを投げ続けるとどんどん点数が上がるじゃないですか!

ということで、脆弱性のあるCaptchaでした。というオチです。TMCTF{217dae3fd34cee799658d4552e37827f}

つまり、今年のSECCON決勝戦のこれといっしょですね!
OCRじゃなくて人間が学習するべきでした…

CAPTCHA ノイズ除去

CAPTCHA ノイズ除去

Calculate it

TCPで接続すると、次から次に四則演算の問題が出題される感じ。Pythonから接続してevalしたらOK。

だと思ってたのですが、途中からローマ数字や、英語表記とか出てきて眠気に負けて断念。
ローマ数字はネットで変換プログラムを見つけてきて対応したのですが、英語表記は次のようなのもでてきてパースが大変そうだったのであきらめました。

7 * 10 – 30 1 THOUSAND 2 HUNDRED 30 4 + 50 – 3 * 7 HUNDRED 20 5

これは後できひろちゃんが解きました。

まとめ

本当は9月に行われる予定だったのですが、問題サーバから問題が漏れた?ようで、一ヶ月延期になっちゃって…
ISUCONとかぶったので本腰を入れて解くことができなかったのが残念です。

SECCON運営メンバが作問してるだけあって、面白い問題がおおかったので本当はちゃんとときたかったです。
このチームでちゃんと解いてたら本戦いけたかな…来年に期待。

ISUCON5オンライン予選に参加してきた

「お題となるWebサービスを決められたレギュレーションの中で限界まで高速化を図るチューニングバトル、それがISUCONです。過去の実績も所属している会社も全く関係ない、結果が全てのガチンコバトルです。」(公式説明)であるISUCON5のオンライン予選に参加してきました。

メンバーは、CTFの時のメンバーと同じく、チーム竹田氏の、

で参加しました。3人参加が上限なので、いつものメンバのきひろちゃん (@aki33524) も含めた4人のうちから3人で出場しました。

ISUCONは Iikanjini Speed Up Contest の略で、Webアプリケーションがデプロイされたイメージを渡されて、その上で何をしてもいいからとにかくパフォーマンスを上げることが競技内容です。

オンライン予選

今回はイメージと競技マニュアルをもらった時点で次のことがわかっていました。

  • Ubuntu 15.04
  • フロントはNginx
  • アプリケーションは次の言語で実装されてる (どれか好きに選んでもいいし、書き直してもいい)
    • Ruby
    • Perl
    • Python
    • PHP
    • Java (正常に動作しない)
    • GoLang (正常に動作しない)
    • Scala (正常に動作しない)
  • DBはMySQL
  • インスタンスはGoogle Cloud Platformのn1-highcpu-4 (vCPU x 4、メモリ 3.6 GB)

今回パフォーマンスを上げるアプリケーションはこちら!

ISUxi

その名も ISUxi!足跡機能もあって、どこかでみたことあるアプリケーションです。
これが超絶重い…特にトップページなんかかなり待たされます…これを最適化してくわけですね。

大まかにやったことは以下のような感じです。

  • 設定関係
    • gunicornをUNIXソケットに
    • MySQLへの接続をUNIXソケットに
    • 静的ファイルはNginxで提供
    • ファイルディスクリプタ数の上限変更
    • 各種プロセス数の調整
    • MySQLの一時ディレクトリをRAMディスクに移動
    • MySQLの各種パラメータ調整
  • アプリケーション関係
    • ユーザーテーブルを全てオンメモリで持つ (変更が無く、5000レコードしかなかったため)
    • 各種SQLの最適化
      • ロジックで判定しているところをSQLで判定させるとか
      • 1レコードずつ取得するようなことが無いように
      • あしあとテーブルのスキーマ変更
      • etc…

ISUCON4は結構設定まわりのチューニングだけで本戦出場できる感じだったのに対し、今回はアプリケーションの規模も大きく、実装の方にも手を出さないと本戦出場できなさそうな感じになってました。

途中はMySQLのクエリログを全て取得して、スコアのために測定される1分間でどこのクエリが時間を占めているのかを調査してそこから潰していきました。

特にトップページがLIMIT 1000とかのSQLを3回も吐いてるのでかなり重く、トップページを改善するだけで1万点以上上がったのではないかと思います。

あとはあしあとテーブル。記事にアクセスがあるたびにレコードが追加されるのですが、これを日付、アクセスユーザー毎にGROUP BYしてSELECTするのでとっても重いのです…
こちらは (ユーザーIDアクセスユーザーID日付、最終アクセス日時) の形にスキーマを変更し、あしあとは INSERT…ON DUPLICATE KEY UPDATEにすることで、 SELECT時のパフォーマンスをかなり改善することに成功しました。

こんな感じで進めていくことで、最初はもたついていたISUxiもとっても快適に動作するようになり、スコアも16000点以上出すことができました。

最後に再起動テストをしたのですが、なぜかスコアが下がってしまって、最終スコアは14795点になってしまったのですが、無事263チーム中12位で予選通過することができました!

たぶんPython+MySQLのデフォルト構成のままではこれぐらいのスコアが上限なきがしますので、かなり健闘した方だと自負しています。

ほんとはRedisにデータを載せ替えたり、もっとオンメモリで処理したかったのですが、それは本戦で頑張ることにします♪

コードはGitで管理していて、ブランチ切って作業して、テストケース通ったらmasterにマージってしていたのですが、最後のほうはもう直接masterにマージしちゃってますね笑 (コミットユーザは合ってません)

network

おまけ (準備編)

去年の傾向から、MySQLを使うのだろうなとは思っていたので、事前に別のインスタンスでPHPMyAdminを用意してました。
これがデータ構造を把握したり、ちょっとSQLを試したりするのに超便利で、準備しておいてよかったものNo.1かもと思ってます。

SECCON CTF 2014 決勝戦 参加記

昨年の9月にオンライン予選が開催された,SECCON CTF 2014の決勝戦に参加してきました.

昨年はチーム”竹田氏”という名前で決勝戦に出場していたチームの一人と入れ替わり,チーム”Mr. Takeda”として参加しました.
英語表記になったのは,今年からマルチバイトはだめと言われたためで大意はありません.懇親会等でも”たけだし”と呼ばれたので漢字表記のほうが定着しているようです.

国内だけの大会だったはずが,世界大会になり,さらには世界的なハッキングコンテストが開催されるDEFCONの出場権がついてくることになったため,有名な海外のチームもやってきて超難関な決勝戦になってしまいました.Twitterでは,「国内野球大会かと思って参加したら、突然優勝賞品にワールドシリーズ出場権が追加されて、参加チームにヤンキースをはじめ世界の超一流プロチームが集まっていて、ふと隣を見るとイチローがアップを始めていた」と例えられていました(笑)

今回の目標は半分冗談で1桁の順位と決めていたのですが,24チーム中 9位の成績を収めることができ,メンバー一同騒然となる,総合的にはとてもうれしい結果を残すことができました.

SECCON CTF 2014 決勝戦スコア

SECCON CTF 2014 決勝戦スコア

6台のサーバが用意されており,攻撃に成功するとフラグと呼ばれる文字列が手に入ります.これをスコアサーバに送信することで,ひとつあたり100点が加算されます.

また,各サーバに定期的に更新される自分のチームのDefence Keywordを書き込むと,5分ごとに得点が入るルールがあります.

残念ながら,本題のフラグは一つも取ることができなかったのですが,他のメンバーが解いている間にDefence Keywordをなんとかしてそのタイミングにサーバに書き込むことを続けていました.
これにより,3+α個のフラグに相当する得点ができたので,なんとかチームに貢献できてよかったです.

予選ではないDefence Keywordを賭けた他のチームとの攻防戦はとても楽しかったです.

SECCONの詳細は後で加筆することにして,問題のWriteUpを先に書いておきます.

サーバ壱

Redmineのデザインそっくりな”Secmine”というユーザー登録が必要な架空のサイトについての問題でした.

Secmine 登録ページ

Secmine 登録ページ

メニューから,管理者に対して任意のURLを開かせることができる脆弱性がありましたので,クロスドメインの問題を避けながらなんとかセッションか,その他の情報を管理者から奪取すればよさそうというところで頓挫.

このサーバでは,チームで登録したアカウント数のランキング上位に5分ごとに得点できる状態になっていたのですが,単位時間あたりに登録が可能な回数が制限されているため,一番最初に気づいたチームが独占状態で,参戦するのはやめました.

Secmine アカウント数ランキング

Secmine アカウント数ランキング

サーバ弐

以下のような種類があるCAPTCHAがついた掲示板でした.

掲示板

掲示板

CAPTCHAには,

  • 単純に文字列
  • 四則演算
  • 図形の位置をマウスで合わせる
  • 一部が欠けた図形の位置をマウスで合わせる
  • 文字列の位置をマウスで合わせる

というパターンがありました.

CAPTCHA パターン

CAPTCHA パターン

ここで,ランキングというページを見ると,5分間に投稿された回数がアクセス元IPアドレス別にランキングされており,1位を取ると管理ページにアクセスする権利が得られ,無事一つのフラグをゲット.

掲示板管理ページ

掲示板管理ページ

ちなみに,このページで表示されるCAPTCHAのタイプやその他のパラメータを調整することができ,他のチームの邪魔をすることもできます.

もう一つどこかに攻撃できる点があるはずなんですが,ここで頓挫.

このサーバでは,最新数件が含まれる”History”に自分のチームのDefence Keywordが本文として書き込まれていると5分ごと得点が入るのでなんとかしてCAPTCHAを自動化してたくさん投稿する作戦を立てました.

“文字列”,”四則演算”,”図形”の3パターンだけを自動化すると絞り込んで,Pythonでノイズを除去し2値化,オープンソースのtesseract-ocrでデコード,四則演算の場合には計算した結果を送信.円の場合には左上の座標を算出し送信し,無事自動化しました.ところが,画像処理が挟まるためすごくおそい….5分間で数百回が限度でした.

CAPTCHA ノイズ除去

CAPTCHA ノイズ除去

その後他のチームが5分間に数千という回数の投稿をしてきたので,脆弱性をついてCAPTCHAをスキップする作戦に変更.
調査をしてみると,”cap_token”というCookieがあり,それと答えが1対1に対応する上に,何度でも通ってしまう脆弱性が見つかりました.これを突いて,CSRFトークンと,固定の答えだけを1度目のだけ画像解析を使い,2度目以降は同じ答えを使い回すことで大幅に速度を向上させました.

ここまでくると,Pythonを使わずにbashとcurlコマンド(+α)だけで実装すればさらなる高速化が期待できると考えたので,シェルスクリプトを作成.チーム全員に配布し各人100プロセス以上並列に起動させて,もはやDDoS状態でした.

掲示板投稿ランキング

掲示板投稿ランキング

私たちのチームは192.168.4.0/24なのですが,ここに載ってるタイミングで1万リクエスト以上成功しています.

この時点で,チームの現在のDefense Keywordをスコアサーバから取得する必要があるのですが,このページ,WebSocketでできてるんです.
なので取得が面倒くさい.そこで,PythonでWebSocketクライアントを書いて,取得した最新のDefence KeywordをHTTPで配信するサーバを立てました.
これにより,他のメンバーはDefense Keywordをcurl等でGETするだけで利用できます.この設計が後々サーバ伍ですごく役に立つことに.

サーバ参

オーバーフローの脆弱性があるプロセスが用意されており,ROP(Return-Oriented Programming)の手法を用いて攻撃する問題.

@aki33524が解いたのでWriteUpにリンク張ります.

サーバ四

mips, h8300, m32r, mn10300, rxのアーキテクチャで動作する脆弱性のあるプロセスに対し攻撃をかける問題.逆アセンブルしてコードを読むと,オーバーフローが起きる問題を見つけたのですが,攻撃コードを考える時間がなくて断念.

サーバ伍

よくわからないHTTPサーバが動いてる.どうやら4台あるよう.@misodengakuがひとつフラグをゲットしたので,WriteUpにリンク張ります

二つ目以降のフラグが手に入らなかったのですが,どうやらこの問題はWebの問題ではなくて,TCP/IPの問題だったそうで,不正なIPヘッダのダミーのパケットが返って来るために通信できないポートがあったそうな.
そのダミーパケットをうまく選別して,iptablesでDROPさせればつながるポートがあるらしい.だれかWriteUp書いたらリンクはります.

ネットワークの問題って気付けば解けたのに!これが個人的にはすごく悔しいです.
Webの問題に見せかけるのずるい…

このサーバでは,トップページに自分のDefence Keywordを書いておけば,5分ごとに得点できました.
パスワードがかかっていないSubversion-WebDAVが動いているのを発見したので,ファイルをすべて消して,自分のDefence Keywordのファイル名のファイルだけを作成しサーバにコミットするスクリプトを無限ループで実行.
ここにDefence Keywordが書き込めていたのは,準優勝のHITCONとうちだけだったようです.

ここで,サーバ弐のときに準備しておいたキーワード配信サーバが役に立ちました.

サーバ六

様々な方法で暗号化された文字列を元に戻す問題.@__mathが説いたのでWriteUpにリンク張ります

このサーバでは本題とは別に,Pythonで書いた暗号・復号プログラムを投稿し,最も短いコードかつ,誰にも解かれていないスクリプトを投稿できているチームに5分ごとに得点が入る構造になっていました.

最初のうちは @__math がまともに投稿して,何度か得点していたのですが,これ以上は難しいという短さまで到達.得点が加算されるタイミングを分析して,INPUT=OUTPUTという全く暗号化していないけれども最も短いコードをその瞬間に投げることで,何度か得点することができました.

 

追記

NHKにしっかり映ってた

SECCON CTF 2014 Online 予選 Write Up まとめ

連投で自分が関わった問題のWrite Upを書きましたが、他のメンバーやチームが解いた情報をいくつかリンクしておこうと思います。

このブログの記事

他のメンバーの記事

他のチームの記事

SECCON CTF 2014 Online 予選 Write Up #7

あと、これは途中まで準備して、@misodengaku に解いてもらいました。

Web 300の、”Bleeding “Heartbleed” Test Web”。

hb

hbtestどうみても、OpenSSLのHeartbleed脆弱性があるかどうかするテストページです。脆弱性があるサーバが必要なのかな?と思い、さくらのクラウドに脆弱性のあるUbuntu 12.04を構築しました。

レスポンスのHTMLを見てみると、DBにインサートされてることがわかる。

hb_src

さらに、同一時刻にリクエストを投げると、あきらかなSQLエラーが。

hb_error

ということは脆弱性があるふりをして、SQLインジェクションを起こせそう…?というところで @misodengaku にまかせたら解いてくれました。

具体できにどんなレスポンスを投げたのか気になるところ…

追記

みそでんがWrite Upを書いてくれました。“SECCON 2014 オンライン予選2に出た”

“; SELECT flag AS time FROM ssFLGss; —

でOKだそうです。

SECCON CTF 2014 Online 予選 Write Up #6

他にもQRコードには手をつけていたのですが、最後まで解けず…

その一つがQR 200の、”QR (Easy)”

qreasys

なんと、パンケーキにQRコードが書いてある…しかも食べられてる!

しかし、大丈夫!QRコードは右半分に生データ、左半分にリードソロモンエラー訂正符号が入っているため、右半分あれば読める!

@misodenngaku が見える部分を画像にしてくれた。

qr200

これをQRコード、バージョン3の訂正レベルHの規則に従って、復元してみた。が、SECCONまでは読めたけどそこからがよくわからない…

qr200_numbers

Excelのbin2hexは8bitまでしか対応してないけど、Numbersならもっといけたので助かった。

もう一つが、QR 400の”BBQR”。バーベキューアールっていうネタ。

bbqrQRコードでBBQされている…焼く前に写真撮って欲しいものである。さっきとちがって、左半分が残っている。幸い制御情報がすべてあるので、バージョン3、訂正レベルH、マスクの種類もすべてわかったので、とりあえず綺麗な画像にしてみた。

bbqr_orig

リードソロモンで訂正するには何バイトかまだ足りない…というところであきらめた。

SECCON CTF 2014 Online 予選 Write Up #5

#4までが僕が解いた問題です。少な….。他にも手をつけた問題があったので、何ができたかをかきます。できれば追記で解き終わりたい…

一番長く時間をかけたのが、Programming 400の”The Golden Gate”。

goldenGoogle Driveへのリンクがあるので開いてみると、ユニバーサル基板でできた回路の写真が!

golden_gd

 

74HC00を10個使ってでできた、8bit入力、8bit出力の暗号?化回路みたいです。配線がきたna….

なので、とりあえず回路図をEagleで復元することにしました。これが大変で、重なった配線のわかりにくいこと…

golden_sch

 

写真を印刷して、書き込みをしながら復元しました。苦行…

ここからはPythonで処理を行いました。都合のいいことにEagleの回路図データはXMLなので、普通に扱うことができます。なので、配線情報を取り込んで、セグメントの配列オブジェクトを作れるところまで実装しました。

golden_read

 

この情報は閉路のない有効グラフとして扱えるので、トポロジカルソートでランク順に並び替え、順番に出力を確定していけば最終的な出力を求めることができます。ここからは超競プロ勢の@__math先生にお願いしました。

ところが、デコードしても文字列のような結果が出てこない….というところで時間切れ。

他からの情報だと、どうやら、gzipで圧縮された結果がでてくるようで、解凍が必要だったみたいです。

 

SECCON CTF 2014 Online 予選 Write Up #4

#3に引き続き、解いたのがWeb 100の”jspuzzle”です。

jspuzzle解凍してみると、HTMLとJavascriptが入っているので開いてみます。

jspuzzle_blankどうやら、空欄を下の選択肢から埋めて、alert(1)を実行するコードを作ればいいようです。まさにパズルですね。同じ選択肢は1度しか使えません。

Scriptを読んだところ、10箇所の空欄を結合したSHA1ハッシュ値がFlagになってたので、正攻法以外では解けなさそう。なので、ちゃんとパズルとして考えていきます。

説明上、次の図のように番号を振ります。

jspuzzle_num

最初5行で辞書をつくって、関数オブジェクトをつっこみ、それを最後の行で参照して、実行していることがわかります。7,8の行が実際にalert(1)を実行する箇所ということになります。

まず、“[1]”と、“{9}”[“{10}”]() が同値でないとだめであることから考えます。JavaScriptでは、オブジェクトと辞書は一緒なので、Hoge.fuga()と書いてもHoge[“fuga”]()と書いてもおなじなので、きっと{10}は文字列オブジェクトのメソッドであることがわかります。

ということは、選択肢からtoLowerCaseが{10}で、Functionが{9}、対応してfunctionが{1}であることがわかりました。

同じ原理で、“{2}”と、r[“{7}”](pattern)が同値でなければいけません。rはRegExpオブジェクトなので、{7}は選択肢から考えると”constructor”か”exec”が入ります。constructorの戻り値はまたRegExpオブジェクトなので、違うだろうと推測し、{7}にexecを入れるとr.exec(pattern)となります。では次に{6}を考えてみると、正規表現の文法上/*^_^*/は入りません、それ以外の普通の文字列はいれてしまうと、execの返り値がリストになってしまいます。なので、{6}には^[w]$をいれます。そうするとexecの返り値はnullになります。

ここで疑問がでてきます、{2}は文字列なのに、nullはどうがんばっても入れられないじゃないか!と。ところがJavaScriptは辞書のキーは全部文字列で扱いますので、参照時に自動でキャストされるため”null”で問題ありません。(最初、これはちがうなぁと思っていたので少し時間がかかりました…)。なので、{2}はnullで決まりです。

最後、{3}{4}{5}と{8}ですが、”{3}{4}{5}”と結合すると、命令になるはずなので、で”return hogehoge”となるはずです。しかし、空白は選択肢にありませんが、なんとコメントをいれるとそこは空白扱いになるのです。したがって、{3}はreturn、{4}は/*^_^*/ですね。

ここまで考えると、この新しく生成されている関数で返るオブジェクトをHogeとすると、{8}の 部分ではこういうことになります。

Hoge.{8}(1);

これがalert(1)にならなければいけません。そこで、alertを持っている親オブジェクトを考えると、window….つまりはthisです!ということはreturn thisして、alertを呼びだせばOK

結果、{5}はthis、{8}はalertですね。

jspuzzle_ans

 

殴り書きなので、読みづらいのはスルーしてください…