sonickun.log

備忘録

楕円曲線上の離散対数問題に対するアプローチ(Baby-step giant-stepとPollard's rho algorithm)

本稿では楕円曲線暗号の安全性の根拠とされている離散対数問題について、それを高速に解く方法をまとめる。

過去に「CTFにおける離散対数問題に対するアプローチ - sonickun.log」という記事を書いたが、この記事で言う離散対数問題(主にElGamal暗号で利用される)は、有限体上の離散対数問題と呼ばれるのに対し、今回扱うのは楕円曲線上の離散対数問題というものである。ちなみにこれまで楕円曲線上を離散対数問題を題材としたCTF問題に巡り合ったことはほとんどない(あったら教えてください)。

この楕円曲線上の離散対数問題を高速に解く手法として、Baby-step giant-stepPollard's rho algorithmを紹介し、実際に実装してみる。なお、楕円曲線の基礎知識や楕円曲線暗号アルゴリズムの説明については省略する。また、厳密な定義や証明は省き、イメージとして理解することを目指す。

楕円曲線上の離散対数問題(ECDLP: Elliptic Curve Discrete Logarithm Problem)

有限体{\displaystyle \mathbb{F}p}上の楕円曲線{\displaystyle E}において、{\displaystyle E}上のある点(ベースポイント){\displaystyle P}と整数 {\displaystyle d}から点 {\displaystyle Q = d × P}スカラー倍算)を計算するのは容易である。逆に、点 {\displaystyle P}{\displaystyle Q}から {\displaystyle Q = d × P} を満たす整数{\displaystyle d}を求めよ、という問題を楕円曲線上の離散対数問題と呼ぶ。

巡回群の位数が巨大な素数となるような楕円曲線とベースポイントを選んだ場合、この離散対数問題を解くことは非常に困難であることが知られている。その理由の一つには、スカラー倍算の結果が離散的に変化するという性質が挙げられている。

言い換えれば、楕円曲線上の点を巡っていく際に、ある点から{\displaystyle d}回たどることは簡単だが、始点と終点を与えられたときに、始点から何回たどって終点にたどり着いたかを求めることは困難である、ということである。

楕円曲線上の離散対数問題は、楕円曲線暗号の安全性の根拠とされている。ちなみに、1024ビット鍵長のRSA暗号ElGamal暗号と同等の安全性を持つためには、楕円曲線暗号では160ビットの鍵長で十分であるといわれている。そのため、暗号化・復号や署名認証用のハードウェア規模やソフトウェアの計算速度は、楕円曲線暗号のほうが数倍も優れており、たとえばICカードなど、コンパクト化・軽量化が要求される場合には、楕円曲線暗号が活用されている。

Baby-step giant-step

楕円曲線上の離散対数問題に対するBaby-step giant-stepは、過去記事で解説した、有限体上の離散対数問題に対するBaby-step giant-stepと根本的な考え方は同じである。

離散対数問題 {\displaystyle Q = dP} に対し、ベースポイント{\displaystyle P}の位数{\displaystyle n}を用いて{\displaystyle d=im+j}{\displaystyle m=\lceil\sqrt{n}\rceil}{\displaystyle 0 \leq i,j \lt m})として、以下の式を得る。

{ \displaystyle
Q = dP \\
Q = (im+j)P \\
Q - imP = jP
}

この式において、両辺が一致するように {\displaystyle i}{\displaystyle j} を総当たりし、{\displaystyle d} を求める。そうすることで、列挙法で{\displaystyle d}を求めるよりも少ない試行数で離散対数問題が解ける。

各辺の計算にはそれぞれ{\displaystyle m}回ずつのスカラー倍算を必要とするため、全体では{\displaystyle 2m}回、つまり{\displaystyle 2\sqrt{n}}回程度のスカラー倍算が必要になる。

以上をSageMathで実装したものが以下である。

def baby_step_giant_step(E, P, Q):
    m = int(E.order()^0.5 + 1)

    baby = []
    b = Q
    for j in range(m):
        baby.append(b)
        b -= P

    giant = m * P
    for i in range(1, m):
        if giant in baby:
            d = i*m + baby.index(giant)
            return d
        else:
            giant += (m * P)
    print "not found"
    return -1

p = 229
a = 1
b = 44

E = EllipticCurve(GF(p), [a, b])
P = E([5, 116])
Q = E([155, 166])

