フォルトゥナ（PRNG）

Fortunaは、ブルース・シュナイアーとニールス・ファーガソンによって考案され、2003年に公開された暗号的に安全な疑似乱数生成器（CS-PRNG）です。ローマの偶然の女神フォルトゥナにちなんで名付けられました。FreeBSDは/dev/randomにFortunaを使用しており、/dev/urandomはFreeBSD 11以降にシンボリックリンクされています。^[1] Apple OSは2020年第1四半期からFortunaに切り替えました。^[2]

Fortuna は、安全な PRNG のファミリーです。その設計では、実装者にいくつかの選択肢が残されています。次の要素で構成されています。

• ジェネレータ自体は、一度シードされると、無限量の疑似ランダム データを生成します。
• エントロピーアキュムレータは、さまざまなソースから真にランダムなデータを収集し、十分な新しいランダム性が到着したときにそれを使用してジェネレーターを再シードします。
• シード ファイル。コンピューターが起動するとすぐに乱数の生成を開始できるように十分な状態を保存します。

ジェネレーターは、優れたブロック暗号に基づいています。Practical Cryptography では、 AES、Serpent、またはTwofish が推奨されています。基本的な考え方は、暗号をカウンター モードで実行し、増加するカウンターの連続した値を暗号化することです。

128 ビット ブロック暗号では、統計的に識別可能なランダム性からの偏差が発生します。たとえば、2 ^{64 個の}完全にランダムな 128 ビット ブロックを生成すると、平均して約 1 組の同一ブロックが生成されますが、カウンター モードの 128 ビット暗号によって生成される最初の 2 ^{128 個}には、重複するブロックはまったくありません。したがって、キーは定期的に変更されます。キーの変更なしで生成されるデータは 1 MiB (2 ^{16 個}の 128 ビット ブロック) 未満です。この本では、当時はあまり人気がなかった 256 ビット (またはそれ以上) のブロック サイズのブロック暗号には、この統計的な問題はないと指摘しています。

また、データ要求 (どんなに小さなものでも) のたびにキーが変更されるため、将来のキー侵害によって以前のジェネレーターの出力が危険にさらされることはありません。この特性は、「高速キー消去」または「前方秘匿性」と呼ばれることもあります。

エントロピー アキュムレータは、高度な (そして必然的に信頼性の低い) エントロピー推定器を必要とせずに、「インジェクション」攻撃に耐性を持つように設計されています。エントロピーには複数の「プール」があり、各エントロピー ソースは、その主張するエントロピーをプールに均等に分配します。そして (ここが重要な考え方です) 、ジェネレータのn回目の再シードでは、 n が2 ^kの倍数である場合にのみプールkが使用されます。したがって、k番目のプールは 1/2 ^kの時間だけ使用されます。つまり、番号が大きいプールは、(1) 再シードにあまり頻繁に寄与しませんが、(2) 再シード間でより多くのエントロピーを収集します。再シードは、指定されたエントロピー プールをSHA-256の 2 回の反復を使用してブロック暗号のキーにハッシュすることによって実行されます。

攻撃者がシステムに流入するエントロピーのソースをすべて制御できない限り(その場合、アルゴリズムではシステムを侵害から守ることはできません)、あるkについて、k番目のプールが再シード間で十分なエントロピーを収集し、そのプールで再シードすることでセキュリティが確保されます。そして、そのプールは、問題のエントロピーの量に比例した間隔で使用されます。したがって、システムは常にインジェクション攻撃から回復し、回復にかかる時間は、どのエントロピーのソースが破損していて、どのソースが破損していないかを特定できた場合に理論上かかる時間よりも最大で一定倍長くなります。

この結論は、十分な数のプールがあることに依存します。Fortuna は 32 個のプールを使用し、再シードは 1 秒あたり最大 10 回に制限されます。プールが不足するには約 13 年かかりますが、Ferguson と Schneier は、実用上十分な長さであると考えています。より偏執的な実装者、または膨大な速度でランダム データを生成し、それに応じて頻繁に再シードする必要がある実装者は、より多くのプールを使用できます。

Fortuna は、Schneier、Kelsey、Ferguson による以前のYarrow アルゴリズムファミリとは、主にエントロピー アキュムレータの処理方法が異なります。Yarrow では、各エントロピー ソースに、実際に供給されるエントロピーを推定するメカニズムが付随する必要があり、2 つのプールのみを使用しました。また、提案された実施形態 ( Yarrow-160と呼ばれます)では、反復SHA-256ではなくSHA-1 を使用しました。

2014年にフォルトゥナの分析と改良案が発表された。^[3]

• ブルーム・ブルーム・シュブ
• 暗号生成ランダム
• 乱数ジェネレータ攻撃
• ヤローアルゴリズム

• Niels Ferguson と Bruce Schneier 著『Practical Cryptography』、2003 年に Wiley 社から出版。ISBN 0-471-22357-3。 
• John Viega、「ソフトウェアにおける実用的な乱数生成」、acsac、pp. 129、第 19 回コンピュータ セキュリティ アプリケーション カンファレンス (ACSAC '03)、2003 年

• 「ブルース・シュナイアーのウェブサイト上のFortuna」

• Ferguson, Niels ; Schneier, Bruce ; Kohno, Tadayoshi (2010)。「第 9 章: ランダム性の生成」(PDF)。暗号工学: 設計原理と実際のアプリケーション。Wiley Publishing, Inc. ISBN 978-0-470-47424-22020年7月29日時点のオリジナル（PDF）よりアーカイブ。

• 「Javascript 暗号ライブラリ」。Fortuna PRNG の Javascript 実装が含まれています。

• Cooke, Jean-Luc (2005)。「jlcooke による /dev/random の説明と改善」。LinuxカーネルにFortuna の実装を追加するパッチ。

• Litzenberger, Dwayne (2013-10-20)。「Python での Fortuna 実装、Python 暗号化ツールキットの一部」。GitHub。

• Dodis, Yevgeniy; Shamir, Adi; Stephens-Davidowitz, Noah; Wichs, Daniel (2014-03-14)。「エントロピーを食べて、それを手に入れる方法 - 侵害された RNG の最適な回復戦略」。Cryptology ePrint Archive。

• 「C++14 での Fortuna 実装」。サンプル サーバー、エントロピー ソース、およびコマンド ライン クライアントが含まれています。2015-06-01。