English

セキュリティのための乱雑性についての要件
(Randomness Requirements for Security)

このメモの位置づけ

この文書は、 インターネットの「現時点における最善の実践(ベストカレントプラクティス)」を示すものであり、 改善するために議論と示唆を求めるものです。 このメモの配布に制限はありません。

著作権表記

Copyright (C) The Internet Society (2005).

要旨

セキュリティシステムは、強い暗号アルゴリズムに基づくようになっており、 これによって、パターン解析の試みをくじきます。 しかし、これらのシステムのセキュリティは、 パスワードや暗号鍵について秘密の数を生成すること、および、 同様の数に依存しています。 秘密の数を生成するために擬似的に乱雑なプロセスを利用することによって、 擬似的なセキュリティをもたらすことができます。 洗練された攻撃者が、 秘密の数を生成した環境を再現することが容易であると気づいて、 結果として、潜在的にすべての数の空間より狭い範囲の可能性を探査することで十分にしてしまう可能性があります。

資源をもち、動機をもつ攻撃者を失敗させるような乱数の選択は、 驚くほど困難です。 本書は、このような乱数を生成するために、 エントロピーが乏しい源泉や、 従前の擬似乱数生成テクニックを使う際の多くの落とし穴を指摘します。 これは、真に乱雑なハードウェアテクニックの利用を推奨し、 「多くのシステムにある既存のハードウェアが、 この目的のために使えること」を示します。 これは、ハードウェアによる解決が不能なとき、 この問題を改善するための示唆を提供し、 「あるアプリケーションについて、そのような乱数は、 どれくらい大きい必要があるか？」の例を提示します。

目次

1. 1. 導入と概要
2. 2. 一般的な要件
3. 3. エントロピーの源泉
   1. 3.1. 要求される量
   2. 3.2. 乱数生成のために手元のハードウェアを使うことができる
      1. 3.2.1. 手元の音声／ビデオ入力を使う
      2. 3.2.2. 手元のディスクドライブを使う
   3. 3.3. リングオシレータ源泉
   4. 3.4. 時計とシリアル番号についての諸問題
   5. 3.5. 外部イベントのタイミングと値
   6. 3.6. 乱雑性の非ハードウェア源泉
4. 4. 平滑化
   1. 4.1. 平滑化するためにStream Parityを使う
   2. 4.2. 平滑化するためにTransition Mappingsを使う
   3. 4.3. 平滑化するためにFFTを使う
   4. 4.4. 平滑化するために圧縮を使う
5. 5. 撹拌
   1. 5.1. 卑近な撹拌関数
   2. 5.2. より強い撹拌関数
   3. 5.3. 撹拌のためにSボックスを使う
   4. 5.4. 撹拌関数としてのDiffie-Hellman
   5. 5.5. 乱雑なビット列を延長するために撹拌関数を使う
   6. 5.6. 撹拌関数を選択する際の他の要素
6. 6. 擬似乱数生成器
   1. 6.1. いくつかの悪いアイディア
      1. 6.1.1. 複雑な操作の誤り
      2. 6.1.2. 大規模データベースからの選択の誤り
      3. 6.1.3. 従前の擬似乱数シーケンス
   2. 6.2. 暗号技術的に強いシーケンス
      1. 6.2.1. OFBおよびCTRのシーケンス
      2. 6.2.2. Blum Blum Shubシーケンス生成器
   3. 6.3. エントロピープールテクニック
7. 7. 乱雑性生成の例および標準
   1. 7.1. 完成した乱雑性生成器
      1. 7.1.1. 米国国防総省のパスワード生成についての推奨事項
      2. 7.1.2. /dev/randomデバイス
      3. 7.1.3. Windows CryptGenRandom
   2. 7.2. エントロピーの源泉を想定する生成器
      1. 7.2.1. X9.82擬似乱数生成
      2. 7.2.2. X9.17鍵生成
      3. 7.2.3. DSS擬似乱数生成
8. 8. 要求される乱雑性の例示
   1. 8.1. パスワード生成
   2. 8.2. 極めて高いセキュリティのための暗号鍵
9. 9. 結論
10. 10. セキュリティについての考慮事項
11. 11. 謝辞
12. 補遺A： RFC 1750からの変更点
13. 参考情報

1. 導入と概観 English

ソフトウェア暗号技術は、普及するまでには、長期間かかりますが、 広く使われるようになってきています。 SSH [SSH]、IPSEC [IPSEC]、 TLS [TLS]、S/MIME [S/MIME]、 PGP [MAIL_PGP*]、 DNSSEC [DNSSEC*]、 Kerberos等のシステムは、成熟しつつあり、 ネットワーク基盤の一部となりつつあります。 比較のために紹介しますが、 本書の以前の版 [RFC1750] が1994年に発行されたとき、 IETFにおける唯一のインターネットの暗号技術的セキュリティ仕様は、 PEM(Privacy Enhanced Mail)プロトコル [MAIL_PEM*] でした。

これらのシステムは、 盗聴(snooping)および偽装(spoofing)に対する実質的な防護を提供します。 しかし、潜在的な欠陥があります。 すべての暗号技術的システムの心臓部には、 秘密(推測不可能な(すなわち、乱雑な)数)の生成があります。

このような乱数を生成するために一般に利用可能な設備の欠如(すなわち、 真に推測不能な源泉の一般的な利用可能性の欠如)は、 暗号技術的ソフトウェアの設計における開いた傷といえます。 広範なハードウェア上で動作する鍵もしくはパスワード生成手順を構築することを望むソフトウェア開発者にとって、 これは、極めて現実的な問題です。

「その要件は、 攻撃者が推測もしくは判定できる確率が非常に低いデータについてであること」に注意してください。 従前の乱雑性についての統計的なテストにのみ適合する擬似乱数データ、 あるいは、 時計のような限られた範囲の源泉に基づく擬似乱数データが使われた場合、 これは、簡単に失敗してしまう可能性があります。 しばしば、このような擬似乱数は、 とまどうほどに狭い可能性ある空間(のみ)を検索する攻撃者によって、 推測されてしまいます。

この BCP文書には、 攻撃に耐える乱数を生成するためのテクニックが記述されています。 これは、「将来のシステムがハードウェア乱数生成を含むか、あるいは、 この目的のために使うことができる既存のハードウェアへのアクセスを提供すること」を推奨します。 これは、このようなハードウェアが入手不能な場合に使う手法を示唆します。 そして、これは、サンプルアプリケーションのために要求される、 いくつかの乱雑なビットの数の見積もりを提供します。

2. 一般的な要件 English

今日、普通に出会う乱雑性の要件は、ユーザパスワードについてであり、 通常、(これは)単純な文字列です。 明らかに、推測できるパスワードは、セキュリティを提供しません。 再利用可能なパスワードについて、「ユーザが、 そのパスワードを覚えることができること」が渇望されます。 これは、「発音可能な文字列、もしくは、 おそらく通常の単語から成る文句を使うこと」を助言する可能性があります。 しかし、これは、パスワード情報のフォーマットにのみ影響を与え、 パスワードが非常に推測困難である要件には影響を与えません。

多くの他の要件が、暗号技術的な場から来ています。 暗号技術的テクニックは、 守秘性確保と本人認証を含む様々なサービスを提供するために使うことができます。 このようなサービスは、(従前より「鍵」と呼ばれる)数に基づいています。 これは、 攻撃者には知られていない推測困難なものです。

一般に、上記の例は、 望まれる可能性がある2つの異なる種類の乱数も描写します。 人間が使うことができるパスワードの場合、唯一の重要な特徴は、 「それらが推測困難であること」です。 「それらは、ASCII文字から成る可能性があるので、例えば、 各バイトの先頭ビットがゼロであること」は、重要ではありません。 他方、固定長の鍵等について、人は、通常、 真に乱雑であるように見える数(すなわち、 そのビット列が統計的な乱雑性テストに合格する数)を望みます。

場合によっては、(ワンタイムパッドによる共通鍵暗号化、もしくは、 米国のAES (Advanced Encryption Standard) [AES] のようなアルゴリズムの利用のように、 )秘匿性を確保して、かつ／あるいは、 認証と共に通信することを望む主体は、 同一の秘密鍵を知らなければなりません。 他の場合として、 共通鍵もしくは「公開鍵」暗号技術的テクニックが使われるとき、 鍵は、ペアとなります。 そのペアのひとつの鍵は、プライベートなものであり、 ひとりによって、秘密に保たなければなりません。 他方は、公開するものであり、世界中に公開することができます。 プライベート鍵をその公開鍵から判定することは、 計算量的に非現実的であり、公開鍵の知識は、 攻撃者 [ASYMMETRIC] に有用となりません。 一般的な参考文献 [SCHNEIER, FERGUSON, KAUFMAN] を参照。

乱数についての要件の頻度と量は、 暗号技術的システムごとに大きく異なります。 純粋なRSAについて、乱数は、 新しい鍵ペアが生成されるときにのみ要求されます。 それゆえ、どのような数のメッセージでも、 さらなる乱雑性を必要とすることなく署名できます。 米国NIST (National Institute of Standards and Technology)によって考案された公開鍵デジタル署名アルゴリズムは、 各署名 [DSS] について、良い乱数を要求します。 そして、 ワンタイムパッド(原理的には最強の暗号化テクニック候補)による暗号化は、 処理されるべきメッセージの総量と等量の乱雑性を要求します。 一般的な参考文献について [SCHNEIER, FERGUSON, KAUFMAN] を参照。

これらの場合の大部分において、攻撃者は、試行錯誤によって、 「秘密」鍵を見つけることを試みることができます。 これは、 その鍵が正しい鍵を一意に識別できるほど鍵がメッセージよりも十分に小さい限り可能です。 攻撃者がこれに成功する確率は、特定のアプリケーションに応じて、 許容できるように低くしなければなりません。 その攻撃者が探査しなければならない空間の大きさは、 情報理論的な意味における鍵がもつ「情報」量と相関します [SHANNON]。 これは、下記のように、異なる「秘密の値」候補の数と、 各値の確率に依拠します。：

                      -----
                      \
Bits of information =  \     - pi   * log2  ( pi )
                       /
                      /
                      -----
    

ここでは、iは、1から「秘密の値」候補の数までの変数であり、 下付のiを添えたpは、i番目の確率です。 (なぜならば、下付のiを添えたpが1より小さいく、logは負であり、 よって、各項の合計は、正となるからです。)

等確率の2ⁿ異なる値がある場合、 n bitの情報があり、攻撃者が「秘密の数」を推測するためには、 平均2の(n-1)乗回試行する必要があります。 異なる値の確率が等しくない場合、情報量が、より少なくなり、 平均的には、攻撃者に要求される推測は、より少なくなります。 特に、「可能性がないこと／可能性が低いこと」を知り得るすべての値は、 攻撃者によって無視され、攻撃者は、 より可能性の高い値域を検索する可能性があります。

例えば、128bit鍵を使う暗号技術的システムを考えてみましょう。 これらの鍵が、 8bitの種が投入される固定長の擬似乱数生成器を使って得られる場合、 攻撃者は、(一見して考えられる2の128乗の鍵を検索する必要はなく、 可能性のあるすべての種で擬似乱数生成器を動作させることによって、 )たった256の鍵を検索すればすみます。 8bitの「情報」のみが、これらの128bitの鍵中にあります。

