1001001

73。CTFのWrite-upから始まったけど最近は技術全般の備忘録となっています。

OCRツール「Tesseract OCR」をインストールしてPythonで使う

ocr_test

個人的な創作物の中で,「画面のスクリーンショットを取ってその中の文字をOCRで読み取る」ということをしたかったので調べたところ,Tesseract OCRというOCRツールがあることを知りました.しかもPythonライブラリであるpyocrを使うことでPythonからも扱うことができるということで早速使ってみました.

そのインストール手順のメモになります.

OCRとは

OCR(Optical Character Recognition/Reader、オーシーアール、光学的文字認識)とは、手書きや印刷された文字を、イメージスキャナやデジタルカメラによって読みとり、コンピュータが利用できるデジタルの文字コードに変換する技術です。

私の用途的に説明すると,画像データ中の文字をテキストに起こしてくれる技術ということです.

Tesseract OCRとは

OCRツールの一種で,以下の特徴があります.

おそらくPythonに限らずにTesseract OCR(以下,Tesseract)を使えるようなライブラリはあると思います.

Tesseract + PythonOCRを行う

以下の順で説明していきます.

  • 環境
  • Tesseractのインストール
  • Tesseractを使ってみる
  • pyocrのインストールしてPythonで使う

環境

Tesseractのインストール

今回は確実に最新版をインストールするために,ソースからビルドしてみます.と言っても,Githubに公開されている手順通りにやっていくだけです.また,Githubの手順では自身でトレーニングを行うためのトレーニングツールが必要な人向けの手順も書いてありますが,私は取り急ぎOCRが使えれば良かったため,本記事では飛ばしたいと思います.

まずは依存関係をインストールします.

$ sudo apt-get install g++ # or clang++ (presumably)
$ sudo apt-get install autoconf automake libtool
$ sudo apt-get install autoconf-archive
$ sudo apt-get install pkg-config
$ sudo apt-get install libpng12-dev
$ sudo apt-get install libjpeg8-dev
$ sudo apt-get install libtiff5-dev
$ sudo apt-get install zlib1g-dev

次にLeptonicaという画像ライブラリをインストールします.apt-getでも入れられるのですが,Tesseractの最新版では1.74.0が必要になりますので,Leptonicaも最新版をソースからビルドします.ソースはこちらから最新版を得られます.

$ wget http://www.leptonica.com/source/leptonica-1.74.1.tar.gz
$ tar xvzf leptonica-1.74.1.tar.gz
$ cd leptonica-1.74.1
$ ./configure
$ make
$ sudo make install

さて,ここまででTesseractをビルドする準備ができました.以下のようにしてビルドします.

$ git clone https://github.com/tesseract-ocr/tesseract.git
$ cd tesseract
$ ./autogen.sh
$ ./configure
$ make
$ sudo make install

これでTesseractが入りました.

Tesseractは/usr/local/share/配下の訓練データを参照してOCRを行います.Tesseractインストール直後は訓練データがありませんので,こちらから興味のある言語の訓練データをダウンロードしましょう.私は英語日本語が使いたいので,eng.traineddatajpn.traineddataをダウンロードし,/usr/local/share/配下に置きました.

ここまで行うと,コマンドラインからTesseractを使用できるようになります.適当なデータで試してみましょう.私はこのようなデータを使いました.

my_test

コマンドは以下です.

$ tesseract my_test.png result

 

my_test.pngが上の画像ファイル,resultは出力ファイル名です.自動的にresult.txtとなります.結果は以下です.

result

テスト用の画像作るときも結果を参照する時も同じエディタを使っていてわかりにくいかもですが,ちゃんと読み取れています.

同様に日本語でもやってみます.

my_jpn_test

コマンドは以下です.

$ tesseract my_jpn_test.png jpn_result.png -l jpn

-l オプションで言語を指定します.結果は以下です.

jpn_result

思ったよりきちんと読み取れています.

(参考にした記事では,複雑な文章等を扱うとはちゃめちゃな結果になるとありました.そのような場合は自分で訓練データを作ると良いそうです.公開されている訓練データも改善されているのかもしれませんね.)

追記)

いくつかの日本語の文章を試してみましたが,やはり英語に比べると精度が低いようです.しかし画像を拡大したりするだけで精度が変わるので,画像中の文字が細かい場合や画像自体が小さい場合は画像を加工すればだいぶ読みやすくなります.

pyocrをインストールしてPythonで使う

では,TesseractをPythonから使ってみます.まずはpyocrをインストール.

$ sudo pip install pyocr

これでPythonでTesseractを扱えます.

(参考にした記事ではTesseractをソースからビルドした場合,とあるひと手間必要とのことでしたが,現在は修正されてひと手間がいらないみたいです.)

では,簡単なテストコードを書いてみます.先ほどの日本語のデータでテストしてみます.

 

$ python ocr_test.py
私 は ペ ル ソ ナ 5 が 大 好 き で す 。

このように,コマンドラインから実行した時と同様の結果なります.

ソースコード中のimage_to_stringというメソッドの引数にbuilderというものがあります.さらに中を見ると,pyocrのTextBuilderの中でterreract_layoutというパラメータに6を指定しています.これはTerreractコマンドの-psmオプションにあたるもので,-psm 6 と同義になります.このオプションはpage seg modeの略で,画像をどのように(どんな画像だと思って)読み取るかというものです.以下が各値の対応です(参考).

