ペパ研 ランダムネス 運用技術

コンピュータとランダムネスの現状

ペパ研 ランダムネス 運用技術

ペパボ研究所客員研究員の力武健次（りきたけ・けんじ）です。この記事では、ここ10年ほど力武が研究対象の1つとしてきた、コンピュータで扱うランダムネス（乱雑さ）と物理乱数の扱い方について述べます。（文中敬称略）

コンピュータとランダムネスは相性が悪い

ランダムネス（randomness）は日本語では「乱雑さ」と訳され、一切の法則性を持たず、予測が不可能な状態のことを指します。コンピュータは基本的に人間がプログラムした通りに動き、それ以外の動作をしないことが前提となっている機械ですから、ランダムネスから最も遠い存在です。

しかし、あらゆるものが事前にプログラムされ、予定調和となっている決定的なアルゴリズム手法だけでは、現実の問題には対応できません。いくら周到に準備しても予定外や想定外のことが起こるのは不可避である以上、これらに対して可能な限り備えてプログラムを書く必要があります。そのためには、プログラムの中に予想不可能な要素を組み入れる必要があり、そのためにランダムネスを定式化かつ定量化してプログラムの中に組み込むという、本質的に矛盾した作業をしなければならなくなります。いわば必要に応じてサイコロを振れる仕組みをコンピュータの中に作っておく必要があるのです。

物理乱数によるランダムネスの定量化とエントロピー

自然現象の中には本質的にランダムネスの要素を持つものがあり、それらを観測して数値化することで、ランダムネスを定量化して、ランダムな（ランダムネスを持つ）数列を作ることができます。これらを物理乱数と呼びます。

物理乱数の作り方の一例としては、電子回路は電子の不規則な運動によって生じる熱雑音を発生するため、これを増幅して測定することで予測不能な数列を作ることができます。発振回路も熱雑音の影響を受けるため、特に周波数制御を行わない自励発振回路の出力を一定間隔で測定すれば予測不可能なビット列を得ることができます。最近のCPUやマイクロコントローラ（MCU）内部での物理乱数発生回路の多くがこの自励発振の技術を使っています。

ランダムネスの定量化の他の方法としては、半導体のダイオードに逆方向接続で一定以上の電圧をかけたときに急激に電流が不規則に流れることによって発生するなだれ降伏雑音を測定したり、放射性元素の放射性崩壊に伴い放出される電離放射線の発生時間間隔をガイガーカウンターなどで測定する方法などがあります。さらに高速なものとしては、光そのものの量子的な不確定性を利用したレーザーを使った生成装置[1]などがあります。

物理乱数は自然現象の産物であり、アルゴリズムを使って作り出すことはできません。そのため、一定時間内に得られる量には限りがあります。この乱雑さを示す量を、情報科学ではエントロピーと呼ぶことがあります（単位はビット）[2]。パスワードや暗号鍵の生成など予測不能性を重視する情報セキュリティの分野では、単位時間あたりのエントロピーをどれだけ使えるかが、性能の基準の1つとなります。

普通の環境ではエントロピーを得ることは極めて難しい

現在のコンピュータの中からランダムネスを得ることは容易ではありません。乱雑に見える動作でも一定のパターン、つまり予測可能性が見られるためです。それでもいくつかの動作にはばらつきつまりランダムネスがあるので、OSではこれらの情報を積極的に取得してエントロピー源としています。

しかし、サーバのように人間が直接触れることが想定されていない機器や、仮想マシンのように物理的な差異を吸収して管理しやすくした動作環境では、十分なエントロピー源を得ることは難しくなります。昨年力武が測定しBuilderscon 2018 Tokyoで発表した際の実験結果（スライドはこちら）では、わずか0.62ビット/秒のエントロピーしかLinuxサーバから得ることはできませんでした。同様の報告は10年前のBlack Hat USA 2009カンファレンスでの発表[3]でもなされており、ブロックデバイスのアクセス毎に1.03ビットのエントロピーしか収集できないとの推定結果が報告されています。