上記の分析は、概ね正しいのですが、これは、 「攻撃者の作業量」が重視される暗号解析技術的解析について、 場合によっては誤解を招く可能性があります。 例えば、「(前段落のように)128bitの鍵を生成する擬似乱数生成器があるが、 それは、半分の時間はゼロを生成し、 残りの時間で残る2^128-1の値から無作為な選択を行う」と想定します。 上記のShannonの公式は、 「これらの鍵値のひとつの中に64bitの情報があるが、攻撃者は、 単純に値としてゼロを試すことによって、半分の乱雑性に関わらず、 使われている半分のセキュリティを破ることができる」と言います。 それゆえ、暗号技術的な目的について、 下記のように定義されるmin-entropyのような他の手段に注目することも有用です。

Min-entropy =  -log(maximum(pi))
    

ここで、iは、上記のとおりです。 この公式を使うと、我々は、 1bitの新しい仮説に基づいた(hypothetical)分散についてのminエントロピーを64bitの伝統的なShannonエントロピーとは対称的なものとして得ます。

しばしばRenyiエントロピーと呼ばれるcontinuousエントロピーのスペクトラムは、 パラメータrによって、定義・規定されています。 ここで、r = 1は、Shannonエントロピーであり、 r = infinityは、minエントロピーです。 r = zeroのとき、これは、単にlog(n)であり、ここでnは、 ゼロでない確率の数です。 Renyiエントロピーは、rの非増加関数ですので、 minエントロピーは、常に、最もconservativeなエントロピーの手段であり、 通常、暗号技術的評価に最善です [LUBY]。

従前の観点から統計的にテストされた乱雑性は、 セキュリティ用途に要求される予測困難性と同等ではありません。

例えば、(CRC Standard Mathematical Tablesからのランダムテーブルのような)広く利用可能な一定のシーケンスの利用は、 攻撃者に対して非常に弱いです。 これを学習したり、推測する攻撃者は、 容易に(過去・未来を問わず)そのシーケンス [CRC] に基づいて、 すべてのセキュリティを破ることができます。 他の例として、AESを1, 2, 3... のような連続した整数を暗号化する一定の鍵と共に使うことは、 優れた統計的乱雑性をもつが予測可能な出力を作り出します。 他方、6面のサイコロを連続して転がして、 その結果の値をASCIIにエンコードすることは、 実質的に予測困難なコンポーネントをもちながらも「統計的に貧弱な出力」を作り出します。 それゆえ、「統計的テストの合否は、『何かが予測不可能であるか否か、 あるいは、予測可能であるか否か』を表さないこと」に注意してください。

3. エントロピーの源泉 English

エントロピーの源泉は、非常に、実装依存である傾向があります。 ひとたび人が十分なエントロピーを生成したら、これは、 (6章および7章に記述したように)暗号技術的に強いとさるために要求される量の擬似的な乱雑性を作り出す種として使えます。 それは、(4章および5章に記述したように)必要に応じて撹拌・混合された後のことです。

将来、真性な、強い、 ポータブルな乱雑性を期待できるでしょうか？ おそらく、できます。 必要なのは、予測不可能な数の物理的源泉です。

熱雑音(しばしば、集積回路において、 ジョンソン・ノイズと呼ばれる)もしくは放射能崩壊、そして、 高速な自走式オシレータは、そのトリックを直接、行います [GIFFORD]。 これは、よくある量のハードウェアであり、これは、容易に、 コンピュータシステムのアーキテクチャの標準的な部分として含められる可能性があります。 大部分の音声(もしくはビデオ)入力デバイスが、利用可能です [TURBID]。 さらに、回転するディスクもしくはリングオシレータや、 安定した(クリスタル)時刻発振器類をもつ、あらゆるシステムは、 乱雑性の適切な源泉([DAVIS] および3.3節)をもちます。 必要なのは、「それにアクセスするために、 この小さな追加的ハードウェアやソフトウェアは、必要不可欠であり、 有用であること」という、コンピュータベンダーが共有している価値観です。

ANSI X9は、現在、 「エントロピーの源泉」に特化したパートを含む標準を策定中です。 [X9.82] のPart 2を参照。

3.1. 要求される量 English

「どれくらいの予測困難性が必要とされるのか？」、「(例えば、『毎秒、 何bitの乱雑性？』というように、要件を定量化することは、可能か？」

その答えは、「さほど必要ではない」となります。 AESについて、その鍵は、128bitである可能性があり、 8章中の例に示したように、 最高のセキュリティシステムでさえ、 200bit以上の強い鍵とする素材を要求する可能性は低いといえます。 一連の鍵が必要とされる場合、それらは、 6.2節において説明されるように、 強い乱雑な種(初期値)から暗号技術的に強いシーケンスを使って生成できます。 このようなテクニックが使われる場合、(起動時に、 もしくは1日に1回、生成される)数百の乱雑なビット列で十分です。 たとえ、その乱雑なビット列が毎秒1bitのように遅く生成され、そ の生成プロセスをオーバーラップさせることができない場合でも、 大部分の高セキュリティアプリケーションにおいて、 ときどき200秒位、待つ我慢ができる必要があります。

これらの数は、普通に達成可能です。 これは、コイン・トスを繰り返すことによって達成される可能性があり、 ほとんど、あらゆるハードウェアに基づくプロセスは、 はるかに早い傾向があります。

3.2. 乱数生成のために手元のハードウェアを使うことができる English

下記のように、多くのコンピュータは、 真性乱数を生成するために(注意を払って)使うことができるハードウェア部品を備えています。

3.2.1. 手元の音声／ビデオ入力を使う English

多くのコンピュータは、 マイクからの音声やカメラからのビデオ入力のような、 何らかの現実世界のアナログ源泉をデジタル化する入力を備えて製造されるようになってきています。 音源が接続されていない音声デジタイザや、 レンズにキャップがされたカメラからの「入力」は、要するに、熱雑音です。 そのシステムがすべてを検出できるだけの増幅能力をもつ場合、 このような入力は、合理的に高品質な乱雑なビット列を提供できます。 この手法は、そのハードウェア実装に極めて強く依存します。

例えば、いくつかのUNIX系システムにおいて、「/dev/audioデバイス」から、 マイクジャックに何も挿さずに入力を得たり、あるいは、 マイクが低レベルな背後のノイズのみを拾うようにして、 入力を得ることができます。 ハードウェア故障の場合、何らかのチェックをすること無しに、 これを信頼してはいけませんが、このようなデータは、要するに、 乱雑なノイズであり、これは平滑化される必要があります。

このアプローチを平準化するための圧縮(4章参照)と組み合わせると、 人は、UNIX 流のコマンドラインで、 膨大な量の中程度の品質の乱雑なデータを生成できます。：

cat /dev/audio | compress - >random-bits-file
    

この種の乱雑性の源泉の詳細な説明は、 [TURBID] にあります。

3.2.2. 手元のディスクドライブを使う English

ディスクドライブの回転速度には、 無秩序な空気の乱気流による小さく乱雑な変動があります [DAVIS, Jakobsson]。 システムに低レベルのディスクシーク時間測定器を追加することは、 この乱雑性を含む一連の測定結果を作り出します。 このようなデータは、通常、高度に相関しているので、 下記5.2節に記述されているように、 FFTのような有意な処理が必要とされます。 それにもかかわらず、10年くらい前の実験では、「このような処理について、 当時の、 より遅いコンピュータに搭載されていた遅いディスクドライブでさえ、 容易に毎分100bit以上の秀逸な乱雑なデータ を作り出せること」を示しました。 CPCの処理速度の向上は、ディスク動作スケジュールを改善したり、 ディスク・シーク頻度を向上し、 このテクニックで可能な乱雑なビットの生成を高速化させます。 本稿の執筆時点において、そして、現代のハードウェアでは、 乱雑なbit生成についてのより典型的な値(rate)は、毎秒、 10,000bit以上となります。 このテクニックは、 多くのオペレーティングシステムのライブラリに含まれる)乱数生成器中に使われています。

注：キャッシュにヒットさせるシーク時間がとても短く、 単純に無視される場合、 キャッシュメモリをディスクコントローラに入れることは、 このテクニックについて、あまり効果がありません。

3.3. リングオシレータ源泉 English

集積回路が設計されたり、あるいは、試作される場合、 自走式(free-running)リングオシレータを作るために、 奇数個の論理ゲートを、直列に接続することができます。 一定周期(例えば、 安定的な水晶発振オシレータによって決定されるもの)でリングオシレータ上の点をサンプリングすることによって、 一定量のエントロピーが取り出せます。 (これは、自走式オシレータのタイミング変動に起因します。) 互いに素な長さをもつ少数のリングオシレータからサンプリングされた値の排他的論理和をとることによって、 エントロピー値を増加することが可能です。 「たとえリングオシレータが、 どういうわけか相互に同期してロックしてしまうような場合にも、なお、 サンプリングされるビットの遷移があるように、 奇数個のリングオシレータが使われること」が、しばしば推奨されます。 もうひとつの可能性のある発信源は、雑音が多いダイオードの出力です。

このような発信源から採取されたビット列は、 ディスク回転のタイミングが平滑化されなければならない(4章参照)のと同様に、 強く平滑化されなければなりません。 特定の設計に依存して作り出されるエントロピーの量を決定するために設計検討が必要とされます。 いずれにせよ、これらは、現代の基準では、 取るに足らない量のハードウェア負担の良い発信源になれます。

一例として、IEEE 802.11i [IEEE_802.11i] は、下記の回路を提案します。 ここには、リングオシレータ間の分離や、 望まない同期化等を避けるためのクロック回路からの分離、 および大量の後処理についての設計における相当の注意が示されています。

3.4. 時計とシリアル番号についての諸問題 English

コンピュータ時計や、 同様のオペレーティングシステム／ハードウェアの値は、 それらの仕様に表現されていることより、 顕著に少ないビット数の予測困難性しか提供しません。

これまで、数多くのシステム上の時計についてテストがなされ、 「それらの振る舞いは、多様であり、想定外のものであること」 が発見されました。 一定のハードウェア上で動作するオペレーティングシステムによっては、 実際に (例えば、マイクロ秒精度の時計を)提供する可能性がありますが、 一方、「同一の」システムの異なる設定は、 常に同一の低位ビットを提供する可能性があり、 かなり低い精度で上位ビットのみカウントします。 これは、「たとえ時計の公称精度に基づいて値が変化する『必要がある』十分な時間が経過した場合でも、 連続する時刻の読み出しが同値を作り出す可能性があること」を意味します。 また、頻繁に時刻を読み出す場合でも、追加的なコードによって、 2回の読み出しの間に値が変わらない時計をチェックし、 これに1を加えることによって、 人為的な連続値を作り出すことさえ可能です！ このようなシステム時計に基づいて予測困難な数値を生成する移植可能なアプリケーションコードを設計することは、格別、挑戦に値するものです。 なぜなら、システム設計者は、 コードが実行される予定のシステム時計の特性を知っているとは限らないからです。 (イーサネットMACアドレスのような)ハードウェアシリアル番号の利用は、 人が推測するより少ないビットの固有性しか提供しない可能性もあります。 このような数は、通常、相当に構造化されており、サブフィールドは、 制限された範囲の候補値のみ、もしくは、 およその作成日や他のデータに基づいて容易に推測可能な値をもつ可能性があります。

