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

sonickun.log

備忘録

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

セキュリティ

我が家の情報セキュリティ関連の蔵書リスト。
(マウスオーバーで本のタイトルが見れて、クリックすると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版 秘密の国のアリス




【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++}

GoogleがTLSでの採用を提唱している共通鍵暗号方式「ChaCha」についてまとめた

セキュリティ プログラミング

ChaCha(チャチャ)という一見ふざけた名前の暗号が最近(自分の中で)話題ということで,勉強がてらに記事にしてみました.

背景

2016年4月現在,TLSの新しいバージョンとしてTLS 1.3が提案されており,ドラフトが公開されている.

TLS 1.2からの大きな変更点として,以下の2つがある.

  • ハンドシェイクの省略によるRTT(Round Trip Time)の削減
  • 危殆化した暗号の廃止

「危殆化した暗号」とは,Forward SecrecyでないCipher Suite(RSAのみを用いたもの)や,認証つき暗号でないCipher Suite(CBCモードのブロック暗号やRC4を用いたもの)のことを指す.
上記のドラフトによれば,2016年4月現在で実装必須暗号として制定されている暗号方式は以下の通りとなっている.

A TLS-compliant application SHOULD implement the following cipher
suites:

TLS_ECDHE_ECDSA_WITH_AES_256_GCM_SHA384
TLS_ECDHE_ECDSA_WITH_CHACHA20_POLY1305_SHA256
TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
TLS_ECDHE_RSA_WITH_CHACHA20_POLY1305_SHA256

共通鍵暗号は,ブロック暗号としてAES,ストリーム暗号としてChaCha20の二つのみとなっており,3DESやRC4は廃止される見込みである.
ChaChaという,実績も少なく,聞き慣れない暗号方式がTLS 1.3で提案されている理由の一つとして,Googleがこの暗号方式を推奨していることが挙げられる.

TLS1.3の他に,次世代のWeb通信規格として,HTTP/2がある.HTTP/2は元々はGoogleのSPDYを元に策定さていることもあり,GoogleTLS 1.3に対する発言力もかなり大きいものと推察できる.

ChaChaの構造

Salsa20

Salsa20は,ダニエル・バーンスタインによって開発されたストリーム暗号であり,後に同氏がSalsa20の変種としてChaChaを発表した.両者は互いに似たような構造を持つが,今回はChaChaのアルゴリズムを中心に解説する.

Chacha

ChaChaは,RFC 7538によって標準化されている.
ChaChaの暗号化と復号は,まったく同じ手順によって実現可能である.暗号化・復号の流れの全体像は以下のとおりである.

1. 定数,鍵,ブロックカウント,Nonce から64byteの入力ストリームを作る
2. 入力ストリームに対して20ラウンドの演算を行い,最終アレイを元のアレイに加えて64byteの出力ストリームを得る
3. 最後に平文と出力ストリームのXORをとり,暗号化(復号)する

初期状態

上記の手順1について,入力ストリームは以下のように定まる.

  • 定数:16byte(4 words)->{0x61707865, 0x3320646e, 0x79622d32, 0x6b206574}
  • 鍵:32byte (8 words)
  • ブロックカウント:4byte(1 word)
  • Nonce: 12byte(3 words)

ブロックカウントとは,暗号化(復号)するブロックが何番目のブロックかを示しており,1ブロック64byteなので,最大256GBのデータまで対応できる.
Nonceは1度だけ使われるワンタイムトークンを意味し,リトルインディアンで格納される.
入力ストリームの構造は以下のようになる.

cccccccc cccccccc cccccccc cccccccc
kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk
kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk
bbbbbbbb nnnnnnnn nnnnnnnn nnnnnnnn

c=constant k=key b=blockcount n=nonce

ラウンド操作

ChaChaは"ChaCha20"とも呼ばれるように,合計20ラウンドの操作を行う.
ChaChaのラウンドは"column rounds"と"diagonal rounds"という二種類のラウンドの繰り返しとなる.またそれぞれのラウンドは以下のように4つの"quarter-rounds"で構成されている.QUARTERROUNDの引数はストリームの何番目のwordかを示す.