例えば,縦書きのテキストの画像を読み取る場合,virtically aligned textなので5を指定します.精度良く読み取るためには,このようなオプションの値もしっかり設定する必要があるでしょう.

まとめ

Tesseract OCRxUbuntuにインストールしてコマンドラインで簡単なOCRを行いました.今回はソースからビルドする方法を紹介しました.

また,pyocrをインストールしてPythonからTesseract OCRを使用しました.

 

参考

巷で話題のGoogleのSHA-1衝突やってみた

最近,ハッシュの一種であるSHA-1について,米Googleが初めて衝突に成功させたということが話題になりました.その衝突ハッシュを使った衝突例として,SHA-1の一致する二つのPDFを作成していました.

その方法について説明されている資料があったので自分でもSHA-1を衝突させたPDFを作成してみました.その方法について書こうと思います.

はじめに

本記事はGoogleの発見したNear-collision Pairを用いて二つの異なるPDFのSHA-1を衝突させる(SHA-1の異なる二つのPDFを作る)手法を解説した記事ですが,以下の点について知識が不足している部分があります.

  • PDFのフォーマット

この点については,衝突の原理に直接かかわらないので細かく調べていませんがご了承ください.そしてもし詳しい方がいたらその点ご指摘いただけたらありがたいです.

SHA-1? ハッシュ関数? 衝突?

まずハッシュ関数についてから書こうと思ったら,あれも書きたい,これも書かなきゃ,となって本命のSHA-1衝突の話題がかすれてしまいそうだったので,これは機会があれば別記事に書きたいと思います .

簡単に説明しますと,

  • SHA-1一方向性関数で,あるデータに対して一意の数列 (ハッシュ) が得られる
  • 同じく一方向性関数であるMD5は,異なる二つのデータから同様のハッシュが得られることが知られている
  • SHA-1も危ないと昔から言われていたが,とうとうGoogleが衝突例を発見した

という感じです.

GoogleがやったPDF衝突方法

Googleが実現した衝突方法は以下の通りです.

  • PDFとJPGの機能を用いた衝突
  • 多量のリソースを使った大規模な演算で,あるヘッダPについてSHA-1( P | M1  ) = SHA-1( P | M2  )となる P, M1 , M2を見つけた
  • SHA-1の計算の性質上,( P | M1 )と( P | M2 )の時点で衝突が発生すれば,あるデータSについて( P | M1 | S ) と ( P | M2 | S )のハッシュも衝突する

Googleがこのような( P | M1 )と( P | M2 )をIdentifical-prefix Collision Attackという手法で発見しました.Googleが発見してくれたおかげで,僕らはSの部分をちょっと細工するだけで簡単に衝突PDFを作ることができます(このM1とM2という同じSHA-1を取るペアはNear-collision Pairと名付けられています).Googleの衝突PDFは,開くと違う画像が表示されるのに同一のSHA-1ハッシュが得られるという代物なのですが,実はこの2種類の画像はどちらのPDFにも含まれています.詳細は後程説明します.

原理については私が参考にした資料であるGoogleのSHA-1の話 (サイボウズさんの社内勉強会用のスライド)を参照するのが参考になると思います.この記事では自分が実際に行ったSHA-1衝突PDF作成手順について図を用いて説明したいと思います.

衝突手順

用意するもの

衝突原理の理解のために僕が使ったものです.

まず,既存の衝突PDFファイル二つです.こちらのサイトから入手できます.Attack ProofのとこのPDF1 | PDF2 という部分をクリックすればそれぞれダウンロードできます.開いてみると二つの異なるJPGが表示される全く別のPDFファイルであるにも関わらず,SHA-1の値が同じになっていることが分かります.

$ md5sum shattered-*
ee4aa52b139d925f8d8884402b0a750c *shattered-1.pdf
5bd9d8cabc46041579a311230539b8d1 *shattered-2.pdf

$ sha1sum shattered-*
38762cf7f55934b34d179ae6a4c80cadccbb7f0a *shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a *shattered-2.pdf

次に,それぞれのPDFから,表示されている画像を抽出するスクリプトを入手します.こちらのGithubで公開されてます.先ほども申し上げた通り,衝突PDFで表示されている2種類の画像は,どちらのPDFにも含まれているにも関わらず,互いに違う方のみが表示されます.上記のスクリプトは,そのうちの表示されている方のみ抽出できるスクリプトであるということです.これを使って既存の衝突PDFから画像を抽出して構造を見比べたり,自分で作った衝突PDFに使ってみてきちんと画像が抽出されるかを確認したりできます.例えば,自分で作ったPDFに対して使ったらきちんと画像を抽出できるにも関わらずPDFが表示されない時は,上手く相互を参照するようにはできているのにどこか別の要因で表示されていないということになります.とりあえずやってみればわかります!

衝突PDFの構造の理解・自作をするためにはバイナリエディタが必要になります.これでバイナリを見ながら値を細工していきます.細工と言ってもやることが分かってしまえば簡単です.

既存の衝突PDFの構造(衝突原理)の概要を把握する

まずは衝突PDFをリーダーで見てみます.赤と青の別の画像が表示されています.

sample

次はこれらの16進バイナリを見てみます.サイボウズの資料によりますと,先頭320バイトの部分で衝突が起きていてそれ以降が同じ値ならずっと衝突し続けるとのことです.なので,まずはコマンドで先頭320バイトのSHA-1を見てみます.

// 320バイトではどちらのSHA-1も衝突している
$ dd bs=1 count=320 < shattered-1.pdf | sha1sum
f92d74e3874587aaf443d1db961d4e26dde13e9c *-

