![そんな中、こんな論文が出る
「Yevgeniy
?Dodis,
?David
?Pointcheval,
?
Sylvain
?Ruhault,
?Damien
?Vergnaud,
?
Daniel
?Wichs:
?Security
?analysis
?of
?
pseudo-?‐random
?number
?generators
?
with
?input:
?/dev/random
?is
?not
?robust.
?
ACM
?Conference
?on
?Computer
?and
?
CommunicaTons
?Security
?2013:
?
647-?‐658」（以下[DPRVW13]とする）
?
?
要約：
?
入力付き乱数生成器の理論モデルつ
くって検証してみたら、そもそもLinuxの
「/dev/random」「/dev/urandom」はどっ
ちもエントロピー推定器に問題があって
ロバストとまでは言えないっぽい。
?
俺がもっと良い実装考えたから使って
みれば良いと思うよ。
サーバーがロックする
↘
?
/dev/urandomに変更
↙
?
[DPRVW13]が発表される
?
↘
?
心ぴょんぴょんできない
↙
?
＿人人人人人人＿
＞ 突然の死 ＜
￣^Y^Y^Y^Y^￣](https://image.slidesharecdn.com/random-140712041102-phpapp02/85/-17-320.jpg)
![問題A
?:
?エントロピー推定器問題
エントロピー
源
??デタラメなビット列を出力
エントロピー
推定器
??デタラメなビット列からランダムネスな部分（エント
ロピーが高い）を切り取る
エントロピー
プール
??集めたエントロピーを蓄える
エクストラク
タ
??エントロピープールからビット列を出力
エントロ
ピーI
状態
Sn-1
状態
Sn
refresh
条件
1
問題
A
ここから攻撃可能
?
(injecTon攻撃)
そもそも、エントロピー推定
器がランダムネスを抽出で
きるという想定が崩れると、
安全性が崩壊する
[DPRVW13]によって、
?
?? LINUXのエントロピー推定器が高いとみなし
ても実際はエントロピー低い場合
?
?? LINUXのエントロピー推定器が低いとみなし
ても実際はエントロピーが高い場合
?
がそれぞれ示された。
?](https://image.slidesharecdn.com/random-140712041102-phpapp02/85/-22-320.jpg)
![ザオリク！
信じがたいことだが、今年はじめて
?
入力付き乱数生成器（/dev/randomなど）の
?
安全な使い方を理論的に議論できるようになった
Premature
?Next問題に関する理論的に健全
な運用方法が2014年3月に「How
?to
?Eat
?Your
?
Entropy
?and
?Have
?it
?Too
?-?‐
?OpAmal
?Recovery
?
Strategies
?for
?Compromised
?RNGs」 で発表さ
れた。（以下、[DSSD14]とする）
?](https://image.slidesharecdn.com/random-140712041102-phpapp02/85/-29-320.jpg)
![まとめ
?? 乱数は暗号に不可欠なのであり、その質を保つことは
急務である
?
?? 入力付き乱数生成器には問題がある
?
–? エントロピー推定器問題
?
–? Premature
?Next問題
?
?? Linuxのエントロピー推定器には問題がある
（[DPRVW13]）が、乱数を判定するという方法では対策
が本質的に困難である
?
?? Premature
?Next問題に関するロバストネスな運用法は、
[DSSD14]で理論的に示された
?
?? 理論的な攻撃を秘密裏に研究することで、サイバース
ペースを支配することが可能かも](https://image.slidesharecdn.com/random-140712041102-phpapp02/85/-31-320.jpg)
![参考論文
?? [DPRVW13]Yevgeniy
?Dodis,
?David
?Pointcheval,
?
Sylvain
?Ruhault,
?Damien
?Vergnaud,
?Daniel
?Wichs:
?
Security
?analysis
?of
?pseudo-?‐random
?number
?
generators
?with
?input:
?/dev/random
?is
?not
?
robust.
?ACM
?Conference
?on
?Computer
?and
?
CommunicaTons
?Security
?2013:
?647-?‐658
?
?? [DSSD14]
?Yevgeniy
?Dodis,
?Adi
?Shamir,
?Noah
?
Stephens-?‐Davidowitz,
?Daniel
?Wichs:
?How
?to
?Eat
?
Your
?Entropy
?and
?Have
?it
?Too
?-?‐
?OpTmal
?Recovery
?
Strategies
?for
?Compromised
?RNGs.
?IACR
?
Cryptology
?ePrint
?Archive
?2014:
?167
?(2014)
?](https://image.slidesharecdn.com/random-140712041102-phpapp02/85/-32-320.jpg)
入力付き乱数生成器
- 2. SUMMARY ?? 自己紹介 ? ?? 乱数の話 ? ?? 入力付き乱数生成器の話 ? ?? 問題A ?: ?エントロピー推定器問題 ? ?? 問題B ?: ?Premature ?Next問題 ? ?? まとめ
- 3. 自己紹介 アイダック ? Idkqh7 ? ?? 電子情報学類生命情報コース ? ?? 情報セキュリティ研究室 所属 ? バイオ版3次元プリンタを作ること （新たな方針を考え中） 野望
- 4. ? ところで
- 5. ? 乱数って何？ ?
- 6. （一様）乱数とは？(1) 数学的に厳密なことを言い始めるとキリがない ので、以下から雰囲気を感じる ? ?? それぞれの数が等しい確率で出る ? –?無作為性 ← ここが非常に胡散臭いが我慢 ? ?? 次に出てくる数が分からない ? –?独立性＝予測不可能 ? ?? 同じ出力を持つようなものを作れない ? –?再現不可能性＝周期が無限大 ?
- 7. （一様）乱数とは？(2) ?? 無作為性 ? ?? 予測不可能 ? ?? 周期が無限大 ? ホワイトノイズ ? それ白色雑音や ? ※平均、分散が与えられると正規分布になるが、 ? ボックスミュラー法を用いれば一様分布と正規分布は変換可能 ? 実際、ハードウェア乱数生成器は ? 熱雑音や量子ゆらぎなどによって ? 実現されている。
- 10. 乱数の质が悪い（イメージ）
- 11. ? 本題 ?
- 12. 入力付き乱数生成器 Linuxでお馴染みのコイツ ? ? /dev/random ? ? Linuxで乱数が欲しい時に使用 ?
- 13. 奥颈办颈より抜粋
- 14. 重大な問題発生 運用されるサーバーはエントロピー源が不足しがち ? （キーボード入力タイミングなどがエントロピー源のため） ? ↓ ? 暗号通信しまくりで/dev/random連発 ? ↓ ? サーバがロック ? ↓ ? ＿人人人人人人＿ ＞ 突然の死 ＜ ￣^Y^Y^Y^Y^￣
- 16. 差し伸ばされる救いの手 「Myths ?about ?/dev/urandom」 ? まとめると ? ?? /dev/randomはロックマンL? ? ?? /dev/urandomはロックフリーマンJ? ? ?? /dev/urandomでもそれなりの（擬似）乱数が作 れるから安心して使いな！！！ ? 鯖管J? ?
- 17. そんな中、こんな論文が出る 「Yevgeniy ?Dodis, ?David ?Pointcheval, ? Sylvain ?Ruhault, ?Damien ?Vergnaud, ? Daniel ?Wichs: ?Security ?analysis ?of ? pseudo-?‐random ?number ?generators ? with ?input: ?/dev/random ?is ?not ?robust. ? ACM ?Conference ?on ?Computer ?and ? CommunicaTons ?Security ?2013: ? 647-?‐658」（以下[DPRVW13]とする） ? ? 要約： ? 入力付き乱数生成器の理論モデルつ くって検証してみたら、そもそもLinuxの 「/dev/random」「/dev/urandom」はどっ ちもエントロピー推定器に問題があって ロバストとまでは言えないっぽい。 ? 俺がもっと良い実装考えたから使って みれば良いと思うよ。 サーバーがロックする ↘ ? /dev/urandomに変更 ↙ ? [DPRVW13]が発表される ? ↘ ? 心ぴょんぴょんできない ↙ ? ＿人人人人人人＿ ＞ 突然の死 ＜ ￣^Y^Y^Y^Y^￣
- 20. 一番シンプルな攻撃の想定 エントロピー 源 ??デタラメなビット列を出力 エントロピー 推定器 ??デタラメなビット列からランダムネスな部分（エント ロピーが高い）を切り取る エントロピー プール ??集めたエントロピーを蓄える エクストラク タ ??エントロピープールからビット列を出力 エントロ ピーI 状態 Sn-1 状態 Sn refresh 乱数 R 状態 ? Sn+1 next ? 状態Snが推測されると、 ? 生成される乱数Rは ? 予測可能 エントロピーIと状態Sn-1が分かれ ばXORをとって状態Snを求める ことができる。
- 22. 問題A ?: ?エントロピー推定器問題 エントロピー 源 ??デタラメなビット列を出力 エントロピー 推定器 ??デタラメなビット列からランダムネスな部分（エント ロピーが高い）を切り取る エントロピー プール ??集めたエントロピーを蓄える エクストラク タ ??エントロピープールからビット列を出力 エントロ ピーI 状態 Sn-1 状態 Sn refresh 条件 1 問題 A ここから攻撃可能 ? (injecTon攻撃) そもそも、エントロピー推定 器がランダムネスを抽出で きるという想定が崩れると、 安全性が崩壊する [DPRVW13]によって、 ? ?? LINUXのエントロピー推定器が高いとみなし ても実際はエントロピー低い場合 ? ?? LINUXのエントロピー推定器が低いとみなし ても実際はエントロピーが高い場合 ? がそれぞれ示された。 ?
- 23. エントロピー推定器を?x!…できる？ ?? よく勘違いしている人がいるが、乱数の判定 自体がそもそも超困難 ? –?次に出てくる数が予測できないということを、どこ までどうやって確かめれば判定できる？ ? –?Kolmogorov-?‐ChaiTn ?複雑性（確率論を用いずに乱 数を定義）を用いても、結局は停止性問題に帰結 する ? ?? 決定的なアルゴリズムで非決定的なもの（ラ ンダムネス）を判定しようとする本質的な問題 が存在する ?
- 25. 問題B ?: ?Premature ?Next問題 ?(1) エントロピー 源 ??デタラメなビット列を出力 エントロピー 推定器 ??デタラメなビット列からランダムネスな部分（エント ロピーが高い）を切り取る エントロピー プール ??集めたエントロピーを蓄える エクストラク タ ??エントロピープールからビット列を出力 エントロ ピーI 状態 Sn-1 状態 Sn refresh 乱数 R 状態 ? Sn+1 next ? 条件 1 乱数Rから次の状態Snを 推測することができる か？ エントロピーによって、状態Sn+1 は再びランダムネスを取り戻す 問題 B
- 26. 問題B ?: ?Premature ?Next問題 (2) エントロピー 源 ??デタラメなビット列を出力 エントロピー 推定器 ??デタラメなビット列からランダムネスな部分（エント ロピーが高い）を切り取る エントロピー プール ??集めたエントロピーを蓄える エクストラク タ ??エントロピープールからビット列を出力 エントロ ピーI 状態 Sn-1 状態 Sn refresh 乱数 R 状態 ? Sn+1 next ? 条件 1 問題 B エントロピーが0であれば ? 乱数Rから新しい ? 状態Snを取得可能 エントロピーによって、状態Sn+1 は再びランダムネスを取り戻す
- 27. 問題B ?: ?Premature ?Next問題 (3) エントロピー 源 ??デタラメなビット列を出力 エントロピー 推定器 ??デタラメなビット列からランダムネスな部分（エント ロピーが高い）を切り取る エントロピー プール ??集めたエントロピーを蓄える エクストラク タ ??エントロピープールからビット列を出力 エントロ ピーI 状態 Sn-1 状態 Sn refresh 乱数 R 状態 ? Sn+1 next ? 条件 1 問題 B エントロピーを0に近づけるこ とは可能か？ ?蓄えるより ? 早く…… 乱数を出力 ? させまくる！ 最終的には ? 次の状態Snを予測可能 ? （Premature ?Next攻撃） ? エクストラクタが ? 一定の値を出力 ? ＝エントロピーが０
- 29. ザオリク！ 信じがたいことだが、今年はじめて ? 入力付き乱数生成器（/dev/randomなど）の ? 安全な使い方を理論的に議論できるようになった Premature ?Next問題に関する理論的に健全 な運用方法が2014年3月に「How ?to ?Eat ?Your ? Entropy ?and ?Have ?it ?Too ?-?‐ ?OpAmal ?Recovery ? Strategies ?for ?Compromised ?RNGs」 で発表さ れた。（以下、[DSSD14]とする） ?
- 30. 安心して欲しいこと！ ? 安全性が破られる≠攻撃可能 ? ? ?? エントロピー推定器やPremature ?Nextを用いた現実的 な攻撃法はまだ存在しない（ことになっている） ? ?? しかし、1980年末に発表された差分解読法のときのよ うに、発表されてない可能性も十分ある。（1970年台 にはIBMが知っており、NSAと協議した結果、第3者に よる発表があるまで沈黙を守った）
- 31. まとめ ?? 乱数は暗号に不可欠なのであり、その質を保つことは 急務である ? ?? 入力付き乱数生成器には問題がある ? –? エントロピー推定器問題 ? –? Premature ?Next問題 ? ?? Linuxのエントロピー推定器には問題がある （[DPRVW13]）が、乱数を判定するという方法では対策 が本質的に困難である ? ?? Premature ?Next問題に関するロバストネスな運用法は、 [DSSD14]で理論的に示された ? ?? 理論的な攻撃を秘密裏に研究することで、サイバース ペースを支配することが可能かも
- 32. 参考論文 ?? [DPRVW13]Yevgeniy ?Dodis, ?David ?Pointcheval, ? Sylvain ?Ruhault, ?Damien ?Vergnaud, ?Daniel ?Wichs: ? Security ?analysis ?of ?pseudo-?‐random ?number ? generators ?with ?input: ?/dev/random ?is ?not ? robust. ?ACM ?Conference ?on ?Computer ?and ? CommunicaTons ?Security ?2013: ?647-?‐658 ? ?? [DSSD14] ?Yevgeniy ?Dodis, ?Adi ?Shamir, ?Noah ? Stephens-?‐Davidowitz, ?Daniel ?Wichs: ?How ?to ?Eat ? Your ?Entropy ?and ?Have ?it ?Too ?-?‐ ?OpTmal ?Recovery ? Strategies ?for ?Compromised ?RNGs. ?IACR ? Cryptology ?ePrint ?Archive ?2014: ?167 ?(2014) ?
- 34. Appendix:実装について ? （2014/07/12現在) ?? /dev/random(Linux) ? –? ?エントロピープールは実質的に1本 ? ?? 4096ビットのエントロピープールを1本（入力プール） ? ?? 1024ビットの内部プールが2本(出力プール) ? –? /dev/randomは入力プールのエントロピーが十分でないとき、ロックする。 ? –? /dev/urandomは入力プールのエントロピーが十分でないとき、出力プールを 再利用して擬似乱数を返す。つまり、ロックフリー。 ? ?? Yarrow-?‐160(FreeBSD/Mac ?OS ?X) ? –? ?エントロピープールは2本。ロックフリー。 ? ?? Fast ?pool ?–頻繁にリシード可?エントロピー抽出機の質は低い ? ?? Slow ?pool–頻繁にリシード不可?エントロピー抽出機の質は高い ? ?? Fortuna(Windows ?8から？) ? –? エントロピープールは32本。ロックフリー？（一応Yarrowベース） ? –? InjecTon攻撃に耐性あり ? –? Premature ?Next攻撃へ対策済み（エントロピープールのスケジューラが存在） ?