# column rounds
QUARTERROUND ( 0, 4, 8,12)
QUARTERROUND ( 1, 5, 9,13)
QUARTERROUND ( 2, 6,10,14)
QUARTERROUND ( 3, 7,11,15)

# diagonal rounds
QUARTERROUND ( 0, 5,10,15)
QUARTERROUND ( 1, 6,11,12)
QUARTERROUND ( 2, 7, 8,13)
QUARTERROUND ( 3, 4, 9,14)

また,ラウンド関数QUARTERROUND()の演算は以下のように行う.なお,^排他的論理和<<<は左ローテート操作を示す.

QUARTERROUND(a, b, c, d):
    a += b; d ^= a; d <<<= 16;
    c += d; b ^= c; b <<<= 12;
    a += b; d ^= a; d <<<= 8;
    c += d; b ^= c; b <<<= 7;

最後に,手順3にある通り,ラウンド操作を施したストリームと入力ストリームを足しあわせて出力ストリームとし,暗号文(平文)とXORをとることで復号(暗号化)できる.


ChaChaの安全性

Salsa20およびChachaは,XOR,32-bit addition mod 2^32,32ビット長のワード16個のローテートを用いており,これにより,ソフトウェア実装におけるタイミング攻撃を回避することができる.
2013年時点では,Salsa20/12およびSalsa20/20の解読に成功した例はない.最良の攻撃法では12あるいは20ラウンド中8ラウンドまで解読されている.
ChaChaではラウンドごと,あるいはブロックごとの発散を大きくすることでSalsa20に比べパフォーマンスが向上している.ChaChaに対する攻撃も試みられたが,Salsa20よりも1ラウンド少ない結果となり失敗した.

その後の経過について調べることができなかったが,AESのように十分な安全性評価を行ったのかどうかが疑問に残る.


実装してみた

2015年に開催されたTrend Micro CTFの演習問題で出題されたChaCha暗号の問題を解いてみる.

Hi this is chacha. I'm 20 years old.
I have a question. Could you answer a question below?...haha. Just kidding.
6bd00ba222523f58de196fb471eea08d9fff95b5bbe6123dd3a8b9026ac0fa84

Key: 23AD52B15FA7EBDC4672D72289253D95DC9A4324FC369F593FDCC7733AD77617
nonce:5A5F6C13C1F12653

"Hi this is chacha."と言っていることから,これはChaChaで暗号化された文章であることがすぐに分かる.

Solver

なお,今回は暗号文が1ブロック分のデータ量しか無かったため,ブロックカウントの更新は実装していない.

Result

flag: TMCTF{Whose_garden_is_internet?}

無事,ChaCha暗号を復号できたことが分かる.

参考


2015/04/04 追記
このエントリが公開された翌日に,ChaCha20-Poly1305についてさらに詳しくまとめられた記事が出ました.
ぜひこちらも併せて読んでみると良いと思います.
d.hatena.ne.jp

BKPCTFのRSA暗号問題を解く

CTF セキュリティ

2016年3月4日に開催されたBoston Key Party CTFにチームm1z0r3として少しだけ参加した.大会からかなり日が経ってしまって今更感があるが,今回はbob's hatというRSA暗号の問題のWrite-upを書こうと思う.
f:id:sonickun:20160323130718p:plain
http://bostonkey.party/

bob's hat - Crypto 4

問題概要

Task:
bob’s hat — 4 : crypto : Alice and Bob are close together, likely because they have a lot of things in common.This is why Alice asked him a small *q*uestion, about something cooler than a wiener.

File: bkpctf_crypto_bobhat_task.zip

zipファイルを解凍すると,以下のファイルが得られる.

  • almost_almost_almost_almost_there.pub - 公開鍵
  • almost_almost_almost_almost_there.encrypted - 公開鍵で暗号化された暗号文
  • almost_almost_almost_almost_there.zip - パスワード付きzipファイル