$ dd bs=1 count=320 &lt; shattered-2.pdf | sha1sum
f92d74e3874587aaf443d1db961d4e26dde13e9c *- // 256バイトの段階では衝突していない $ dd bs=1 count=256 < shattered-1.pdf | sha1sum
5b72b916c85d1980f8ac6846fad79b9b70ea7f85 *-

$ dd bs=1 count=256 &lt; shattered-2.pdf | sha1sum
b93c8b91b1822d1f23d0b67c12e97ed0208b491e *-

じゃあこの320バイトってどうなってるの?ってなるので,早速バイナリエディタで見てみます.

diff

こんな感じです.この画像は320バイトの最後の方が見えてないのですが,320バイト目までずっと0が続くだけなので良しとします.大事なのは選択している部分です.それぞれ以下のようになっています.

  • FF FE 01 73:shattered-1.pdf
  • FF FE 01 7F:shattered-2.pdf

このバイナリが何を表しているかというと,実はJPGファイル内にあるコメント部分を表しています.「何で突然JPG? PDFじゃないの?」となりますが,実はそれより前にあるFF D8がJPGの開始を表しており,既にPDF内のJPGが埋め込まれている部分を見ていることになります.

diff2

このようにJPGは開始していますが,まだ表示される赤と青のJPG画像は関係ありません.ここで大事なのは先ほど申し上げたJPG内のコメント部分です.

ここで,少しJPGファイルの構造について触れます.こちらのサイトでJPGのJFIF形式を見ていただけると参考になると思いますが,ここでは必要なものだけ説明します.以下がJFIF形式のフォーマットの一部になります.

  • FF D8 -> JPGデータの開始
  • FF D9 -> JPGデータの終了
  • FF DA -> スキャン開始
  • FF FE -> コメント

FF XXなどの値をマーカー値と呼びます.JFIF形式では,FF D8が開始を表し,FF D9が終了を表します.また,FF DA からが目に見える画像自体のデータの開始です (スキャン開始).これらのマーカー値は覚えておくとこの後の構造理解がしやすいです.またセグメント一覧の一番下を見ると,FF FEというマーカー値があり,コメントと書いてあるのが分かると思います.コメントの部分は画像データとはみなされず,任意の文字列を含めることが可能です.さて,FF FEの後にコメントが来るわけですが,どこまでがコメントなのでしょうか.それは,FF FEの直後の2バイトが表しています.FF FEの直後の2バイトの値から2を引いた分のコメントが続きます.つまり,shattered-1.pdfの方は0x173,つまり371から2を引いた369バイト分のコメントが続き,shattered-2.pdfの方は0x17f,つまり383から2を引いた381バイト分のコメントが続きます.

このコメントが衝突PDFに何の関係があるかと言いますと,このコメントの値が違うことでPDFに表示される画像が変化しているのです.

衝突PDFの構造を考える

言葉で説明しにくいので百聞は一見に如かずなので,以下に衝突PDFの仕掛けを図示します.左右二つに分かれた四角は各PDFの16進バイナリだと思ってください.

 

overview-1-3

構造的にはこんな感じです.各ブロックには16進バイナリが入ります.また,Near-collision Pair以下は全く同じで,全く同じ16進が並びます.

この構造の元,以下のようにバイナリを組み立てます.

overview-2-3

 

赤い部分で,各JPGをスキップするようにコメントの範囲を設定すると,以下のようにデータがスキップされます.

 

overview-3-3

衝突PDF1では,最初のスキップで369バイトしかスキップしないので,一つ目の赤いブロックのコメントを読み込むことができます.すると,JPG-1のコメント部分までスキップします.ここで,FF FE 00 06も飛ばしてFF FE XX XXまでいくようにコメント範囲を設定しておきます.さらにFF FE XX  XXの部分でJPG-2までスキップするようにコメント範囲を設定しておけば,JPG-2のみが正常に読み込まれます.そうすると,衝突PDF1ではJPG-2の方が表示されることになります.

一方,衝突PDF2では,最初のスキップで381バイトスキップして,一つ目の赤いブロックもスキップしてJPG-1までいけます.JPG-1を正常に読み込んだ時,読み込むコメントはFF FE 00 06となります.これは4バイトをコメントとみなすということになるので,「JPG-2までスキップするコメント(FF FE XX XXの部分)」をスキップすることができ,JPG-1のFF DA以降も正常に読み込めます.そのようにJPG-1を正常に読み込んだ後は,既に画像データがきちんと終了しているので,次の画像データであるJPG-2が読み込まれて表示されることはありません.これはおそらく仕様だと思っています.仕様周りは分かり次第書き直します.

そして,最後は双方共にPDFの残りのフォーマットを読み込むのできちんとPDFを作ることが可能です.

overview-4-3

このような構造を作ることができれば,衝突PDFを作ることが可能です.正確には,コメントは上だけでは不十分なこともあります.例えば,画像データが大きくてFF DA(スキャン開始)が何度も出てくる場合は,一度のスキップではスキップしきれないことがあるので,FF DAごとにコメントをつけてスキップさせる必要があります.その場合はFF DAの前にコメントを入れます.また,PDFフォーマットも画像の大きさ等によって書き換える必要があります.

自分で衝突PDFを作ってみる