例えば、コンピュータとイーサネットアダプタの両方を製造する会社が、 (少なくとも内部的には)自社のアダプタを使う可能性が高く、これは、 組み込まれたアドレスの範囲を顕著に制限します。

上記のような問題は、 コードが様々なコンピュータのプラットフォームやシステムに移植される予定である場合、 コードが予測困難な数を作り出すことを困難にします。

3.5. 外部イベントのタイミングと値 English

マウスの移動、打鍵、 および同様なユーザによるイベントのタイミングや内容を測定することができます。 これは、一定の資格をもつ推測困難なデータの合理的な源泉です。 マシンによっては、打鍵のような入力は、 バッファに貯められることがあります。 ユーザの打鍵間隔は、十分な多様性と予測困難性をもつ可能性がありますが、 その多様性にアクセスする容易なやり方が無い可能性があります。 別の問題は、 「タイミングの詳細をサンプリングするための標準的手法が存在しないこと」です。 このことは、このテクニックに基づく広範なマシンへの配布を意図された標準ソフトウェアの構築を困難にしています。

マウスの移動と実際の打鍵の量は、通常、 タイミングにアクセスするより簡単ですが、それらの予測困難性は、 低下する可能性があります。 なぜなら、ユーザは、反復的な入力を提供する可能性があるからです。

(ネットワークパケットの到着時刻のような)他の外部イベントも、 注意を払って使うことができます。 特に、 攻撃者によるこのようなネットワークトラフィック測定の操作の可能性と、 システム起動時における履歴の欠如が、 注意深く考慮されなければなりません。 この入力が捜査の対象となる場合、これを、 エントロピーの源泉として信頼してはなりません。

原則として、放射能検出や、 適切に備えられたコンピュータにおける温度測定のように、 ほとんどすべての外部センサを使うことができます。 しかし、各場合において、「どの程度、このデータは、 攻撃者による操作の対象となるか？」と、 「どの程度のエントロピーまで、 これは実際に提供できるのか？」について、注意深い考察が、 なされなければなりません。

上記のテクニックは、 測定される量にアクセス権限をもたない攻撃者に対して、極めて強力です。 例えば、これらのテクニックは、 人の環境にアクセス権限をもたないオフラインの攻撃者や、 事後的に人の乱雑な種を破ろうとしている攻撃者に対して強力です。 すべての場合において、 より正確に人が外部センサーのタイミングもしくは値を測定できるほど、 より速く人はビット列を生成できます。

3.6. 乱雑性の非ハードウェア源泉 English

入力エントロピーの最善の源泉は、リングオシレータ、 ディスクドライブのタイミング、 熱雑音もしくは放射性物質の崩壊のようなハードウェアに基づく乱雑な源泉です。 しかし、これらのいずれもが利用不能な場合、他の可能性があります。 これらには、システム時計、システムバッファもしくは入出力バッファ、 ユーザ／システム／ハードウェア、 ネットワークのシリアル番号／アドレス／タイミング、 およびユーザ入力が含まれます。 残念ながら、これらの源泉の各々は、一定の環境において、 非常に限られた値、もしくは、予測可能な値しか作り出せません。

上記の源泉として、 (システムの各ユーザが本質的に乱雑性の源泉である)マルチユーザシステムには、 極めて強いものがあります。 しかし、「少数ユーザのシステム」もしく「は組込みシステム」には、 (特に、起動時には、)攻撃者が同様の設定をすることが可能である可能性があります。 これは、攻撃者に対して、「当初、 網羅的探索を現実的なものとするために使われた設定と十分に相関した撹拌プロセスへの入力」を与えてしまう可能性があります。

強い撹拌関数を伴う複数の乱雑な入力の利用は、推奨され、 あらゆる特定の入力にある弱点を克服できます。 要求される「乱雑な」ユーザの打鍵のタイミングと内容は、 数百の乱雑なビット列を生成できますが、保守的な想定をする必要があります。 例えば、ひとつの合理的に保守的な想定は、「打鍵間隔時間は、 たかだか数bitの乱雑性しか提供しない。 (ただし、その間隔時間が、 その時点までの一連の間隔時間において固有であるときのみ)」でしょう。 同様の想定として、「キー・コードは、数bitの乱雑性しか提供しない。 (ただし、 そのコードがそのシーケンスにおいて固有であるときのみ)」が挙げられます。 それゆえ、以前の値と重複する間隔もしくはキー・コードは、 追加的な乱雑性を提供しないと想定されます。 これらのタイミングを打鍵された文字で撹拌した結果は、さらに、 時計の値や他の入力と組み合わされる可能性があります。

この戦略は、たとえ、その標的システムのいずれかにおいて、 その入力のいくつかが非常に弱い場合でも、 セキュリティ向きの良い乱数を作り出すための実践的な移植可能なコードを作る可能性があります。 しかし、これは、特に、 その攻撃者が過去にその生成プロセスを観察できていた場合、 なおも「小さな小人数のシステム」や「組込みシステム」における高度な攻撃に対して敗れる可能性があります。 ハードウェアに基づく乱雑な源泉は、なおも選好されます。

4. 平滑化 English

乱数を作り出すためのエントロピーのために生成された量の分散の型について、 何らかの特定の要件があるでしょうか？ よい知らせは、「その分散は、統一されている必要がないこと」です。 「『どの程度、単型から偏るか？』についての保守的な見積もり」が、 性能に影響する必要とされることのすべてです。 ビットストリームを平準化するためのシンプルなテクニックが、 後述され、より強い暗号技術的テクニックは、 5.2節に記述されます。

4.1. 平滑化するためにStream Parityを使う English

単純ではあるが特別に実践的ではない例として、 十分に長いビット列をとって、 そのビット列を「ゼロ」か「1」に対応させることを検討します。 その対応付けは、完全に一様な分布にはならないでしょうが、 近いものになる可能性があります。 この目的に合う対応付けのひとつは、その文字列のパリティをとることです。 これは、「予想されている最大の偏りの程度まで、 あらゆる程度の偏りについて強く、 「ハードウェアに実装することが普及している」という優位性をもちます。

下記の分析は、サンプリングされなければならないビット数を与えます。：

「1と0の比率は、0.5 + e : 0.5 - e」と想定します。 ここで、eは、0と0.5の間であり、分散の「乖離率」の尺度です。 N bitサンプルのパリティ関数の分散を考慮します。 そのパリティが1か0となる確率は、 2項展開式(p + q)^Nの偶数か奇数の項の和です。 ここで、1の確率は、p = 0.5 + Eであり、 0の確率は、q = 0.5 - Eです。

これらの和は、下記にように、容易に計算できます。

    1/2 * ((p + q)N + (p - q)N)

and

    1/2 * ((p + q)N - (p - q)N).
    

(この公式は、Nが偶数であるか、奇数であるかにより、一方が、 パリティが1となる確率に対応しています。)

p + q = 1 かつ p - q = 2E であるので、これらの式は、短く変形できます。

    1/2 * [1 + (2E)N]

and

    1/2 * [1 - (2E)N].
    

これらののいずれも、Eがゼロでない限り、ちょうど0.5となることは、 ありえませんが、我々は、任意に0.5に近づけることができます。 我々が、この確率を0.5からデルタ d以内にしたい場合、 下記のようになります。

(0.5 + (0.5 * (2E)N)) < 0.5 + d.
    

Nについて解くと、N > log(2d)/log(2e)となります。 (「2Eは、1未満なので、そのlogは、負値であること」に注意してください。 負の数値による剰算は、不等式の意味を逆にします。)

下表は、様々な程度の偏りについて、 50：50の比率から 0.001以内になるようにするためにサンプリング対象としなければならない文字列の長さNを示します。

最後の行は、 「たとえ分散が一方に99%偏っている場合でも、 308のサンプル文字列のパリティは、 50：50の比率から0.001以内となること」を示しています。 しかし、5.2節で説明するように、 利用可能なエントロピーの、より多くを得られる、 はるかに強いテクニックがあります。

4.2. 平滑化するためにTransition Mappingsを使う English

元々、von Neumann [VON_NEUMANN] に由来する別のテクニックには、 重複しない対のシーケンスとしてビットストリームを吟味するものあります。 そして、00または11の対が発見されたら、すべて無視し、 01を0、10を1と解釈できます。 「1の確率が0.5+e、0の確率が0.5-eであり、ここで、Eは、 源泉の乖離率であり、前節において記述したもの」と想定します。 そこで、各ペアの確率は、下表に示されます。：

このテクニックは、いかなる偏りも完全に根絶しますが、 望まれる特定の出力ビット数を得るために費やす入力ビット数は、 確定しません。 無視される個々のペアの確率は、0.5 + 2e²であるので、 X bitの出力を作り出すために期待される入力は、X/(0.25 - e²) bit です。

このテクニックは、 次のようなストリームからビットが得られるものと想定します。 つまり、 各ビットはストリーム内の他の任意のビットと同様に同じ確率で0または1となり、 ビット間に相関関係がない(つまり、 ビット列が同様の独立分布を示す)ストリームです。 例えば、代替的なビット列が2つの相関する源泉からのものである場合、 上記の分析は、破綻します。

上記のテクニックは、「どのように、単純な統計的分析は、 人が攻撃者によって攻略される可能性があるパターンを常に見張っていない場合、 誤解を招く可能性があるのか？」についての別の描写も提供します。 そのアルゴリズムが、わずかに誤解され、 重複しないビット列の対の代わりに重複する連続ビット列のペアが使われた場合、 与えられる統計的分析は、同様となります。 しかし、偏りが無く、 相関関係のない一連の乱雑な1と0ビット列を提供する代わりに、これは、 1と0が交互になってしまっている総合的には予測可能なシーケンスを作り出します。

4.3. 平滑化するためにFFTを使う English

現実世界のデータが大きく偏ったビットや相関したビットから成るときでも、 なおも、有用な量の乱雑性を含む可能性があります。 このエントロピーは、様々な変換を通じて得られます。 その中で最も強力なものが、 下記5.2節に記述されています。

データのフーリエ変換、もしくは、その最適化された流儀であるFFTの利用は、 主に論理的な理由で興味深いものです。 「このテクニックは、 強い相関関係を除去すること」が示される可能性があります。 適切なデータが処理され、かつ残存する相関性が衰える場合、 統計的独立性に近似するスペクトル曲線と、 通常の分散の乱雑性を作り出すことができます [BRILLINGER]。

4.4. 平滑化するために圧縮を使う English

可逆な圧縮テクニックも、 偏ったビット列を平準化する粗い手法を提供します。 これは、可逆圧縮の定義に直接従うとともに、 2章で示したシーケンス内の情報量の公式にも従います。 圧縮は可逆なので、長い入力の中にあった情報量が、 より短い出力の中にもあるはずです。 Shannon情報量の等式によると、これは、普通は、異なる、 より短いシーケンスの確率が、 より長いシーケンスの確率よりも均一に分布する場合にのみ成立します。 それゆえ、より短いシーケンスは、 その入力と比べて平準化されているのです。