d = 176

assert Q == d * P

print d
print baby_step_giant_step(E, P, Q)

実行結果

# sage elliptic.sage
176
176

Pollard's rho algorithm

離散対数問題 {\displaystyle Q = dP} (位数は{\displaystyle n})に対し、何らかの方法で

{ \displaystyle
a_i P + b_i Q = a_j P + b_j Q
}

となる{\displaystyle a_i, b_i, a_j, b_j (a_i \not= a_j, b_i \not= b_j)}が見つかったとする。ことのき

{ \displaystyle
Q = \frac{a_j - a_i}{b_i - b_j}P
}

となり、

{ \displaystyle
 d = \frac{a_j - a_i}{b_i - b_j} \pmod{n}
}

となるので、離散対数問題の解 {\displaystyle d} を求まる。

{\displaystyle R_i = a_i P + b_i Q}としたとき、このアルゴリズムの目標は {\displaystyle R_i = R_j}となる点のペア {\displaystyle R_i}{\displaystyle R_j} を見つけることである。このような点のペアをコリジョンペアと呼ぶ。

ここでは、コリジョンペアを探索するために、楕円曲線上の点をランダムに選んでいく方法をとる。楕円曲線上の点 {\displaystyle R}をもとにランダムな点を効率的に求めるために、次のようなRandom Walk関数 {\displaystyle f} を利用する。

