読者です 読者をやめる 読者になる 読者になる

sonickun.log

備忘録

Webトラッキングの大規模調査―Online tracking: A 1-million-site measurement and analysis

セキュリティ 研究

本稿は「情報セキュリティ系論文紹介 Advent Calendar 2016 - Adventar」9日目の記事である。

ACM CCS 2016で発表されたWebトラッキングに関する論文を紹介する。なお、本記事で用いられている図表はこの論文から引用したものである。

背景と前提知識

Webトラッキングとは、オンライン上でのユーザーの行動を追跡・分析する営みのことを言う。皆さんも、ショッピングサイトで閲覧したことのある商品(またはそれに関連するもの)の広告が、別のサイトで表示された経験があるのではないだろうか。そういった現象の裏ではWebトラキングの技術が使われている。

Webトラッキングのあまり知識がない場合は、過去に#ssmjpで発表を行った時の資料を参照されたい。

www.slideshare.net

Webトラッキングはターゲット広告やアクセス解析等に活用さている一方で、ユーザーのプライバシー侵害や不正広告への悪用といったリスクもはらんでいる。学術界でも近年頻繁にWebトラッキング関連の論文が発表されており、大きく分類して以下の3つの論調がある。
・Webトラッキングのメカニズム解明(新たなFingerprinting手法の提案など)
・Webトラッキングの防御(Anti-Fingerprinting手法の提案、ユーザーのプライバシーを保護した広告システムの提案など)
・Webトラッキングの実態調査(Webクローラを用いた大規模調査など)

今回紹介する論文は3つ目のMeasurement系の論文の当たる。Measurement系の研究の意義は”Transparency”を高めることにあり、それによって何らかの示唆や提言を与えることを目指している。

論文紹介

  • Title: Online Tracking : A 1-million-site Measurement and Analysis
  • Authors: Steven Englehardt and Arvind Narayanan of Princeton University
  • Conference: ACM CCS 2016

著者らはこの論文を紹介するためのWebサイトを公開している。

ちなみにACM CCSは、情報セキュリティ系の国際会議(Security Conference Ranking and Statistic)でRank1に位置する、いわゆるTop of Topのカンファレンスである。

※記事が長くなってしまったが、忙しい人には次の「3行で概要」と「Key Findings」だけを読んでいただけばざっくりと論文を理解できるかと思う。

3行で概要

  • Alexa100万サイトの大規模かつ詳細なWebトラッキングサイトの実態調査を行った。
  • Cookie/Fingerprintベースのトラッキング、対策ツールの有効性、Cookie Syncingについて調査を行った。
  • 実ブラウザおよびヘッドレスブラウザにより自動的にクロールを行うプラットフォーム「OpenWPM」を開発した。

Key Findings

  • ラッキングサイトのリンク数の分布は「ロングテール」になることが分かった。
  • ラッキング強度の定量化手法を用いて、トラッキング対策ツールであるGhosteryが有効に働くことを示した。
  • Cookie Syncingが以前よりも広く利用されるようになった。
  • 調査の中で、これまで観測されていなかった新たなFingerprinting手法を観測した。

OpenWPM

OpenWPMは著者らが開発した、実ブラウザとヘッドレスブラウザを用いて自動的にWebクロールを行うプラットフォームである。
f:id:sonickun:20161204181115p:plain

OpenWPMの特徴は以下のとおりである。

  • Browser automation: ブラウザをプログラムによって制御する
  • Stateful crawls: セッションごとにCookieやLocal Storageを保存する
  • Persistent profiles: セッションをまたいでCookieやLocal Strageを維持する
  • Fine-grained profiles: Flash Cookieなどの補助的な個別の情報を保持する
  • Advanced plugin support: ブラウザのプラグインを使用することができる
  • Detect tracking cookies: Cookie Syncで使用されるCookieを検知する
  • Monitor state changes: Cookieやブラウザ情報に対するアクセスを記録する
  • JavaScript Instrumentation: JavaScriptが実行可能である

OpenWPMは過去のmeasurement研究で用いられたWebクローラよりも高機能に作られており、より網羅的かつ詳細な分析が可能になっている。
f:id:sonickun:20161204182106p:plain

こういった実態調査のためのツールは研究コミュニティで広く共有されるべきとして、著者らはOpenWPMとそのログデータを公開している。
github.com

実態調査

OpenWPMを用いてAlexaのTop100万サイトをクロールし、Webトラッキングの実態調査を行う。Webサイトにアクセスした際のHTTP request/responseやJavaScriptの実行ログを収集する。今回はトップページにのみアクセスし、エラーハンドリングのために1サイトごとに90秒のタイムアウトを設けている。

前述したKey Findingsにならって実態調査の結果を示す。

ラッキングサイトのリンク数の分布は「ロングテール型」になる

ラッキングサイトにはファーストパーティ(ユーザーが直接アクセスするサイト)とサードパーティ(ファーストパーティからリンクされている外部のサイト)に分類されるが、調査の結果、2つ以上のファーストパーティからリンクされているサードパーティ81,000サイト抽出された。下図のようにリンク数の大きい順にサードパーティを並べると、ロングテール型のグラフになる。最もリンク数の多かったgoogle-analytics.comは、ファーストパーティ100万サイトのうち、約70%という非常に広い範囲にリンクされていることが判明した。また、全体の1%(1万サイト)以上にリンクされているサードパーティはわずか123/81,000サイトしかなく、10%(10万サイト)以上にリンクさているサードパーティに至っては、GoogleFacebookTwitter、AdNexusの4組織しか存在しなかった。このことから、ユーザーは日常的にアクセスするほとんどのWebサイトで同一の組織にトラッキングさている一方で、エンカウントするサードパーティの種類はかなり限定的であることがわかった。
f:id:sonickun:20161204222147p:plain

ラッキング対策ツールであるGhosteryが有効に働く

GhosteryはサードパーティCookieをブロックできるブラウザのプラグインであり、サードパーティによるトラッキングを防ぐことができる。
chrome.google.com
今回の調査では、Ghosteryを用いて、すべてのサードパーティCookieのうち99.6%Cookieをブロックでき(ブロックできなかったのは237サイト)、ツールの有効性を示した。
本論文では独自のロジックでサードパーティProminence(目立ち具合、影響度)を定量化しており、Prominenceが小さいサードパーティ(マイナーなサードパーティ)であるほど、Ghosteryの検知漏れの割合が高いことが分かった。著者らによれば、Ghosteryの検知ロジックの中にはBlacklistを用いた手法が使わているらしく、マイナーなトラッキングサイトほどBlacklistから漏れやくなっているのではないかと分析している。
f:id:sonickun:20161204225221p:plain