しかし、多くの圧縮テクニックは、 何らかの予測可能な事前情報をその出力ストリームに追加し、 同様のシーケンスを再度、定期的にその出力に挿入したり、あるいは、 自身のかすかなパターンを導入する可能性があります。 それらは、5.2節に記述されているものと比べると、 大ざっぱなテクニックに過ぎないと見なされる必要があります。 最低限、圧縮されたシーケンスの先頭は、無視される必要があり、 以降のビットのみが概ね乱雑なビット列を要求するアプリケーションに使われる必要があります。

5. 撹拌 English

強く信頼できるハードウェアのエントロピー源泉が無い場合、 何が推測不能な乱数を得ることについて、最善の全体戦略でしょうか？ それは、数多くの相関しない源泉から入力を得て、 それらを強い撹拌関数で撹拌することです。 このような関数は、 たとえ組み合わされる他の数がたまたま一定あるいは容易に推測可能(低いエントロピー)である場合でも、 あらゆる源泉にあるエントロピーを確保します。 このアプローチは、ハードウェアも故障する可能性があるので、 たとえ良いハードウェア源泉を使うときでも助言できる可能性があります。 しかし、これは、 追加されたソフトウェアの複雑性に起因する失敗全体の機会における可能性ある増加に照らして重みづけられる必要があります。

ひとたび3章に列挙したもののような良い源泉を使い、 それらをこの章に記述されているように攪拌すれば、 人は、強い種を得ます。 そこで、これは、 6章と7章に記述するように、 大量の暗号技術的に強い素材を作り出すのに使えます。

強い撹拌関数は、 すべての入力ビット列の異なる複雑な非線形関数である入力を組み合わせて出力ビットを作り出す関数です。 平均的には、いずれかの入力ビットを変更することは、 その出力の約半分のビットを変化させます。 しかし、その関連性は、複雑であり、非線形であるので、 ある特定の入力ビットが変更されたときに変化することを保証されている特定の出力ビットは、 ありません。

0か1に歪ませられたビットストリームを、 あるいは(4章において検討したように)より乱雑なビットストリームを何らかの予測可能なパターンをもつように歪ませられたより短いビットストリームを変換することの問題を検討します。 これは、単純に、 入力ビットを撹拌してより少ない出力ビット列を作り出すために強い撹拌関数が渇望される別の事例です。 4.1節で述べた、 数多くのビット列のパリティを使うテクニックは、単に、 それらの排他的論理和を求めた結果です。 これは、直下の「卑近な撹拌関数」の一例です。 偏ったビット列のストリームから、より多くの乱雑性を取り出すための、 より強い撹拌関数の利用は、 5.2節において吟味されています。 [NASLUND] も参照。

5.1. 卑近な攪拌関数 English

解説の都合上、我々は、 排他的論理和(XOR)関数を使う単bit入力について、卑近な例を記述します。 この関数は、下表に示されるように、 パリティ(carry)無しの加算と同等です。 これは、退化した事例です。 ここでは、いずれかの入力ビットの変化に伴って、常に、 出力ビットが変化します。 しかし、その単純さにかかわらず、これは、有用な表を提供します。

入力1と入力2が相関せず、このように組み合わされた場合、 その出力は、入力よりも、 さらに良い(偏りが少ない)乱雑なビットとなります。 我々が"eccentricity" Eを上記4.1節に定義されているように想定する場合、 その出力は、下記のように、出力乖離率は、入力乖離率と関連します。：

Eoutput = 2 * Einput 1 * Einput 2
    

Eは、決して 1/2 より大きくならないので、 少なくとも一方が完全に定数である場合を除いて、 乖離率は、常に向上します。 これは、下表に示されています。 ここで、先頭行と左端の列の値は、2つの入力の乖離率であり、 その項目は、出力の乖離率です。：

しかし、「上記の計算は、入力は、 相関しないと想定していること」に注意してください。 例えば、数秒単位で正確な2つの時計において、 深夜零時からの分数のパリティを入力値とする場合、 1分以上の間隔で乱雑に拾えば、各々は、乱雑に見える可能性があります。 しかし、それらが同時に拾われて排他的論理和と組み合わされている場合、 その結果は、ほとんどの場合、ゼロとなります。

5.2. より強い撹拌関数 English

米国政府のAES (Advanced Encryption Standard) [AES] は、複数のbit数についての強い撹拌関数の一例です。 これは、384bitまでの入力(128bitの「データ」と256bitの「鍵」)を受け取って、 128bitの出力を作り出します。 各出力ビットは、 すべての入力ビット列に対する複雑な非線形関数の出力となります。

この特徴をもつ他の暗号化関数([DES]等)も、 (すべての鍵とデータ入力ビットを攪拌することを考慮することによって)使うことができます。

別の良い撹拌関数のファミリには、 米国政府のセキュアハッシュ標準 [SHA*] やMD4, MD5 [MD4, MD5] シリーズのような「メッセージダイジェスト」もしくはハッシュ関数があります。 これらの関数は、皆、実際に無制限の量の入力を受けて、 すべての入力ビット列を撹拌することによって、 比較的短い固定長の出力を作り出します。 MD*シリーズは、128bitの出力を作り出し、SHA-1は、 160bitの出力を作り出し、他のSHA関数は、 512bit までの出力を作り出します。

メッセージダイジェスト関数は、可変量の入力用に設計されていますが、 AESや他の暗号化関数は、任意の数の入力を組み合わせるためにも使えます。 128bitの出力が適切である場合、その入力は、必要に応じて、 0をパディングして、 128bitデータ量と連続したAES「鍵」にまとめることができます。 そして、その量は、その「鍵」によって、AESのECM (Electronic Codebook Mode)を使って連続的に暗号化するために使われます。 代わりに、その入力は、ひとつの128bit鍵にパックでき、 複数のデータブロックとCBC-MACを計算処理できます [MODES]。

128bit以上の出力が必要とされ、AESを採用することを望む場合、 より複雑な撹拌が、行われる必要があります。 (ただし、「入力された以上の『乱雑性』をもつビット列を得ることは、 まったく不可能であること」に注意。) 例えば、「入力は、3つの量(A、BおよびC)にまとめられる」と想定します。 AESを使って、まず鍵Aを鍵Bで暗号化し、さらに鍵Cで暗号化して、 出力の最初の部分を生成し、次に、Bを鍵A、 鍵Cで暗号化して次の出力を生成します。 さらに、必要不可欠である場合、鍵Cを鍵A、鍵Bで暗号化して、 より多くの出力を得る可能性があります。 より多くの出力が、上記の鍵の順序を逆にすることによって作り出せます。 同様のことが、複数の出力を作り出すために、 入力データの様々な部分群をハッシュ化することによって、 ハッシュ関数について行えます。

強い撹拌関数を使う例として、 99%のビットが0に偏っている308bitの文字列の事例を再検討します。 4.1節 に述べたパリティテクニックは、 これを0と1の確率が等しい状態からたった1/1000だけ異なる1bitに偏りを低減しました。 しかし、2章で紹介した情報についての式を適用すると、 この308bitの偏ったシーケンスは、5bit以上の情報を含みます。 それゆえ、それをSHA-1でハッシュ化し、 その結果の末尾5bitをとることによって、歪みのない5bit、かつ、 その文字列のパリティを計算することによって得られる1bitではないものが生成されます。 代わりに、何らかのアプリケーション用に、あなたは、 160bit中の5bit 以上のエントロピーの大部分を保持するために、 そのハッシュ出力全体を使うことができます。

5.3. 撹拌のためにSボックスを使う English

(DESやAESを含む)多くの現代のブロック暗号化関数は、 「Sボックス(substitution box)」として知られているモジュールをもっています。 これらは、 より多くの入力からの有限なエントロピーを結合して出力する効果を持つ複雑な非線形撹拌関数を通じて、 より少ない出力を作り出します。

「Sボックス」は、しばしば、「bent Boolean関数(同等の長さの出力ビット列を作り出し、 各ビットが最大の非線形性となる関数)」を組み込みます。 あらゆる特定のビットの位置が異なる、 すべての入力ペアについて出力に注目すると、 ちょうど半分の出力が異なります。 これらの関数のあらゆる線形な組合せがbent関数ともなるように各出力ビットをbent関数によって作り出す「Sボックス」は、 「perfect Sボックス」と呼ばれます。

「Sボックス」や、様々な繰り返し処理があるアプリケーション、 もしくは、このようなボックスの縦列は、撹拌のために使うことができます [SBOX1, SBOX2]。

5.4. 撹拌関数としてのDiffie-Hellman English

Diffie-Hellman鍵交換は、 2者間で共有された秘密を生成するテクニックです。 第三者がこの秘密を判定することは、 たとえ彼らが通信を行う2主体間のべてのメッセージを観察できる場合でも、 計算量的に非現実的である可能性があります。 この「共有された秘密」は、 各主体によって生成された初期の数の混合です。[D-H]

これらの初期量が乱雑であり、相関しない場合、その共有された秘密は、 それらのエントロピーを組み合わせますが、当然ながら、 生成された「共有された秘密」の大きさより多くの乱雑性は、 作り出せません。

これは、そのDiffie-Hellman計算処理がプライベートに行われた場合、 真ですが、その公開鍵の両方を観察でき、 使われているモジュールを知る攻撃者は、 「共有された秘密」 [D-H] を計算できるようにするために、 他方のプライベート鍵の空間を探索する必要があるのみです。 それゆえ、保守的には、 公開鍵暗号技術であるDiffie-Hellmanが2つの入力に相当する推測可能性の量を作り出すことを考慮することが最善となります。 これと、「Diffie-Hellmanは、計算量的に重い」という事実に起因して、 その撹拌関数としての利用は、推奨されません。

5.5. 乱雑なビット列を延長するために撹拌関数を使う English

撹拌関数について、その入力と同数、もしくは、 より少ないビットの出力を作り出すことは、必要不可欠ではありませんが、 撹拌ビット列は、現在、 入力中にある乱雑な予測困難性の量を「増大」できません。 それゆえ、(各入力における4,096の同等な確率の値のように)12bit相当の予測困難性をもつ各32bitの4つの入力は、 48bit以上に相当する予測不可能な出力を作り出せません。 その出力は、(例えば、 連続した整数で撹拌することによって)数百から数千bitに延長できますが、 賢い攻撃者の探査空間は、2⁴⁸分の1の確率のままです。 さらに、入力よりも少ないビット数への撹拌は、 その出力の乱雑性を強化する傾向があります。

5.1節中の最後の表は、 「乱雑なビットを固定ビットとの排他的論理和で撹拌することは、 乱雑なビットを作り出すこと」を示します。 これは、真ですが、 乱雑な1bitを複数bitのものに「延長」する方法は提供しません。 例えば、ある任意のビットが0で撹拌され、次に1で撹拌される場合、 これは、2bitシーケンスを作り出しますが、 これでは常に01か10のいずれかとなります。 2つしか候補値がないので、 なおも当初の乱雑性の1bitにすぎません。

5.6. 撹拌関数を選択する際の他の要素 English