衝突PDFを作るにあたって必要なものは以下になります.

  • バイナリエディタ (stirlingとか)
  • 衝突PDFの片方に表示させるJPG-1 (既存のものと同じサイズだと楽)
  • 衝突PDFのもう片方に表示させるJPG-2 (既存のものと同じサイズだと楽)
  • Near-collision Pair
  • Near-collision Pairの後に付けるコメント (図の一つ目の赤いブロック)
  • 末尾に付加するPDFのフォーマット

このうち,最低限細工が必要なのはJPG-1と先頭320バイト+αです.これらを上の図のように上手いこと相互のJGPをスキップするよう細工して作ったPDFが以下になります.

sha1-collision

このように,md5が異なる別々のファイルにも拘わらず,SHA-1が同じになっていることが分かります.

制限

以下,私ができていない部分になります.

  • 一部の画像では衝突PDFが作れない
  • 正確にはPDFフォーマットに準拠していない

一つ目については,コメントで飛ばすことができないデータ構造のJPGが使えないということです.コメントはFF FE XX XXのXの部分2バイトできまるので,この範囲を超える場合はどうすれば良いのかが分かっていません...(色々試したり調べたのですが...)

二つ目はPDFフォーマットに準拠していない点です.PDFフォーマットが異なるとブラウザでは表示できますがAdobeのリーダー等ではきちんと表示されません.例えば以下のスクリプトでつくった衝突PDFはブラウザでは表示されますがAdobeでは表示されません.

https://github.com/73spica/sha1-collision

上図では既存の衝突PDFに使われていたJPGと同じ大きさのJPGを用意したので,Adobeのリーダーで上手く表示されますが,そうでない場合PDFフォーマットを書き換える必要があります.ですが今回はそこまでできていません.もちろんできた方が良いですが,今回はSHA-1衝突の原理の理解が目的だったのでそこまでしなくて良いと考え,ここまでにしました.こちらのsonickunという方がPDFフォーマット準拠については行っているので,そちらを参考にするとよいと思います.

まとめ

GoogleがIdentifical-prefix Collision Attackによって発見したNear-collision Pairを使うことによって,簡単にSHA-1衝突PDFを作ることができます.衝突PDFはJPG仕様であるコメントを細工することによって作ることが可能です.興味のある人は是非やってみてください.

参考

GoogleのSHA-1衝突の手法で衝突PDFを作るスクリプトを書いてみた

sha1-collision-neta

sha1

2017年2月23日,とうとうSHA-1の衝突例をGoogleが発見したとの発表がありました.一部のコミュニティでは,その手法を使って自作の衝突PDFを作るのが流行っています.

ということで,私もその流れに乗って,二つのJPG画像からSHA-1衝突PDFを自作してみました.また,二つのJPGファイルを入力としてSHA-1衝突PDFを自動生成するスクリプトを書いてみました.

https://github.com/73spica/sha1-collision

私の理解不足で一部制約もあるのですが,その点はGithubの方に書いておこうと思います.

今回は以上になりますが,SHA-1衝突PDFの作り方についても追々まとめたいと思っています.

参考

サイバーコロッセオ × SECCON 2016に参加しました

cyber_colosseum

サイバーコロッセオと呼ばれるCTFのコンテストに,チーム"m1z0r3_NSL"として参加しました.Koth形式のCTFは初めてだったのでとても良い経験になりました.この記事では,サイバーコロッセオがどのような競技であるか,また私の着手した一部の問題について書きたいと思います.(問題の説明は中盤からです)

サイバーコロッセオとは

SECCON 2016の大会の一部とした開かれたCTFのコンテストなのですが,公式の内容には以下のようにあります.

2020年東京オリンピックパラリンピック競技大会開催に向けた総務省のセキュリティ演習事業 「サイバーコロッセオ」とコラボしたSECCON大会です。

サイバーコロッセオというのは,総務省のセキュリティ演習事業のことです.それを今回はSECCON2016の競技として行っていただけるようです.本競技はKing of the hillという形式のCTFで,計24チームが参加しました.先に結果を申し上げますと,私の所属していたチーム"m1z0r3_NSL"は893点8位でした.

cyber_colosseum_ranking

 

King of the hillって何 ?

King of the hill というのは,CTFにおける競技形式の一つです.CTFというのはセキュリティの知識を競うコンテストのことで,そのコンテストには3つの形式があります."Jeopardy", "Attack and Defence", "King of the hill"の3種類です.

Jeopardy

一言で言うと,クイズ形式の競技です.1964年からアメリカで放送されているクイズ番組の名前が由来です.この形式では,セキュリティの知識を生かして,出題されたクイズ (問題) を解きます.問題を解くことで答えとなる文字列 (フラグ)を手に入れることができ,それを解答ページで入力・送信し,正解であれば得点が得られます.例えば,ジャンル「暗号」の問題においては,「この暗号を解読しろ.」という問題文と共に暗号文が渡されます.その暗号文を解読すると,「答えはFlag{It's the flag!!}」というような文が手に入り,答えとなる文字列はFlag{It's the flag!!}となります.フラグは,それが答えだと分かりやすいように,大抵の場合「大会名{なんらかの文字列}」のように,なんらかの文字列が中括弧で囲まれ,先頭にその大会・コンテストの名前がくっついているような形をしています.これはJeopardyに限らず,他の形式の大会でも同じだと思います.例えば,今回のコンテスト,「サイバーコロッセオ×SECCON 2016」のフラグ形式は,「SECCON{なんらかの文字列}」でした.

Attack and Defence (A&D)