Cookie Syncingが以前よりも広く利用されるようになった

Cookie Syncingとは、前提知識のスライドにもある通り、ユーザーを識別するIDを複数のサードパーティで共有し、Same-Origin Policyを超えてトラッキングができる広告システムである。トラッカーAがトラッカーBとユーザーのIDを共有したいとき、トラッカーBへのリクエストURLの中、あるいはリファラURLの中にIDを埋め込む。したがって、HTTP Request/Response をモニターすることでCookie Syncingを検知できる。

調査の結果、最も顕著なCookie Syncingサードパーティであったdoubleclick.netは、118の他のサードパーティ108ユニークなCookieを共有していることが判明した。また、主要な(Prominenceが大きな)サードパーティの大多数は、少なくとも他の1つのサードパーティCookieを共有していた。驚くべきことに、ProminenceがTop 50のサードパーティを無作為に2つ選択したとき、両者が互いにCookieを共有している確率は約85%であることが分かった。著者らは過去にも同様の調査を行い論文を発表しているが、今回のこの数字は過去のそれよりも高く、Cookie Syncingがより広範に利用されるようになったことを示唆している。

新たなFingerprintingの発見

Webトラッキングで言うところの”Fingerprint”とは、ブラウザの種類、インストールさているプラグインやフォントの種類、スクリーンのサイズといった、端末に固有の情報の組み合わせのこと言い、毎年のように新しいFingerprintが発見さている。今回の調査ではこれまで見つかっていなかった(公に発表されていなかった)Fingerprintを用いたトラッキングを発見している。いわば「ゼロデイFingerprinting」のようなものである。

発見されたFingerprintingは以下の4つである。
Canvas Font Fingerprinting
Canvasでフォントを指定して文字を描画した際に、画像のサイズをもとにそのフォントがインストールされているかどうかがわかり、インストール済みフォントのリストが作れる。Canvasの画像データのハッシュ値を識別子とするCanvas Fingerprintとは区別される。

・Web-RTC Fingerprinting
Web-RTCで取得できるNAT配下のローカルネットワークのインターフェースやアドレスの情報がFingerprintとして利用されていた。

・AudioContext Fingerprinting
音声を発信するAPIを使うと音声信号がソフトウェア/ハードウェアに依存して微妙に変化することを利用して、フーリエ変換後の周波数情報をハッシュ化しFingerprintとして利用していた。
f:id:sonickun:20161204235550p:plain

・Battery API Fingerprinting
バイスのバッテリー残量情報を利用して短時間のユーザー識別を行っていた。たとえば、ユーザーがネットサーフィンの途中でシークレットブラウジングに切り替えた際(Cookieが無効になったとき)、バッテリーの減り具合から、シークレットブラウジング切り替え前後のユーザーを紐づけることができる。

その他の発見
  • サードパーティのトラッキングサイトのHTTPS非対応により、Mixed-content Errorが頻発していることがわかった
  • ラッキングサイトを分類した結果、ニュースサイトでトラッキングが多いのに対し、政府組織・教育機関・非営利組織のサイトではトラッキングは少ない(Funding sourcesの存在が関係している)
  • 前回の調査から、最も主要な広告サードパーティ(AddThis)がCanvas Fingerprintingを取りやめた(論文を通して脅威を示したことが効果的であった証明)
  • 既存のツールで新しいFingerprintingをブロックできる割合は低い

まとめと今後の展望

本研究のようなWebプライバシーに関する調査は、プライバシー侵害やユーザー⇔Webサイト間の力の不均衡(たとえば、"ユーザーの意思に反して"プライバシー情報が搾取されている状況など)を監視する役割がある。また、調査のためのツールは研究コミュニティの中で広く共有されるべきであり、今回開発したOpenWPMはオープンソースとして公開している。

今後は機械学種によって自動的にトラッキングサイトを検知・分類することを目指している。

所感

・良かった点
過去のWebトラッキングのMeasurement系の論文と比較しても、かなり網羅的かつ詳細な調査を行っている。トラッキングの手法にもさまざまな種類があるが(Cookieを使ったもの、Fingerprintを使ったものなど)、それぞれを検知するのに必要十分なログが取れるようにシステムを開発している。自分もWebクローラを開発した経験があるが、OpenWPMはかなりの労力と時間をかけて作られている印象を受けた。たとえば、任意のブラウザプラグインを動かしながらクロール(ログ記録)したり、JavaScriptの実行ログをすべて記録したり、といったことは、やろうと思ってもなかなかできないことである。しかも開発したツールや収集したデータが公開されており、さすがトップカンファレンスに採択されるだけの論文だなと思った。

また、これまでのMeasurement系の研究にはない試みとして、ゼロデイFingerprintingの発見に成功している。新しいFingerprintというのはこれまで我々が想像しなかったものになるのが常であり、今回見つかったFingerprintもどれもユニークなものばかりであり、大きな驚きがあった。

・いまひとつな点(コマカイ話)
ラッキングされていることはわかっていてもそれが実際にどれほど脅威になりうるのかということはイメージしにくいが、本論文ではトラッキングサイトの影響度(Prominence)を独自の方法で定量化しそれを指標として用いている。しかし、定量化の数式についての妥当性については言及がなく、個人的にはあまり最適とは言えない印象を持った(Paperを見てもらえばわかるが、Alexa最上位のサイトのスコアが異常に高くなり、Google一強にしか見えなくなる)。おそらく「指標が何もないよりよいだろう」という心情で決め打ちで作ったのだろうけど、今後改良の余地があると思う。

また、ゼロデイのFingerprintingの検知について、どうやって見つけたのか?というと、著者らによれば「JSの実行ログを見てりゃわかる」といった言いっぷりだったが、それだけではいくらProfessionalでも膨大なログから見つけるのは難しいとおもう。おそらく「このへんがFingerprintとして狙われるだろう」というヤマを張っておいて見つけたのだろうと推測する。ヒューリスティックな方法ではなく、ある程度自動的にゼロデイFingerprintingを検知できるような手法(例えば、同じサイトのJSコードの変化を継続的に監視するなど)が共有されればなおよいと思った。

他にも、トラッキング対策ツールを他のものともっと比較検証するとよいのではないか、など、まだまだコマカイ話はあるが、今回はこの辺にしておこうと思う。

SageMathでPythonの外部ライブラリを使えるようにする

