English

セキュリティのための乱雑性についての推奨事項
(Randomness Recommendations for Security)

このメモの位置付け

このメモはインターネットコミュニティのための情報を提供します。これは、いかなるインターネット標準をも定めるものではありません。このメモの配布に制限はありません。

要旨

今日のセキュリティシステムは、ますます、強い暗号アルゴリズムに基づいて構築されるようになってきており、これらは、パターン解析の試みを失敗させます。しかし、これらのシステムのセキュリティは、パスワードや暗号技術的鍵のための秘密の数、および同様の数を生成することに依拠しています。秘密の数を生成するために擬似的に乱雑なシステムを使うことは、擬似的なセキュリティをもたらすに過ぎません。これらのセキュリティシステムに対する洗練された攻撃者は、秘密の数を生成した環境を再現することが、 （結果として得られたいくつかの可能性を検索することによって）数値の空間全体における数から捜し出すことよりも容易であると発見する可能性があります。

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

謝辞

本書について採用されたコメントは、次の方々から受け取ったものです。（アルファベット順）：

David M. Balenson (TIS)
Don Coppersmith (IBM)
Don T. Davis (consultant)
Carl Ellison (Stratus)
Marc Horowitz (MIT)
Christian Huitema (INRIA)
Charlie Kaufman (IRIS)
Steve Kent (BBN)
Hal Murray (DEC)
Neil Haller (Bellcore)
Richard Pitkin (DEC)
Tim Redmond (TIS)
Doug Tygar (CMU)

目次

1. はじめに

2. 要件

3. 伝統的な擬似的に乱雑なシーケンス

4. 予測困難性
4.1 時刻とシリアル番号についての問題
4.2 外部イベントのタイミングと内容
4.3 複雑な操作の誤り
4.4 大規模データベースからの選択の誤り

5. 乱雑性のためのハードウェア
5.1 要求される量
5.2 偏りについての感度
5.2.1 平準化するためにストリームパリティを使う
5.2.2 平準化するために変換マッピングを使う
5.2.3 平準化するために FFT を使う
5.2.4 平準化するために圧縮を使う
5.3 乱数生成のために手元のハードウェアを使うことができる
5.3.1 手元の Sound/Video 入力を使う
5.3.2 手元のディスクドライブを使う

6. 推奨される非ハードウェア戦略
6.1 攪拌関数
6.1.1 卑近な攪拌関数
6.1.2 より強い攪拌関数
6.1.3 攪拌関数としての Diff-Hellman
6.1.4 乱雑なビット列を延長するために攪拌関数を使う
6.1.5 攪拌関数を選択する際の他の要素
6.2 乱雑性の非ハードウェア源泉
6.3 暗号技術的に強いシーケンス
6.3.1 伝統的な強いシーケンス
6.3.2 Blum Blum Shub 生成器

7. 鍵生成標準
7.1 米国国防総省のパスワード生成についての推奨事項
7.2 X9.17 鍵生成

8. 要求される乱雑性の例
8.1 パスワード生成
8.2 極めて高いセキュリティの暗号技術的な鍵
8.2.1 鍵を試すのに費やす労力
8.2.2 中間一致攻撃
8.2.3 他の考慮事項

9. 結論

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

参考文献

著者のアドレス

1. はじめに English

ソフトウェア暗号技術は、広く使われるようになってきています。Kerberos, PEM, PGP 等のシステムは、成熟しつつあり、ネットワーク基盤の一部となりつつあります。[PEM] これらのシステムは、盗聴と偽装に対する実質的な防護を提供します。しかし、潜在的な欠陥があります。それは、すべての暗号技術システムの中心には、秘密の推測困難な数（つまり、乱数）の生成機能が存在することです。

現在まで、このような予測困難な数を生成するための一般に利用可能な設備が無かったことは、暗号技術的ソフトウェアの設計における開いた傷といえます。広範なハードウェアで動作する、鍵またはパスワードの生成手順を構築しようとしているソフトウェア開発者にとって、これまで、唯一の安全な戦略は、ローカルにおけるインストールにおいて、適切な乱数を生成するルーチンを提供することを強制することでした。少なくとも、これは、使いにくく、エラーを起こしがちな、受け入れ難い解決策です。

「必要とされるのは、攻撃者が推測／判定できる可能性が極めて低いデータである」ことを覚えておくことが重要です。擬似的に乱雑なデータが使われる場合、これは、失敗します。このようなデータは、乱雑性についての伝統的な統計的テストにのみ適合するか、もしくは、時計のような限られた範囲の源泉に基づくものです。しばしば、このような乱数は、とまどうほどに狭い可能性ある空間を検索する攻撃者によって判定可能です。

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

2. 要件 English

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

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

ワンタイムパッド [CRYPTO*] や、米国の DES （Data Encryption Standard） [DES] による共通鍵暗号化を利用するなどのケースでは、守秘性を確保し、かつ／または、認証機能をもって、通信することを望む主体は皆、同一の秘密鍵を知らなければなりません。これ以外の、「非対称鍵」もしくは「公開鍵」の暗号技術的なテクニックを使う場合は、鍵はペアで得られます。 ペアの1つの鍵は、プライベートであり、１方によって秘密に保たれなければならず、他方は、公開であり、世界に向けて公表できます。公開鍵からプライベート鍵を判定することは、計算量的に非現実的です。[ASYMMETRIC, CRYPTO*]