もちろん、キーボードやマウスが接続されている機器であれば、人間のタイピングやマウス移動の動作にまつわるタイミングや動かし方のばらつきを使うことは可能でしょう。また、物理的な円盤であるハードディスクが接続されていればそのアクセスタイムにばらつきがあるでしょうし、ネットワークパケットが到着する時間にもばらつきがあります。しかし、定期的に暗号通信用の鍵を生成するなどより多くのエントロピーが必要なアプリケーションの場合、これらのエントロピー源だけではおよそ十分とはいえません。

エントロピー不足の対処と安全なエントロピー源の問題

このエントロピー源を得ることが困難であることについての対処法として、OSの多くではこれらのエントロピー源から暗号論的強度の高い方法、つまり予測可能性はゼロではないが極めて小さい方法で数列を作り出す暗号用疑似乱数アルゴリズムを使っています。実際にプログラマが使う予測性の少ない疑似乱数デバイス/dev/urandomの出力は、この暗号用疑似乱数のアルゴリズムが生成したものです。

しかし、暗号用疑似乱数アルゴリズムを使ったとしても、毎秒1ビットに満たないエントロピー源では実用上十分というにはおよそほど遠い状態であると言わざるを得ません。また、数列の持つランダムネスが本当に予測不能であるかどうかはアルゴリズムでは検証できないことを考えると、もっと高速あるいは大量にエントロピーを得られるエントロピー源をコンピュータの中に用意することは急務といえます。

このエントロピー源の問題はすでに周知の事実であり、IntelはRDRAND命令など物理乱数発生器をCPUから直接使えるようにして対応しました。しかし、RDRAND命令の出力をそのまま信頼して使うことはバックドアなど製造者の介入が可能な脆弱性の存在の可能性を考えると適切ではないという判断がFreeBSDの開発者によってすでになされています（2013年12月のArsTechnicaの関連記事）。このような観点からも、製造過程と手法が信頼できる物理乱数発生器をコンピュータの中に持つことが今後のコンピュータのセキュリティ確保、そして各種応用分野の発展には重要だといえます。

力武がやってきたこと

力武は2009年ごろからランダムネスのコンピュータでの実現についてどのような手法があるかの実証実験に取り組んできました。この実験そのものは一般的なテーマですが、力武の目標として、現実にある問題をどうやって解いていくかについて注力するようにしています。

avrhwrng

2008年ごろからArduino Duemilanove、そして現在販売されているArduino UNOを使って、avrhwrngという物理乱数発生器の実装を作り検証しました。汎用のトランジスタを使ったなだれ降伏雑音生成の回路を使っています。物理乱数の生成速度は10kバイト/秒程度です。実装は回路図やコードも含めすべてGitHubで公開しています。Arduino UNO等を新規で入手しても1台数千円程度の部品代で作れます。

avrhwrngの実装については以下の成果発表を行っています。

飛石技術 NeuG 乱数発生器

2015年に飛石技術の物理乱数発生ソフトウェアNeuGの評価を行いました。このソフトウェアは飛石技術のハードウェアFST-01の内蔵MCUであるSTM32F103の中の熱雑音を利用して物理乱数を生成するものです。力武は汎用のSTM32F103ボードを使うための実装方法を発表しています。物理乱数の生成速度は600kビット/秒程度となっています。

Infinite noise TRNG

2014年に発表されたInfinite noise TRNGは、熱雑音をMCUに頼らずに生成でき、実装のライセンスがパブリックドメインで公開されているため、再実験が容易であり透明性の高い方法です。これを13-37.orgが製品化した製品がCrowd Supplyから2018年に入手できるようになったため、力武もLinux, FreeBSD, Windowsでの評価を行っています。これらのソフトウェアは元のライセンスに従いパブリックドメインで公開しています。13-37.orgの製品の物理乱数の生成速度は300kビット/秒となっており、価格も米ドルで35ドルと手頃に購入できます。回路図等も開示されているので、さらに高速なバージョンを作ることも不可能ではないでしょう。