SageMathはPythonベースで作られているが、外部の(標準でない)Pythonライブラリをインポートしようとするとエラーが起きることがある。

たとえばPyCryptoだと、普通のPythonの対話シェルではインポートできているのに、

$ python
Python 2.7.11 (default, Dec  7 2016, 17:13:00)
[GCC 4.4.7 20120313 (Red Hat 4.4.7-17)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from Crypto.Util.number import *
>>>

Sageでは失敗する。ということが起きる。

$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 7.3, Release Date: 2016-08-04                     │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
sage: from Crypto.Util.number import *
---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-1-3aca3f9edb99> in <module>()
----> 1 from Crypto.Util.number import *

ImportError: No module named Crypto.Util.number

この場合、Pythonライブラリを"Sageから"インストールする必要がある。

Solution

Sageには「シェルモード」というものがあり、そのモードでPythonライブラリのインストールコマンドを打てばよい。シェルモードはsage -shで起動する。

$ sage -sh

Starting subshell with Sage environment variables set.  Don't forget
to exit when you are done.  Beware:
 * Do not do anything with other copies of Sage on your system.
 * Do not use this for installing Sage packages using "sage -i" or for
   running "make" at Sage's root directory.  These should be done
   outside the Sage shell.

Bypassing shell configuration files...

Note: SAGE_ROOT=/path/to/sage-7.3
(sage-sh) $ pip install pycrypto
Collecting pycrypto
  Using cached pycrypto-2.6.1.tar.gz
Installing collected packages: pycrypto
  Running setup.py install for pycrypto ... done
Successfully installed pycrypto-2.6.1
(sage-sh) $ exit

これにてSage上でPyCryptoが使えるようになる。

おわり。

CTFにおける離散対数問題に対するアプローチ

CTF セキュリティ

CTFの暗号分野では、離散対数問題を利用したアルゴリズムElGamal暗号、Diffe-Hellman鍵共有など)がよく扱われる。本稿ではこの離散対数を高速に解く方法を備忘録としてまとめておく。

離散対数問題(DLP: Discrete Logarithm Problem)

素数{\displaystyle p} と定数{\displaystyle g} が与えられたとき

{ \displaystyle
g^x \equiv y\pmod{p}
}

において、{\displaystyle x}から{\displaystyle y}を計算することは容易だが、その逆の、{\displaystyle y}から{\displaystyle x}を求めることは困難であることを、離散対数問題と呼ぶ。公開鍵暗号方式では、このことを安全性の根拠とした暗号アルゴリズムがいくつか考案されている。CTFでは、この離散対数を解き、暗号の秘密鍵を特定する問題が出題される。

離散対数に対するアプローチ

離散対数に対するアプローチとして、列挙法Baby-step Giant-step algorithmPohlig–Hellman algorithmの3つの手法を紹介する。

列挙法

列挙法は最もシンプルな手法であり、上式において、{\displaystyle x=1,2,3,4,...}に対して合同式が成り立つかどうかを一つひとつ確認していく方法である。ただし、{\displaystyle g}の位数が大きいときは膨大な試行数になるため現実的ではない。オーダーは{\mathcal{O}(n)}

Baby-step Giant-step algorithm

Baby-step Giant-step algorithmは列挙法による試行数を削減したアルゴリズムであり、オーダーは{\mathcal{O}(\sqrt{n}\log n)}となる。

{ \displaystyle
g^x \equiv y\pmod{p}
}

において、{\displaystyle x=im+j}{\displaystyle m=\lceil\sqrt{p}\rceil}{\displaystyle 0 \leq i,j \lt m})として、以下の式を得る。

 \begin{align}
g^{im+j} &\equiv y\pmod{p} \\
g^j &\equiv y(g^{-m})^i\pmod{p}
\end{align}

このアルゴリズムでは上式の両辺が一致するように{\displaystyle i}{\displaystyle j}を総当たりし、{\displaystyle x}を求める。そうすることで、列挙法よりも試行数が少なくて済む。
Baby-step Giant-step algorithmの詳細な手順は以下のとおりである。

1. {\displaystyle m\leftarrow \lceil\sqrt{p}\rceil}
2. {\displaystyle 0 \leq j \lt m}を満たすすべての{\displaystyle j}について(Baby-step):
 1. {g^j  \pmod{p}}を計算し、{(j, g^j  \pmod{p})}のペアをテーブルに保存する
3. {g^{-m}}を計算する
4. {\displaystyle \gamma\leftarrow y}
5. {\displaystyle i=0}から{\displaystyle (m-1)}まで(Giant-step):
 1. {\gamma}がテーブルの第二要素{(g^j  \pmod{p})}に含まれるかチェックする
 2. もし含まれていれば、{\displaystyle x=im+j}を返す
 3. もしそうでなければ、{\displaystyle \gamma\leftarrow \gamma \cdot g^{-m}}とする

Pohlig–Hellman algorithm

Pohlig–Hellman algorithmは、

{ \displaystyle
g^x \equiv y\pmod{p}
}

に対し、{\displaystyle \phi(p)}の素因数が小さいときに有効に働くアルゴリズムである。ここで{\displaystyle \phi(n)}とはオイラー特性関数であり、{\displaystyle n}より小さい自然数のうち{\displaystyle n}と互いに素なものの個数を示し、特に{\displaystyle n}素数の場合は{\displaystyle \phi(n)=n-1}となる。

Pohlig–Hellman algorithmのアイデアとしては、{\displaystyle g}の位数が大きすぎて総当たりが困難だったものを、{\displaystyle g}の位数が小さな離散対数問題に分割して解き、後で結合するといったものである。

まず、{\displaystyle \phi(p)}を以下のように素因数分解する。

{ \displaystyle
\phi(p) = p_1 \cdot p_2 \cdot\cdot\cdot p_n
}

このとき、{\displaystyle p_i}の値は小さい(英語では"smooth"という)ことが望ましい。
{\displaystyle x = a_k p_k+b_k}としたとき、それぞれの{\displaystyle k}についてオイラーの定理より以下の計算を行う。

 \begin{align}
y^{\phi(p)/p_k} &\equiv (g^x)^{\phi(p)/p_k}\pmod{p} \\
&\equiv (g^{\phi(p)})^{a_k}g^{b_k\phi(p)/p_k}\pmod{p} \\
&\equiv (g^{\phi(p)/p_k})^{b_k}\pmod{p}
\end{align}