乱数についての頻度と量の要件は、暗号技術的なシステムごとに大きく異なります。純 RSA [CRYPTO*] を使う際、乱数は、鍵ペアが生成されるときに要求されますが、以降は、 いかなる追加的な乱雑性の必要性なしに、いくつのメッセージでも、署名できます。米国 NIST （National Institute of Standards and Technology）によって提案された公開鍵 DSA （Digital Signature Algorithm） は、各署名について、良い乱数を要求します。そして、ワンタイムパッド（原則的には、最も強力である可能性が高い暗号化テクニック）で暗号化することは、処理されるメッセージ全体と同量の乱雑性を要求します。

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

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

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

例えば、56 bit 鍵を使う暗号技術的システムを考えてください。これらの 56 bit 鍵が 8 bit の種を入れる擬似乱数生成器を使って生成される場合、攻撃者は、（すべての種候補によって擬似乱数生成器を動作させることにより）たった 256 個の鍵を探す必要があるのみです。2の56乗個の鍵が最初に現れるわけではありません。たった 8 bit の「情報量」しか、これらの 56 bit 鍵の中にありません。

3. 伝統的な擬似的に乱雑なシーケンス English

大部分の伝統的な乱数の源泉は、「擬似的に乱雑な」数の決定論的な源泉を使います。これらは、典型的には、「種」数で始まり、数値演算または論理演算を行って、値のシーケンスを作り出します。

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

数の「乱雑性」を検査するために、Knuth は、 統計的なものや、スペクトル的なものを含む様々な手段を示唆しています。これらのテストは、「乱雑な」シーケンスの異なる部分間の自動相関や、その値の分散のような事項をチェックします。これらは、CRC 標準の数学的表 [CRC] に印刷された「乱雑な」シーケンスのような蓄積された一定の乱雑なシーケンスによって適合できます。

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

        V    = ( V  * a + b )(Mod c)
         N+1      N
    

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

例：

      +----+     +----+     +----+                      +----+
      | 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
    

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

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

線形合同（擬似乱数）生成器が解読されただけではなく、現在では、すべての多項式合同（擬似乱数）生成器を解読するためのテクニックが知られています。[KRAWCZYK]

4. 予測困難性 English

第 3 章 に記述された伝統的なセンスにおける乱雑性は、セキュリティ用途に要求される予測困難性と同等ではありません。

例えば、CRC 表からのもののような、広く利用可能な定数シーケンスの利用は、攻撃者に対して極めて弱いといえます。一旦、彼らが、それを学習、もしくは、推測したら、そのシーケンス [CRC] に基づいて、過去・未来の、すべてのセキュリティを破ることができます。ただし、この表の統計的特性に問題はありません。

下記の節は、いくつかの乱雑性を生成するテクニックと源泉の限界について記述しています。

4.1 時刻とシリアル番号についての問題 English

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

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

また、イーサネットアドレスのようなハードウェアのシリアル番号の使用は、人が推測するより少ないビットの固有性しか提供しない可能性があります。このような数は、通常、相当に構造化されており、部分フィールドは、制限された範囲の候補値のみ、もしくは、およその作成日や他のデータに基づいて容易に推測可能な値をもつ可能性があります。例えば、DEC （Digital Equipment Corporation）内の DEC のハードウェアに装着されたイーサーネットカードの大部分が DEC 自身によって製造された可能性は高く、これは、組み込まれたアドレスの範囲を顕著に制限します。

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

4.2 外部イベントのタイミングと内容English

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

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

（ネットワークパケットの到着時刻のような）他の外部イベントも、注意を払って使うことができます。特に、攻撃者によるこのような時刻の操作の可能性が考慮されなければなりません。

4.3 複雑な操作の誤りEnglish

予測困難性について、誤解を招く外観を与える可能性がある戦略の 1つは、極めて複雑なアルゴリズム（または、 秀逸な伝統的擬似乱数生成器を良い統計的特性とともに）を採用しながら、コンピュータシステム時計の現在値を種として、暗号技術的鍵を計算することです。 およそ、いつ、（擬似乱数）生成器が起動されたかを知った攻撃者は、システム時計のおよその値を知っているので、比較的少数の種の値をテストするだけでかまいません。多数の擬似的な乱雑なビット列が生成される可能性がありますが、攻撃者がチェックする必要がある検索空間は、極めて小さい可能性があります。

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

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

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

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

予測困難性について、誤解を招く外観を与える可能性があるその他の戦略は、データベースからの数の無作為な選択であり、「その強度は、そのデータベース中のビット総数に関連する」と想定することです。例えば、今日の典型的な USENET サーバーは、1日に 35 MB 以上の情報を処理します。「このデータ中の無作為な起点から 32 byte のデータを取り出すことによって、乱数が選択された」と想定します。この仮定からは、32*8 = 256 bit に相当する推測困難性は、生じません。「大部分のデータが自然言語であること（おそらく 1 byte あたり 2, 3 bit 程度の情報）」を許容しても、32*2.5 = 80 bit の推測困難性は、生じません。同じ 35 MB にアクセスできる攻撃者にとって、その推測困難性は、選択の起点についてのみです。この場合、推測困難性は、せいぜい約 25 bit です。

同じ議論は、CD-ROM 上のデータ、音声 CD 録音や、他のあらゆる大規模公衆データベースからシーケンスを選択することについてもいえます。攻撃者が同一のデータベースにアクセスできる場合、この「大量なデータからの選択」からは、ほとんど得るものはありません。しかし、選択が（活動している複数ユーザシステム上のシステムバッファのような）攻撃者がアクセスできないデータから行える場合、何らかの役に立つ可能性があります。