ローカルな利用において、AESは、 「欠陥について広くテストされている」、 「ソフトウェア実装が合理的に効率的である」、そして、 「ハードウェアとソフトウェアの実装が(オープンなソースコードを含めて)世界中に利用可能とされていると共に文書化され、 実装されている」という長所をもっています。 SHA*ファミリについては、これまであまり調べられておらず、 AESより多くのCPUサイクルを要求する傾向がありますが、 それらに欠陥があると信じる理由は、ありません。 SHA*とMD5の両方は、以前のMD4アルゴリズムに由来します。 それらすべてのソースコードは、入手可能になっています [SHA*, MD4, MD5]。 いくつかの弱点の兆候が、MD4とMD5に発見されました。 特に、MD4は、たった3ラウンドしかもたず、 最初の2ラウンドもしくは最後の2ラウンドに、 いくつかの独立した破り方があります。 そして、いくつかの衝突(collision)がMD5出力において発見されました。

AESは、厳格、公開かつ国際的なプロセスによって採択されました。 これとSHA*は、DESがそうであったように、 米国のNSA (National Security Agency)によって、 ほとんど秘密のままのクライテリアに基づいて保証されてきました。 これは、多くの疑念と疑惑の原因でしたが、 何年にも渡るDESの調査結果は、「IBMに端を発する、 この設計の改変におけるNSAの関与は、主に、 それを強化するためのものであったこと」を示しました。 DESについて見つかっている「隠されていた弱点」もしくは「特別な弱点」の発表は、 ありませんでした。 MD4に対するSHAアルゴリズムを作り出すためのNSAによる変更は、同様に、 これらのアルゴリズムを、おそらく暗号技術的コミュニティにおいて、 まだ公には知られていない脅威に対して強化したようです。

入力長が予測不能な場合、ハッシュアルゴリズムは、 ブロック暗号化アルゴリズムより、使うのに便利です。 なぜなら、それらは、一般に、 可変長入力を受容するように設計されているからです。 ブロック暗号化アルゴリズムは、一般に、 そのブロック長の倍数でない場合にも入力を扱うために、 追加的なパディングアルゴリズムを要求します。

本書が書かれた時点において、著者は、 世界中に最終的な(irrevocable)ロイヤリティフリーライセンスが認められている特許以外に、 基本的なAES, DES, SHA*, MD4, MD5アルゴリズムについての特許の主張を知りません。 当然ながら、著者が知らない肝要な特許、 実装もしくは利用法についての特許、あるいは、 発行された(／これから発行される)他の関連特許がある可能性があります。

6. 擬似乱数生成器 English

種(seed)が十分なエントロピーをもつとき、 (3章に記述したように)入力から、そして、おそらく、 (4章と5章に記述したように)平滑化・撹拌して、 アルゴリズム的に、その種を、 多数の暗号技術的に強い乱数を作り出すように延長できます。 このようなアルゴリズムは、プラットフォーム独立的であり、 あらゆるコンピュータ上で、同じように動作できます。 セキュアにされるべきアルゴリズムについて、 それらの入力と内部の動作は、 敵対的な観察から防護されなければなりません。

このような擬似乱数生成アルゴリズムの設計は、 (共通鍵暗号化アルゴリズムの設計のように)アマチュアがやるべき仕事ではありません。 下記6.1節は、 落第したアルゴリズムが使われている数多くの悪いアイディアを掲げています。 何が動作するかを学ぶために、6.1節を飛ばし、 この章の以降の部分と7章のみを読んでください。 そこには、 いくつかの標準的な擬似乱数生成アルゴリズムが記述・参照されています。 ([X9.82] の7章とPart 3を参照。)

6.1. いくつかの悪いアイディア English

以降の節では、一見、合理的に見えるかもしれないが、 セキュアでない擬似乱数生成につながる数多くのアイディアを記述します。

6.1.1. 複雑な操作の誤り English

予測困難性について誤解を招く外観をもたらす可能性がある、 ひとつのアプローチは、非常に複雑なアルゴリズムを(もしくは、 秀逸な従前の擬似乱数生成器を良い統計的特性と共に)採用し、 そのコンピュータのシステム時計の値のような限られたデータを種として開始することによって、 暗号鍵を計算処理することです。 「いつ頃から、その生成器が開始したか？」を知っていた攻撃者は、 システム時計のおよその値を知っているので、 比較的少数の種の値をテストするだけで足ります。 大量の擬似乱数のビット列を生成できますが、 攻撃者がチェックする必要がある探査空間は、 極めて小さい可能性があります。

それゆえ、データの極めて強い、または、複雑なデータの操作は、 その攻撃者が「その操作がどのようなものか？」を学ぶことができ、 種の値に十分な予測困難性が無い場合、役に立ちません。 彼らは、通常、限定された種の値の数によって制限される結果の数をセキュリティを破るために使える可能性があります。

別の深刻な戦略的エラーは、 「非常に強い擬似乱数生成アルゴリズムは、背後の理論、もしくは、 そのアルゴリズムの分析が無いとき、 強い乱数を作り出す」と想定することです。 [KNUTH] の3章の始めあたり(著者が複雑なアルゴリズムを記述している箇所)に、 この誤りについての秀逸な例があります。 「当該アルゴリズムに対応するマシン語プログラムは、複雑すぎて、 プログラムの実行内容をコメントなしに人は読み取ることができないこと」が意図されました。 残念ながら、このアルゴリズムの実際の利用によって、 「1つの値の連続に収束する事例と、 値の短周期性が見られる別の事例」を示しました。

種の範囲に限りがある場合、複雑な操作は役に立たないばかりでなく、 やみくもに選択された複雑な操作は、 良い種による乱雑性を破壊する可能性さえあります！

6.1.2. 大規模データベースからの選択の誤り English

予測困難性について、誤解を招く可能性のある別のアプローチは、 無作為にデータベースから数を選択し、「その強度は、 そのデータベース中のビット総数に関連する」と想定することです。 例えば、典型的なUSENETサーバーは、毎日、多くの情報を処理します [USENET_1, USENET_2]。 「乱数は、 このデータ中の無作為な起点から32byteのデータを取り出すことによって選択された」と想定します。 これからは、32*8 = 256bitに相当する推測困難性は、生じません。 たとえ、そのデータの多くが(1byteあたり2, 3bit程度の情報量しか含まない)自然言語である場合でも、 32*2 = 64bitの推測困難性は、生じません。 同一のUsenetデータベースにアクセスできる攻撃者にとって、 推測困難性は、その起点の選択にあるのみです。 それは、おそらく、数十bit程度の推測困難性となります。

同じことは、一般に入手可能なCD/DVD録音上のデータや、 あらゆる他の大規模公衆データベースからのシーケンスを選択することについてもいえます。 その攻撃者が同一のデータベースにアクセスできる場合、 この「大量なデータからの選択」からは、ほとんど得るものはありません。 しかし、 選択が(活動しているマルチユーザシステム上のシステムバッファのような)その攻撃者がアクセスできないデータから行われうる場合、 役立つ可能性があります。

6.1.3. 従前の擬似乱数列 English

この章では、deterministicの従前の源泉、もしくは、 「擬似乱数」について述べます。 これらは、典型的には、「種」の量で始まり、 値のシーケンスを作り出すために、 単純な数論的操作あるいは論理的操作を行います。 「この節において検討されたテクニックに、 暗号技術的利用に適するものは無いこと」に注意してください。 それらは、一般情報として提供されています。

[KNUTH] は、擬似乱数について、 典型的な説明をしています。 彼が言及するアプリケーションは、自然現象のシミュレーション、 サンプリング、数値解析、コンピュータプログラムのテスト、 意思決定およびゲームです。 これらの中には、 我々が話題にしている種のセキュリティ用途と同じ特徴をもつものは、 ありません。 最後の2つのみに、 乱数を見つけようとする攻撃者が存在する可能性があります。 しかし、これらの場合において、その攻撃者は、通常、 推測した値を使うには、1回しかチャンスをもちません。 パスワードを推測したり、あるいは、 ある暗号化スキームを破ることを試みる際に、その攻撃者は、通常、 正しい値を推測する際に、多くの(おそらく無制限の)機会をもちます。 しばしば、攻撃者は、そのメッセージを解読するために蓄積でき、 繰り返し、それを攻撃します。 攻撃者は、コンピュータによって支援されているとも想定されます。

数の「乱雑性」をテストするために、Knuthは、統計的なものや、 スペクトラルなものを含む様々な手段を示唆しています。 これらのテストは、「乱雑な」シーケンスの異なる部分間、もしくは、 その値の分散の自動訂正のような事項をチェックします。 しかし、これらのテストは、CRC標準の数学的表 [CRC] に印刷された「乱雑な」シーケンスのような、 蓄積された一定の乱雑なシーケンスによって満たされる可能性があります。 Knuthによって示唆された、すべてのテストを満たすにも関わらず、 そのシーケンスは、暗号技術的な利用には適しません。 なぜなら、攻撃者は、一般に公知な、 すべての「乱雑な」シーケンスのコピーをもち、 源泉を当てて将来の値を予測できると想定されなければならないからです。

典型的な擬似乱数生成テクニックは、 線形合同法による擬似乱数生成器です。 このテクニックは、下記のように、N番目の値から、 計算によってN+1番目の値を求める剰余演算です。

VN+1 = (VN * a + b )(Mod c)
    

上記のテクニックは、 暗号技術的によく理解されている線形シフトレジスタ擬似乱数生成器 [SHIFT*] と強く関連しています。 このような生成器において、ビット列は、 レジスタへの選択された固定タップからのビット列の排他的論理和(キャリアなしの2進数加算)として、 シフトレジスタの一端に導入されます。 例えば、下記のことを考慮してください。：

+----+     +----+     +----+                      +----+
| B  | <-- | B  | <-- | B  | <--  . . . . . . <-- | B  | <-+
|  0 |     |  1 |     |  2 |                      |  n |   |
+----+     +----+     +----+                      +----+   |
  |                     |            |                     |
  |                     |            V                  +-----+
  |                     V            +----------------> |     |
  V                     +-----------------------------> | XOR |
  +---------------------------------------------------> |     |
                                                        +-----+

 VN+1 = ((VN  * 2) + B0 XOR B2 ... )(Mod 2n)
    

従前の擬似乱数生成器アルゴリズムの品質は、 このようなシーケンスについての統計的テストによって測定されました。 IVとa, b, cの値の注意深い選択、もしくは、 上記の単純な過程におけるシフトレジスタ捕捉点の適切な配置によって、 秀逸な統計値を作り出すことができます。

これらの数列は、精査している空間の構造と相関しない限り、 シミュレーション(モンテカルロ実験)において適切である可能性があります。 そこでさえ、微妙なパターンが、問題を引き起こす可能性があります。 しかし、このような数列は、明らかに、 セキュリティアプリケーションにおける利用には、良くありません。 それらは、初期状態が知られている場合、完全に予測可能です。 擬似乱数生成器の形態によっては、そのシーケンスは、 そのシーケンスの短い部分の観察によって解読可能である可能性があります [SCHNEIER, STERN]。 例えば、上記の生成器を使えば、人は、V(n)の知識が与えられれば、 V(n+1)を解読できます。 事実、これらのテクニックを使うことによって、 「擬似乱数の1bitだけが公表されている場合でも、 短いシーケンスから種が解読できること」が示されました。