この合同式は最初に示した離散対数問題の形に帰着されるが、{\displaystyle b_k}{\displaystyle p_k}よりも小さいため、比較的容易に{\displaystyle b_k}を求めることが可能である(Baby-step Giant-step algorithmも組み合わせればより高速になる)。
これにより{\displaystyle b_k}の値が定まると、{\displaystyle x\equiv b_k \pmod{p_k}}が求まったことになる。

{ \displaystyle
x\equiv b_1 \pmod{p_1} \\
x\equiv b_2 \pmod{p_2} \\
\cdot\cdot\cdot \\
x\equiv b_n \pmod{p_n} \\
}

について、{\displaystyle p_1, p_2,..., p_n}は互いに素なので、中国人剰余定理より、これらを満たす整数{\displaystyle x}{ \displaystyle \phi(p) = p_1 \cdot p_2 \cdot\cdot\cdot p_n }を法として唯一つ定まる。こうして求まった{ \displaystyle x \pmod{\phi(p)}}が最初に示した離散対数問題の解となる({\displaystyle p}素数であるため、{\displaystyle g}の位数は{\displaystyle \phi(p)=p-1}である)。Pohlig–Hellman algorithmのオーダーは{\mathcal{O}(\sqrt{n})}だが、{\displaystyle \phi(p)}が小さいほどより効率的となる。

Pohlig–Hellman algorithmを使った攻撃の回避策として、安全素数を使う方法がある。安全素数は、{\displaystyle q}{\displaystyle 2q+1}がともに素数である場合における{\displaystyle 2p+1}である。このとき、{\displaystyle q}のほうはSophie Germain素数と呼ばれる。安全素数{\displaystyle p}を使うことで、{\displaystyle \phi(p)=p-1=2q}となり、{\displaystyle \phi(p)}が大きな素因数を持つことになるため、Pohlig–Hellman algorithmが有効に働かなくなる。安全素数が無限に存在するという予想は未だ証明されていないが、実用的には十分存在するといわれている。

実装例

離散対数問題を安全性の根拠としている暗号方式として、ElGamal暗号を取り上げる。ElGamal暗号では、素数{\displaystyle p}、整数{\displaystyle g}、乱数{\displaystyle x}{\displaystyle (0\leq x \lt p)}を選んで、

{ \displaystyle
y = g^x \mod{p}
}

を計算し、{\displaystyle y, g, p}を公開鍵、{\displaystyle x}秘密鍵とする。
暗号化フェーズでは、平文{\displaystyle m}と乱数{\displaystyle r}を用いて、以下のように暗号文{\displaystyle c_1, c_2}を計算する。

{ \displaystyle
c_1 = g^r \mod{p} \\
c_2 = my^r \mod{p} = mg^{rx} \mod{p}
}

復号フェーズでは、平文{\displaystyle m}を以下のように算出する。

{ \displaystyle
c_2(c_1^x)^{-1} \mod{p} = mg^{rx}(g^{rx})^{-1} \mod{p} = m
}

以上が、ElGamal暗号アルゴリズムである。
今回は、ElGamal暗号の例題として、MMA CTF 1st 2015で出題された「Alicegame」という問題を扱う。問題より、ElGamal暗号における以下の値が判明している(本当は鍵がランダムに生成され、最適なpが引けるまでガチャを回す必要があるのだが今回はその部分を割愛)。

c1 = 1851635883910479967256646617880733235123029676545812189105888 
c2 = 2279140729739532482438192630521498934347693926502811537441460 
g = 1828219035112142373387222893932751631772945852477987101590090 
y = 1012750243445446249248731524345776923711031192963358920130436 
p = 3047318456124223787871095946374791137939076290647203431778747 
phi_p = 2 * 3 * 7 * 281 * 585131 * 2283091 * 66558319 * 38812459031 * 8407411055293 * 8899182573469

{\displaystyle \phi(p)}の素因数が小さいので、Pohlig–Hellman algorithmを用いた攻撃が可能である。今回は、Baby-step Giant-step algorithmも併用して以下のようにソルバーを書いた。
gist.github.com
無事、平文を復号できたことがわかる。

【Deep Learning】過学習とDropoutについて

Deep Learning 機械学習

前回、Deep Learningを用いてCIFAR-10の画像を識別しました。今回は機械学習において重要な問題である過学習と、その対策について取り上げます。
sonickun.hatenablog.com

過学習について

過学習(Overfitting)とは、機械学習において、訓練データに対して学習されているが、未知のデータに対して適合できていない(汎化できていない)状態を指します。たとえ訓練データに対する精度が100%近くに達したとしても、テストデータに対する精度が高くならなければ、それは良い学習とはいえません。特にニューラルネットは複雑なモデルのため過学習に陥りやすいと言われています。

過学習の例

過学習の例として、最小二乗法による多項式近似を用いてサインカーブy=sin(2 \pi x)標準偏差0.3の乱数)を推測してみます。

下の図は、多項式の次数Mを変化させた時の学習の結果を表しています。E(RMS)は近似したい関数との平均二乗誤差を表しています。M=9のときE(RMS)の値は0.0(回帰曲線が全てのプロットを通っている)となっていますが、近似したいサインカーブからは大きくはずれてしまっています。このような状態を過学習と呼びます。一方、M=3の時は予測したいサインカーブに近い回帰曲線が描けており、4つのグラフの中ではこれが最も良いモデルだといえます。E(RMS)の値が0.3に近いのは、データが本質的に0.3程度の誤差を含んでいることを示唆しています。
f:id:sonickun:20160714163447p:plain
最小二乗法による多項式近似 スクリプト
https://gist.github.com/sonickun/c7837d0cf732cda7d69d373abc82f99c

Dropoutについて

Dropoutは、階層の深いニューラルネットを精度よく最適化するためにHintonらによって提案された手法です。

Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, Ruslan Salakhutdinov. Dropout: A Simple Way to Prevent Neural Networks from Overfitting. The Journal of Machine Learning Research, Volume 15 Issue 1, January 2014 Pages 1929-1958
・PDF: https://www.cs.toronto.edu/~hinton/absps/JMLRdropout.pdf