5. 乱雑性のためのハードウェア English

将来、小型の強い乱数生成器を期待することができるでしょうか？可能性は、あります。必要とされるのは、「推測困難な数の物理的源泉」がすべてです。

熱雑音、放射性崩壊、高速自走発振器が、そのトリックを直接、行います。[GIFFORD] これは、わずかな量のハードウェアであり、コンピュータシステムのアーキテクチャの標準部分として含めることが簡単にできます。さらに、回転ディスクをもつ、あらゆるシステム、もしくは、その類は、乱数生成のために適切な源泉をもちます。[DAVIS] 「『この小さな追加的ハードウェアと、それにアクセスするソフトウェアが必要不可欠であり、有用である』というコンピュータベンダー間における共通認識」が、必要とされるすべてです。

5.1 要求される量 English

どれくらいの予測困難性が必要とされるのでしょうか？要件を数値化すること（仮に、秒あたりの乱雑なビットの数）は、可能でしょうか？

その答えは、「さほど必要とされない」です。DES について、鍵は、56 bit であり、我々が第 8 章の中の例で示したように、最高のセキュリティシステムでさえ、200 bit 以上の鍵とする素材を要求する可能性は、あまりありません。一連の鍵が必要とされる場合、6.3 において説明したように、強い乱雑な種から、暗号技術的に強いシーケンスを使用することにより、これを生成できます。数百ビットの乱雑性が1日1回生成されるケースでも、このテクニックを使用することで十分です。たとえ、その乱数が1秒あたり1つという遅い速度で生成され、生成過程を並列化できない場合でも、高セキュリティアプリケーションでは、ときとして200秒の待ち時間に耐えられる必要があります。

これらの数値を達成するのは、簡単です。これは、人が反復的にコインを投げ上げることでも可能です。ほとんどあらゆるハードウェア処理は、はるかに速い可能性が高いです。

5.2 偏りについての感度 English

乱数の分散の型について、何らかの特定の要件があるでしょうか？良い知らせがあり、「その分散は、単型である必要がありません」。「性能に影響するほど『いかに単型から異なるか』についての保守的な見積もり」が、必要とされるすべてです。ビットストリームを平準化するための 2つのシンプルなテクニックが、次に述べられており、より強いテクニックは、下記 6.1.2 に記述されています。

5.2.1 平準化するためにストリームパリティを使う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 です。

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

                         N            N
        1/2 * ( ( p + q )  + ( p - q )  )
   および
                         N            N
        1/2 * ( ( p + q )  - ( p - q )  )
    

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

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

                       N
        1/2 * [1 + (2e) ]
   および
                       N
        1/2 * [1 - (2e) ]
    

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

                            N
        ( 0.5 + ( 0.5 * (2e)  ) )  <  0.5 + d
    

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

下記の表は、様々な程度の偏りについて、50：50 の比率から 0.001 以内になるようにするために試査対象としなければならない文字列の長さを提供しています。

Prob(1)	e	N
0.5  0.6  0.7  0.8  0.9  0.95  0.99	0.00 0.10 0.20 0.30 0.40 0.45 0.49	1 4 7 13 28 59 308

最後の行は、「たとえ分散が一方に 99% 偏っている場合でも、308 のサンプル文字列のパリティは、50：50 の比率から 0.001 以内となること」 を示しています。

5.2.2 平準化するために変換マッピングを使うEnglish

元々、Neumann [VON NEUMANN] に由来する、これ以外の他テクニックには、重複しない対のシーケンスとしてビット列を吟味するものあります。 このテクニックでは、00 または 11 の対が発見されたら、すべて無視し、01 を 0 に、10 を 1 に置き換えます。1 の確率が 0.5+e であり、0 の確率が 0.5-e です。ここで、e は、源泉の乖離率であり、前節において記述したものを想定します。このとき、各対の可能性は、下記のとおりです。：

            +------+-----------------------------------------+
            | ペア |              probability                |
            +------+-----------------------------------------+
            |  00  | (0.5 - e)^2          =  0.25 - e + e^2  |
            |  01  | (0.5 - e)*(0.5 + e)  =  0.25     - e^2  |
            |  10  | (0.5 + e)*(0.5 - e)  =  0.25     - e^2  |
            |  11  | (0.5 + e)^2          =  0.25 + e + e^2  |
            +------+-----------------------------------------+
    

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

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

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

5.2.3 平準化するために FFT を使う English

現実世界のデータが大きく偏ったビットや相関したビットから成るときでも、まだ、有用な量の乱雑性を含む可能性があります。この乱雑性を、離散フーリエ変換 （もしくは、その流儀である FFT）を利用することによって、取り出すことができます。

データをフーリエ変換することにより、強い相関関係を除去できます。適当なデータが処理され、残存する相関性を除去する場合、統計的独立性に近似するスペクトル曲線と、通常の分散の乱雑性を作り出すことができます。[BRILLINGER]

5.2.4 平準化するために圧縮を使うEnglish

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

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

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

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

5.3.1 手元の Sound/Video 入力を使うEnglish

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