線形合同(擬似乱数)生成器が解読されたばかりでなく、今や、 すべての多項式合同(擬似乱数)生成器を解読するためのテクニックが知られています [KRAWCZYK]。

6.2. 暗号技術的に強いシーケンス English

一連の乱数が生成されなければならない場合、攻撃者は、 そのシーケンス中の何らかの値を学習する可能性があります。 一般に、攻撃者が、 知っている値から他の値を予測できるようではいけません。

正しいテクニックは、強い乱雑な種で開始し、 その種に暗号技術的に強い手順 [FERGUSON, SCHNEIER] を適用するものであり、シーケンス要素について、 その生成器の完全な状態は明かさないことです。 そのシーケンス中の各値が以前の値から定型的な方法で計算できる場合、 いずれかの値が侵されたとき、すべての将来の値が、判定できてしまいます。 これは、例えば、 たとえその不可逆メッセージダイジェスト関数が極めて強くても、 以前に使われた値から一定の関数で現在の値が得られるような場合に該当します。

(「鍵値のシーケンスを生成するためのテクニックが十分に速い場合、 これは、卑近に、 守秘性システムの基礎として使えること」に注意してください。 2者が同じ数列生成テクニックを使い、同じ種素材で始める場合、それらは、 同一のシーケンスを生成します。 これらは、排他的論理和の可逆性によって、例えば、 一方が送信したデータの排他的論理和がとられて暗号化され、 受け取ったこのデータについて排他的論理和をとって復号できます。 これは、普通、「シンプルストリーム暗号」と呼ばれます。)

6.2.1. OFBおよびCTRのシーケンス English

強いシーケンスを作成するためのひとつの方法は、種値をとり、 種を連続した整数等と連結することによって作り出された数をハッシュ化し、 攻撃者が知ることができる生成器の状態情報の量を制限するように、 取得された値をマスク化することです。

連続した整数を暗号化するために、カウンタ(CTR)モードの暗号化において、 乱雑な鍵と種値をもつ「暗号化」アルゴリズムを使うことが可能です。 代わりに、暗号化の出力値すべてを、 次に暗号化されるべき値にフィードバックできます。 これは、OFB(出力フィードバックモード) [MODES] の特定の例です。

一例は、下図に示されます。 ここで、シフト演算とマスキングが、 出力フィードバックの部分を古い入力の部分と結合するために使われます。 この種の並行フィードバックは、下記の理由によって、 避ける必要があります。

+---------------+
|       V       |
|  |     n      |--+
+--+------------+  |
      |            |     +---------+
 shift|            +---> |         |      +-----+
   +--+                  | Encrypt | <--- | Key |
   |           +-------- |         |      +-----+
   |           |         +---------+
   V           V
+------------+--+
|      V     |  |
|       n+1     |
+---------------+
    

「1のシフトが使われる場合、これは、 6.1.3節に記述された、 シフトレジスタのテクニックと同じですが、最も重要な差異は、 『フィードバックが、 いくつかのビット位置からの出力の単純な線形関数や多項式結合ではなく、 ビット列全体の複雑な非線形関数によって決定されること』であること」に注意してください。

Donald W. Daviesは、「この種のシフトされた並行出力フィードバックは、 出力ビット列を入力としてフィードバックすることと比べて、 アルゴリズムを顕著に弱めること」を示しました。 (特に、DESについて、64bit全体の暗号化の繰り返しは、 約2の63乗回の繰り返しをもたらすことでしょう。)(0より大きく)64bit未満のものをフィードバックすることは、 2³¹から2³²の間の繰り返しを与えてしまいます！

そのシーケンスが、これらのテクニックによって生成されたとき、 シーケンスの値を他から予想することは、 その暗号システムを解読すること、 もしくは、部分的な情報のみが入手可能な状態で「不可逆」ハッシュ化を逆算することに等しいといえます。 各繰り返しにおいて明かされる情報が少ないほど、攻撃者が、 そのシーケンスを推測することは、より難しくなります。 それゆえ、各値から1bitだけを使うのが、最善です。 「生成された値の各々がすべて明かされる場合、 暗号技術的システムが可逆であり、解読可能であるときでさえ、 場合によっては、システムを破ることを不可能にすること」が示されてきました。

6.2.2. Blum Blum Shubシーケンス生成器 English

現在、強度について最強の公的証明をもつ生成器は、 その発明者にちなんで、Blum Blum Shub生成器 [BBS] と呼ばれています。 これは、極めてシンプルであり、平方剰余に基づきます。 その唯一の欠点は、 「6.1.3節で述べた従前のテクニックと比べて、 計算量的に重いこと」です。 これは、 セッション鍵生成のように頻度が中程度の目的のために使われる場合には、 深刻な足かせにはなりません。

単純に2つの大きな素数(仮に、pとq)を選択します。 両者は、4で割った場合、余が3となる属性をもつものとします。 n = p * qとします。 次に、nと互いに素である乱数xを選択します。 生成器に対する初期種と以降の値の計算方法は、下記のとおりです。：

s0 = x2 Mod n
si+1 = si2 Mod n
    

各sの底から数ビットだけを使うように注意してください。 最低位順のビットのみを使うことが常に安全です。 次式を越える低位ビットを使う場合：

log2(log2(si))
    

この作法によって生成されたシーケンスから、 いかなる追加的なビット列を予測することは、 nを素因数分解することと同等に困難であることが証明できます。 初期xが秘密である限り、nは、望まれれば公開することができます。

この生成器の興味深い特徴は、 「直接、あらゆるsの値を計算できること」です。特に、

si = s0(2^i) Mod ((p-1)*(q-1)) Mod n
    

これは、「このように多くの鍵が生成されているアプリケーションにおいては、 それらすべてを保存することは、必要不可欠ではないこと」を意味します。 各鍵は、効果的に、インデックス化される可能性があり、 その小さなインデックスと、そのsとnの初期値から復元できます。

6.3. エントロピープールテクニック English

7.1.2節と7.1.3節に記述されているような、 多くの現代の擬似乱数源は、ビット列の「プール」を維持管理し、 入力をそのプール中に何らかの乱雑性で強く撹拌するための操作を提供し、 このプールから擬似乱数ビット列を得るテクニックを活用します。 これは、下図中に表現されています。

    +--------+    +------+    +---------+
--->| Mix In |--->| POOL |--->| Extract |--->
    |  Bits  |    |      |    |   Bits  |
    +--------+    +------+    +---------+
                      ^           V
                      |           |
                      +-----------+
    

このプール中に入力されるビット列は、上記の様々なハードウェア源泉、 環境的源泉あるいはユーザ入力源泉のいずれからも来る可能性があります。 安定したストレージが利用可能なとき、システムのシャットダウン時に、 そのプールの状態を保存し、再起動時に復元することも、 卑近に行われています。

「特定の出力が要するものを使うこと」をサポートするために、 十分なエントロピーが、そのプールに加えられるように、 注意が払われなければなりません。 同様の示唆については、[RSA_BULL1] を参照。

7. 乱雑性生成の例および標準 English

いくつかの公的標準と、広く配備された例が、現在、 鍵もしくは他の暗号技術的に乱雑な数の生成のために存在します。 7.1節中には、エントロピー源泉を含むものがあります。 他に、7.2節に記述されたものは、 強い擬似乱数シーケンス生成器を提供しますが、乱雑な種の入力、もしくは、 エントロピーの源泉からの入力を想定します。

7.1. 完成した乱雑性生成器 English

3つの標準が、以下に記述されます。 2つの古い標準が、DESを64bitのブロック長と鍵長の制限で使いますが、 あらゆる同等に強い、あるいは、より強い撹拌関数が、 代わりに使えます [DES]。 3番目のものは、SHA-1 [SHA*] に基づく、 より新しく、より強い標準です。 最後に、広く配備されている現代のUNIXとWindowsの乱数生成器が記述されます。

7.1.1. 米国国防総省のパスワード生成についての推奨事項 English

米国国防総省(Department of Defense)は、パスワード生成について、 具体的な推奨事項 [DoD] をもっています。 これは、下記のように、米国のDES(Data Encryption Standard)[DES] を出力フィードバックモード [MODES] で使うことを示唆します。：

初期ベクトル(IV：initialization Vector)の決定に、システム時計、 システムID、ユーザIDおよび日付と時刻を使います。；

システム割り込みレジスタ、システム状態レジスタ、 およびシステムカウンタによって決定される鍵を使います。；

平文として、システム管理者によって打たれた8文字のような、 外部で乱雑に生成された64bitの数を使います。

そのとき、そのパスワードは、 64bit出力フィードバックモードにおいて生成された64bitの「暗号文」から計算できます。 なぜなら、人間がパスワードを覚える必要がある場合、 必要とされるだけのビット数は、これらの64bitから得られ、 発音可能な単語、文句、もしくは他のフォーマットに拡張されるからです。

7.1.2. /dev/randomデバイス English

UNIXオペレーティングシステムのいくつかのバージョンは、 カーネル中において乱数生成器を提供しています。 このような生成器には、通常のシステム運用において、 カーネルによって捕捉されたイベントを使うものがあります。

例えば、いくつかのLinuxのバージョンにおいては、その生成器は、 各4byteの128ワードとして表現される512byteの乱雑性のプールから成ります。 (ディスクドライブの割り込みのような)イベントが発生したとき、 そのイベントの時刻は、プール中に排他的論理和がとられ、そのプールは、 128次のプリミティブ多項式を通じて撹拌されます。 プール自体は、リングバッファとして扱われ、新しいデータについては、 プール全体に渡って、 (多項式について活発に処理したあとに)排他的論理和がとられます。

そのプールにエントロピーを加える各呼び出しは、 その入力が含んでいる概ね真のエントロピーの量を見積もります。 そのプール自体は、 そのプールのエントロピー全体を見積もるアキュムレータを含みます。

入力イベントは、下記のように、いくつかの源泉から来ます。 残念ながら、人間のオペレータが居ないサーバーマシンについて、 最初のものと、3番目のものは、入手できず、 エントロピーは、その場合において、ゆっくりと加えられる可能性があります。

1. キーボード入力：
   割り込みとスキャンコードの時刻が、プールに追加されます。 これは、結果として、 人間の操作から打鍵間時間を測定することによってエントロピーを加えます。
2. ディスク関連の割り込み：
   ある人によって使われているシステムは、 ディスクアクセスの予測困難なパターンをもつ傾向があります。 (しかし、すべてのディスクドライブが、 このタイミング情報を有用な程度に十分な精度で捕捉することをサポートするわけではありません。)
3. マウスの動き：
   そのタイミングとマウスの位置が、加えられます。

乱雑なバイト列が要求されるとき、そのプールは、 SHA-1 [SHA*] で返される乱雑なバイト列を生成するようにハッシュ化されます。 SHA-1の出力(20byte)より多くのバイト列が要求される場合、 そのハッシュ化された出力は、そのプールに撹拌用に再投入され、 新たなハッシュ化が、次の20byteを得るために行われます。 byte数がプールから除かれるにしたがって、エントロピーの見積もりは、 対応して、減少します。