暗号文を解読し,得られた平文がzipファイルのパスワードとなる.このzipファイルを解凍するとまた同じような構成のファイルが抽出され,暗号を繰り返し解いていくと最後にフラグが得られる.いつぞやに見かけたエクストリームCTFと似たような形式である.

Stage 1

まず,公開鍵の情報を確認する.

# openssl rsa -text -modulus -pubin < almost_almost_almost_almost_there.pub
Public-Key: (1024 bit)
Modulus:
    00:86:e9:96:01:3e:77:c4:16:99:00:0e:09:41:d4:
    80:c0:46:b2:f7:1a:4f:95:b3:50:ac:1a:4d:42:63:
    72:92:3d:8a:45:61:d9:6f:bf:b0:24:05:95:90:72:
    01:ad:32:25:cf:6e:de:d7:de:02:d9:1c:38:6f:fa:
    c2:80:b7:2d:0f:95:ca:e7:1f:42:eb:e0:d3:ed:ae:
    ac:e7:ce:a3:19:5f:a3:2c:1c:60:80:d9:0e:f8:53:
    d0:6d:d4:57:2c:92:b9:f8:31:0b:bc:0c:63:5a:5e:
    26:95:25:11:75:10:30:a6:59:08:16:55:4e:76:30:
    31:bc:bb:31:e3:f1:19:c6:5f
Exponent: 65537 (0x10001)
Modulus=86E996013E77C41699000E0941D480C046B2F71A4F95B350AC1A4D426372923D8A4561D96FBFB0240595907201AD3225CF6EDED7DE02D91C386FFAC280B72D0F95CAE71F42EBE0D3EDAEACE7CEA3195FA32C1C6080D90EF853D06DD4572C92B9F8310BBC0C635A5E26952511751030A6590816554E763031BCBB31E3F119C65F
writing RSA key
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCG6ZYBPnfEFpkADglB1IDARrL3
Gk+Vs1CsGk1CY3KSPYpFYdlvv7AkBZWQcgGtMiXPbt7X3gLZHDhv+sKAty0Plcrn
H0Lr4NPtrqznzqMZX6MsHGCA2Q74U9Bt1Fcskrn4MQu8DGNaXiaVJRF1EDCmWQgW
VU52MDG8uzHj8RnGXwIDAQAB
-----END PUBLIC KEY-----

鍵長は十分な長さがあり,ModulusやExponentの値も特に怪しい点はない.このようなケースの場合,各種素因数分解アルゴリズムを用いてModulusの素因数分解を試みると良い.
今回はFermat法によって素因数分解に成功した.

参考

Fermat法は素数同士の積からなる合成数において、二つの素数の差が小さい場合に有効なアルゴリズムである。 具体的には、合成数nの平方根周辺のある値をxとしたとき、(x-k)*(x+k) == nとなるkを小さいものから求める。

Solver


実行結果

p= 9733382803370256893136109840971590971460094779242334919432347801491641617443615856221168611138933576118196795282443503609663168324106758595642231987246769
q= 9733382803370256893136109840971590971460094779242334919432347801491641617443615856221168611138933576118196795282443503609663168324106758595642231987245583
pass: XtCgoEKksjKFWlqOSxqsEhK/+tsr1k5c

pとqの値が非常に近いことが分かる.
なお,今回rsatool.pyを使って秘密鍵を生成して復号する手法を取ろうとしたが,なぜかopensslコマンドでうまく復号できず,結局復号の処理をpythonで実装した.他にも同様の現象に陥った人もいたようなので,この原因について暗号のプロに教えを請いたいところ.


Stage 2

公開鍵の情報を確認.