例えば、Sun の SPARCstation において、「/dev/audio」のデバイスから、マイクジャックに何も挿さずに入力を得ることができます。ハードウェア故障の場合、何らかのチェック無しに、これを信頼してはいけませんが、このようなデータは、要するに、乱雑な雑音です。いかなる場合でも、他の箇所で記述されているように、 これは平準化される必要があります。

平準化するために圧縮と組み合わせることは、UNIX においては下記のようにすることによって可能であり、膨大な量の中程度の品質の乱雑なデータを生成できます。

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

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

ディスクドライブの回転速度には、無秩序な空気の乱気流による小さく乱雑な変動があります。[DAVIS] システムに低レベルのディスクシーク時間測定器を追加することによって、乱雑性を含む一連の測定結果が得られます。このようなデータは、通常、高度に相関しているので、FFT のような有意な処理が必要とされます。（5.2.3 参照。）それにもかかわらず、実験結果は、「（このような処理によって）ディスクドライブは、毎分 100 bit 以上の秀逸な乱雑なデータを易々と作り出すこと」を示しました。

この処理の必要性を部分的に補っているのは、「通常、ディスクドライブの故障は、すぐに気づかれる」という事実です。それゆえ、この乱数生成法については、ハードウェアの故障に起因する問題は、めったに起きません。

6. 推奨される非ハードウェア戦略English

信頼できるハードウェア源泉が無いとき、推測困難な乱数についての要件に適合するための最善の全体戦略は、どのようなものでしょうか？それは、「相関しない多数の源泉から乱雑な入力を入手し、強い攪拌関数によって、それらを攪拌すること」です。

このような関数は、たとえ結合されている他の数が固定であったり、もしくは、推測が容易であっても、あらゆる源泉にある乱雑性を確保します。ハードウェアは故障する可能性があるので、良いハードウェア源泉の場合でもこれを用いることは賢明です。しかし、ソフトウェア的な複雑さが追加されるので、全体が失敗する可能性が高まることも強調する必要があります。

6.1 攪拌関数 English

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

上記 5.2 において検討したように、0 もしくは 1 に偏ったビット列を、より乱雑な、より短いストリームに変換する問題を検討します。これは、単に、強い攪拌関数が望まれる他の事例で、 より少ない出力ビット列を作り出すために入力ビット列を攪拌します。多くのビット数のパリティを使う 5.2.1 において紹介したテクニックは、単に、それらの排他的論理和をとった結果です。これは、直下で、 卑近な攪拌関数として吟味されています。偏ったビットのストリームから、より多くの乱雑性を抜き出すための、より強い攪拌関数の利用は、6.1.2 において検討されています。

6.1.1 卑近な攪拌関数 English

1ビット入力についての卑近な一例は、排他的論理和関数です。これは、下表に示すように、パリティ無しの加算と等しくなります。これは、退化した事例です。ここでは、いずれかの入力ビットの変化にともなって、常に出力ビットが変化します。しかし、その単純さにかかわらず、これは有用な表を提供しています。

入力 1	入力 2	出力
0 0 1 1	0 1 0 1	0 1 1 0

「入力 1」と「入力 2」が相関せず、このように組み合わされる場合、「出力」は、入力よりも、さらに良い（偏りが少ない）乱雑なビットとなります。「乖離率」 e を上記 5.2 において規定したように想定する場合、下記のように、出力乖離率は、入力乖離率と関連します。：

        e       = 2 * e        * e
         output        input 1    input 2
    

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

e	0.00	0.10	0.20	0.30	0.40	0.50
0.00  0.10  0.20  0.30  0.40  0.50	0.00  0.00  0.00  0.00  0.00  0.00	0.00  0.02  0.04  0.06  0.08  0.10	0.00  0.04  0.08  0.12  0.16  0.20	0.00  0.06  0.12  0.18  0.24  0.30	0.00  0.08  0.16  0.24  0.32  0.40	0.00  0.10  0.20  0.30  0.40  0.50

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

6.1.2 より強い攪拌関数 English

米国政府の DES （Data Encryption Standard）[DES] は、複数 bit 数のための強い攪拌関数の一例です。これは、120 bit までの入力（64 bit の「データ」と 56 bit の「鍵」）を得て、64 bit の出力を作り出します。各出力ビットは、すべての入力ビット列に対する複雑な非線形関数の出力となります。この特徴をもつ他の強い暗号化関数も（すべての鍵とデータ入力ビットを攪拌することを考慮することによって）使うことができます。

これ以外にも、良い攪拌関数の例として、「メッセージダイジェスト」、米国政府の SHS （Secure Hash Standard） [SHS] や MD* シリーズ [MD2, MD4, MD5] のようなハッシュ関数があります。これらの関数すべては、任意の量の入力を受け取って、すべての入力ビット列を攪拌することによって、出力を作り出します。MD* シリーズは、128 bit の出力を、SHS は、160 bit の出力を作り出します。

メッセージダイジェスト関数は、可変量の入力のために設計されたものですが、DES や他の暗号化関数も、いかなる数の入力でも組み合わせるために使うことができます。出力として 64 bit が適切である場合、入力は、必要に応じて 0 をパディングして、64 bit のデータ量と連続した 56 bit の鍵にまとめることができ、これは、次に、DES を ECM （Electronic Codebook Mode）で使って連続的に暗号化するために使われます。[DES MODES] 64 bit 以上の出力が必要とされる場合、より複雑な攪拌を使います。例えば、入力が 3 つの数 A, B, C にまとめられる場合、まず、DESを使用し、Aを鍵Bで暗号化し、さらに鍵Cで暗号化して、出力の最初の部分を生成します。次に、Bを鍵A、鍵Cで暗号化して次の出力を生成します。さらに、必要な場合は、Cを鍵A、鍵Bで暗号化して残りの出力を得ます。この鍵の順番を逆にすれば、さらに多くの出力を得られます。同様のことが、複数の出力を作り出すために、入力データの様々な部分群をハッシュ化することによって、ハッシュ関数について行えます。 しかし、「入力された以上の『乱雑性』をもつビット列を出力することは、不可能であること」を銘記してください。

