6.1. Some Bad Ideas (悪いアイデア)
6.1. Some Bad Ideas (悪いアイデア)
以下のサブセクションでは, 合理的に見えるかもしれませんが, 安全でない擬似乱数生成につながる多くのアイデアを説明します。
6.1.1. The Fallacy of Complex Manipulation (複雑な操作の誤謬)
予測不可能性の誤解を招く外観を与える可能性のある 1 つのアプローチは, 非常に複雑なアルゴリズム (または優れた統計特性を持つ優れた従来の擬似乱数生成器) を取り, シードとしてコンピュータシステムクロック値などの限られたデータから開始して暗号鍵を計算することです。生成器がいつ開始されたかをおおよそ知っている敵は, システムクロックの可能性のある値を知っているため, テストする比較的少数のシード値を持つことになります。多数の擬似ランダムビットを生成できますが, 敵が検索する必要がある検索空間は非常に小さい可能性があります。
したがって, 開始シード値に十分なエントロピーがなく, 敵が操作を学習できる場合, 非常に強力または複雑なデータ操作は役に立ちません。彼らは通常, 限られた数のシード値から生じる限られた数の結果を使用してセキュリティを打ち負かすことができます。
もう 1 つの深刻な戦略的誤りは, アルゴリズムの背後に理論や分析がない場合に, 非常に複雑な擬似乱数生成アルゴリズムが強力な乱数を生成すると仮定することです。[KNUTH] の第 3 章の冒頭近くにこの誤謬の優れた例があり, 著者は複雑なアルゴリズムを説明しています。アルゴリズムに対応する機械語プログラムが非常に複雑になり, コメントなしでコードを読もうとする人がプログラムが何をしているのかわからないようにすることが意図されていました。残念ながら, このアルゴリズムの実際の使用は, 1 つのケースではほぼ即座に単一の繰り返し値に収束し, 別のケースでは値の小さなサイクルに収束することを示しました。
複雑な操作は, シードの範囲が限られている場合には役に立たないだけでなく, 無闇に選択された複雑な操作は, 良好なシードのエントロピーを破壊する可能性があります!
6.1.2. The Fallacy of Selection from a Large Database (大規模データベースからの選択の誤謬)
予測不可能性の誤解を招く外観を与える可能性のあるもう 1 つのアプローチは, データベースからランダムに量を選択し, その強度がデータベース内のビットの総数に関連していると仮定することです。たとえば, 典型的な USENET サーバーは 1 日あたり多くのメガバイトの情報を処理します [USENET_1, USENET_2]。このデータのランダムな開始点から 32 バイトのデータをフェッチすることによってランダムな量が選択されたと仮定します。これは 328 = 256 ビット分の推測不可能性を生成しません。データの多くが, バイトあたり 2 または 3 ビット以下の情報を含む人間の言語である場合でも, 322 = 64 ビットの推測不可能性を生成しません。同じ Usenet データベースにアクセスできる敵にとって, 推測不可能性は選択の開始点にのみ依存します。それはおそらく 24 ビットを少し超える程度の推測不可能性です。
同じ議論は, 公開されている CD/DVD 記録のデータまたは他の大規模な公開データベースからシーケンスを選択することに適用されます。敵が同じデータベースにアクセスできる場合, この "大量のデータからの選択" ステップはほとんど役に立ちません。ただし, 敵がアクセスできないデータから選択できる場合, たとえばアクティブなマルチユーザーシステム上のシステムバッファなど, それは役立つかもしれません。
6.1.3. Traditional Pseudo-random Sequences (従来の擬似ランダムシーケンス)
このセクションでは, 決定論的または "擬似ランダム" 数の従来のソースについて説明します。これらは通常 "シード" 量から始まり, 単純な数値または論理演算を使用して値のシーケンスを生成します。このセクションで説明されている技術はいずれも暗号使用には適していないことに注意してください。それらは一般的な情報のために提示されています。
[KNUTH] には擬似乱数に関する古典的な解説があります。彼が言及するアプリケーションは, 自然現象のシミュレーション, サンプリング, 数値解析, コンピュータプログラムのテスト, 意思決定, ゲームです。これらのいずれも, 私たちが話しているセキュリティ使用と同じ特性を持っていません。最後の 2 つでのみ, ランダムな量を見つけようとする敵がいる可能性があります。ただし, これらのケースでは, 敵は通常, 推測された値を使用する機会が 1 回しかありません。パスワードを推測したり暗号化スキームを破ろうとしたりする場合, 敵は通常, 正しい値を推測するための多くの, おそらく無制限の機会を持っています。時には敵は破られるメッセージを保存し, 繰り返し攻撃することができます。敵はコンピュータの支援も受けていると想定されます。
数の "ランダム性" をテストするために, Knuth は統計的およびスペクトルを含むさまざまな尺度を提案しています。これらのテストは, "ランダム" シーケンスの異なる部分間の自己相関またはその値の分布などをチェックします。しかし, これらのテストは, CRC 標準数学表の "ランダム" テーブルなどの定数保存されたランダムシーケンスによって満たされる可能性があります [CRC]。Knuth によって提案されたすべてのテストを満たすにもかかわらず, そのシーケンスは暗号使用には適していません。敵はすべての一般に公開された "ランダム" シーケンスのコピーを持ち, ソースを特定して将来の値を予測できると想定する必要があるためです。
典型的な擬似乱数生成技術は線形合同擬似乱数生成器です。この技術はモジュラー算術を使用し, N+1 番目の値は次のように N 番目の値から計算されます:
V = ( V * a + b )(Mod c)
N+1 N
上記の技術は, 暗号学的によく理解されている線形シフトレジスタ擬似乱数生成器と強い関係があります [SHIFT*]。そのような生成器では, ビットはレジスタへの選択された固定タップからのビットの排他的論理和 (キャリーなしの二進和) としてシフトレジスタの一端に導入されます。たとえば, 次を考えます:
+----+ +----+ +----+ +----+
| B | <-- | B | <-- | B | <-- . . . . . . <-- | B | <-+
| 0 | | 1 | | 2 | | n | |
+----+ +----+ +----+ +----+ |
| | | |
| | V +-----+
| V +----------------> | |
V +-----------------------------> | XOR |
+---------------------------------------------------> | |
+-----+
V = ( ( V * 2 ) + B XOR B ... )(Mod 2^n)
N+1 N 0 2
従来の擬似乱数生成器アルゴリズムの品質は, そのようなシーケンスの統計テストによって測定されます。上記の単純なプロセスで慎重に選択された値 a, b, c, および初期 V または慎重に選択されたシフトレジスタタップの配置は, 優れた統計を生成できます。
これらのシーケンスは, シーケンスが探索される空間の構造に直交している限り, シミュレーション (モンテカルロ実験) で適切である可能性があります。そこでさえ, 微妙なパターンが問題を引き起こす可能性があります。ただし, そのようなシーケンスは明らかにセキュリティアプリケーションでの使用には悪いです。初期状態がわかっている場合, それらは完全に予測可能です。擬似乱数生成器の形式に応じて, シーケンスの短い部分の観察からシーケンスを決定できる場合があります [SCHNEIER, STERN]。たとえば, 上記の生成器では, V(n) の知識があれば V(n+1) を決定できます。実際, これらの技術では, 擬似ランダム値の 1 ビットのみが公開されている場合でも, 短いシーケンスからシードを決定できることが示されています。
線形合同生成器が破られただけでなく, すべての多項式合同生成器を破るための技術が知られています [KRAWCZYK]。