# openssl rsa -text -modulus -pubin < almost_almost_almost_there.pub
Public-Key: (1024 bit)
Modulus:
    00:ab:e6:33:ce:c2:e7:ec:10:a8:51:92:79:05:a6:
    57:df:4e:10:41:60:23:c0:c3:4f:c6:4d:64:bd:8b:
    82:57:b7:bf:20:7a:dd:04:7b:0a:df:21:c5:25:b0:
    52:06:8c:70:29:5c:74:6c:3b:1b:e1:43:6f:39:ed:
    8b:f7:a8:13:e4:b8:45:ce:0c:a8:9c:a8:28:b4:57:
    63:d4:6b:18:98:c7:a2:fa:5f:8f:e7:84:28:ca:b6:
    cd:f7:0e:f8:71:db:97:1b:32:32:84:1a:1c:e2:45:
    9c:e6:50:a1:54:36:2f:80:cf:b6:41:63:c3:ca:63:
    ad:72:bc:fb:db:f0:15:4f:f7
Exponent: 65537 (0x10001)
Modulus=ABE633CEC2E7EC10A851927905A657DF4E10416023C0C34FC64D64BD8B8257B7BF207ADD047B0ADF21C525B052068C70295C746C3B1BE1436F39ED8BF7A813E4B845CE0CA89CA828B45763D46B1898C7A2FA5F8FE78428CAB6CDF70EF871DB971B3232841A1CE2459CE650A154362F80CFB64163C3CA63AD72BCFBDBF0154FF7
writing RSA key
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCr5jPOwufsEKhRknkFplffThBB
YCPAw0/GTWS9i4JXt78get0EewrfIcUlsFIGjHApXHRsOxvhQ2857Yv3qBPkuEXO
DKicqCi0V2PUaxiYx6L6X4/nhCjKts33Dvhx25cbMjKEGhziRZzmUKFUNi+Az7ZB
Y8PKY61yvPvb8BVP9wIDAQAB

こちらも鍵長,Modulus・Exponentの値ともに怪しいところはない.
ところが,今回のModulusとStage 1のModulusのGCDをとったところ,1ではない公約数が存在することが判明した.要は,鍵生成において「素数の使い回し」をしていたことになる.これによりModulusの素因数分解が可能となる.

Solver


実行結果

p= 9733382803370256893136109840971590971460094779242334919432347801491641617443615856221168611138933576118196795282443503609663168324106758595642231987246769
q= 12401828372292379853813876769631673931562555174641979554254424458038243058638417065284301266881242433017828663818811606556559256084249679274024474025282343
pass: rlSpJ6HbP+cZXaOuSPOe4pgfevGnXtLt

Stage 3

公開鍵の情報を確認する.

# openssl rsa -text -modulus -pubin < almost_almost_there.pub
Public-Key: (1040 bit)
Modulus:
    00:ba:d2:0c:f9:7e:d5:04:2d:f6:96:ce:4d:f3:e5:
    a6:78:cf:4f:b3:69:3d:3d:f1:2d:fe:9f:d3:fd:8c:
    c8:aa:b8:b9:55:33:e4:14:e3:fc:0c:37:7f:4e:e5:
    48:27:11:8b:1d:30:56:1a:3c:74:1b:ea:7c:76:89:
    97:89:b5:17:43:e0:76:09:2d:f9:eb:05:dc:97:eb:
    15:05:ce:9e:b1:2b:5a:b9:e1:0a:bf:56:f9:20:a5:
    8e:7e:00:ec:f0:59:77:e8:72:83:4d:d8:58:4c:f4:
    ac:87:cb:7d:c5:01:59:bd:96:2c:75:cb:ef:b6:c6:
    ac:3a:31:a7:4e:7d:8f:1e:4c:10:d5