Dropoutでは、ニューラルネットワークを学習する際に、ある更新で層の中のノードのうちのいくつかを無効にして(そもそも存在しないかのように扱って)学習を行い、次の更新では別のノードを無効にして学習を行うことを繰り返します。これにより学習時にネットワークの自由度を強制的に小さくして汎化性能を上げ、過学習を避けることができます。隠れ層においては、一般的に50%程度を無効すると良いと言われています。当初Dropoutは全結合のみに適用されていましたが、先ほど挙げた論文によれば、畳み込み層等に適用しても同様に性能を向上させることが確かめられています。
f:id:sonickun:20160714170858j:plain
Dropoutが高性能である理由は、「アンサンブル学習」という方法の近似になるからとも言われています。アンサンブル学習とは、複数の機械学習結果を利用して判定を行うことで、学習の性能を上げることです。これを応用した学習器として、ランダムサンプリングしたデータによって学習した多数の決定木を平均化するランダムフォレストなどがあります。

実験

前回記事とおなじCIFAR-10の画像識別を行い、Dropoutを実装した時としない時の比較を行ってみたいと思います。使用したDeep Learningフレームワークは前回と同じCaffeです。
学習の設定は以下のとおりです(細かいパラメータは割愛)。前回の知見を踏まえて、「学習率は徐々に小さく」、「活性化関数はReLU関数」、「ニューラルネットワークはCNN」を意識しました。

  • 学習回数(Iterations): 70000
  • バッチサイズ(Batch Size): 100
  • 勾配降下法の学習率(Learning Rate): 0.001(~60000iters) -> 0.0001(~65000iters) -> 0.0001(~70000iters)
  • 活性化関数(Activation Function): ReLU関数
  • ニューラルネットワーク: CNN (畳み込み層×2+プーリング層×2+LRN層×2+全結合層×2)

今回は3つのパターンを試します。
1. CNNのみ
f:id:sonickun:20160714175543p:plain
2. CNN + Dropout (全結合層のみ)
f:id:sonickun:20160714175719p:plain
3. CNN + Dropout (全層)
f:id:sonickun:20160718182854p:plain
なお、Dropoutのユニットの選出確率pは全結合層ではp=0.5、その他はp=0.2としています。

結果と考察

以下の図は、上記の3つのパターンそれぞれについて、Train Accuracy(訓練データに対する精度)とTest Accuracy(テストデータに対する精度)の変化の様子を表したグラフです。CNNのみのグラフでは、学習が進むにつれてTest AccuracyとTrain Accuracyの差が開いていっていますが、これは過学習が起きていることを表しています。一方、Dropoutを実装するとこの差が小さくなり、特に全層に適用した場合はTest AccuracyとTrain Accuracyの差はほとんどなくなっています。このことより、Dropoutが過学習の回避策として機能していることが分かります。

CNNのみ

f:id:sonickun:20160718183605p:plain

CNN + Dropout (全結合層のみ)

f:id:sonickun:20160718183830p:plain

CNN + Dropout (全層)

f:id:sonickun:20160718183705p:plain

最後まで学習したときの(70000 iters)3つのパターンの識別精度を以下の表にまとめました。やはり全層に対してDropoutを適用した場合は過学習をほぼ回避できているようです。ただし、Dropoutで過学習を回避することがそのまま識別精度の向上につながるわけではなさそうです。予備実験では、全結合層以外のユニット選出確率もすべてp=0.5にしたところ、確かに過学習を回避できましたが、識別精度は60%代にまで落ち込んでしまいました。どの層にDropoutを施すかによって、ユニット選出確率の値を慎重に選ぶ必要がありそうです

Dropoutの詳細 Train Accuracy (%) Test Accuracy (%) Train - Test
CNNのみ 94.0 80.3 13.7
CNN + Dropout (全結合層のみ) 91.0 81.8 9.2
CNN + Dropout (全層) 82.0 81.1 0.9

おまけTips: CaffeのログにTrain Accuracyを出力する

Caffeのチュートリアル通りに学習を行うと、Iterationsの途中でTest Accuracy(テストデータに対する正解率)とTrain Loss(誤差関数の値)をログに出力してくれますが、Train Accuracy(学習データに対する正解率)は出力してくれません。

I0712 12:22:57.474715  4721 solver.cpp:337] Iteration 62000, Testing net (#0)
I0712 12:23:44.508533  4721 solver.cpp:404]     Test net output #0: accuracy = 0.8094
I0712 12:23:44.508831  4721 solver.cpp:404]     Test net output #1: loss = 0.555002 (* 1 = 0.555002 loss)
I0712 12:23:45.563415  4721 solver.cpp:228] Iteration 62000, loss = 0.294429
I0712 12:23:45.563508  4721 solver.cpp:244]     Train net output #0: loss = 0.294429 (* 1 = 0.294429 loss)

Train Accuracy(および Test Loss)を出力するにはニューラルネットワークの定義ファイル(.prototxt)を編集し、"Accuracy"の層のincludeの部分を削除すればよいです。

layer {
  name: "accuracy"
  type: "Accuracy"
  bottom: "ip1"
  bottom: "label"
  top: "accuracy"
  include {      # <-
    phase: TEST  # <- この3行を削除
  }              # <-
}

修正後のログ

I0714 17:34:24.503883 27309 solver.cpp:337] Iteration 60000, Testing net (#0)
I0714 17:35:07.727932 27309 solver.cpp:404]     Test net output #0: accuracy = 0.7468
I0714 17:35:07.728186 27309 solver.cpp:404]     Test net output #1: loss = 0.842801 (* 1 = 0.842801 loss)
I0714 17:35:08.998235 27309 solver.cpp:228] Iteration 60000, loss = 0.287727
I0714 17:35:08.998337 27309 solver.cpp:244]     Train net output #0: accuracy = 0.93
I0714 17:35:08.998360 27309 solver.cpp:244]     Train net output #1: loss = 0.287727 (* 1 = 0.287727 loss)


次回 -> http://そのうち

Deep Learning はじめました【CIFAR-10の識別】

機械学習 Deep Learning

f:id:sonickun:20160710224502p:plain
最近趣味で機械学習の勉強をしていて、中でもDeep Learningに興味を持って取り組んでいたので、備忘録としてブログにまとめておきます。

はじめに

本稿の目的は

  • Deep Learning で実際に画像識別を行う
  • Deep Leraning の特性を理解する(性能向上について考察を行う)

の2点です。Deep Learningの概要・アルゴリズムについてはあまり触れません。ニューラルネットやDeep Learningについて参考にした書籍・Webサイトは以下の通りです。

書籍

Web

Deep Learningフレームワークについて

今回、Deep Learningのフレームワークとして、「Caffe」を使用しました。

他にもいろいろとフレームワークがありますが、Caffeを選んだ理由として、高速であること、ドキュメント・チュートリアルが豊富であること、開発コミュニティが活発であること、などがあります。