強い攪拌関数使用の一例は、99% のビットが 0 に偏っている 308 bit の文字列の事例を再考することです。上記 5.2.1 で紹介したパリティテクニックは、これを 0 と 1 の確率が等しい状態からたった 1/1000 だけ異なる 1 bit に偏りを低減しました。しかし、第 2 章において述べた情報量についての式を適用すると、この 308 bit シーケンスは、5 bit の情報量をもちます。それゆえ、その文字列のパリティを計算することによって得られる1ビットと比べ、これを SHS または MD5 でハッシュ化し、その結果の末尾 5 bit をとることによって、歪みの無い乱雑な 5 bitが生成されます。

6.1.3 攪拌関数としての Diffie-Hellman English

Diffie-Hellman 鍵共有は、2 者間において共有された秘密を生み出すテクニックです。これは、たとえ第 3 者が 2 つの通信主体間のすべてのメッセージを観察できる場合でも、それを解読することが計算量的に現実的でないようにできます。この共有された秘密は、各々によって生成された初期値を攪拌したものです。[D-H] これらの初期値が乱雑である場合、共有された秘密は、両者の組み合わされた乱雑性を含みます。ここで、両者は相関していないことが想定されています。

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

攪拌関数について入力より短いビット列を作り出すことは必要不可欠ではありませんが、拡散されたビット列は、乱雑性の予測困難性を、入力にあった以上に「高める」ことはできません。それゆえ、各々 12 bit 相当の予測困難性をもつ 4 つの 32 bit 入力は、（4,096 の同等に可能性ある値のように）48 bit 相当以上の予測困難な出力を作り出すことはできません。例えば、連続した整数を攪拌することによって、出力を数百または数千ビットまでも延長することができますが、賢い攻撃者の検索空間は、2 の 48 乗の可能性のままです。さらに、入力のビット数よりも少ないビットに攪拌する（前の 2 bit から 1 bit の排他的論理和を求めるやり方）は、出力の乱雑性を高める傾向があります。

6.1.1 にある最後の表は、「乱雑なビットについて固定ビットと排他的論理和をとって攪拌することによって乱雑なビットを作り出すこと」を示します。これは、真実ですが、乱雑な 1 bit を 1 bit 以上に「延長」するやり方は提供しません。例えば、乱雑なビットが 0 と攪拌され、次に 1 と攪拌された場合、これは、2 bit のシーケンスを作り出しますが、これは、常に 01 か 10 となります。2 つの候補値しかないので、当初の 1 bit の乱雑性しか無いままです。

6.1.5 攪拌関数を選択する際の他の要素 English

米国内利用に関して、DES は、「欠陥について広くテストされている、よく文書化されている、anonymous FTP から入手可能なソースコードを含めて、世界中で入手可能なハードウェア・ソフトウェアに広く実装されている」という点で優勢性を持ちます。SHS と MD* 系ファミリーは、DES ほどはテストされていない、より新しいアルゴリズムですが、それらに欠陥があると信じる確たる根拠はありません。MD5 と SHS の両方は、以前の MD4 アルゴリズムに由来します。これらすべてには、FTP によって入手可能なソースコードがあります。[SHS, MD2, MD4, MD5]

DES と SHS は、（主要な部分が秘密のままとされている政策判断に基づいて）米国 NSA （National Security Agency）が引き受けています。これが多くの憶測や疑念の原因ですが、数年に渡った DES についての調査結果は、「当初、IBM が行った設計についての NSA の関与は、主に、それを強化するためのものであったこと」を示しました。DES について、隠されているまたは特別な弱点、発見されていません。「同様に、SHS を作り出すための MD4 に対する NSA による改変は、おそらく公開鍵暗号技術のコミュニティにおいて、 まだ知られていない脅威に対して、このアルゴリズムを強化したこと」は、ほぼ確かです。

DES, SHS, MD4 および MD5 は、すべての目的について、ロイヤリティは無償です。MD2 は、PEM （Privacy Enhanced Mail）に組み込む非営利の用途のみ、無償でライセンスされました[PEM]。 MD* 系アルゴリズムにおいて、（「三匹の熊」（トルストイ）になぞらえて）「MD2 は強いが遅く、MD4 は速いが弱すぎ、MD5 がちょうど良い」と信じる人がいます。

MD* 系の（もしくは同類の）ハッシュアルゴリズムの、暗号化アルゴリズムに対するその他の優位性は、「それらは、暗号化／復号機能をもつソフトウェアやハードウェアの無許可の輸出入を規制している、従前の米国政府によって提起されている規制の対象とされていないこと」です。同様のことが、不可逆ハッシュ結果を作り出す DES についてもいえる必要がありますが、大部分の DES パッケージは、復号可能（可逆）な暗号化を指向しています。

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

