ヤローアルゴリズム

Yarrowアルゴリズムは、 John Kelsey、Bruce Schneier、Niels Fergusonによって考案され、1999 年に公開された暗号疑似乱数生成器(CSPRNG)のファミリーです。Yarrow アルゴリズムは明示的に特許取得されておらず、ロイヤリティフリーでオープンソースであるため、使用にライセンスは必要ありません。Ferguson と Schneier による改良設計であるFortunaは、彼らの著書Practical Cryptographyで説明されています。

YarrowはFreeBSDで使用されていましたが、現在はFortunaに置き換えられています。^[1] YarrowはiOS ^[2]やmacOSの/dev/randomデバイスにも組み込まれていましたが、Appleは2020年第1四半期からFortunaに切り替えました。^[3]

ノコギリソウという名前は、易経の占いのランダム生成プロセスでノコギリソウの植物が使用されることを暗示しています。夏王朝（紀元前 2070年頃～紀元前 1600年頃）以来、中国ではノコギリソウの茎が占いに使用されていました。占い師は50本のノコギリソウの茎を山に分け、モジュラー演算を再帰的に使用して、非均一分布 を持つ2ビットのランダム情報^[4]を生成します。

Yarrow の主な設計原則は、攻撃に対する耐性、暗号の知識を持たないプログラマーでも簡単に使用できること、既存のビルディング ブロックの再利用性です。ANSI X9.17 や RSAREF 2.0 PRNG などの以前広く使用されていた設計には、状況によっては攻撃の機会を与える抜け穴があります。それらのいくつかは、実際の攻撃を考慮して設計されていません。Yarrow は、PRNG 機能に関する知識がほとんどないシステム設計者でも簡単に統合できるようにすることも目的としています。^[5]

Yarrow の設計は、エントロピーアキュムレータ、再シードメカニズム、生成メカニズム、および再シード制御という 4 つの主要コンポーネントで構成されています。

Yarrow は、エントロピーを 2 つのプールに蓄積します。高速プールは、キーの侵害期間をできるだけ短くするためにキーの再シードを頻繁に行います。低速プールは、キーの再シードをまれに、しかし慎重に行います。これにより、エントロピーの推定値が非常に楽観的な場合でも、再シードが確実に保護されます。

再シード メカニズムは、エントロピー アキュムレータを生成メカニズムに接続します。高速プールからの再シードでは、現在のキーと、起動以降の高速プールへのすべての入力のハッシュを使用して新しいキーを生成します。低速プールからの再シードも同様に動作しますが、低速プールへのすべての入力のハッシュも使用して新しいキーを生成します。どちらの再シードでも、高速プールのエントロピー推定値はゼロにリセットされますが、最後の再シードでは低速プールの推定値もゼロに設定されます。再シード メカニズムはキーを常に更新するため、再シード前に攻撃者がプール情報のキーを知っていたとしても、再シード後は攻撃者に知られなくなります。

再シード制御コンポーネントは、望ましいものの反復推測攻撃を許してしまう可能性のある頻繁な再シードと、キーを持つ攻撃者にさらに多くの情報を漏らしてしまう不定期な再シードの間で活用されます。Yarrow は、ソースが何らかのしきい値を超えるたびに高速プールを使用して再シードし、少なくとも 2 つのソースが他の何らかのしきい値を超えるたびに低速プールを使用して再シードします。具体的なしきい値については、Yarrow-160 のセクションで説明されています。

Yarrow は、PRNG が予測不可能な状態になることを保証するために十分なエントロピーを蓄積できると想定しています。設計者は、キーが侵害された場合でも PRNG を回復する能力を維持する目的でエントロピーを蓄積します。同様の設計哲学は、RSAREF、DSA、および ANSI X9.17 PRNG でも採用されています。

Yarrow は、一方向ハッシュ関数とブロック暗号という 2 つの重要なアルゴリズムを使用します。具体的な説明とプロパティについては、以下の表を参照してください。

Yarrow-160 は、カウンター モードで3 つのキーを持つTriple DES を使用して出力を生成します。Cはnビットのカウンター値、Kはキーです。次の出力ブロックを生成するために、Yarrow はここに示す関数に従います。

Yarrow は出力ブロックの数をカウントします。これは、キーが侵害されると、侵害された出力の前の古い出力の漏洩を直ちに止めることができるためです。システム セキュリティ パラメータP _gに達すると、アルゴリズムはkビットの PRNG 出力を生成し、それを新しいキーとして使用します。Yarrow-160 では、システム セキュリティ パラメータは10に設定されており、これはP _g = 10を意味します。このパラメータは、バックトラックできる出力の数を最小限に抑えるために意図的に低く設定されています。