その名の通り攻防戦です.各チームが自分のサーバを持っていて,自チームのサーバを守りながら他チームのサーバを攻撃します.競技開始と同時にサーバの脆弱性を調査し,自チームのサーバの脆弱性を潰しながら他チームのサーバを攻撃するプログラムを書く,というようなことを行います.Jeopardyがフラグをサブミットすることでしか得点できないのに対し,A&Dは攻撃で得られるAttack Point (AP)と,防御で得られるDefence Point (DP)の二種類の加点要素が存在します.

King of the hill (Koth / KoH)

A&Dの特殊形式・派生形式などと言われています.私の個人の見解では,JeopardyとA&Dの中間という感じです.複数の問題を持つ大きなサーバがあり,各チームはそのサーバにアクセスして問題を解きます.A&Dとは違いチームごとにサーバを持っているわけではないので複雑な攻防は無いですが,小数チームが物理的に一つの場所に集まって行われる形式なので,Jeopardyには無い面白いルールが用意されていたりします(A&DのようなAPとDPなど)

サイバーコロッセオにおけるKoth

以上を踏まえた上で,今回行われたサイバーコロッセオにおけるKothについて説明します.

  • 問題サーバは6つ(大問が6問)
  • それぞれのサーバに問題が3~4つずつ(小問が3~4つ,問題サーバ1,6は例外)
  • 各問題サーバの小問を解くとAttack Keyword (フラグ)が手に入り,サブミットするとAttack Pointが入る
  • Attack Point獲得後に特定のファイルにDefence Keywordを書き込むことでDefence Pointが入る

問題サーバが6つあり,それぞれのサーバに複数の小問があります.小問一つに答えとして一つのAttack Keywordがあり,これをサブミットすればフラグが得られます.

問題を解き進めると,DPを得るための行動ができるようになります.そうしたら,指示通りに,予めチーム毎に通知されているDefence Keywordを特定のファイルに書き込みます.運営側が一定時間ごと(5分毎)にチェックをして,Defence Keywordの書き込みがあれば,そのチームへDPが入ります.DPは一つの問題につき20ポイントと決められていますが,これは複数のチームとの折半となります.例えば,1つのチームだけがそのサーバを攻略し,Defence Keywordの書き込みを行っていたら,そのチームには5分毎に20ポイントが入ります.その後他の3チームが攻略し,Defence Keywordを書き込めば,5分毎に割り振られるポイントは20 / (1+3) = 5となり,各チームに5ポイントのDPが入ります.ですから,先にDefence Keywordの書き込みに成功したチームは,他のチームがDefence Keywordを書き込めないように妨害してきます.このルールを見ると,問題を解く形式の点はJeopardyに似ており,AP,DPを奪い合う点はA&Dに似ているということで,私がJeopardyとA&Dの中間という理由が伝わると思います..

ここまで本競技では各問題にAPとDPがあるという説明をしてきましたが,問題サーバ1と6は例外で,上述のような得点形式ではありませんでした.問題サーバ1については後程説明いたします.問題サーバ6は,DPが存在せず,APのみが存在しました .

手を付けた問題

いつものCTFと違って,大問が6つしかないので一応全てのサーバを見ました.序盤でサーバ1の問題に着手していたら他のメンバーが他の問題を解いてくれていたので,サーバ1を定期的に見たりサーバ6のpcapを見たりしていました.今回はサーバ1について説明したいと思います.

(他の問題の説明については他のメンバーが書いてくれると信じてる)

サーバ1:セキュアでなるべく小さなModulusを作れ

(何となく問題のタイトルをつけてみましたが,最終的なアプローチは少し変わってきます.)

サーバ1では,各チームは30分に一度,二つの素数をアップロードすることができます.「二つの素数(p,qとする)なんかをアップロードして何をするの?」というと,以下のようなルールに従い任意のp,qをアップロードする必要があります.

  • 各チームが二つの素数p,qをアップロードし合う
  • 素数p,qと,その積p*q (RSAで言うModulus) がランキングに表示され,そのランキングを競う
  • 小さいModulus程ランキング上位に入る
  • ランキングに表示される各Modulusに対し,ブレイクという行動が可能
  • そのModulusを構成するp,qを特定してサブミットすることで,そのModulusをランキングから除外することができる
  • ランキング1位を維持すると一定時間ごとにDPが入る

つまるところサーバ1は,他のチームがアップロードするModulusよりも小さくてかつブレイクされにくいModulusを構成できるp,qを見つけてアップロードする問題です.ここで重要なのが,「ランキング1位を維持すると一定時間ごとにDPが入る」という部分です.ここでいう一定時間というのは,他の問題でDefence Keywordを書き込んでいる時に運営がチェックをする5分毎という時間のことです.(私は一定時間とあるので必ずしも他と同じ5分とは限らないと思っていたのですが,確認したところ運営の方が他のDPのルールと同様5分毎に確認をしていると言っていました.)つまり,チェックをするのは5分毎なので,ずっと1位を維持していなくても,チェックの直前に1位になってチェックを受けられれば得点は貰えるということになります.だったらその時を狙って超小さいp,qをアップロードすれば良いじゃん,という話になるのですが,もう一つ重要なルールが「各チームは30分に1度しかp,qをアップロードできない」という部分です.つまりあまりにも弱い素数をアップロードしてしまうと (運が良ければ) 一度はDPを取れますが,それを過ぎると再アップロードのできない30分の間は絶対にDPを獲ることができなくなります.