攪拌する入力の最善の源泉は、気流によって影響を受けるディスクドライブ、熱雑音のある音声入力、もしくは、放射性崩壊のようなハードウェアによる乱雑性です。しかし、それが入手不能な場合、他の可能性はあります。これは、システム時計、システムバッファや入力／出力バッファ、ユーザ／システム／ハードウェア／ネットワークのシリアル番号、かつ／または、アドレスやタイミング、およびユーザ入力を含みます。残念ながら、これらの源泉のいずれも、一定の環境下で、制限された値、または、予測可能な値しか作り出すことができません。

上記の源泉には、複数ユーザシステムについての極めて強いものがあります。ここで、本質的に、システムの各ユーザが、乱雑性の源泉です。しかし、（典型的な IBM PC もしくは Apple Macintosh のような）小さな単一ユーザシステムにおいては、攻撃者が同様の設定を再現できる可能性があります。これは、攻撃者が網羅的な検索を行うことを現実的にするのに有用な攪拌過程への入力として、オリジナルと十分に相関するものを与える可能性があります。

強い攪拌関数を伴う複数の乱雑な入力の利用が推奨され、いかなる特定の入力における弱点をも克服できます。例えば、要求された「乱雑な」ユーザ打鍵のタイミングと内容は、数百の乱雑なビット列を生成できますが、保守的な想定がなされる必要があります。例えば、数ビットの乱雑性を想定し、一連の打鍵間の間隔が、その乱雑性を満たすほど固有な場合、打鍵が固有であれば同様の想定ができますが、初期鍵値や、以前の値とタイミングか鍵値が重複する場合には、乱雑なビット列が無いものと想定します。これらのタイミングを攪拌した結果とタイプされた文字は、さらに時計の値や他の入力と組み合わされる可能性があります。

たとえ入力に、ある標的システムについて極めて弱いものがある場合でも、この戦略によって、セキュリティのための良い乱数を作り出すための実践的な小さなコードが得られる可能性があります。しかし、特に攻撃者がかつて生成過程を観察できた場合は、小さな単一ユーザシステムについての高等な攻撃に対して、失敗する可能性があります。ハードウェアに基づく乱雑性の源泉の方が、まだ好ましいでしょう。

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

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

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

「鍵値のシーケンスを生成するためのテクニックが十分に速い場合、これを卑近なものとして、守秘性保護システムのための基礎として使うことができること」は、覚えておく必要があります。2 者が同一のシーケンス生成テクニックを使い、同一の種とする素材を入れる場合、それらは、同一のシーケンスを生成します。排他的論理和の可逆性によって、例えば、一方が送信したデータの排他的論理和がとられて暗号化され、受け取ったこのデータについて排他的論理和をとって復号できます。

6.3.1 伝統的に強いシーケンス English

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

暗号化された出力値の部分または全部を次の呼び出しのために暗号化されるべき値に暗号化し、フィードバックするために、乱雑な鍵と種値をもつ「暗号化」アルゴリズムを使うことも可能です。適切なフィードバックテクニックは、通常、暗号化アルゴリズムと共に推奨されます。一例は、下図に示されています。ここで、その暗号出力フィードバックを組み合わせるために、シフトとマスクが使われます。この種のフィードバックは、DES と組み合わされて、米国政府によって推奨されています。[DES MODES]

      +---------------+
      |       V       |
      |  |     n      |
      +--+------------+
            |      |           +---------+
            |      +---------> |         |      +-----+
         +--+                  | Encrypt | <--- | 鍵  |
         |           +-------- |         |      +-----+
         |           |         +---------+
         V           V
      +------------+--+
      |      V     |  |
      |       n+1     |
      +---------------+
    

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

Donald W. Davies によって、「この種のシフトされた部分的出力フィードバックは、出力ビット列を入力としてフィードバックすることと比べて、アルゴリズムを顕著に弱くすること」が示されました。特に、DES について、64 bit 全体の暗号化の繰り返しは、約 2 の 63 乗回の繰り返しをもたらすことでしょう。（0 より大きく） 64 bit 未満をフィードバックすることは、2**31 と 2**32 の間の回数の繰り返しをもたらすことでしょう！

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

6.3.2 Blum Blum Shub 生成器English

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

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

                   2
        s    =  ( x  )(Mod n)
         0

                   2
        s    = ( s   )(Mod n)
         i+1      i
    

各 s の底から数ビットだけを使うように注意しなければなりません。最低位順のビットのみを使うことが常に安全です。次式を越える低位ビットを使う場合、 

                  log  ( log  ( s  ) )
                     2      2    i
    

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

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

                     i
               ( ( 2  )(Mod (( p - 1 ) * ( q - 1 )) ) )
      s  = ( s                                          )(Mod n)
       i      0
    

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

7. 鍵生成標準 English

現在、鍵の生成に関するいくつかの公的標準が存在する。これらのうち、2 つのものが、以下に記述されています。両者は、DES を使いますが、あらゆる同等以上に強い攪拌関数が代替できます。

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

米国国防総省は、パスワード生成についての特定の推奨事項をもっています[DoD] 。国防総省は、下記のように、米国 DES （Data Encryption Standard） [DES] を Output Feedback Mode [DES MODES] で使うことを推奨しています。：

初期ベクトル（initialization vector）の決定に、システム時計、システム ID、ユーザ ID および日付と時刻を使います。； システム割り込みレジスタ、システム状態レジスタ、およびシステムカウンタによって決定される鍵を使います。； 平文として、システム管理者によって打たれた 8 文字のような、外部で乱雑に生成された 64 bit の数を使います。

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