Yarrow-160 の再シード メカニズムでは、ハッシュ関数とブロック暗号として SHA-1 と Triple DES を使用します。詳細な手順は元の論文に記載されています。

Yarrow-160はJavaとFreeBSDで実装されています。例はMark RV Murrayによる 「FreeBSD用Yarrow PRNGの実装」^{[6]に記載されています。}

• Yarrow は既存のビルディング ブロックを再利用します。
• 以前の PRNG と比較すると、Yarrow はかなり効率的です。
• Yarrow は、暗号化の知識がないプログラマーでも、十分に安全に使用できます。Yarrow は移植可能で、正確に定義されています。インターフェイスはシンプルで明確です。これらの機能により、実装エラーの可能性がいくらか減少します。
• Yarrow は、攻撃指向の設計プロセスを使用して作成されました。
• Yarrow のエントロピー推定は非常に保守的であるため、網羅的な検索攻撃を防止できます。実際のアプリケーションでは、エントロピーの過大評価と推測可能な開始点が原因で PRNG が失敗することがよくあります。
• Yarrow の再シード プロセスは比較的計算コストが高いため、PRNG のキーを推測しようとするコストが高くなります。
• Yarrow はシード ファイルの管理を簡素化する機能を使用しているため、ファイルは継続的に更新されます。
• 暗号解読攻撃に対処するため、Yarrow は安全なブロック暗号に基づいて設計されています。生成メカニズムのセキュリティ レベルは、ブロック暗号によって異なります。
• Yarrow は、データに依存する実行パスを回避しようとします。これは、タイミング攻撃や電力分析などのサイドチャネル攻撃を防ぐために行われます。これは、内部操作に関する追加情報が保護されなくなると完全に機能しなくなる RSAREF 2.0 PRNG などの以前の PRNG と比較すると改善されています。
• Yarrow は、暗号化ハッシュ関数を使用して入力サンプルを処理し、安全な更新関数を使用してサンプルを既存のキーと組み合わせます。これにより、攻撃者が入力サンプルを簡単に操作できなくなります。RSAREF 2.0 PRNG などの PRNG には、このような選択入力攻撃に抵抗する機能がありません。
• ANSI X9.17 PRNGとは異なり、Yarrowは鍵の侵害から回復する能力を持っています。つまり、鍵が侵害された場合でも、攻撃者は将来の出力を永久に予測することはできません。これは、Yarrowの再シードメカニズムによるものです。^{[5] : 5}
• Yarrow では、エントロピー サンプル プールがキーから分離されており、エントロピー プールの内容が完全に予測できない場合にのみキーが再シードされます。この設計により、キーを持つ攻撃者が次のサンプルを推測し、次の出力を観察して結果を確認する反復推測攻撃を防止できます。

• YarrowはSHA-1に依存していますが、このハッシュはYarrowの公開以来（衝突耐性の観点から）破られており、もはや安全とは見なされていません。^[7]しかし、SHA-1の衝突を利用してYarrowのランダム性を損なう攻撃は公開されていません。
• Yarrow の出力は暗号的に導出されるため、その出力を使用するシステムのセキュリティは、生成メカニズム自体のセキュリティと同程度にしかなりません。つまり、生成メカニズムを破ることができる攻撃者は、Yarrow の出力に依存するシステムを簡単に破ることができます。この問題は、エントロピーの蓄積を増やすことでは解決できません。
• Yarrowはエントロピー推定を必要としますが、これは実装にとって非常に大きな課題です。^[8] PRNGの再シードに使用する前に、どれだけのエントロピーを収集すればよいかを確実に把握することは困難です。^{[9]この問題は、Yarrowの改良版である}Fortunaによって解決されています。Fortunaにはエントロピーを収集するための32のプールがあり、エントロピー推定器を完全に削除しました。
• Yarrow の強度はキーのサイズによって制限されます。たとえば、Yarrow-160 の有効なキー サイズは 160 ビットです。セキュリティに 256 ビットが必要な場合、Yarrow-160 ではその機能を果たすことができません。

• Yarrow アルゴリズム ページ
• 「Java での Yarrow の実装」
• 「FreeBSD での Yarrow の実装」
• 「FreeBSD 用の Yarrow PRNG の実装」