つまり,この問題で素数をアップロードするアプローチは以下の二つに絞られます(たぶん).

  • 相手よりも小さいけども簡単にはブレイクされないModulusを作れるp,qを見つけて30分毎にアップロードする
  • 安全性は度外視して,とにかく小さい素数を確実に1回DPを獲れるタイミング (30分毎) でアップロードする

私は,序盤は以下のようなコードを書いて,現在1位の人よりは小さいけど簡単にはブレイクされない素数を生成していました.

p,qのおおよそのbit数とか決める処理が適当なので,もっと頭良くできると思いますね.最後の方はなるべく大きめにしても仕方なかったので一個見つけたらbreakしてました.

最初のうちはこの選びかたで結構1位を維持できたのですが,途中からタイミングゲーになってきました(もとからそういうゲームだと言われればその通りなのですが).30分のサイクルでたまたま競合の少ない5分毎のタイミングでアップロードできることが重要になってきまして,終盤はこのスクリプトの方法で選ぶよりも狙いすまして短い素数を挙げることに努めました.

また,素数のアップロード以外に,弱いModulusをブレイクするという処理も必要なのですが,これに関してはどのような手法が良いのかよくわかりませんでした.私はsageyafu自作のfermat法solverを回して,短いのは即ブレイク,長いのはワンチャンにかける,ということをしていました.ですが,やはり大きなModulusは全然sage等でもブレイクできなかったです.でも他のチームには大きめのModulusでもブレイクできてた方々がいました.是非ともやり方をご教授いただきたいです....

 良かったこと・悪かったこと

良かったこととしては,チームで分担ができていたことだと思います.というのも,チームメンバーの得意ジャンルのバランスが良く,普段バイナリ担当なのが2人,Web担当なのが1人,暗号担当なのが1人の計4人でした.分担ができたといいつつバイナリ担当の二人に重荷を背負わせてしまいましたが,彼らは優秀だったのでどんどんAPを稼いでくれました.僕も他のサーバ攻略しなきゃとは思っていたのですが,序盤はサーバ1で結構調子が良かったのでそちらに注力していました.(とはいえサーバ1は30分に一度しかチャンスが巡ってこないので,さっさと自動化して,もっと早くwebnetwork担当のもう一人のサーバ6攻略を手伝うべきだったと感じます.)

あと,初めてのKothを楽しめたのは良かったと思います.

悪かったこととしては個人としてもチームとしてもめちゃくちゃあると思っています.自分の整理のためにも書くと,

  • 準備不足 ( CTFを解く環境という意味で )
  • 情報共有不足
  • サーバ1の攻め方
  • 冷静さ
  • スキル不足

まずは準備不足です.本競技では問題サーバに繋ぐために無線ネットワークが用意されていました.持ち物に優先ケーブルが無いことや無線が使えるPCを指定されていたことから無線を使うことは分かっていたのですが,その影響で無線のアダプタを使ってしまうのでテザリング等で外のネットワークに繋ぐことができませんでした.つまるところ手軽にググったりslackとかで情報共有ができなかったんですね.我ながらアホだなと感じました.僕はiPhoneでケーブルを繋いでやってたのですが上手いことネットワークの設定ができず,両方繋ぐとiPhoneの方に引っ張られてしまって問題サーバに繋げなくなってしまったので,結局ほぼググったりせずに競技を進めて,どうしても必要な時だけ繋げ変えたりしていました.ググるのはともかくとして,slack等による情報共有ができなかったことで,一人がゲットしたAttack Keywordに記載されたヒントをスルーしてしまって次の答えがすぐに分からないという状況に陥ったりしたので,これは事前に考えておくべき事案だったと思います.

サーバ1の攻め方も他にも色々あったなぁと思っています.まず,素数の選び方ですが,

  • 他の素数と被らないようにする
  • next_primeなどの関数ですぐ見つからないようにする

などのチェックも入れても良かったかなと思います.普通はこんなんで重複することないと思うのですが,「前の人の素数よりは少ないけどなるべくセキュアなやつ」とかやっているともしかしたら作り方が他のチームと似ていて近い素数を選んでしまうなどが考えられるのかなぁとか思いました.また,ブレイクの方法については,

  • 素数の使いまわしもチェックする

という手法もあったなぁと思いました.自分や他チームにブレイクされたModulusについてはブレイク履歴としてp,qが見れるようになる仕組みでしたので,その素数群を取ってきておいて使いまわしをチェックする,という手法もあったかなと思いました.

また,わたくし,少し浮足立っていました....「何か会場かっけぇ」「強い人めっちゃおる!」こんな感じでなんかふわふわしていて,自動化スクリプト書くときも何かすごく効率の悪い書き方をしたりしていました.スキル不足で手を出せなかった問題もあるのでそこは精進が必要ですが,次は場慣れして冷静に問題を解きたいです.

感想

初めてのKing of the hill形式のCTFはとても良い経験になりました.オンラインCTFと違い対戦相手が近くにいるという環境,Jeopardyとは違うAP,DPという加点要素などから,普段とは違う楽しさを感じることができました.

もっと勉強して次はトラブルシューティングコンテストなどに参加してみたいです.大事なのはコンテストのための勉強にならないことだと思います.コンテストをモチベーションにすることは良いことだと思いますが,普段の勉強の成果を確認する場としてコンテストを活用するのが理想の形だと考えます.今後もセキュリティやインフラに関する知識を磨いていきたいこうと思います.

参考

PythonのWeb開発フレームワーク「Flask」のインストール・使い方