システムの起動時に、合理的な程度に乱雑なプールを確保するために、 標準スタートアップ(起動)と、シャットダウンスクリプトは、 そのプールをシャットダウン時にディスクファイルに保存し、 システムの起動時に、このファイルを読みます。

2つのユーザとのインタフェイスがあります。 /dev/randomは、そのプールからのバイト列を返しますが、 見積もられるエントロピーがゼロとなるとき、ブロックします。 エントロピーが、イベントから、そのプールに追加さえれるに従って、 より多くのデータが/dev/randomを通じて利用可能になります。 このような/dev/randomデバイスから得られた乱雑なデータは、 十分な乱雑なビット列がそのプール中にある場合、あるいは、 合理的な時間が延長されている場合、長期鍵用の鍵生成のために適切です。

/dev/urandomは、/dev/randomのように動作します。 しかし、これは、 たとえ乱雑性のプールについてのエントロピー見積もりがゼロに落ちるときでさえ、 データを提供します。 これは、セッション鍵生成用、あるいは、 より多くの乱雑なビット列を待ち受けるのをブロックすることが許されないような他の鍵生成用に適切である可能性があります。 たとえ、そのプールのエントロピーの見積もりが、 その過去の出力において小さいときでさえ、 データを採り続けることのリスクは、攻撃者がSHA-1を逆算できるとしたら、 現在の出力から計算可能でしょう。 SHA-1が繰り返されないように設計されている場合、 これは、合理的なリスクです。

上記のように、ソースコードと共に提供されるLinux、 Solarisもしくは他のUNIXシステムのもとで乱数を得るために、 すべてのアプリケーションがやらなければならないことは、 /dev/randomか、あるいは、/dev/urandomのいずれかを開けて、 必要なバイト数を読むことです。