関連研究: Erlang/OTPの疑似乱数に関する脆弱性の指摘と疑似乱数モジュールrandの設計

物理乱数と直接関連はしていませんが、関連研究としてErlang/OTPの疑似乱数に関する各種研究活動も行ってきました。以下に成果を列挙します。

おわりに: 物理乱数生成器の利用に伴う今後の課題

物理乱数発生器にはすでに複数の実用的な実装があり（実装の一部を示したリスト）、技術的にも成熟しているといえます。生成速度も毎秒数十〜数百kビット/秒あれば、現在の主要OSのエントロピープールを満たすには十分です。しかし、現実に物理乱数生成器を使う上では、以下の課題が残っています。

  • 各種OSにエントロピー源を供給する方法が開示されていない。LinuxやFreeBSDではシステムコールがあり外部のエントロピー源をOSの暗号用疑似乱数生成器に供給できるが、WindowsやmacOS、AndroidやiOSではこれらの方法が開示されていない。
  • 標準ハードウェアとしてはIntelのRDRAND命令等CPUに実装したものしか存在しないため、実装の多様性と透明性が担保できない。
  • ハイパーバイザを前提とした仮想化環境での各仮想マシンへのエントロピー供給の仕組みが十分開示されているとは言い難く、クラウド環境での問題になり得る。

コンピュータの中のランダムな現象をサンプリングするだけではランダムネスの問題は実用的には解決しないことが明らかになっている現在、スマートフォンからタブレット、デスクトップパソコン、そしてサーバやスーパーコンピュータに至るまで、どのように各種コンピュータの実装OSに必要なエントロピーを確保し、かつエントロピー源の多様性と透明性を確保するかを考えることは今後の重要な課題といえるかと思います。

公開後の訂正履歴

  • 2019年2月7日: 「飛石技術」の名前が間違っていたのを訂正しました。また、オライリージャパンのMake:ブログへのリンクを正しいものに訂正しました。

参考文献

[1] 内田 淳史, 光のランダム現象を応用した超高速物理乱数生成器の研究開発の最新動向, レーザー研究, 2011, 39 巻, 7 号, p. 508-514, 公開日 2015/09/03, Online ISSN 1349-6603, Print ISSN 0387-0200, https://doi.org/10.2184/lsj.39.508, https://www.jstage.jst.go.jp/article/lsj/39/7/39_508/_article/-char/ja, 抄録: The recent development of ultra-fast physical random number generators based on optical random

[2] 池田 信行, 乱数とエントロピー, 応用統計学, 1971-1972, 1 巻, 2 号, p. 61-75, 公開日 2009/06/12, Online ISSN 1883-8081, Print ISSN 0285-0370, https://doi.org/10.5023/jappstat.1.61, https://www.jstage.jst.go.jp/article/jappstat1971/1/2/1_2_61/_article/-char/ja, 抄録: 乱数に関する情報理論の立場からの最近の研究のいくつかについて紹介する.内容はすでに諸外国で論文として発表されているものを集め2,3の解説をつけたものである.1.まえがき,2.”複雑さ”,3.”複雑さ”の性質,4.乱数,5.まとめ,附記よりなっている.

[3] Alex Stamos, Andrew Becherer, and Nathan Wilcox: “Cloud Computing Security”, スライドPDF: https://www.nccgroup.trust/globalassets/resources/us/presentations/cloud-blackhat-2009-isec.pdf / ブロックデバイスから得られるエントロピーの量についてはスライドの65ページを参照。

【PR】パートナー積極採用中！

ペパボ研究所では、新しいパートナーを求めています。詳細については、当研究所のトップページをご覧ください。

書いた人

力武健次

ペパボ研究所客員研究員。2008年よりErlang/OTPユーザ。Erlang/OTPやElixirでのソフトウェア開発をOSS活動として行っている。2015年にはErlang/OTPのrand疑似乱数モジュールを共著者としてリリースした。