Caffeのインストール

使用したデータセット(CIFAR-10)について

今回、CIFAR-10というデータセットを用いて画像識別を行いました(MINSTの手書き文字認識のようなものは飽きた)。CIFAR-10は、以下のような32×32pixの10カテゴリ60000枚(1カテゴリにつき6000枚)の画像データです。クラスラベルはairplane, automobile, bird, cat, deer, dog, frog, horse, ship, truckの10クラスで、50000枚の訓練画像と10000枚のテスト画像に分割されています。
f:id:sonickun:20160710171636p:plain

実験の概要

実際にCaffeを用いてCIFAR-10の画像を識別してみます。Caffeの公式サイトにはCIFAR-10を使用したチュートリアルが公開されています。

CaffeではDeep Learningの細かい条件を設定して学習・テストを行うことができます。今回はこの条件を変化させながら実験して精度の比較を行い、以下の点について考察を行います。

初期設定

実験の際の初期設定は以下の通りです(細かいパラメータは割愛)。このうちいずれかの条件を変化させながら実験を行います。なお、学習回数について、これは十分な回数とは言えませんが、今回はできるだけ高精度なモデルを作ることが目的でないので、処理時間も考慮してあえて少なめにしてあります。

  • 学習回数(Iterations): 5000
  • バッチサイズ(Batch Size): 100
  • 勾配降下法の学習率(Learning Rate): 0.001
  • 活性化関数(Activation Function): ReLU関数
  • ニューラルネットワーク: CNN(Convolutional Neural Network)

下図はCaffeのPython用ライブラリ「Pycaffe」を用いて描画したCNNのネットワーク図です。文字が小さくて見にくいですが、青が入力層・出力層、赤が畳み込み層、オレンジがプーリング層、紫が全結合層を表しています。また緑色の部分で活性化関数を施します。
f:id:sonickun:20160710182528p:plain

なお今回は、100回のIterationごとに学習データの損失関数の値(Training Loss)を、500回のIterationごとにテストデータの正解率(Test Accuracy)を算出します。


結果と考察

勾配降下法の学習率の影響

ニューラルネットのエッジの重みの最適化には、勾配降下法を利用します。勾配降下法は以下の式で変数の更新を行います。
x_{i+1}=x_i-\epsilon\frac{\partial f}{\partial y}
ここで、x_iはある時点の変数の値、\frac{\partial f}{\partial y}は勾配、x_{i+1}は更新後の値です。つまり、変数を勾配の方向に動かしていくわけですが、この変数を動かす量\epsilon学習率(あるいは学習係数)です。したがって、この学習率の決め方が学習の性能に大きな影響を与えます。そこで、学習率を変えたときの影響を見ていきます。

下の図は、学習率を0.0001、0.001、0.01とした時の損失関数の値を比較したグラフです。学習率が0.001、0.0001の時は学習が進むにつれて損失関数の値(訓練誤差)が小さくなっているのに対し、学習率が0.01の時は損失関数の値が全く減少しません。学習率が小さいと学習を重ねるごとに確実に誤差を小さくしていくことができますが、学習率が大きすぎると変数の移動が大きすぎるために精度がすぐに頭打ちになり、途中で学習自体が破綻することがあります

また、学習率が0.001の時と0.0001の時を比べると、0.0001の時のほうが誤差関数の値の落ち込みが遅いことが分かります。学習率が小さすぎると、エッジの重みの更新量が小さくなってしまうので、反復回数が増加し学習にかかる時間が大きくなってしまいます
f:id:sonickun:20160710194018p:plain

このように、学習率の決定が学習の性能に大きな影響を及ぼすことが分かります。一般的に、学習の序盤(誤差が大きい時)では学習率を大きめに設定し、学習が進むにつれて徐々に学習率を小さくしていくのが良いとされています。

活性化関数の影響