(Linux Randomデバイスは、Theodore Ts'oによって書かれました。 これは、概ね、(PGP 5.0として知られている)PGP 2.XおよびPGP 3.0 中の乱数生成器に基づきました。)

7.1.3. Windows CryptGenRandom English

広く配備されているWindowsオペレーティングシステムのユーザ宛のMicrosoftの推奨は、 一般的に、 CryptAPI暗号技術的サービスプロバイダと共にCryptGenRandom擬似乱数生成呼び出しを使うことです。 これは、暗号技術的サービスプロバイダのライブラリへのハンドル、 呼び手がエントロピーを提供できるようにするとともに、 生成された擬似的な乱雑性が返されるバッファへのポインタ、および、 「何オクテットの乱雑性が必要とされるか？」の表示を受け取ります。

Windows CryptAPI暗号技術的サービスプロバイダは、 ユーザによって変化する可能性がある種の状態を蓄積します。 CryptGenRandomが呼ばれるとき、これは、 (呼び出しによって提供されたり様々なシステムやプロセスIDのようなユーザデータにある)あらゆる乱雑性、 スレッド ID、システム時計、システム時刻、システムカウンタ、メモリ状態、 空いているディスククラスタ、および、 ハッシュ化されたユーザ環境ブロックと組み合わされます。 このデータは、すべてSHA-1に投入され、 その出力は、RC4鍵ストリームの種として使われます。 その鍵ストリームは、要求された擬似乱数データを作りだし、 そのユーザの種の状態変数を更新するために使われます。

Windows ".NET"のユーザは、おそらく、 RNGCryptoServiceProvider.GetBytes手法のインタフェイスを使うことがより容易であることに気づくことでしょう。

詳細な情報については、[WSC] 参照。

7.2. エントロピーの源泉を想定する生成器 English

以降の3節において記述されている擬似乱数生成器は、すべて、 「十分なエントロピーをもつシード値が、それらに提供される」を想定します。 そして、それらは、 その種から強いシーケンス(6.2節 参照)を生成します。

7.2.1. X9.82擬似乱数生成 English

ANSI X9F1委員会は、 真正乱数生成器と擬似乱数生成器の両方を扱う乱数生成についての標準策定の最終段階にあります。 これは、ハッシュ関数に基づく数多くの擬似乱数生成器を含み、そのひとつは、 おそらく、HMAC SHAハッシュの組み立て [RFC2104] に基づきます。 この生成器のドラフト版 [X9.82] は、数多くの運用論点を省略して、後述されます。

下記の節において、HMACハッシュの組み立ては、HMACとして言及されますが、 当然ながら、特定の標準SHA関数が、 特定の用途について選択されなければなりません。 一般に、 生成されるべき擬似乱数値の強度がN bitでなければならないとされる場合、 選択されたSHA関数は、N bit以上の出力を生成しなければならず、 少なくともN bitの入力エントロピーの源泉が要求されます。 同一のハッシュ関数が、 この生成器の導入を通じて使われなければなりません。

7.2.1.1. 表記法 English

以降の節において、後述する表記法が使われます。：

7.2.1.2. 生成器を初期化する English

各byteの下位ビットは1にセットされることを除いて、 Vをすべてゼロbyteにセットする。

Kをすべてゼロbyteにセットし、次に、下記のようにセットする。：

K = HMAC ( K, V | 0x00 | input_entropy )
V = HMAC ( K, V )
K = HMAC ( K, V | 0x01 | input_entropy )
V = HMAC ( K, V )
    

注：すべてのSHAアルゴリズムは、整数byteを作り出すので、 KとVの長さは、整数byteとなります。

7.2.1.3. 乱雑なビット列を生成する English

出力が呼び出されたとき、下記のように単純にセットします。：

V = HMAC ( K, V )
    

そして、Vの先頭からのビット列を使います。 Vの長さより多くのビット列が必要とされる場合、 "temp"にnullビット列をセットし、次に、繰り返し、 下記の処理を行います。：

V = HMAC ( K, V )
temp = temp | V
    

temp直後で止めると、要求される乱雑なビット列の数と同等以上になります。 要求されたビット数をtempの先頭から使います。 そのアルゴリズムの規定は、 2³⁵bitより多くを要求することを禁止します。

上記のように、擬似乱数出力ビット列取り出し、保存したあと、 返す前に、あなたは、下記のように、あと2回HMACも行う必要があります。：

K = HMAC ( K, V | 0x00 )
V = HMAC ( K, V )
    

7.2.2. X9.17 鍵生成 English

ANSIは、鍵のシーケンスを生成することについて、下記の手法を規定しました [X9.17]。：

DES(K, Q)は、数Qを鍵KでDES暗号化します。

次に、：

gn    = DES ( k, DES ( k, t ) XOR sn  )

sn+1    = DES    ( k, DES ( k, t ) XOR gn  )
    

g_nがDES鍵として使われる場合、毎8bitは、パリティについて、 その用途に応じて調整される必要がありますが、 64bitの変更されていないgの全体は、 次のsを計算する際に使われる必要があります。

7.2.3. DSS擬似乱数生成 English

NISTのデジタル署名標準 [DSS] のAppendix 3は、 プライベート鍵等として使うための擬似乱数160bitのシーケンスを作成するための手法を提供しています。 これは、 汎用目的の擬似乱数を生成するための下記のアルゴリズムを作り出すために、 Change Notice 1 [DSS_CN1] によって変更されました。：

t = 0x 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0

XKEY0 = 初期種

For j = 0 to ...
  XVAL = (XKEYj + optional user入力) Mod 2512
  Xj = G(t, XVAL)
  XKEYj+1 = (1 + XKEYj + Xj) Mod 2512
    

これによって作り出される数Xは、160bitの値の擬似乱数シーケンスです。 2つの関数が上記"G"に使えます。 各々は、160bit値を作りだし、 2つのアーギュメント(160bitの値と512bitの値)をとります。

最初のものは、SHA-1に基づいており、 SHA-1仕様中の記述法でHと表記される5つのリンキング変数を5つに分割される最初のアーギュメントにセットすることによって動作します。 そして、NIST SHA-1仕様の7章の(a)から(e)までの手順は、 これが512bitのデータブロックであるかのように2番目のアーギュメントで実行されます。 その手順のあと、その連結している変数の値は、次に、結合され、 Gの出力を作り出します。[SHA*]

代替手段として、NISTは、DES暗号化関数 [DSS] の複数のアプリケーションに基づくalternate G関数も規定しました。

8. 要求される乱雑性の例 English

下記のものは、 セキュリティのために必要とされる乱雑性についての大ざっぱな計算を示す2つの例です。 最初のものは、中程度のセキュリティパスワードのためのものであり、 2番目のものは、 非常に高いセキュリティのための暗号鍵についての必要性を想定します。

加えて、 [ORMAN] と [RSA_BULL13] は、 共通鍵を交換するために使われる必要がある公開鍵の長さについての情報を提供します。

8.1. パスワード生成 English

「ユーザのパスワードは、1年に1回、変更され、 攻撃者が特定のアカウントについてのパスワードを推測できる確率が1,000分の1以下であることが望まれる」と想定します。 さらに、 「システムにパスワードを送り込むことがパスワードを試す唯一のやり方である」と想定します。 そして、決定的な問題は、「何回、 攻撃者が可能性を試すことができるか？」です。 「攻撃者が6秒毎に、ひとつのパスワードを試すことしかできないように、 システムに遅延のしかけが導入されている」と想定します。 これは、毎時600回(毎日約15,000回、毎年約5,000,000回)です。 何らかの監視活動を想定するとき、 誰かが一年を通じてコンスタントに試すことは、実際には、 ありそうにありません。 たとえログファイルが月例でしかチェックされない場合でも、 攻撃が知覚される前に500,000件の試みがある可能性があり、 パスワード変更の手順をとることによって、 より多くのパスワードを試すことを困難にします。

500,000回の試行でパスワードが推測される確率を1,000分の1とするためには、 少なくとも500,000,000件のパスワード(約2の29乗の空間)を意味します。 それゆえ、29bitの乱雑性が必要とされます。 これは、おそらく、 「米国国防総省が推奨したパスワード生成のための入力」を使うことによって達成できます。 なぜならば、これは、各々、平均で、 おそらく5bit以上の乱雑性をもつ8つの入力をもつからです (7.1節 参照)。 パスワードは、1,000語のリストを使うことによって、 3単語の句(1,000,000,000の可能性)として表現したり、 大文字と小文字を区別しない文字とディジット(1桁の整数)を6文字((26+10)⁶ = 2,176,782,336の可能性)以上使うことによって表現できます。

より高いセキュリティのパスワードのためには、 要求されるビット数が増えます。 確率を1,000分の1減らすことは、 パスワード空間を同一要素によって約10bit増加することを要求します。 それゆえ、 上記のシナリオのもとでパスワードが推測される確率をわずかに100万分の1とするためには、 39bit相当の乱雑性(1000単語のリストから抽出した4単語の句のパスワード、 もしくは、8文字／ディジットのパスワード)を要求します。 10の9乗分の1の確率とするためには、49bit相当の乱雑性が必要とされ、 5単語の句のパスワード、もしくは、 10文字(ディジット)のパスワードを意味します。

当然、現実のシステムにおいては、他の要素があります。 例えば、パスワードがより長く、より覚えにくくなれば、ユーザは、 それらを書き留めておくようになりがちであり、 侵される追加的リスクを招きます。

8.2. 極めて高いセキュリティの暗号鍵 English

「極めて高いセキュリティの鍵が2者間の共通鍵による暗号化／復号のために必要とされる」と想定します。 「攻撃者は、通信を観察でき、 使われているアルゴリズムを知っている」とも想定します。 乱雑である可能性のあるフィールドについて、その攻撃者は、 1者が使っている鍵を見つけることを期待して、鍵の値を試すことができます。 以降、「鍵のブルートフォース攻撃まで、その攻撃者は、 できる」と想定します。

8.2.1. 鍵の試行あたりの労力 English

「各鍵を試すのに、 どれくらいの労力を要するか？」極めて高セキュリティアプリケーションについては、 少ない労力を想定するに越したことはありません。 たとえ、ひとつの鍵を試すのに、 数万以上のコンピュータサイクルがかかることが明らかである場合でも、 各鍵ごとにはるかに少ない労力で膨大な数の鍵値を試すことを可能にする何らかのパターンがある可能性があります。 それゆえ、おそらく、各鍵について、数百サイクル以下を想定することが、 最善の策です。(この明確な下限は、ありません。 なぜならば、コンピュータは、数多くのビット列を並行処理するので、 貧弱な暗号化アルゴリズムには、 多くの鍵や鍵の群を並行してテストできる可能性があります。 しかし、我々は、何らかの値を想定する必要があり、 「高いセキュリティを要する仕事というこの仮説のために、 合理的に強いアルゴリズムが選択されること」を期待できます。)

その攻撃者が高度な並行処理計算機(もしくは、 ワークステーションの大規模ネットワーク)に命令できる場合、 毎秒2*10¹¹サイクルは、今日、おそらく、可用性について、 最低限の想定です。 数年先を見通せば、少なくとも、1桁の向上があることでしょう。 それゆえ、「毎秒10¹⁰、あるいは毎時3.6*10¹²、 あるいは毎週6*10¹⁴、 あるいは毎月2.4*10¹⁵の鍵をチェック可能である」と想定するのが合理的です。 これは、1ヶ月中にそれらが見つからないようにするためには、最低限、 63bit相当の乱雑性をもつ鍵が必要であることを意味します。 そのときでさえ、「数年後、 強固な意志と資源をもつ攻撃者が鍵を2週間で破ることができること(平均で、 彼らは、鍵の半分だけを試す必要がある)」は、ありえます。

これらの疑問は、Business Software Allianceがスポンサーとなった"Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security: A Report by an Ad Hoc Group of Cryptographers and Computer Scientists" [KeyStudy] において詳細に考察されています。 これは、「1995年において、 非常に高いセキュリティについての合理的な鍵長は、 75bitから90 bitの範囲内にある」と結論づけ、暗号技術の費用は、 鍵長によって大差ないので、90bitを推奨しています。 これらの推奨事項を更新するためには、「ムーアの法則 [MOORE]」について、単純に、 年あたり2/3bitを追加します。 これは、2004年において、判断のために翻訳すると、合理的な鍵長は、 81bitから96bitの幅の中になります。 事実、今日、「AESについて128bit(もしくは、 それ以上の)鍵」や「triple-DESについて、 有効な長さが112bitの鍵」のような、 96bit以上の長さの鍵を使うことが、ますます卑近になってきています。

8.2.2. 中間一致攻撃 English

選択／既知の平文と結果としての暗号文が入手可能な場合、 「中間一致攻撃(meet-in-the-middle attack)」は、 暗号化アルゴリズムの構造が許容する場合、可能です。 (「既知平文攻撃」において、その攻撃者は、暗号化されたメッセージの、 すべて、もしくは部分を知っており、それが標準ヘッダーのどれかや、 その後続フィールドである可能性があります。 選択平文攻撃において、その攻撃者は、 ある選択された平文を暗号化することを強いることができ、おそらく、 「漏洩」によって、それは、 攻撃者によって暗号化されたチャネル越しに送られることになります。 なぜなら、そのテキストは、興味の的であるからです。

下記のものは、「中間一致攻撃」について、角に単純化されたものです。 その攻撃者は、既知平文もしくは選択平文を、 すべての前半用鍵の候補で半分暗号化し、出力を並べ替え、 それらの暗号文を、すべての後半用の鍵候補で半分復号することができます。 一致が発見された場合、鍵全体は、両半分の鍵から組み立てることができ、 メッセージの他の部分や他のメッセージを復号するのに使うこと ができます。 この種の攻撃は、うまくいけば、 攻撃者に要求される作業量の指数を半分にすることができます。 一方、大変ではありますが、概ね一定の追加的労力を要します。 それゆえ、この攻撃を放つことができる場合、 [KeyStudy] の分析によれば、2004年においては、 非常に強い鍵における乱雑性の量を最低限192bit (96 x 2)までに、 倍にすることが要求されます。

この乱雑性の量は、パスワード生成について、 米国国防総省によって推奨されている入力中の制限を越えており、 ユーザ打鍵タイミング、ハードウェアによる乱数生成、もしくは、 他の乱雑性の源泉を要求する可能性があります。

「中間一致攻撃」は、「その暗号アルゴリズムは、 この方法で構成部分に分解できる」と想定します。 願わくば、「現代のアルゴリズムに、この弱点は無い」と考えたいのですが、 我々がそれについて確信をもてない場合、あるいは、 どのアルゴリズムとともに鍵が使われているかについてさえ確信がもてない場合がある可能性があります。 たとえ、基本的なアルゴリズムが「中間一致攻撃」の標的とならない場合でも、 基本的アルゴリズム2回(あるいは、 2つの異なるアルゴリズムを順番に)異なる鍵で適用することによって、 より強いアルゴリズムを作り出す試みは、 期待されるほどセキュリティを高められない可能性があります。 このような組み合わされたアルゴリズムは、 「中間一致攻撃」の標的となります。

「中間一致攻撃(meet-in-the-middle attack)」をしかけるためには、 莫大な資源が要求される可能性がありますが、それらは、おそらく、 主要国の国家安全保障サービスの範囲内でしょう。 要するに、すべての国は、他の国のトラフィックをスパイするのです。

8.2.3. 他の考慮事項 English

[KeyStudy] も、 特別目的の暗号解読ハードウェアの可能性と、 適切な安全マージン(余裕)をもつことを検討しています。

「上記のような鍵長計算は、論争になりやすく、 使われている暗号アルゴリズムについて、 様々な想定事項に依存すること」に注意してください。 場合によっては、「アルゴリズム解読テクニック」と「使われているアルゴリズムの強度」についての深い知識をもつプロフェッショナルは、 上記の192bit鍵長の半分未満で満足する可能性があります。

保守的な設計原則のさらなる例示については、 [FERGUSON] 参照。

9. 結論 English

セキュリティ用途の推測不能な秘密の乱数の生成は、肝要でありながら、 困難な課業です。

必要とされるエントロピーを作成することについて、 ハードウェアテクニックは、比較的シンプルです。 特に、量と品質は、高い必要が無く、 音声入力やディスクドライブのような、 手元のコンピュータのハードウェアを使うことができます。

広く利用可能な計算テクニックによって、 複数源泉からの低品質の乱数、 または単一源泉からの低品質の大量の入力を処理して、 高品質かつ予測困難性の高い少量の鍵素材を作り出すことができます。 乱雑性のハードウェア源泉が無い場合、しばしば、代わりに、 多様なユーザおよびソフトウェアの源泉を注意を払って使うことができます。 しかし、大部分の現代のシステムは、既に、 ディスクドライブや音声入力のようなハードウェアをもっています。 これらは、高品質の乱雑性を作り出すために使うことができます。

一旦、十分な量の高品質な種鍵とする素材(数百ビット)が利用可能となると、 この種の素材から予測困難な数の暗号技術的に強い数列を作成するために、 強い計算テクニックが利用できます。

10. セキュリティについての考慮事項 English

本書の全体が、パスワード、暗号鍵、IV、 シーケンス番号および同様のセキュリティアプリケーションに使う、 推測不能な「乱数」を生成するためのテクニックと推奨事項に関するものです。

11. 謝辞 English

大量のコメントを寄せてくださったPaul HoffmanとJohn Kelseyに多謝。 論文「実際に強い乱数のソフトウェア生成」から題材を組み込むことを許諾してくださったPeter Gutmannにも多謝。

下記の人々(アルファベット順)は、十分に本書に貢献してくださいました。：

Steve Bellovin, Daniel Brown, Don Davis, Peter Gutmann, Tony Hansen, Sandy Harris, Paul Hoffman, Scott Hollenback, Russ Housley, Christian Huitema, John Kelsey, Mats Naslund, Damir Rajnovic.

下記の人々(アルファベット順)は、 本書の前版であるRFC 1750に貢献してくださいました。：

David M. Balenson, Don T. Davis, Carl Ellison, Marc Horowitz, Christian Huitema, Charlie Kaufman, Steve Kent, Hal Murray, Neil Haller, Richard Pitkin, Tim Redmond, Doug Tygar.

補遺A： RFC 1750からの変更点 English

1. 追加的に「謝辞」を追加。
2. 「Sボックス」による撹拌についての5.3節を挿入。
3. リングオシレータによる乱雑性の源泉についての3.3節の追加。
4. 160bit以上を生成するAESとSHA系のものの追加。 AESの利用が強調され、DESの利用が強調されなくなった。
5. エントロピープールテクニックについての6.3節の追加。
6. 7.2.3節にFIPS 186-2 (with Change Notice 1)の擬似乱数生成テクニックについてを追加し、 7.2.1節にX9.82の擬似乱数生成テクニックについてを追加し、 7.1.2節にLinuxや他のUNIXシステムにおける /dev/random デバイスの乱数生成テクニックについてを追加し、 7.1.3節にWindowsオペレーティングシステムにおける乱数生成テクニックについてを追加。
7. 参考文献に、1996年1月に発行された調査： "Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security" [KeyStudy] と、 [RFC1948] を追加。
8. 撹拌関数としてDiffie-Hellmanを使うことの警告を追加し、その警告と、 その計算量的負荷の性格に起因して、それを利用しないことを推奨した。
9. X9.82成果と [TURBID] と [NASLUND] の論文に対する参照の追加。
10. minエントロピーおよびRenyiエントロピーの検討と、 [LUBY] への参照の追加。
11. 大幅な再構成、小幅な文章の変更、および、様々な参考文献の更新。

参考情報

著者のアドレス

Donald E. Eastlake 3rd
Motorola Laboratories
155 Beaver Street
Milford, MA 01757 USA

電話： +1 508-786-7554 (w)
　　　　+1 508-634-2066 (h)
EMail： Donald.Eastlake＠motorola.com

Jeffrey I. Schiller
MIT, Room E40-311
77 Massachusetts Avenue
Cambridge, MA 02139-4307 USA

電話： +1 617-253-0161
EMail： jis＠mit.edu

Steve Crocker

EMail： steve＠stevecrocker.com

翻訳者のアドレス

宮川 寧夫
独立行政法人 情報処理推進機構
セキュリティセンター
EMail： miyakawa＠ipa.go.jp

著作権表記全文

Copyright (C) The Internet Society (2005).

This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.

This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

知的財産権

The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.

Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.

The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr＠ietf.org.

謝辞

Funding for the RFC Editor function is currently provided by the Internet Society.