{ \displaystyle
\begin{eqnarray}
f(R)=\left\{ \begin{array}{ll}
R + M_0 & (x(R) \equiv 0 \pmod{4}) \\
R + M_1 & (x(R) \equiv 1 \pmod{4}) \\
R + M_2 & (x(R) \equiv 2 \pmod{4}) \\
R + M_3 & (x(R) \equiv 3 \pmod{4}) \\
\end{array} \right.
\end{eqnarray}
}

ここで {\displaystyle x(R)}は点 {\displaystyle R}{\displaystyle x}座標を表す。ただし、 {\displaystyle M_i = u_i P + v_i Q}楕円曲線上からランダムに選ばれた点である。{\displaystyle R_{i+1} = f(R_i)}として次々に楕円曲線上の点を求めていくと、確率的にコリジョンペアが見つかる。

上のRandom Walk関数の例ではランダム性を向上させるために4分割されていた(このパラメータを分割数という)が、Pollard's rho algorithmにより大規模な離散対数問題を解く際には、分割数が20程度の関数が使用される。ちなみに、Pollard's rho algorithmでランダムな点を求める方法は他にもあるらしい(Wikipedia)。

以上をSageMathで実装したものが以下である。

from random import randint

def pollards_rho(E, P, Q, div):

    n = E.order()
    R = []
    Rab = []
    a = randint(0, n)
    b = randint(0, n)
    R.append((a*P) + (b*Q))
    Rab.append([a, b])

    M = []
    Mab = []
    for i in range(div):
        a = randint(0, n)
        b = randint(0, n)
        M.append((a*P) + (b*Q))
        Mab.append([a, b])

    S = R[0]
    i = 0
    while True:
        m = int(S[0]) % div
        S = S + M[m]
        Sa = Rab[i][0] + Mab[m][0]
        Sb = Rab[i][1] + Mab[m][1]

        if S in R:
            Ra, Rb = Rab[R.index(S)]
            d = (Sa - Ra)*inverse_mod((Rb - Sb), n) % n
            return d
        else:
            R.append(S)
            Rab.append([Sa, Sb])
            i += 1

p = 229
a = 1
b = 44

E = EllipticCurve(GF(p), [a, b])
P = E([5, 116])
Q = E([155, 166])

d = 176

assert Q == d * P

print d
print pollards_rho(E, P, Q, 20)

実行結果

# sage elliptic.sage
176
176

誕生日のパラドックスによれば、コリジョンペアを見つけるには{\displaystyle \sqrt{n}}個の点を計算・保存する必要があるが、保存する点を特徴点(その点の{\displaystyle x}座標がある値{\displaystyle \theta}で割り切れる点)に限定することで、記憶すべき点の個数を{\displaystyle 1/\theta}に節約することもできる。

したがって、Pollard's rho algorithmは{\displaystyle \sqrt{n}}回のスカラー倍算を必要とするため、Baby-step giant-stepと同程度の計算時間を必要とするが、保存するべき点の数は{\displaystyle \sqrt{n}/\theta}となり、Baby-step giant-stepよりも少なくて済むというメリットがある。

なお、楕円曲線上の離散対数問題に対してはPollard's rho algorithmが最も優れていることが経験的に知られているが、さらに優れた解法が登場することは否定されていない。楕円曲線上の離散対数問題に対するほかのアプローチは、「ECDLPに対する攻撃手法のまとめ - 一般的攻撃手法 - ₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです」によくまとまっている。

【CTF】暗号の勉強を始めて1年たったのでWriteupまとめてみた

本稿は「CTF Advent Calendar 2016 - Adventar」19日目の記事です。

去年の冬あたりからCTFの暗号問題を解くようになって、Writeupがだいぶ溜まってきたので整理して公開しました(一部紛失してしまいましたが)。

「あの暗号のあの攻撃ってどうやるんだっけ」ってなったときに(自分が)見返すのに役立つと思います。

といってもほとんどソルバのスクリプトと一言Writeupだけのものなので、今後充実させていこうと思います。

github.com
f:id:sonickun:20161215003828p:plain


ちなみに去年の私の実力は「RSAアルゴリズムなら知ってる(素因数分解以外に攻撃あるの?)」、「ブロック暗号モードってなに?」ぐらいでしたが、今ではRSAの公開鍵を読めばある程度既知の脆弱性を見つけられますし、パディングオラクルを見つければすぐExploitを書けるくらいにはなりました。

まだまだ世界のトップCryptographerの足下に及びませんが、追い付け追い越せで頑張ります。

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の暗号分野では、離散対数問題を利用したアルゴリズム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
無事、平文を復号できたことがわかる。

蔵書リスト【情報セキュリティ編】

我が家の情報セキュリティ関連の蔵書リスト。
(マウスオーバーで本のタイトルが見れて、クリックするとAmazonページヘ飛びます。)

蔵書

暗号理論と楕円曲線 サイバー攻撃の足跡を分析するハニーポット観察記録 Webセキュリティ担当者のための脆弱性診断スタートガイド 上野宣が教える情報漏えいを防ぐ技術 サイバーセキュリティテスト完全ガイド ~Kali Linuxによるペネトレーションテスト~ もしも社長がセキュリティ対策を聞いてきたら サイバーセキュリティ入門: 私たちを取り巻く光と闇 (共立スマートセレクション) 実践サイバーセキュリティモニタリング 新版暗号技術入門 秘密の国のアリス Hacking: 美しき策謀 第2版 ―脆弱性攻撃の理論と実際 サイバーセキュリティプログラミング ―Pythonで学ぶハッカーの思考 ブラウザハック ハッカーの教科書 完全版 PHPサイバーテロの技法―攻撃と防御の実際 デバッガによるx86プログラム解析入門【x64対応版】 体系的に学ぶ 安全なWebアプリケーションの作り方 脆弱性が生まれる原理と対策の実践 実践ネットワークセキュリティ監査―リスク評価と危機管理 データ分析によるネットワークセキュリティ サイバー戦争論: ナショナルセキュリティの現在 データ解析におけるプライバシー保護 (機械学習プロフェッショナルシリーズ) インシデントレスポンス 第3版 実践 パケット解析 第2版 ―Wiresharkを使ったトラブルシューティング 情報処理教科書 情報セキュリティスペシャリスト 2014年版 (EXAMPRESS) ポケットスタディ 情報セキュリティスペシャリスト 第2版 (情報処理技術者試験) データマイニングによる異常検知

ほしい本

(研究室にあるものも含む)
ハッカーの学校 個人情報調査の教科書 たのしいバイナリの歩き方 Binary Hacks ―ハッカー秘伝のテクニック100選 ハッカーの学校 実践 Metasploit ―ペネトレーションテストによる脆弱性評価 アナライジング・マルウェア ―フリーツールを使った感染事案対処 (Art Of Reversing) リバースエンジニアリング ―Pythonによるバイナリ解析技法 (Art Of Reversing) リバースエンジニアリングバイブル ~コード再創造の美学~ 実践CSIRT 現場で使えるセキュリティ事故対応 セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方- 徳丸浩のWebセキュリティ教室 暗号技術入門 第3版 秘密の国のアリス OpenSSL―暗号・PKI・SSL/TLSライブラリの詳細― クラウドを支えるこれからの暗号技術




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

前回、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://そのうち