BSD界隈四方山話

第12回 擬似乱数アルゴリズム,YarrowからFortunaへ

この記事を読むのに必要な時間:およそ 1 分

擬似乱数アルゴリズム,YarrowからFortunaへ

2015年6月末に実施されたコミットで,FreeBSD 11-CURRENTのカーネルデフォルトのエントロピー処理アルゴリズムがYarrowからFortuna(フォーチュナ,フォルトゥナ)に変更されました。RANDOM_YARROWとRANDOM_DUMMYというカーネルオプションが追加されていまして,希望するのであれば従来のYarrowを使い続けることも,ブロックするだけのドライバに置き換えることもできます。しかし,基本的にこの新しい実装をそのまま使えばよいと思います。

FreeBSDは暗号論的擬似乱数生成器の実装系にYarrowアルゴリズムを採用してきました。Yarrowアルゴリズムは特許による規制がかけられておらず,自由に利用できる状態で提供されています。FreeBSDに限らずOpenBSDやMac OS XでもYarrowアルゴリズムが使われてきました。安全に利用できる擬似乱数生成器として広く使われています。

FortunaはYarrowの後継となるアルゴリズムです。Yarrowと同じく特許による規制がなく,コピーライトフリーで,自由に利用できる状態で提供されています。FreeBSDのYarrow実装や/dev/randomの実装は改善の余地があることは2013年ごろには活発に議論されるようになりました。当時のタイムスケジュールでは10.0-RELEASEに間に合わせることは困難だろうとし,11.0-RELEASEを目処に取り込まれることになりました。

リビジョン284959でがつっと入れ替え

2015年6月30日(協定世界時)にコミットされた284959でこのあたりのコードががつっと置き換わりました。注目される変更内容をいくつかピックアップすると次のとおりです。

  • random(4)コードの大幅なクリーンナップ
  • カーネルオプションRANDOM_YARROWおよびRANDOM_DUMMYの導入
  • プリリードおよびポストリードオーバーローディング問題の修正
  • いくつかのsysctl値をチューニング可能に変更
  • 要求に応じて(ダイレクト,キュー,高速性)処理できるようにハーベストのスタイルを複数追加
  • FFS atimeイベントのハーベスト機能を追加
  • スラブアロケータイベントのハーベスト機能の追加

2015年6月30日以降も随時開発の成果物が取り込まれています。しばらくはこのあたりの開発が続くことになると思います。

擬似乱数生成器の難しさ

擬似乱数生成器はセキュリティにおいて最も重要なものです。あらゆる状況で推測されない数が出力されることが求められます。この部分が推測可能だと内部の動作が推測されてしまいますので,まずここが安全な必要があるわけです。

Yarrowはよく知られたアルゴリズムです。FortunaはYarrowの後継となるもので,今後は基本的にさまざまな実装がYarrowからFortunaに置き換わっていくのだと思います。実装する側にはアルゴリズムをよく知ったうえで,さらに間違いが発生しないように実装する必要があります。実装も論理もどちらもエキスパートたるというのは難しいことです。擬似乱数実装をぽんぽん変えられないのにはそういった理由があります。

たとえば2015年2月にはJohn-Mark Gurney氏からURGENT: RNG broken for last 4 monthsにおいて,当時の実装に問題があるのではないかという指摘も出ています。数日後にはNaked SecurityにおいてFreeBSD and the YARNBUG - more trouble at the Random Number Millが掲載されました(自分はこのあたりは詳しくないので公開されている以上のことはわからないのですが……)⁠

このあたりの情報は今後も随時出てくると思いますので,なにか発表があり次第,BSD界隈四方山話でも取り上げていこうと思います。

コメント

コメントの記入