7.2 X9.17 鍵生成 English

ANSI （American National Standards Institute）は、下記のように、鍵のシーケンスを生成するための手法を仕様としています。：

        s  は、64 bit の初期種です。
         0

        g  は、生成された 64 bit の鍵のシーケンスです。
         n

        k は、この鍵シーケンスを生成するために確保された乱雑な鍵です。

        t は、鍵ができる限り長く（最高 64 bit）生成された時刻です。

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

        g    = DES ( k, DES ( k, t ) .xor. s  )
         n                                  n

        s    = DES ( k, DES ( k, t ) .xor. g  )
         n+1                                n
    

下付nを伴うg が DES 鍵として使われる場合、各 8 bit は、その使用のパリティのために微調整される必要がありますが、64 bit 全体の、調整されていない g が、次の s を計算する際に使われる必要があります。

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

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

8.1 パスワード生成  English

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

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

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

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

8.2 極めて高いセキュリティの暗号技術的な鍵  English

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

8.2.1 鍵を試すのに費やす労力 English

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

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

8.2.2 中間一致攻撃 English

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

「中間一致攻撃」をかなり単純化した説明は、下記のとおりです。： 攻撃者は、既知平文もしくは選択平文を、すべての前半用鍵の候補で半分暗号化し、出力を並べ替え、それらの暗号文を、すべての後半用の鍵候補で半分復号することができます。一致が発見された場合、鍵全体は、両半分の鍵から組み立てることができ、メッセージの他の部分や他のメッセージを復号するのに使うことができます。この種の攻撃は、その最善のとき、 攻撃者に要求される作業量の指数を半分にすることができます。一方、多くはありますが、概ね一定の追加的労力を要します。これに対する安全性が保証されるためには、鍵中の乱雑性の量を倍加し、最低限102 bit とすることが要求されます。

中間一致攻撃は、「当該暗号アルゴリズムが、このように構成部分に分解できること」を想定しますが、我々は、アルゴリズムの深い知識無しに、規定しきることはできません。たとえ基本的なアルゴリズムが「中間一致攻撃」の標的でない場合においても、基本的アルゴリズムを 2回（もしくは、2つの異なるアルゴリズムを順番に)異なる鍵で適用することによって、より強いアルゴリズムを作り出す試みは、期待していたほどセキュリティを高められない可能性があります。このような組み合わされたアルゴリズムは、「中間一致攻撃」の標的となります。

「中間一致攻撃」をしかけるためには、莫大な資源が要求される可能性がありますが、それらは、おそらく、主要国の国家安全保障サービスの範囲内でしょう。要するに、すべての国は他国政府のやり取りについて諜報活動を行っていて、一部の国は経済的優位性のために商用のやり取りについても諜報活動を行っていると信じられています。

8.2.3 他の考慮事項 English

特別な目的の暗号解読ハードウェアの可能性や、上記の想定にどの程度の安全上のマージンを見込むかについて、これまで我々は考慮して来ませんでしたが、おそらく、極めて高いセキュリティの暗号技術的鍵のための最低線は、128 bit の乱雑性であり、これは、最低限 128 bit の鍵長を意味します。2 者が Diffie-Hellman 鍵共有 [D-H] に合意する場合、原則として、たった半分のこの乱雑性が、両者によって提供される必要があります。しかし、おそらく、彼らの乱雑な入力の間には何らかの相関関係があるので、おそらく、「Diffie-Hellman が使われている場合、各者は、極めて高いセキュリティのためには、少なくとも、96 bit 相当の乱雑性を提供する必要がある」と想定するのに越したことはありません。

この乱雑性の量は、米国国防総省がパスワードの生成において推奨する入力の制限を超えており、ユーザの打鍵タイミング、ハードウェア乱数生成器または他の源泉が必要となります。

「上記のような鍵長の計算については、議論の余地があり、使われている暗号アルゴリズムについての様々な仮定に依拠すること」が銘記される必要があります。場合によっては、暗号解読テクニックと、使われているアルゴリズムの強度についての深い知識をもつプロフェッショナルが、上記の半分以下の鍵長で満足することがあります。

9. 結論 English

セキュリティ用途の推測困難な「乱雑な」秘密の数を生成することは、肝要ですが、困難な作業です。

我々は、「このような乱雑性を作り出すハードウェアによるテクニックは、比較的単純であること」を示しました。特に、量と品質は、高い必要が無く、（ディスクドライブのような）手元のコンピュータのハードウェアを使うことができます。計算テクニックを利用すると、複数源泉からの低品質の乱数、または単一源泉からの低品質の大量の入力を処理して、高品質かつ予測困難性の高い少量の鍵素材を作り出すことができます。乱雑性のハードウェア源泉が無いとき、しばしば、様々なユーザとソフトウェアの源泉を、代わりに注意を払って使うことができます。； しかし、大部分の現代のシステムは、既に、ディスクドライブや音声入力のようなハードウェアをもっています。これらは、高品質の乱雑性を作り出すために使うことができます。

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

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

本書の全体が、パスワード、暗号技術的な鍵、および同様なセキュリティ用途に使う推測困難な乱数の生成のためのテクニックと推奨事項に関するものです。

参考文献

[ASYMMETRIC] - Secure Communications and Asymmetric Cryptosystems, edited by Gustavus J. Simmons, AAAS Selected Symposium 69, Westview Press, Inc.