活性化関数とは、前の層のノードとエッジの重みの積の和に対して施す関数のことです。今回、中間層の活性化関数としてSigmoid関数、TanH関数、ReLU関数の比較を行います。それぞれの関数は下図のようなグラフになります。
f:id:sonickun:20160710180559p:plain
(画像引用: http://www.rubedo.com.br
下のグラフはそれぞれの活性化関数を利用した時の、テストデータの正解率の変化の様子を表したものです。グラフを見ると、ReLU関数>TanH関数>Sigmoid関数の順で正解率が高いことがわかります。TanH関数やSigmoid関数は値が大きくなると関数の勾配が0に近づき学習が進みにくくなるのに対し、ReLU関数は比較的学習の速度が早く、学習が止まってしまうことも少ないです。
f:id:sonickun:20160710204115p:plain
ReLU関数が登場する以前は、活性化関数としてSigmoid関数やTanH関数が使われていましたが、最近は収束の速さや安定性の観点からReLU関数がよく利用されています。

ニューラルネットワーク構成の影響

最後に、ニューラルネットワーク構成を変化させた場合の影響を検証します。今回、CNNとの比較対象として、全結合ニューラルネットワークを考えます。

CNN(Convolutional Neural Network)とは、畳み込み層とプーリング層を含むニューラルネットのことであり、画像認識でよく使われます。畳み込み層は、前の層で近くにあるノードの集合同士が次のノードと接続するような構造を持ち、ある画像の局所的な部分を抽象化する役割を果たします。プーリング層は、前の層のノードの局所的な部分をまとめあげる処理を行い、小さな平行移動に対する不変性を持たせる役割を果たします。

一方、全結合層(Inner Product)とは、前の奥ノードと自分の層のノードがすべてエッジで結ばれている層を指します。今回は、下図のような5つの全結合層を持つニューラルネットを用いて実験を行います(これより層の少ないネットワークでは全く精度が上がりませんでした)。
f:id:sonickun:20160710182617p:plain

下のグラフはCNNと全結合ニューラルネットワークを利用した時のテストデータの正解率の変動を表したものです。グラフを見ると明らかにCNNのほうが精度が高いことがわかります。画像のような2次元情報においては、縦・横方向のズレを吸収できる畳み込みやプーリング層をもつCNNのほうが有効であるといえます。
f:id:sonickun:20160710204155p:plain

全結合層では、ノード同士の組み合わせの分のエッジが必要となり、計算量が増大する傾向があります。したがって、ノード数の多い層で全結合層を利用することはあまり好ましくなく、隠れ層の後半や出力層によく利用されます。

最後に

今回、Deep LearningのフレームワークCaffeを用いてCIFAR-10の画像識別を行い、以下の項目を検証しました。

それぞれの条件は学習の性能に大きく影響し、慎重に選ぶ必要があることがわかりました。Deep Learningは人間が何も考えなくても問題を解決してくれる魔法の杖というわけではないと言えます。

今後

Deep Learningアルゴリズムには他にも様々なパラメータがあるため、それらも変更しながらいろいろなパターンを試してみようと思います。
また、今回の知見も踏まえ、学習回数を増やしてCIFAR-10の識別を行い、訓練誤差と予測誤差の関係を見たり、中間層の可視化をやったりしようと思います。



次回
sonickun.hatenablog.com

Google CTF 2016 Writeup - Eucalypt Forest, Wolf Spider

CTF セキュリティ

2016/4/29~2016/5/1に開催されたGoogle CTF 2016にチームm1z0r3として参加しました.今回はEucalypt ForestとWolf Spiderという暗号問題のWrite-Upを書こうと思います.
https://capturetheflag.withgoogle.com/

Eucalypt Forest [Crypto 100pt]

Task

Can you find any weaknesses in the use of the encryption keys?

Head over to eucalypt-forest.ctfcompetition.com

Overview

リンクにアクセスするとブログサイトが表示される.このサイトに攻撃を仕掛け,adminとしてログインするとFlagが得られることが分かる."Signup"からは任意のユーザー名を入力してログインできるが,ユーザー名にadminに指定した時にのみアクセスが弾かれるようになっている.

ブログの開発記事を読んでみると,Cookie(UID)を用いてセッション管理をしていることが分かる.セッション情報は{ "username": "hoge" }のようなフォーマット(これをobjと呼ぶことにする)になっているが,objはAES-CBCで暗号化され,以下のようにUIDが決定する.

UID = IV + Encrypt(obj + padding)

IVはCBCモードのInitial Vector(16byte)であり,暗号文のバイト数が16(ブロック長)の倍数になるようにpaddingが挿入されている.

暗号化および復号処理のコードは以下のようになっている.

class CookieCutter:
	KEY_SIZE=16

	@staticmethod
	def encode(obj):
		s = json.dumps(obj)

		iv = os.urandom(16)

		# because len(s) may not be a multiple of the key size, we need to pad it
		# https://tools.ietf.org/html/rfc2315#section-10.3 has a way of
		# clearly indicating how padding should be performed, and how it
		# should be removed.

		pad = (16 - (len(s) % 16))
		s += chr(pad) * pad 

		algo = AES.new(Storage.aes_key,
			AES.MODE_CBC,
			IV=iv)
		crypttext = algo.encrypt(s)
		c = (iv + crypttext).encode('hex')
		return c

	@staticmethod
	def decode(string):
		crypttext = string.decode('hex')
		if len(crypttext) < 16:
			return None
		iv, crypttext = crypttext[:16], crypttext[16:]
		algo = AES.new(Storage.aes_key,
			AES.MODE_CBC,
			IV=iv)
		plaintext = str(algo.decrypt(crypttext))
		pad = ord(plaintext[-1])
		if pad > CookieCutter.KEY_SIZE:
			raise ValueError, "pad error - pad is %d" % (pad)

		expected = chr(pad) * pad
		piece = plaintext[-pad:]

		if piece != expected:
			raise ValueError, "padding is corrupted"

		try:
			obj = json.loads(plaintext[:-pad])
		except:
			return None

		return obj

Solution

概要より,"Signup"からログインしなくてもadminのCookieを特定してセットすることでセッションハイジャックが成立し,adminとしてログインできることが推測できる.つまり,objが{ "username":"admin" }と復号されるようなCookieを作成すればよい.ここで,ブロック暗号におけるCBCモードの復号処理は以下のようになっている.
f:id:sonickun:20160506225403p:plain
暗号利用モード - Wikipedia

図からわかるように,CBCモードでは1ブロック目の平文にはIVの値が影響を与える.今回,IVの値を任意の値に改ざんして送信することができるため,つまりは1ブロック目の平文を自由に操作することができるとうことになる.このようなCBCモードへの攻撃については,結城浩先生の『暗号技術入門 秘密の国のアリス』でも言及されている.

今,ユーザー名にadminを指定してログイン出来ないため,`dminとしてログインしてみると,以下のUIDの値を得る.

UID=e3c9e5d160562dd4fb7d8944f46b67429b23b5aeb301ff166d780197c1b84b0eabe6c79a622fe09b95533a0b5a3d3684

これをブロックごとに分割すると以下のようになる

e3c9e5d160562dd4fb7d8944f46b6742 <- IV
9b23b5aeb301ff166d780197c1b84b0e <- encrypt('{ "username":"`d')
abe6c79a622fe09b95533a0b5a3d3684 <- enctypt('min" }' + padding)

これを見ると,1つ目の平文ブロックの後ろから2byte目は`となっており,復号の直前にIVの後ろから2byte目の値(0x67)とXORされることがわかる.`はASCIIコードで言えばaのひとつ前の文字であり,1bitの差がある.つまり,IVの後ろから2byte目を1bit反転して0x66にすると,`として復号されるはずのものがaとして復号され,{ "username":"admin" }という形になる.

したがって,adminとしてログインしたい時のUIDの値は次のようになる.

UID=e3c9e5d160562dd4fb7d8944f46b66429b23b5aeb301ff166d780197c1b84b0eabe6c79a622fe09b95533a0b5a3d3684

これをCookieにセットしてサイトにアクセスするとadminとしてログインでき,Flagが得られる.
f:id:sonickun:20160506230538p:plain

Flag: CTF{lettuce.3njoy.our.f00d.puns}


Wolf Spider [Crypto 125pt]

Task

Continuing on from Eucalypt Forest - can you break Message Authentication in Wolf Spider

Overview

この問題はEucalypt Forestと姉妹問題であり,Eucalypt Forestをよりセキュアにしたブログとなっている.具体的には,以下の実装により改ざん検知用のハッシュ値を付加されており,前問のようにobjの値の一部を書き換える,といったことが不可能になっている.

@staticmethod
def make(dct):
	tcd = urllib.urlencode(dct)

	# Use RFC1321 to hash our data, so it can't be tampered with.
	h = SHA.new()
	h.update(Storage.mac_key)
	h.update(tcd)
	s = h.digest()

	coded = CookieCutter.encode(tcd)

	return s.encode('hex') + "." + coded.encode('hex')

@staticmethod
def unmake(st):
	pieces = st.split(".")
	if len(pieces) != 2:
		return None

	s = CookieCutter.decode(pieces[1].decode('hex'))
	if s == None:
		return None

	h = SHA.new()
	h.update(Storage.mac_key)
	h.update(s)
	f = h.hexdigest()

	if pieces[0] != f:
		# print "hash comparasion failed :("
		return None

	kv = urlparse.parse_qsl(s)
	ret = {}
	for k, v in kv:
		ret[k] = v
	return ret

ソースコードより,UIDの値は以下のように決定する.

UID = Hash(key + tcd) + '.' + IV + Encrypt(tcd + padding)

URL enocodeにより,例えばユーザー名がhogeのとき,tcdの値はusername=hogeとなる.

Solution

まず,改ざん検知のためのハッシュ関数ではRFC1321が採用されているが,これにはLength-Extension Attack(伸長攻撃)脆弱性がある.Length-Extension Attackとは,ハッシュ関数Hについて,H(secret+x)のxとyが既知であるとき、secretの逆算はできなくても、H(secret+x+z)が求めることができる,といった攻撃手法である.ハッシュ関数が入力を先頭から処理していくので、yからsecret+xの処理が終わった状態を求め、その状態からzの計算をすれば良い。

今回の問題では,Hash(key + tcd)において,keyの値を知ることができないが,Hash(key + tcd + x)ハッシュ値を作ることができる.このことを利用してどんなことができるだろうか.ここで,tcdをusername=hoge,xを&username=adminとすることを考えてみる.Length-Extension AttackのツールとしてHashPumpを使い,ハッシュ値を算出してみる.

単純にhogeとしてログインした時のハッシュ値d16edda3f35fbb1cac1f9381ff1c263e60143511だったので,コマンドは以下のようなる.

# hashpump -s d16edda3f35fbb1cac1f9381ff1c263e60143511 -d 'username=hoge' -a '&username=admin' -k 32
b78ca576701807fc18e64db090aa4f6939232416
username=hoge\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01h&username=admin

Length-Extension Attackの結果,

Hash(key + "username=hoge\x80\x00\x00....\x01&username=admin") = b78ca576701807fc18e64db090aa4f6939232416

を得ることができた.

URLパラメータは同じ変数名が&で続いた場合,後ろの値に上書きされる(usernameの値はadminになる).つまり,username=hoge\x80\x00\x00....\x01&username=adminの暗号文がわかりさえすれば,adminのUIDを作ることができる.ただし,"Signup"から入力した値はURL Encodeによって&=などの特殊文字がエスケープされてしまうため,この暗号文を作るのは一筋縄ではいかない.

ここで用いるのが,Padding oracle attackである.Padding oracle attackは,ブロック暗号のPadding部分にPadding長の情報が埋め込まれることを利用し,任意のブロックの情報をブルートフォースで1byteずつ特定していく手法である.ちなみに,SSL v3.0の重大な脆弱性である"POODLE"も,このPadding oracle attackを利用したものである.

今回の問題においても,上記の暗号化・復号処理のプログラムを見ると,Padding oracle attackの脆弱性があることが分かる.Padding oracle attackは主に暗号化前の平文ブロックを特定するために使われるが,今回はこの攻撃を暗号ブロックを特定するために使用する.

特定したい暗号ブロックの,元の平文ブロックは以下のとおりである.

P1: 'username=hoge\x80\x00\x00'
P2: '\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01h'
P3: '&username=admin'

また,P1~3に対応する暗号ブロックをそれぞれC1~3と呼ぶことにする.IVおよびC1~3が特定できれば,先ほどLength-Extension Attackで求めたハッシュ値と合わせてadminのUIDを作ることができる.

まず,C2,C3を特定する(ここではまだPadding oracle attackは使わない).
平文P'(16byte)を暗号化したとき,IV'+C1'+C2'を得たとする(C2'はPaddingの分).ちなみにP'の値は何でもいい(16byteに収まるように "username=aaaaaaa" とでもしておけばよい).このとき,暗号ブロックC1'をC3として利用することを考える.

ここで,C2 = IV' ^ P' ^ P3と定めると,C1'がP3として復号される.なお,記号^排他的論理和を表す.
f:id:sonickun:20160507130540p:plain

ここまででC2とC3の値が決定した.次にC1を決定したいのだが,C2の復号器にかけた直後の値(これをR2とする)がわからない.このR2を特定するために使うのがPadding oracle attackである.
f:id:sonickun:20160507015054p:plain

Padding oracle attackのために,さきほどのIV'+C1'+C2'を使い回す(Validであればusernameはなんでもいい).これらの暗号ブロックに2つの攻撃ブロックを付加してサーバに送信する.一つはブルートフォース用のブロック(mid),もう一つがC2である.midの最下位バイトを0x01~0xffまでブルートフォースしていくと,1度だけHTTP Status Codeが200で返ってくる時がある(それ以外は500).これは,復号の結果Paddingが0x01になり,サーバに受理されたことを示す.仮にmidの最下位バイトが0x12のとき,R2の最下位バイトは0x12 ^ 0x01 = 0x13と計算できる.
f:id:sonickun:20160507021053p:plain
このようにして,R2の他のバイトも特定していく(例えばPadding長が2byteのとき,Paddingは\x02\x02となり,R2の後ろから2byte目を特定できる).

これにより無事R2を特定することができた.あとはC2を特定した時とおなじ要領でC1を特定する.また,もう一度同じようにPadding oracle attackを適用するとR1の値がわかり,IVの値も特定できる.以上で必要なブロックをすべて揃えることができた.ここまでの手順をまとめると以下のようになる.

  1. C3 = C1'
  2. C2 = IV' ^ P' ^ P3
  3. R2 = Decrypt(C2)
  4. C1 = R2 ^ P2
  5. R1 = Decrypt(C1)
  6. IV = R1 ^ P1

Decrypt()はPadding Oracle Attackにより実行可能

あとはこれらをくっつけてUIDにすればadminのCookieの出来上がりである.

Solver

Result
UID: b78ca576701807fc18e64db090aa4f6939232416.dc3cd1cc0697b720cd117bb4f59b7b71ccb94738c7f771ba5af213666f00f9a21c3c2097b3a786e80eb9c56aba7d4b9f03e5b64f4174f1752ab93ac24a78257f

このUIDをCookieにセットしアクセスするとセッションハイジャックが成功し,adminとしてログインできる.
f:id:sonickun:20160507134931p:plain

Flag: CTF{++How+do+you+fix+a+cracked+pumpkin+++With+a+pumpkin+patch++}