PythonでWeb開発したいと思っていたので使ってみることに.バイト等ではPHPマンですが研究やCTFではPython使っていて,サーバ側の処理書くときに慣れたPython使えると楽しそうだなぁと思っていました.PythonでのWeb開発に手を出してみるファーストステップです.

Flaskとは

FlaskはPythonでWeb開発するためのマイクロフレームワークです.所謂フルスタックフレームワークと逆のものと思っていれば良いのではないでしょうか.公式ドキュメントには以下のようにあります.

“Micro” does not mean that your whole web application has to fit into a single Python file (although it certainly can), nor does it mean that Flask is lacking in functionality. The “micro” in microframework means Flask aims to keep the core simple but extensible. 省略

別に単一ファイルで作るとか機能が不足しているっていうことは無いんだけど,シンプルかつ拡張性があることを意味してるんだよねみたいなことを書いてる.機能が欠けているわけではないけど最小限のものに留めてあるので,ORM等はPeeweeなど別のものを使う必要がある?という感じでしょうか.

環境

今回Flaskをインストールして使ってみる環境です.

以下のように確認.

$ python -V
Python 2.7.10

$ virtualenv --version
15.1.0

 

環境構築

こちらの公式ドキュメントを参考にインストールします.インストールはpip install でできるのでとても簡単ですが,今回はドキュメントに従ってvirtualenvを使った環境構築をしてみます.

virtualenvとは

あるディレクトリに仮想的な環境を作ることができます.この仮想的な環境の中でインストールしたPythonライブラリなどは,実環境のlib等を汚しません.ですから,色んなバージョンを試したいとか色んなライブラリを試したいといった時に,virtualenvで作った仮想的な環境の中でやることで実環境を汚さずに試すことができるのです.

以降この記事では,virtualenvによって作成した仮想的な環境を仮想環境と呼びましょう.

virtualenvのインストール

管理者権限でCygwinを起動して以下のコマンドを実行.

$ pip install virtualenv

 virtualenvで仮想的な環境を作成

以下のようにワークスペースを作っていきます.任意のディレクトリで以下のコマンドを実行します.3行目のvenvは任意の名前です.

$ mkdir myproject
$ cd myproject
$ virtualenv venv
New python executable in /cygdrive/c/Users/省略/myproject/venv/bin/python2.7
Also creating executable in /cygdrive/c/Users/Haruka/Desktop/vernal_local/hobby/PCrelation/study/flask/myproject/venv/bin/python
Installing setuptools, pip, wheel...done.

念のため以下のように環境ができているか確認.

$ ls
venv
$ ls venv/
bin  include  lib  pip-selfcheck.json

できてそう.

仮想環境のアクティベート

以下のようなコマンドを実行することで,仮想環境を立ち上げることができます.

$ . venv/bin/activate
(venv)

このように (venv) って出ていたらOK.逆に終了する時は以下のコマンド.

$ deactivate

 

Flaskのインストール

本命のインストールです.と言っても仮想環境立ち上げてpip installするだけ.

$ . venv/bin/activate
(venv)
$ pip install Flask
Collecting Flask
  Downloading Flask-0.12-py2.py3-none-any.whl (82kB)
    100% |████████████████████████████████| 92kB 554kB/s
Collecting itsdangerous>=0.21 (from Flask)
  Downloading itsdangerous-0.24.tar.gz (46kB)
    100% |████████████████████████████████| 51kB 551kB/s
Collecting click>=2.0 (from Flask)
  Downloading click-6.7-py2.py3-none-any.whl (71kB)
    100% |████████████████████████████████| 71kB 810kB/s
Collecting Jinja2>=2.4 (from Flask)
  Downloading Jinja2-2.9.5-py2.py3-none-any.whl (340kB)
    100% |████████████████████████████████| 348kB 1.0MB/s
Collecting Werkzeug>=0.7 (from Flask)
  Downloading Werkzeug-0.11.15-py2.py3-none-any.whl (307kB)
    100% |████████████████████████████████| 317kB 656kB/s
Collecting MarkupSafe>=0.23 (from Jinja2>=2.4->Flask)
~~~省略~~~
Installing collected packages: itsdangerous, click, MarkupSafe, Jinja2, Werkzeug, Flask
Successfully installed Flask-0.12 Jinja2-2.9.5 MarkupSafe-0.23 Werkzeug-0.11.15 click-6.7 itsdangerous-0.24
(venv)

最後に (venv) と出てるのが仮想環境内でコマンドを叩いた証.

これでFlaskのインストールも完了し,環境構築完了です.

Flaskの使い方

公式ドキュメントのQuick StartのA Minimal Applicationから.Flaskを使った最小限のアプリケーションは以下のコードで作成できます.

このような感じです.必要な環境変数を追加して実行します.

$ export FLASK_APP=hello.py
$ flask run
 * Serving Flask app "hello"
 * Running on http://127.0.0.1:5000/ (Press CTRL+C to quit)

この状態で上記URLにブラウザでアクセスすれば,ブラウザに"Hello, World!"が印字されることが確認できる.

なおこのコマンドはテスト向きだが実際にサーバで動かす時は別のオプションが必要になるとのこと.その辺はまだちゃんと見ていない.また,テストでローカル以外からアクセスさせたい時は以下のオプションで全IPからのアクセスを許可する.

$ flask run --host=0.0.0.0
 * Serving Flask app "hello"
 * Running on http://0.0.0.0:5000/ (Press CTRL+C to quit)
(venv)