[BBS] - A Simple Unpredictable Pseudo-Random Number Generator, SIAM Journal on Computing, v. 15, n. 2, 1986年 5月, L. Blum, M. Blum, & M. Shub.

[BRILLINGER] - Time Series: Data Analysis and Theory, Holden-Day, 1981年, David Brillinger.

[CRC] - C.R.C. Standard Mathematical Tables, Chemical Rubber Publishing Company.

[CRYPTO1] - Cryptography: A Primer, A Wiley-Interscience Publication, John Wiley & Sons, 1981年, Alan G. Konheim.

[CRYPTO2] - Cryptography: A New Dimension in Computer Data Security, A Wiley-Interscience Publication, John Wiley & Sons, 1982, Carl H. Meyer & Stephen M. Matyas.

[CRYPTO3] - Applied Cryptography: Protocols, Algorithms, and Source Code in C, John Wiley & Sons, 1994年, Bruce Schneier.

[DAVIS] - Cryptographic Randomness from Air Turbulence in Disk Drives, Advances in Cryptology - Crypto '94, Springer-Verlag Lecture Notes in Computer Science #839, 1984年, Don Davis, Ross Ihaka, and Philip Fenstermacher.

[DES] - Data Encryption Standard, United States of America, Department of Commerce, National Institute of Standards and Technology, Federal Information Processing Standard (FIPS) 46-1.
- Data Encryption Algorithm, American National Standards Institute, ANSI X3.92-1981.
（FIPS 112, Password Usage, which includes FORTRAN code for performing DES も参照。）

[DES MODES] - DES Modes of Operation, United States of America, Department of Commerce, National Institute of Standards and Technology, Federal Information Processing Standard (FIPS) 81.
- Data Encryption Algorithm - Modes of Operation, American National Standards Institute, ANSI X3.106-1983.

[D-H] - New Directions in Cryptography, IEEE Transactions on Information Technology, 1976年11月, Whitfield Diffie and Martin E. Hellman.

[DoD] - Password Management Guideline, United States of America, Department of Defense, Computer Security Center, CSC-STD-002-85.
（FIPS 112, Password Usage, which incorporates CSC-STD-002-85 as one of its appendices も参照。）

[GIFFORD] - Natural Random Number, MIT/LCS/TM-371, 1988年 9月, David K. Gifford

[KNUTH] - The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Chapter 3: Random Numbers. Addison Wesley Publishing Company, 2nd Edition 1982, Donald E. Knuth.

[KRAWCZYK] - How to Predict Congruential Generators, Journal of Algorithms, V. 13, N. 4, 1992年12月, H. Krawczyk

[MD2] - The MD2 Message-Digest Algorithm, RFC1319, 1992年 4月, B. Kaliski
[MD4] - The MD4 Message-Digest Algorithm, RFC1320, 1992年 4月, R. Rivest
[MD5] - The MD5 Message-Digest Algorithm, RFC1321, 1992年 4月, R. Rivest

[PEM] - RFC 1421 から RFC 1424 まで。：

• RFC 1424, Privacy Enhancement for Internet Electronic Mail: Part IV: Key Certification and Related Services, 02/10/1993, B. Kaliski
• RFC 1423, Privacy Enhancement for Internet Electronic Mail: Part III: Algorithms, Modes, and Identifiers, 02/10/1993, D. Balenson
• RFC 1422, Privacy Enhancement for Internet Electronic Mail: Part II: Certificate-Based Key Management, 02/10/1993, S. Kent
• RFC 1421, Privacy Enhancement for Internet Electronic Mail: Part I: Message Encryption and Authentication Procedures, 02/10/1993, J. Linn

[SHANNON] - The Mathematical Theory of Communication, University of Illinois Press, 1963年, Claude E. Shannon. (originally from: Bell System Technical Journal, 1948年 7月と10月)

[SHIFT1] - Shift Register Sequences, Aegean Park Press, Revised Edition 1982年, Solomon W. Golomb.

[SHIFT2] - Cryptanalysis of Shift-Register Generated Stream Cypher Systems, Aegean Park Press, 1984年, Wayne G. Barker.

[SHS] - Secure Hash Standard, United States of American, National Institute of Science and Technology, Federal Information Processing Standard (FIPS) 180, 1993年4月.

[STERN] - Secret Linear Congruential Generators are not Cryptograhically Secure, Proceedings of IEEE STOC, 1987年, J. Stern.

[VON NEUMANN] - Various techniques used in connection with random digits, von Neumann's Collected Works, Vol. 5, Pergamon Press, 1963年, J. von Neumann.

著者のアドレス

Donald E. Eastlake 3rd
Digital Equipment Corporation
550 King Street, LKG2-1/BB3
Littleton, MA 01460

電話： +1 508 486 6577(w) +1 508 287 4877(h)
EMail： dee＠lkg.dec.com

Stephen D. Crocker
CyberCash Inc.
2086 Hunters Crest Way
Vienna, VA 22181

電話： +1 703-620-1222(w) +1 703-391-2651 (fax)
EMail： crocker＠cybercash.com

Jeffrey I. Schiller
Massachusetts Institute of Technology
77 Massachusetts Avenue
Cambridge, MA 02139

電話： +1 617 253 0161(w)
EMail： jis＠mit.edu

翻訳者のアドレス

宮川 寧夫
情報処理振興事業協会
セキュリティセンター

EMail： miyakawa＠ipa.go.jp