Exponent: 65537 (0x10001)
Modulus=BAD20CF97ED5042DF696CE4DF3E5A678CF4FB3693D3DF12DFE9FD3FD8CC8AAB8B95533E414E3FC0C377F4EE54827118B1D30561A3C741BEA7C76899789B51743E076092DF9EB05DC97EB1505CE9EB12B5AB9E10ABF56F920A58E7E00ECF05977E872834DD8584CF4AC87CB7DC50159BD962C75CBEFB6C6AC3A31A74E7D8F1E4C10D5
writing RSA key
-----BEGIN PUBLIC KEY-----
MIGhMA0GCSqGSIb3DQEBAQUAA4GPADCBiwKBgwC60gz5ftUELfaWzk3z5aZ4z0+z
aT098S3+n9P9jMiquLlVM+QU4/wMN39O5UgnEYsdMFYaPHQb6nx2iZeJtRdD4HYJ
LfnrBdyX6xUFzp6xK1q54Qq/VvkgpY5+AOzwWXfocoNN2FhM9KyHy33FAVm9lix1
y++2xqw6MadOfY8eTBDVAgMBAAE=
-----END PUBLIC KEY-----

こちらも鍵長,Modulus・Exponentの値ともに怪しいところはない.
各種素因数分解アルゴリズムを適用したところ,片方の素数の値が非常に小さいことが判明し,Modulusを小さい素数から順に除算していくことにより素因数分解に成功した.

Solver


実行結果

p= 54311
q= 158304142767773473275973624083670689370769915077762416888835511454118432478825486829242855992134819928313346652550326171670356302948444602468194484069516892927291240140200374848857608566129161693687407393820501709299228594296583862100570595789385365606706350802643746830710894411204232176703046334374939501731
pass: hQdK+dKleMJqth/dofWyFaiWp3PW7jil

Stage 4

これが最後の問題.公開鍵の情報を確認する.

# openssl rsa -text -modulus -pubin < almost_there.pub
Public-Key: (1024 bit)
Modulus:
    00:9c:2f:65:05:89:91:20:90:6e:5a:fb:d7:55:c9:
    2f:ec:42:9f:ba:19:44:66:f0:6a:ae:48:4f:a3:3c:
    ab:a7:20:20:5e:94:ce:9b:f5:aa:52:72:24:91:6d:
    18:52:ae:07:91:5f:bc:6a:3a:52:04:58:57:e0:a1:
    22:4c:72:a3:60:c0:1c:0c:ef:38:8f:16:93:a7:46:
    d5:af:bf:31:8c:0a:bf:02:76:61:ac:ab:54:e0:29:
    0d:fa:21:c3:61:6a:49:82:10:e2:57:81:21:d7:c2:
    38:77:42:93:31:d4:28:d7:56:b9:57:eb:41:ec:ab:
    1e:aa:d8:70:18:c6:ea:34:45
Exponent:
    46:6a:16:9e:8c:14:ac:89:f3:9b:5b:03:57:ef:fc:
    3e:21:39:f9:b1:9e:28:c1:e2:99:f1:8b:54:95:2a:
    07:a9:32:ba:5c:a9:f4:b9:3b:3e:aa:5a:12:c4:85:
    69:81:ee:1a:31:a5:b4:7a:00:68:ff:08:1f:a3:c8:
    c2:c5:46:fe:aa:36:19:fd:6e:c7:dd:71:c9:a2:e7:
    5f:13:01:ec:93:5f:7a:5b:74:4a:73:df:34:d2:1c:
    47:59:2e:14:90:74:a3:cc:ef:74:9e:ce:47:5e:3b:
    6b:0c:8e:ec:ac:7c:55:29:0f:f1:48:e9:a2:9d:b8:
    48:0c:fe:2a:57:80:12:75