Windowsならこの時ファイアウォールの設定変更が促されるのでパブリックを許可すればOK.これで同一ネットワーク内からのアクセスもできるようになる.普段はローカルだけで十分なのでこのコマンドは使わないと思いますが.

ちなみに,以下のオプションを付けると,デバッグでコードを変えた時にいちいちflask runをし直さずに済むそうです.

$ export FLASK_DEBUG=1
(venv)
$ flask run
ですが僕の環境ではこの環境変数を入れるとflask runで簡易サーバが立たなくなってしまったので消しました.
<pre class="theme:dark-terminal lang:default decode:true">$ unset FLASK_DEBUG</pre>
以上,Flaskの環境構築方法と最低限の使い方でした.
<h3>余談</h3>
PythonならDjangoとか有名ですよね.最初はDjangoで始めようと思ってたのですが知人が「Flaskって何かイケてる感じする」と言ったのでFlaskにしました.Djangoもその内触ってみたいです.        

CanonプリンターPIXMA TS8030をUbuntuで使う

プリンターを変えた時に,家の共用PC(Elementary OS)にプリンターの設定した時のメモ.

以前使っていたCanonのプリンターでは公式ページにLinux環境のドライバーも置いてあった気がしたのですが,見当たらなかった.

ちなみに前に使っていたのはMP640というやつで,同じくElementary OSで使っていた.その時のインストール手順はこちら

ドライバのインストーラダウンロード

ググっていたら見つけたこちらのサイトの,Canon PIXMA TS8030 Driver for LinuxIJ Printer Driver ver. 5.40 for Linux (Debian)をダウンロード.

ドライバのインストール

tar.gzを解凍.

$ tar xvzf cnijfilter2-5.40-1-deb.tar.gz

install.shを実行すると,ネットワーク内のプリンタの選択などを対話的に進めることができ,その設定が終わればインストール完了です.

$ sudo ./install.sh
...
USB接続かネットワーク接続の選択やネットワーク内のプリンタの選択が対話的に行われる.

適当なものの印刷画面に行くと,任意のプリンターが選択できるようになっているはずです.

短いですが以上です.

USRPを使い始める話(3)

            USRPを使い始める話(1)でこの投稿の構成を以下のように示しました.
  1. MatlabでUSRPを動かす
  2. USRPのファームウェア及びFPGAイメージのアップデート(前編)
  3. USRPのファームウェア及びFPGAイメージのアップデート(後編)

前回はUSRPの各種操作に必要なUHD(Usrp Hardware Driver)のインストールを行いました.

今回はUSRPのファームウェア及びFPGAイメージのアップデート(後編)ということで本題に入っていきます.

3. USRPのファームウェア及びFPGAイメージのアップデート(後編)

というわけで,(1)でMatlab実行時に促された指示を実際に実行してみます.(実は,UHDのuhd_usrp_probeを実行してもMatlabの時に出たエラーと対処法が表示されるはずです.)

その前にまずUSRPの接続確認をします.UHDのuhd_find_devicesを使いましょう.No UHD Devices Foundと表示されずにIPやデバイス名が表示されればOKです.もし表示されない場合は(1)で行ったネットワークの設定を再度見直したり,きちんとクロスケーブルで接続しているか,USRPの電源が入っているかを確認しましょう.

接続確認ができたら以下のコマンドを実行します.

$ sudo uhd_images_downloader
Images destination : /usr/local/share/uhd/images
...
Images successfully installed to: /usr/local/share/uhd/images

$ sudo uhd_image_loader args="type=usrp2, addr=192.168.10.2"
...
Unit: USRP N210 r4 (4095, 192.168.10.2)
Firmware image: ...
-- Erasing firmware image...successful.
-- Writing firmware image...successful.
-- Verifying firmware image...successful.
FPGA image: ...
-- Erasing FPGA image...successful.
-- Writing FPGA image...successful.
-- Verifying FPGA image...successful.

上手くいくとこのように全ての項目がsuccessfulとなる.その後一度USRPの電源を抜いてもう一度指し直せば,ファームウェアFPGAイメージのアップデートが完了し,正常にUSRPを使うことができるようになる.

上手くいかない場合

私の場合はこれでは上手くいきませんでした.全てにおいてsuccessfulと表示されますが,一向にアップデートをしろという旨のエラーが出続けました.そこで,代わりに以下のコマンドを実行します.

$ usrp_n2xx_net_burner --addr=192.168.10.2 --fw=/usr/share/uhd/images/usrp_n210_fw.bin
$ usrp_n2xx_net_burner.py --addr=192.168.10.2 --fpga=/usr/share/uhd/images/usrp_n210_r4_fpga.bin

これらは,uhd_image_loaderと同じ処理をするコマンドである.usrp_n2xx_net_burnerコマンドを使う場合は,使用するファームウェアFPGAイメージのファイルを指定する必要があります.また,このコマンド実行後は自動的にUSRPを再起動するため電源を入れ直す必要はない.私の環境ではこのコマンドを使うことで正常に動作させることができるようになり,無事MatlabのFM受信を行うことができました.

本記事は(1)から(3)に分けて,USRP+Matlabに必要なセットアップ,UHDのインストール,ファームウェア及びFPGAイメージのアップデートについて説明しました.この記事は今回で終わりになります.しかしながらこの手順は私がUSRPを使い始めた際に起きたことをメモとしてまとめているので説明が煩雑になっている部分もあると思います.そこでUSRPのGet Startedに関しては別途まとめた記事を作りたいと思います.

参考