Modulus=9C2F6505899120906E5AFBD755C92FEC429FBA194466F06AAE484FA33CABA720205E94CE9BF5AA527224916D1852AE07915FBC6A3A52045857E0A1224C72A360C01C0CEF388F1693A746D5AFBF318C0ABF027661ACAB54E0290DFA21C3616A498210E2578121D7C23877429331D428D756B957EB41ECAB1EAAD87018C6EA3445
writing RSA key
-----BEGIN PUBLIC KEY-----
MIIBHzANBgkqhkiG9w0BAQEFAAOCAQwAMIIBBwKBgQCcL2UFiZEgkG5a+9dVyS/s
Qp+6GURm8GquSE+jPKunICBelM6b9apSciSRbRhSrgeRX7xqOlIEWFfgoSJMcqNg
wBwM7ziPFpOnRtWvvzGMCr8CdmGsq1TgKQ36IcNhakmCEOJXgSHXwjh3QpMx1CjX
VrlX60Hsqx6q2HAYxuo0RQKBgEZqFp6MFKyJ85tbA1fv/D4hOfmxnijB4pnxi1SV
KgepMrpcqfS5Oz6qWhLEhWmB7hoxpbR6AGj/CB+jyMLFRv6qNhn9bsfdccmi518T
AeyTX3pbdEpz3zTSHEdZLhSQdKPM73SezkdeO2sMjuysfFUpD/FI6aKduEgM/ipX
gBJ1
-----END PUBLIC KEY-----

これは明らかにExponentの値があやしい.通常は65537などの値が多用されるが,今回は値が大きすぎる.このような場合,Wiener's Attackが成立する可能性が高い.Exponentの値が大きいと,相対的に秘密鍵dが小さくなり,公開鍵からdを復元することができる.素数をp, q,秘密鍵をd,Modulusの値をNとしたとき,Wiener's Attackの成立条件は以下のとおりである.

 { \displaystyle
q < p < 2q,  d < \frac{1}{3}N^{1/4}
}

Wiener's Attackの詳細なアルゴリズムは以下の記事によくまとまっている.

Exponentの値を見た瞬間の弊チームslackの様子(途中バイナリアンが混じっている).
f:id:sonickun:20160323153442p:plain

Solver


実行結果

p= 10843221374140991753173625949764386011485161421520044246309105053489500519257941272796681417497061734054081478280518835582353321569961722963922828311576983
q= 10114792273660656874618568712406420344176220457790563178092222929337786916374923318745284718351487926620784106195715878875311958793629905453919697155685507
pass: /3aAP5dF2zmrPh9K6A4AqMLsIiYDk2C2

最後のzipファイルを解凍すると,FLAGという名前のファイルが抽出される.

# cat FLAG
BKPCTF{Its_not_you,_its_rsa_(that_is_broken)}

というわけで,フラグはBKPCTF{Its_not_you,_its_rsa_(that_is_broken)}

問題の考察

改めて,問題文を振り返ってみる.

Alice and Bob are close together, likely because they have a lot of things in common.This is why Alice asked him a small *q*uestion, about something cooler than a wiener.

これを分解・分析してみると.

  • "Alice and Bob are close together,": pとqの値が近い(Stage 1)
  • "likely because they have a lot of things in common.": 素数の使い回し(Stage 2)
  • "This is why Alice asked him a small *q*uestion,": 小さな素数q(Stage 3)
  • "about something cooler than a wiener": Wiener's Attack(Stage 4)

このように,問題文が解答の大きなヒントになっていたということが分かる.

Let's Encryptの証明書の更新を自動化する

セキュリティ 環境構築

前回Let's EncryptでSSL証明書を取得し、HTTPSサーバを建てた記事を書いた.

sonickun.hatenablog.com

Let's Encryptの証明書の有効期間は90日しかなく,こまめに更新しなければならない.
この更新をなんとか自動化できないかなぁと思っていたら,公式のマニュアルに「cron使うとええよ」と書いてありなるほどねとなった.

/etc/crontabに以下の行を追加する.

00 00 01 * * root /usr/local/letsencrypt/letsencrypt-auto certonly --webroot -d sonickun.xyz --webroot-path /var/www/html/ --renew-by-default --debug && service nginx reload

これにより,上記のコマンドが「毎月1日の0時0分」に実行されることになる.
コマンドの前半部分では,証明書の取得を行っている.ポイントは--renew-by-defaultというオプションで,これをつけることで例の青いUIの画面をスキップすることができる.コマンドの後半部分ではNginxをリロードしている.

これにてLet's Encryptの証明書が毎月1日に自動更新されることとなり,幸せになることができた.

cronについて参考