RFC1750 日本語訳
1750 Randomness Recommendations for Security. D. Eastlake 3rd, S.Crocker, J. Schiller. December 1994. (Format: TXT=73842 bytes) (Obsoleted by RFC4086) (Status: INFORMATIONAL)
プログラムでの自動翻訳です。
RFC一覧
英語原文
Network Working Group D. Eastlake, 3rd
Request for Comments: 1750 DEC
Category: Informational S. Crocker
Cybercash
J. Schiller
MIT
December 1994
ワーキンググループのD.イーストレーク、コメントを求める第3要求をネットワークでつないでください: 1750年12月のカテゴリ: 情報のS.の医者サイバーキャッシュJ.シラーMIT1994年12月
Randomness Recommendations for Security
セキュリティのための偶発性推薦
Status of this Memo
このMemoの状態
This memo provides information for the Internet community. This memo does not specify an Internet standard of any kind. Distribution of this memo is unlimited.
このメモはインターネットコミュニティのための情報を提供します。 このメモはどんな種類のインターネット標準も指定しません。 このメモの分配は無制限です。
Abstract
要約
Security systems today are built on increasingly strong cryptographic algorithms that foil pattern analysis attempts. However, the security of these systems is dependent on generating secret quantities for passwords, cryptographic keys, and similar quantities. The use of pseudo-random processes to generate secret quantities can result in pseudo-security. The sophisticated attacker of these security systems may find it easier to reproduce the environment that produced the secret quantities, searching the resulting small set of possibilities, than to locate the quantities in the whole of the number space.
今日のセキュリティシステムはホイルパターン解析が試みるますます強い暗号アルゴリズムに構築されます。 しかしながら、これらのシステムのセキュリティはパスワード、暗号化キー、および同様の量のために秘密の量を発生させるのに依存しています。 秘密の量を発生させる擬似ランダムの過程の使用は疑似セキュリティをもたらすことができます。 これらのセキュリティシステムの洗練された攻撃者は、秘密の量を生産した環境を再生させるのが、より簡単であることがわかるかもしれません、結果として起こる小さい可能性を捜して、数のスペースの全体における量の場所を見つけるより。
Choosing random quantities to foil a resourceful and motivated adversary is surprisingly difficult. This paper points out many pitfalls in using traditional pseudo-random number generation techniques for choosing such quantities. It recommends the use of truly random hardware techniques and shows that the existing hardware on many systems can be used for this purpose. It provides suggestions to ameliorate the problem when a hardware solution is not available. And it gives examples of how large such quantities need to be for some particular applications.
才略にたけて動機づけられた敵をくじくために無作為の量を選ぶのは驚くほど難しいです。 この論文はそのような量を選ぶのに伝統的な擬似乱数世代のテクニックを使用する際に多くの落とし穴を指摘します。 それは、本当に無作為のハードウェアのテクニックの使用を推薦して、このために多くのシステムの上の既存のハードウェアを使用できるのを示します。 それは、ハードウェア解決が利用可能でないときに、問題を改善するために提案を提供します。 そして、それはいくつかの特定用途のためのそのような量が、どれくらい大きい必要があるかに関する例を出します。
Eastlake, Crocker & Schiller [Page 1] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[1ページ]RFC1750偶発性推薦
Acknowledgements
承認
Comments on this document that have been incorporated were received from (in alphabetic order) the following:
(アルファベット順に)以下からこのドキュメントの法人組織であったコメントを受けました:
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)
デヴィッドM.Balenson(TIS)ドン・銅細工師(IBM)ドン・T.デイヴィス・(コンサルタント)カール・エリソン・(層雲)マーク・ホロビッツ(MIT)のクリスチャンのHuitema(INRIA)チャーリー・カウフマン・(虹彩)スティーブ・ケント(BBN)・ハル・マレー(12月)・ニール・ハラー(Bellcore)・リチャード・ピトキン(12月)・ティム・レッドモンド(TIS)ダグTygar(米カーネギーメロン大学)
Table of Contents
目次
1. Introduction........................................... 3 2. Requirements........................................... 4 3. Traditional Pseudo-Random Sequences.................... 5 4. Unpredictability....................................... 7 4.1 Problems with Clocks and Serial Numbers............... 7 4.2 Timing and Content of External Events................ 8 4.3 The Fallacy of Complex Manipulation.................. 8 4.4 The Fallacy of Selection from a Large Database....... 9 5. Hardware for Randomness............................... 10 5.1 Volume Required...................................... 10 5.2 Sensitivity to Skew.................................. 10 5.2.1 Using Stream Parity to De-Skew..................... 11 5.2.2 Using Transition Mappings to De-Skew............... 12 5.2.3 Using FFT to De-Skew............................... 13 5.2.4 Using Compression to De-Skew....................... 13 5.3 Existing Hardware Can Be Used For Randomness......... 14 5.3.1 Using Existing Sound/Video Input................... 14 5.3.2 Using Existing Disk Drives......................... 14 6. Recommended Non-Hardware Strategy..................... 14 6.1 Mixing Functions..................................... 15 6.1.1 A Trivial Mixing Function.......................... 15 6.1.2 Stronger Mixing Functions.......................... 16 6.1.3 Diff-Hellman as a Mixing Function.................. 17 6.1.4 Using a Mixing Function to Stretch Random Bits..... 17 6.1.5 Other Factors in Choosing a Mixing Function........ 18 6.2 Non-Hardware Sources of Randomness................... 19 6.3 Cryptographically Strong Sequences................... 19
1. 序論… 3 2. 要件… 4 3. 伝統的な擬似ランダム系列… 5 4. 予測不可能性… 7 時計と通し番号に関する4.1の問題… 7 4.2 外部の出来事のタイミングと内容… 8 4.3 複雑な操作の誤り… 8 4.4 大容量データベースからの選択の誤り… 9 5. 偶発性のためのハードウェア… 10 5.1 ボリュームが必要です… 10 歪曲する5.2感度… 10 5.2 .1 反-歪曲する流れの同等を使用します… 11 5.2 .2 反-歪曲する変遷マッピングを使用します… 12 5.2 .3 反-歪曲する高速フーリエ変換を使用します… 13 5.2 .4 反-歪曲する圧縮を使用します… 13 5.3 偶発性に既存のハードウェアを使用できます… 14 5.3 .1 既存の音/ビデオ入力を使用します… 14 5.3 .2 既存のディスクドライブを使用します… 14 6. お勧めの非ハードウェア戦略… 14 6.1 混合は機能します… 15 6.1 .1 些細な混合機能… 15 6.1 .2 より強い混合は機能します… 16 6.1 .3 混合としてのDiffヘルマンFunction… 17 6.1 混合を使用する.4が伸び無作為のビットに機能します… 17 6.1 .5 混合を選ぶ他の要素は機能します… 18 6.2 偶発性の非ハードウェア源… 19、6.3、暗号で、強い系列… 19
Eastlake, Crocker & Schiller [Page 2] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[2ページ]RFC1750偶発性推薦
6.3.1 Traditional Strong Sequences....................... 20 6.3.2 The Blum Blum Shub Sequence Generator.............. 21 7. Key Generation Standards.............................. 22 7.1 US DoD Recommendations for Password Generation....... 23 7.2 X9.17 Key Generation................................. 23 8. Examples of Randomness Required....................... 24 8.1 Password Generation................................. 24 8.2 A Very High Security Cryptographic Key............... 25 8.2.1 Effort per Key Trial............................... 25 8.2.2 Meet in the Middle Attacks......................... 26 8.2.3 Other Considerations............................... 26 9. Conclusion............................................ 27 10. Security Considerations.............................. 27 References............................................... 28 Authors' Addresses....................................... 30
6.3.1 伝統的な強い系列… 20 6.3 .2 ブルームブルームシューブ系列ジェネレータ… 21 7. キー生成規格… 22 7.1 パスワード世代米国のDoD推薦… 23 7.2 X9.17キー生成… 23 8. 偶発性の例が必要です… 24 8.1パスワード世代… 24 8.2 非常に高いセキュリティ暗号化キー… 25 8.2 主要なトライアルあたりの.1の努力… 25 8.2 .2 中央攻撃では、会ってください… 26 8.2 他の.3の問題… 26 9. 結論… 27 10. セキュリティ問題… 27の参照箇所… 28人の作者のアドレス… 30
1. Introduction
1. 序論
Software cryptography is coming into wider use. Systems like Kerberos, PEM, PGP, etc. are maturing and becoming a part of the network landscape [PEM]. These systems provide substantial protection against snooping and spoofing. However, there is a potential flaw. At the heart of all cryptographic systems is the generation of secret, unguessable (i.e., random) numbers.
ソフトウェア暗号は普及しています。 ケルベロスのようなシステム、PEM、PGPなどは熟して、ネットワーク[PEM]風景の一部になっています。 これらのシステムは詮索とスプーフィングに対するかなりの保護を提供します。 しかしながら、潜在的欠点があります。 秘密の、そして、「蹄-可能」な(すなわち、無作為の)数の世代はすべての暗号のシステムの中心です。
For the present, the lack of generally available facilities for generating such unpredictable numbers is an open wound in the design of cryptographic software. For the software developer who wants to build a key or password generation procedure that runs on a wide range of hardware, the only safe strategy so far has been to force the local installation to supply a suitable routine to generate random numbers. To say the least, this is an awkward, error-prone and unpalatable solution.
当分、そのような予測できない数を発生させるための一般に利用可能な施設の不足は暗号ソフトウェアの設計で開いている傷です。 さまざまなハードウェアで動くキーかパスワード世代手順を組立てたがっているソフトウェア開発者に関しては、今までのところの唯一の安全な戦略は、現地搬入を行ったことにさせるのであることがあります適当なルーチンを供給するために乱数を発生させるように。 控えめに言っても、これは無器用で、誤り傾向があってまずい溶液です。
It is important to keep in mind that the requirement is for data that an adversary has a very low probability of guessing or determining. This will fail if pseudo-random data is used which only meets traditional statistical tests for randomness or which is based on limited range sources, such as clocks. Frequently such random quantities are determinable by an adversary searching through an embarrassingly small space of possibilities.
要件がデータのためのものであることを覚えておくために、敵には推測か決定の非常に低い確率があるのは、重要です。 擬似ランダムデータが使用されていると、これは失敗するでしょう(偶発性のための伝統的な統計的検査法を満たすだけであるか、または限られた範囲ソースに基づいています)、時計などのように。 頻繁に、そのような無作為の量は可能性の面くらわせるように小さいスペースを隅々まで捜している敵が決定できます。
This informational document suggests techniques for producing random quantities that will be resistant to such attack. It recommends that future systems include hardware random number generation or provide access to existing hardware that can be used for this purpose. It suggests methods for use if such hardware is not available. And it gives some estimates of the number of random bits required for sample
この情報のドキュメントはそのような攻撃に抵抗力があるようになる無作為の量を生産するためのテクニックを示します。 それは、将来のシステムがハードウェア乱数発生を含んでいるか、またはこのために使用できる既存のハードウェアへのアクセスを提供することを勧めます。 そのようなハードウェアが利用可能でないなら、それは使用のための方法を示します。 そして、それはサンプルに必要である無作為のビットの数のいくつかの見積りを与えます。
Eastlake, Crocker & Schiller [Page 3] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[3ページ]RFC1750偶発性推薦
applications.
アプリケーション。
2. Requirements
2. 要件
Probably the most commonly encountered randomness requirement today is the user password. This is usually a simple character string. Obviously, if a password can be guessed, it does not provide security. (For re-usable passwords, it is desirable that users be able to remember the password. This may make it advisable to use pronounceable character strings or phrases composed on ordinary words. But this only affects the format of the password information, not the requirement that the password be very hard to guess.)
今日のたぶん最も一般的に遭遇した偶発性要件はユーザパスワードです。 通常、これは簡単な文字列です。 明らかに、パスワードを推測できるなら、それはセキュリティを提供しません。 (再使用可能なパスワードに関しては、ユーザがパスワードを覚えていることができるのは、望ましいです。 これで、発音可能な文字列か普通の単語で構成された句を使用するのは賢明になるかもしれません。 しかし、これは要件ではなく、パスワードは非常に推測しにくいというパスワード情報の形式に影響するだけです。)
Many other requirements come from the cryptographic arena. Cryptographic techniques can be used to provide a variety of services including confidentiality and authentication. Such services are based on quantities, traditionally called "keys", that are unknown to and unguessable by an adversary.
他の多くの要件が暗号のアリーナから来ます。 秘密性と認証を含むさまざまなサービスを提供するのに暗号のテクニックを使用できます。 そのようなサービスは伝統的に「キー」と呼ばれる敵で未知の、そして、「蹄-可能」な量に基づいています。
In some cases, such as the use of symmetric encryption with the one time pads [CRYPTO*] or the US Data Encryption Standard [DES], the parties who wish to communicate confidentially and/or with authentication must all know the same secret key. In other cases, using what are called asymmetric or "public key" cryptographic techniques, keys come in pairs. One key of the pair is private and must be kept secret by one party, the other is public and can be published to the world. It is computationally infeasible to determine the private key from the public key [ASYMMETRIC, CRYPTO*].
1個の時間パッド[CRYPTO*]か米国データ暗号化規格[DES]との左右対称の暗号化の使用などのいくつかの場合では、秘密認証で交信したがっているパーティーは皆、同じ秘密鍵を知らなければなりません。 他の場合では、使用して、入って、何が非対称か「公開鍵」暗号のテクニック、キーと呼ばれるか対にされます。 組の1個のキーを個人的であり、1回のパーティーが秘密にしなければならなくて、もう片方は、公共であり、世界に発行できます。 公開鍵[ASYMMETRIC、CRYPTO*]から秘密鍵を決定するのは計算上実行不可能です。
The frequency and volume of the requirement for random quantities differs greatly for different cryptographic systems. Using pure RSA [CRYPTO*], random quantities are required when the key pair is generated, but thereafter any number of messages can be signed without any further need for randomness. The public key Digital Signature Algorithm that has been proposed by the US National Institute of Standards and Technology (NIST) requires good random numbers for each signature. And encrypting with a one time pad, in principle the strongest possible encryption technique, requires a volume of randomness equal to all the messages to be processed.
無作為の量のための要件の頻度とボリュームは異なった暗号のシステムのために大きな開きがあります。主要な組が発生しますが、その後偶発性の少しもさらなる必要性なしでいろいろなメッセージにサインできるとき、純粋なRSA[CRYPTO*]を使用して、無作為の量が必要です。 米国米国商務省標準技術局(NIST)によって提案された公開鍵Digital Signature Algorithmは各署名のために良い乱数を必要とします。 そして、1個の時間パッドによるコード化(原則として可能な限り強い暗号化のテクニック)はすべての処理されるべきメッセージと等しい偶発性のボリュームを必要とします。
In most of these cases, an adversary can try to determine the "secret" key by trial and error. (This is possible as long as the key is enough smaller than the message that the correct key can be uniquely identified.) The probability of an adversary succeeding at this must be made acceptably low, depending on the particular application. The size of the space the adversary must search is related to the amount of key "information" present in the information theoretic sense [SHANNON]. This depends on the number of different
これらの場合の大部分では、敵は試行錯誤で「秘密」のキーを決定しようとすることができます。 (キーが唯一正しいキーを特定できるというメッセージより小さく十分である限り、これは可能です。) 特定用途によって、敵がこれで成功するという確率を許容できて低くしなければなりません。 敵が捜さなければならないスペースのサイズは情報の理論的な意味[シャノン]における現在の主要な「情報」の量に関連します。 これは異なることの数に依存します。
Eastlake, Crocker & Schiller [Page 4] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[4ページ]RFC1750偶発性推薦
secret values possible and the probability of each value as follows:
可能な秘密の値と以下のそれぞれの価値の確率:
-----
\
Bits-of-info = \ - p * log ( p )
/ i 2 i
/
-----
----- インフォメーションの\ビットは\と等しいです--p*、(p)/i2i/を登録してください。-----
where i varies from 1 to the number of possible secret values and p sub i is the probability of the value numbered i. (Since p sub i is less than one, the log will be negative so each term in the sum will be non-negative.)
どこのiが1〜可能な秘密の値の数に異なって、p潜水艦iが価値の確率であるかはiに付番しました。 (ログがp潜水艦iが1未満であるので否定的になるので、合計におけるそれぞれの用語は非否定的になるでしょう。)
If there are 2^n different values of equal probability, then n bits of information are present and an adversary would, on the average, have to try half of the values, or 2^(n-1) , before guessing the secret quantity. If the probability of different values is unequal, then there is less information present and fewer guesses will, on average, be required by an adversary. In particular, any values that the adversary can know are impossible, or are of low probability, can be initially ignored by an adversary, who will search through the more probable values first.
等しい確率の2^n異価があれば、nビットの情報は存在しています、そして、敵は平均して値、または2^(n-1)の半分を試みなければならないでしょう、秘密の量を推測する前に。 異価の確率が不平等であるなら、より少ない存在している情報があります、そして、より少ない推測が敵によって平均的に必要とされるでしょう。 特に、敵は初めは、敵が不可能であるか、または低い確率のものであることを知ることができるどんな値も無視できます。(その敵は、最初に、よりありえそうな値を隅々まで捜すでしょう)。
For example, consider a cryptographic system that uses 56 bit keys. If these 56 bit keys are derived by using a fixed pseudo-random number generator that is seeded with an 8 bit seed, then an adversary needs to search through only 256 keys (by running the pseudo-random number generator with every possible seed), not the 2^56 keys that may at first appear to be the case. Only 8 bits of "information" are in these 56 bit keys.
例えば、56ビットのキーを使用する暗号のシステムを考えてください。 これらの56ビットのキーが8ビットの種子で種を蒔かれる固定疑似乱数生成器を使用することによって引き出されるなら、敵は、256個のキー(あらゆる可能な種子のときに疑似乱数生成器を動かすのによる)(初めにケースであるように見えるかもしれない2^56個のキーでない)だけを隅々まで捜す必要があります。 8ビットの「情報」だけ、がこれらの56ビットのキーにあります。
3. Traditional Pseudo-Random Sequences
3. 伝統的な擬似ランダム系列
Most traditional sources of random numbers use deterministic sources of "pseudo-random" numbers. These typically start with a "seed" quantity and use numeric or logical operations to produce a sequence of values.
乱数のほとんどの伝統的な源が「擬似ランダム」番号の決定論的な源を使用します。 これらは、「種子」量から通常始まって、値の系列を作成するのに数値か論理演算を使用します。
[KNUTH] has a classic exposition on pseudo-random numbers. Applications he mentions are simulation of natural phenomena, sampling, numerical analysis, testing computer programs, decision making, and games. None of these have the same characteristics as the sort of security uses we are talking about. Only in the last two could there be an adversary trying to find the random quantity. However, in these cases, the adversary normally has only a single chance to use a guessed value. In guessing passwords or attempting to break an encryption scheme, the adversary normally has many,
[クヌース]は擬似乱数で古典的な博覧会を開きます。 彼が参照するアプリケーションは自然現象、標本抽出、数値解析、コンピュータ・プログラムを検査する、意志決定、およびゲームのシミュレーションです。 これらのいずれにはも、私たちが話しているセキュリティ用途の種類と同じ特性がありません。 最後の2だけには、無作為の量を見つけようとする敵がいるかもしれません。 しかしながら、これらの場合では、通常、敵は推測された値を使用するただ一つの機会しか持っていません。 パスワードを推測するか、または暗号化計画を壊すのを試みる際に、通常、敵は多くを持っています。
Eastlake, Crocker & Schiller [Page 5] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[5ページ]RFC1750偶発性推薦
perhaps unlimited, chances at guessing the correct value and should be assumed to be aided by a computer.
恐らく無制限であることで、正しい値を推測するのにやってみて、コンピュータによって支援されると思われるべきです。
For testing the "randomness" of numbers, Knuth suggests a variety of measures including statistical and spectral. These tests check things like autocorrelation between different parts of a "random" sequence or distribution of its values. They could be met by a constant stored random sequence, such as the "random" sequence printed in the CRC Standard Mathematical Tables [CRC].
数の「偶発性」をテストするために、クヌースは包含統計的であって、スペクトルであることの形でさまざまな測定を勧めます。 これらのテストは「無作為」の系列の異なった部分か値の分配の間の自己相関のようなものをチェックします。 一定の格納されたランダム・シーケンスでそれらに会うことができました、CRC Standard Mathematical Tables[CRC]に印刷された「無作為」の系列などのように。
A typical pseudo-random number generation technique, known as a linear congruence pseudo-random number generator, is modular arithmetic where the N+1th value is calculated from the Nth value by
典型的な擬似乱数世代のテクニックであって、直線的な適合疑似乱数生成器として知られていて、合同算術がN+最初の値がNth値から計算されるところのそばにありますか?
V = ( V * a + b )(Mod c)
N+1 N
V=(*に対して+b)(モッズc)N+1N
The above technique has a strong relationship to linear shift register pseudo-random number generators, which are well understood cryptographically [SHIFT*]. In such generators bits are introduced at one end of a shift register as the Exclusive Or (binary sum without carry) of bits from selected fixed taps into the register.
上のテクニックには、直線的なシフトレジスタ疑似乱数生成器[SHIFT*]との強い関係があります。(疑似乱数生成器はよく暗号で理解されています)。 中では、そのようなジェネレータビットはビットのExclusive Or(キャリーのない2進の合計)としてシフトレジスタの片端で選択された固定消灯ラッパからレジスタに取り入れられます。
For example:
例えば:
+----+ +----+ +----+ +----+
| B | <-- | B | <-- | B | <-- . . . . . . <-- | B | <-+
| 0 | | 1 | | 2 | | n | |
+----+ +----+ +----+ +----+ |
| | | |
| | V +-----+
| V +----------------> | |
V +-----------------------------> | XOR |
+---------------------------------------------------> | |
+-----+
+----+ +----+ +----+ +----+ | B| <--、| B| <--、| B| <-- . . . . . . <--、| B| <。+ | 0 | | 1 | | 2 | | n| | +----+ +----+ +----+ +----+ | | | | | | | +に対して-----+ | +に対して---------------->|、| +に対して----------------------------->| XOR| +--------------------------------------------------->|、| +-----+
V = ( ( V * 2 ) + B .xor. B ... )(Mod 2^n)
N+1 N 0 2
V=( (V*2) + B.xor。 B… )(モッズ2^n) N+1N0 2
The goodness of traditional pseudo-random number generator algorithms is measured by statistical tests on such sequences. Carefully chosen values of the initial V and a, b, and c or the placement of shift register tap in the above simple processes can produce excellent statistics.
伝統的な疑似乱数生成器アルゴリズムの善良はそのような系列の統計的検査法で測定されます。 上の簡単な過程における、シフトレジスタ蛇口の初期のVの慎重に選ばれた値とaか、bと、cかプレースメントが素晴らしい統計を作成できます。
Eastlake, Crocker & Schiller [Page 6] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[6ページ]RFC1750偶発性推薦
These sequences may be adequate in simulations (Monte Carlo experiments) as long as the sequence is orthogonal to the structure of the space being explored. Even there, subtle patterns may cause problems. However, such sequences are clearly bad for use in security applications. They are fully predictable if the initial state is known. Depending on the form of the pseudo-random number generator, the sequence may be determinable from observation of a short portion of the sequence [CRYPTO*, STERN]. For example, with the generators above, one can determine V(n+1) given knowledge of V(n). In fact, it has been shown that with these techniques, even if only one bit of the pseudo-random values is released, the seed can be determined from short sequences.
探検されるスペースの構造と直交している限り、これらの系列はシミュレーション(モンテカルロ実験)で適切であるかもしれません。 そこでさえ、微妙なパターンは問題を起こすかもしれません。しかしながら、セキュリティアプリケーションにおける使用には、そのような系列は明確に悪いです。 初期状態が知られているなら、それらは完全に予測できます。 疑似乱数生成器のフォームによって、系列は系列[CRYPTO*、スターン]の短い部分の観測によって決定できるかもしれません。 例えば、V(n)に関する知識を考えて、ジェネレータが上であるなら、人はV(n+1)を決定できます。 事実上、擬似ランダム値の1ビットだけが放出されても、これらのテクニックで、種子が短い系列から決定できるのが示されました。
Not only have linear congruent generators been broken, but techniques are now known for breaking all polynomial congruent generators [KRAWCZYK].
直線的な一致しているジェネレータが壊れていただけではなく、テクニックは、すべての多項式の一致しているジェネレータ[KRAWCZYK]を壊すので、今、知られています。
4. Unpredictability
4. 予測不可能性
Randomness in the traditional sense described in section 3 is NOT the same as the unpredictability required for security use.
セクション3で伝統的な意味で説明された偶発性は予測不可能性がセキュリティ使用に必要であるのと同じではありません。
For example, use of a widely available constant sequence, such as that from the CRC tables, is very weak against an adversary. Once they learn of or guess it, they can easily break all security, future and past, based on the sequence [CRC]. Yet the statistical properties of these tables are good.
例えば、CRCテーブルからのそれなどの広く利用可能な一定の系列の使用は敵に対して非常に弱いです。 いったんそれを知っているか、または推測すると、彼らはすべてのセキュリティ、未来、および過去に容易に壊れることができます、系列[CRC]に基づいて。 しかし、これらのテーブルの統計的な特性は良いです。
The following sections describe the limitations of some randomness generation techniques and sources.
以下のセクションは何人かの偶発性世代のテクニックとソースの制限について説明します。
4.1 Problems with Clocks and Serial Numbers
4.1 時計と通し番号に関する問題
Computer clocks, or similar operating system or hardware values, provide significantly fewer real bits of unpredictability than might appear from their specifications.
コンピュータ時計、同様のオペレーティングシステムまたはハードウェア値が本当のビットのそれらの仕様から現れるかもしれないよりかなり少ない予測不可能性を提供します。
Tests have been done on clocks on numerous systems and it was found that their behavior can vary widely and in unexpected ways. One version of an operating system running on one set of hardware may actually provide, say, microsecond resolution in a clock while a different configuration of the "same" system may always provide the same lower bits and only count in the upper bits at much lower resolution. This means that successive reads on the clock may produce identical values even if enough time has passed that the value "should" change based on the nominal clock resolution. There are also cases where frequently reading a clock can produce artificial sequential values because of extra code that checks for
テストは多数のシステムの上で時計で終わっていました、そして、彼らの振舞いが広さに予期していなかった方法で異なることができるのが見つけられました。 たとえば、オペレーティングシステムが、あるセットのハードウェアで動くあるバージョンが実際に提供されるかもしれません、「同じ」システムの異なった構成がはるかに低い解像度で同じ下位ビットとカウントだけを上側のビットにいつも供給するかもしれない間の時計でのマイクロセカンド解決。 これは、時間で通る値の“should"が変える十分が名目上の時計解決を基礎づけたとしても時計における連続した読書が同じ値を生産するかもしれないことを意味します。 ケースも頻繁に時計を読むのがチェックする余分なコードのために人工の連続した値を生産できるところにあります。
Eastlake, Crocker & Schiller [Page 7] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[7ページ]RFC1750偶発性推薦
the clock being unchanged between two reads and increases it by one! Designing portable application code to generate unpredictable numbers based on such system clocks is particularly challenging because the system designer does not always know the properties of the system clocks that the code will execute on.
2の間で変わりがない時計は、それを1つ読んで、増加させます! システム設計者がいつもコードが実行するシステムクロックの特性を知っているというわけではないのでシステムクロックは特にやりがいがあるそのようなものに基づく予測できない数を発生させるように携帯用の応用コードを設計します。
Use of a hardware serial number such as an Ethernet address may also provide fewer bits of uniqueness than one would guess. Such quantities are usually heavily structured and subfields may have only a limited range of possible values or values easily guessable based on approximate date of manufacture or other data. For example, it is likely that most of the Ethernet cards installed on Digital Equipment Corporation (DEC) hardware within DEC were manufactured by DEC itself, which significantly limits the range of built in addresses.
またアドレスがユニークさのビットより1つを提供するかもしれないイーサネットなどのハードウェア通し番号の使用は推測するでしょう。 通常、そのような量は大いに構造化されます、そして、部分体で、限られた範囲の可能な値か値だけが製造か他のデータの大体の期日に基づいて容易に推測可能されるかもしれません。 例えば、12月中にDEC(12月)ハードウェアの上にインストールされたイーサネットカードの大部分は12月自体までに製造されそうでした。(12月は組立のコネの範囲をかなり制限します)。アドレス。
Problems such as those described above related to clocks and serial numbers make code to produce unpredictable quantities difficult if the code is to be ported across a variety of computer platforms and systems.
上で説明されたものなどの問題は時計に関連しました、そして、通し番号で、予測できない量を生産するコードはコードがさまざまなコンピュータプラットホームとシステムの向こう側に移植することであるなら難しくなります。
4.2 Timing and Content of External Events
4.2 外部の出来事のタイミングと内容
It is possible to measure the timing and content of mouse movement, key strokes, and similar user events. This is a reasonable source of unguessable data with some qualifications. On some machines, inputs such as key strokes are buffered. Even though the user's inter- keystroke timing may have sufficient variation and unpredictability, there might not be an easy way to access that variation. Another problem is that no standard method exists to sample timing details. This makes it hard to build standard software intended for distribution to a large range of machines based on this technique.
マウス運動、キーストローク、および同様のユーザ出来事のタイミングと内容を測定するのは可能です。 これはいくつかの資格がある「蹄-可能」データの合理的な源です。 いくつかのマシンの上では、キーストロークなどの入力はバッファリングされます。 ユーザの相互キーストロークタイミングには、十分な変化と予測不可能性があるかもしれませんが、その変化にアクセスする簡単な方法がないかもしれません。 別の問題は標準方法が全くタイミングの詳細を抽出するために存在していないということです。 これで、分配のためにこのテクニックに基づく広範囲なマシンに意図する標準のソフトウェアを組立てるのは困難になります。
The amount of mouse movement or the keys actually hit are usually easier to access than timings but may yield less unpredictability as the user may provide highly repetitive input.
マウス運動の量か実際に打たれたキーが、タイミングより通常アクセスに簡単ですが、ユーザが非常に反復性の入力を提供するかもしれないのに従って、より少ない予測不可能性をもたらすかもしれません。
Other external events, such as network packet arrival times, can also be used with care. In particular, the possibility of manipulation of such times by an adversary must be considered.
また、慎重にネットワークパケット到着時間などの他の外部の出来事を使用できます。 特に、敵によるそのような回の操作の可能性を考えなければなりません。
4.3 The Fallacy of Complex Manipulation
4.3 複雑な操作の誤り
One strategy which may give a misleading appearance of unpredictability is to take a very complex algorithm (or an excellent traditional pseudo-random number generator with good statistical properties) and calculate a cryptographic key by starting with the current value of a computer system clock as the seed. An adversary who knew roughly when the generator was started would have a
予測不可能性の紛らわしい外観を与えるかもしれない1つの戦略は、非常に複雑なアルゴリズム(または、良い統計的な特性がある素晴らしい伝統的な疑似乱数生成器)を取って、種子としてコンピュータシステムクロックの現行価値から始まることによって暗号化キーについて計算することです。 ジェネレータがいつ出発したかをおよそ知っていた敵はaを持っているでしょう。
Eastlake, Crocker & Schiller [Page 8] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[8ページ]RFC1750偶発性推薦
relatively small number of seed values to test as they would know likely values of the system clock. Large numbers of pseudo-random bits could be generated but the search space an adversary would need to check could be quite small.
彼らがシステムのありそうな値を知っているようにテストする比較的少ない数の種子値が時間を計ります。 多くの擬似ランダムビットを発生させることができましたが、敵がチェックするために必要とする検索スペースはかなり小さいかもしれません。
Thus very strong and/or complex manipulation of data will not help if the adversary can learn what the manipulation is and there is not enough unpredictability in the starting seed value. Even if they can not learn what the manipulation is, they may be able to use the limited number of results stemming from a limited number of seed values to defeat security.
したがって、敵が、操作が何であるかを学ぶことができると、データの非常に強い、そして/または、複雑な操作は助けないでしょう、そして、始めの種子値には十分な予測不可能性がありません。 操作が何であるかを学ぶことができないでも、彼らは、セキュリティを破るのに限られた数の種子値による結果の限られた数を使用できるかもしれません。
Another serious strategy error is to assume that a very complex pseudo-random number generation algorithm will produce strong random numbers when there has been no theory behind or analysis of the algorithm. There is a excellent example of this fallacy right near the beginning of chapter 3 in [KNUTH] where the author describes a complex algorithm. It was intended that the machine language program corresponding to the algorithm would be so complicated that a person trying to read the code without comments wouldn't know what the program was doing. Unfortunately, actual use of this algorithm showed that it almost immediately converged to a single repeated value in one case and a small cycle of values in another case.
別の重大な戦略誤りはアルゴリズムのどんな理論も分析もなかったとき、非常に複雑な擬似乱数世代アルゴリズムが強い乱数を作成すると仮定することです。 この誤り権利に関する好例が第3章の始まり頃に作者が複雑なアルゴリズムを説明する[クヌース]にあります。 アルゴリズムに対応する機械語プログラムはとても複雑でしょう、したがって、コメントなしでコードを読もうとする人がプログラムが何をしているかを知らないことを意図しました。 残念ながら、このアルゴリズムの実際の使用は、それがほぼすぐにある場合におけるただ一つの繰り返された値と別の場合における、値の小さいサイクルまで一点に集まったのを示しました。
Not only does complex manipulation not help you if you have a limited range of seeds but blindly chosen complex manipulation can destroy the randomness in a good seed!
限られた範囲の種子がありましたら複雑な操作はあなたを助けるだけではなく、盲目的に選ばれた複雑な操作が良い種子における偶発性を破壊できます!
4.4 The Fallacy of Selection from a Large Database
4.4 大容量データベースからの選択の誤り
Another strategy that can give a misleading appearance of unpredictability is selection of a quantity randomly from a database and assume that its strength is related to the total number of bits in the database. For example, typical USENET servers as of this date process over 35 megabytes of information per day. Assume a random quantity was selected by fetching 32 bytes of data from a random starting point in this data. This does not yield 32*8 = 256 bits worth of unguessability. Even after allowing that much of the data is human language and probably has more like 2 or 3 bits of information per byte, it doesn't yield 32*2.5 = 80 bits of unguessability. For an adversary with access to the same 35 megabytes the unguessability rests only on the starting point of the selection. That is, at best, about 25 bits of unguessability in this case.
予測不可能性の紛らわしい外観を与えることができる別の戦略は手当たりしだいにデータベースからの量の選択です、そして、強さがデータベースのビットの総数に関連すると仮定してください。 例えば、典型的なUSENETサーバは現在の時点では1日あたりの35メガバイト以上の情報を処理します。 無作為の量が魅惑的な32バイトのデータによってこのデータにおける無作為の出発点から選択されたと仮定してください。 これはunguessabilityの価値を32*8 = 256ビットもたらしません。 データの多くが人間の言語であり、たぶんさらに2や3のように1バイトあたりのビットの情報を持っているのを許容さえした後にさえ、それは32*をもたらしません。unguessabilityの2.5 = 80ビット。 同じ35メガバイトへのアクセスの敵に関しては、unguessabilityは選択の出発点だけで静止しています。 この場合それはせいぜいunguessabilityのおよそ25ビットです。
The same argument applies to selecting sequences from the data on a CD ROM or Audio CD recording or any other large public database. If the adversary has access to the same database, this "selection from a
同じ議論はCD-ROMに関するデータ、Audio CD録音またはいかなる他の大きい公共のデータベースからもセレクティングシーケンスに適用されます。 敵が同じデータベース、この「aからの選択」に近づく手段を持っているなら
Eastlake, Crocker & Schiller [Page 9] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[9ページ]RFC1750偶発性推薦
large volume of data" step buys very little. However, if a selection can be made from data to which the adversary has no access, such as system buffers on an active multi-user system, it may be of some help.
「大きいデータ量」ステップはほとんど買いません。 しかしながら、敵がアクセスを全く持っていないアクティブなマルチユーザーシステムの上のシステムバッファなどのデータから選択をすることができるなら、それは何らかの助けのものであるかもしれません。
5. Hardware for Randomness
5. 偶発性のためのハードウェア
Is there any hope for strong portable randomness in the future? There might be. All that's needed is a physical source of unpredictable numbers.
将来、何か強い携帯用の偶発性の望みがありますか? あるかもしれません。 必要であるのは予測できない数の物理的な源だけです。
A thermal noise or radioactive decay source and a fast, free-running oscillator would do the trick directly [GIFFORD]. This is a trivial amount of hardware, and could easily be included as a standard part of a computer system's architecture. Furthermore, any system with a spinning disk or the like has an adequate source of randomness [DAVIS]. All that's needed is the common perception among computer vendors that this small additional hardware and the software to access it is necessary and useful.
熱雑音か放射性崩壊が出典を明示して、速くて、自由な動く振動子は直接[ギフォード]トリックをするでしょう。 これは、些細な量のハードウェアであり、コンピュータ・システムの構造の標準部品として容易に含むことができました。 その上、回転盤か同様のものがあるどんなシステムにも、偶発性[DAVIS]の適切な源があります。 そのすべてによる必要であるのが、コンピュータ・ベンダーの中の一般的な知覚であるということです。この小さい追加ハードウェアとそれにアクセスするソフトウェアは、必要であって、役に立ちます。
5.1 Volume Required
5.1 ボリュームが必要です。
How much unpredictability is needed? Is it possible to quantify the requirement in, say, number of random bits per second?
どのくらいの予測不可能性が必要ですか? たとえば、無作為のbpsの数における要件を定量化するのは可能ですか?
The answer is not very much is needed. For DES, the key is 56 bits and, as we show in an example in Section 8, even the highest security system is unlikely to require a keying material of over 200 bits. If a series of keys are needed, it can be generated from a strong random seed using a cryptographically strong sequence as explained in Section 6.3. A few hundred random bits generated once a day would be enough using such techniques. Even if the random bits are generated as slowly as one per second and it is not possible to overlap the generation process, it should be tolerable in high security applications to wait 200 seconds occasionally.
答えはまさしくその多くが必要であるということではありません。 DESに関しては、キーは56ビットです、そして、私たちがセクション8の例に示すように、最も高いセキュリティシステムさえ200ビット以上の合わせることの材料を必要としそうにはありません。 一連のキーが必要であるなら、強い無作為の種子使用から発生できる、暗号で、強い系列、セクション6.3では、説明されます。 1日に一度発生した無作為の数100ビットはそのようなテクニックを使用するのに十分でしょう。 無作為のビットが1秒あたり1つと同じくらいゆっくり発生し、発生経過を重ね合わせるのが可能でなくても、時折200秒待つのは高いセキュリティアプリケーションで許容できるべきです。
These numbers are trivial to achieve. It could be done by a person repeatedly tossing a coin. Almost any hardware process is likely to be much faster.
これらの数は、達成するために些細です。 繰り返してコインを投げる人はそれができました。 ほとんどどんなハードウェアの過程もはるかに速い傾向があります。
5.2 Sensitivity to Skew
5.2 歪曲する感度
Is there any specific requirement on the shape of the distribution of the random numbers? The good news is the distribution need not be uniform. All that is needed is a conservative estimate of how non- uniform it is to bound performance. Two simple techniques to de-skew the bit stream are given below and stronger techniques are mentioned in Section 6.1.2 below.
何か乱数の分配の形に関する決められた一定の要求がありますか? 朗報は分配が一定である必要はないということです。 必要であるのはそれが制限された性能にどれくらい非一定であるかに関する内輪な見積りだけです。 反-ビットストリームを歪曲する2つの簡易技術を以下に与えます、そして、セクション6.1.2未満で、より強いテクニックについて言及します。
Eastlake, Crocker & Schiller [Page 10] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[10ページ]RFC1750偶発性推薦
5.2.1 Using Stream Parity to De-Skew
5.2.1 反-歪曲する流れの同等を使用すること。
Consider taking a sufficiently long string of bits and map the string to "zero" or "one". The mapping will not yield a perfectly uniform distribution, but it can be as close as desired. One mapping that serves the purpose is to take the parity of the string. This has the advantages that it is robust across all degrees of skew up to the estimated maximum skew and is absolutely trivial to implement in hardware.
ビットの十分長いストリングを取ると考えてください、そして、「ゼロ」か「1つ」にストリングを写像してください。 マッピングは完全に一定の分配をもたらさないでしょうが、それは望まれているのと同じくらい近くにあることができます。 目的に適う1つのマッピングはストリングの同等を取ることです。 これには、ハードウェアで実行するのがすべての度の斜行の向こう側におよそ最大の斜行まで強健であり、絶対に些細である利点があります。
The following analysis gives the number of bits that must be sampled:
以下の分析は抽出しなければならないビットの数を与えます:
Suppose the ratio of ones to zeros is 0.5 + e : 0.5 - e, where e is between 0 and 0.5 and is a measure of the "eccentricity" of the distribution. Consider the distribution of the parity function of N bit samples. The probabilities that the parity will be one or zero will be the sum of the odd or even terms in the binomial expansion of (p + q)^N, where p = 0.5 + e, the probability of a one, and q = 0.5 - e, the probability of a zero.
もの対ゼロの比率が0.5+eであると仮定してください: 0.5--e。(そこでは、eは、0〜0.5であり、分配の「風変わり」の測定です)。 Nビットのサンプルのパリティー機能の分配を考えてください。 同等が1かゼロになるという確率はpが0.5+eと等しい(p+q)^Nの二項式の拡大で変であるか同等の用語の合計になるでしょう、1つ、およびq=0.5の確率--e(ゼロの確率)。
These sums can be computed easily as
容易にこれらの合計を計算できます。
N N
1/2 * ( ( p + q ) + ( p - q ) )
and
N N
1/2 * ( ( p + q ) - ( p - q ) ).
N N1/2*((p+q)+(p--q))とN N1/2*(p+q)--(p--q))。
(Which one corresponds to the probability the parity will be 1 depends on whether N is odd or even.)
(どれが同等が1になるという確率に対応しているかはよりさえします。)
Since p + q = 1 and p - q = 2e, these expressions reduce to
1と2e、これらのp--q=表現が減少するp+q=以来
N
1/2 * [1 + (2e) ]
and
N
1/2 * [1 - (2e) ].
N1/2*[1+(2e)]とN1/2*[1--(2e)]。
Neither of these will ever be exactly 0.5 unless e is zero, but we can bring them arbitrarily close to 0.5. If we want the probabilities to be within some delta d of 0.5, i.e. then
これらのどちらもeがゼロでないならかつて、まさに0.5にならないでしょうが、私たちは0.5の近くで任意にそれらを持って来ることができます。 私たちが、その時、0.5のあるデルタdの中に確率がすなわち、あって欲しいと思うなら
N
( 0.5 + ( 0.5 * (2e) ) ) < 0.5 + d.
N、(0.5 + (0.5*(2e))<0.5+d。
Eastlake, Crocker & Schiller [Page 11] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[11ページ]RFC1750偶発性推薦
Solving for N yields N > log(2d)/log(2e). (Note that 2e is less than 1, so its log is negative. Division by a negative number reverses the sense of an inequality.)
N利回りNのために、>ログ(2d)/ログ(2e)を解決します。 (ログが否定的であるように2eが1未満であることに注意してください。 負数に従った事業部は不平等の意味を覆します。)
The following table gives the length of the string which must be sampled for various degrees of skew in order to come within 0.001 of a 50/50 distribution.
以下のテーブルは0.001の50/50分配に含まれて、様々な度の斜行のために抽出しなければならないストリングの長さを与えます。
+---------+--------+-------+
| Prob(1) | e | N |
+---------+--------+-------+
| 0.5 | 0.00 | 1 |
| 0.6 | 0.10 | 4 |
| 0.7 | 0.20 | 7 |
| 0.8 | 0.30 | 13 |
| 0.9 | 0.40 | 28 |
| 0.95 | 0.45 | 59 |
| 0.99 | 0.49 | 308 |
+---------+--------+-------+
+---------+--------+-------+ | Prob(1)| e| N| +---------+--------+-------+ | 0.5 | 0.00 | 1 | | 0.6 | 0.10 | 4 | | 0.7 | 0.20 | 7 | | 0.8 | 0.30 | 13 | | 0.9 | 0.40 | 28 | | 0.95 | 0.45 | 59 | | 0.99 | 0.49 | 308 | +---------+--------+-------+
The last entry shows that even if the distribution is skewed 99% in favor of ones, the parity of a string of 308 samples will be within 0.001 of a 50/50 distribution.
最後のエントリーは、分配がものを支持して99%歪曲されていても、0.001の50/50分配の中に一連の308個のサンプルの同等があるのを示します。
5.2.2 Using Transition Mappings to De-Skew
5.2.2 反-歪曲する変遷マッピングを使用すること。
Another technique, originally due to von Neumann [VON NEUMANN], is to examine a bit stream as a sequence of non-overlapping pairs. You could then discard any 00 or 11 pairs found, interpret 01 as a 0 and 10 as a 1. Assume the probability of a 1 is 0.5+e and the probability of a 0 is 0.5-e where e is the eccentricity of the source and described in the previous section. Then the probability of each pair is as follows:
別のテクニックは元々フォンノイマン[VON NEUMANN]のため非オーバーラッピング・ペアの系列として流れを少し調べることです。 次に、あなたがどんな00も捨てることができましたか、または11組は、0としての01と1としての10を解釈するようにわかりました。 1の確率が0.5+eであり、0の確率がeがソースであって前項で説明されることの風変わりである0.5-eであると仮定してください。 次に、それぞれの組の確率は以下の通りです:
+------+-----------------------------------------+
| pair | 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 |
+------+-----------------------------------------+
+------+-----------------------------------------+ | 組| 確率| +------+-----------------------------------------+ | 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| +------+-----------------------------------------+
This technique will completely eliminate any bias but at the expense of taking an indeterminate number of input bits for any particular desired number of output bits. The probability of any particular pair being discarded is 0.5 + 2e^2 so the expected number of input bits to produce X output bits is X/(0.25 - e^2).
どんな偏見にもかかわらずも、どんな特定の必要な数の出力ビットにも不確定数の入力ビット取ることを犠牲にしてこのテクニックは完全に排泄されるでしょう。 捨てられているどんな特定の組の確率も0.5+2e^2であるので、X出力ビットを作り出す入力ビットの予想された数はX/です(0.25--e^2)。
Eastlake, Crocker & Schiller [Page 12] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[12ページ]RFC1750偶発性推薦
This technique assumes that the bits are from a stream where each bit has the same probability of being a 0 or 1 as any other bit in the stream and that bits are not correlated, i.e., that the bits are identical independent distributions. If alternate bits were from two correlated sources, for example, the above analysis breaks down.
このテクニックはビットが各ビットが流れでいかなる他のビットとしての0か1であるという同じ確率も持っているところで流れから来ていて、ビットが関連されていなくて、すなわち、ビットが同じ独立している配であると仮定します。 交互のビットが2つの関連ソースから来ていたなら、例えば、上の分析が崩壊します。
The above technique also provides another illustration of how a simple statistical analysis can mislead if one is not always on the lookout for patterns that could be exploited by an adversary. If the algorithm were mis-read slightly so that overlapping successive bits pairs were used instead of non-overlapping pairs, the statistical analysis given is the same; however, instead of provided an unbiased uncorrelated series of random 1's and 0's, it instead produces a totally predictable sequence of exactly alternating 1's and 0's.
また、上のテクニックはいつも1が敵が利用できたパターンに目を光らせていないなら簡単な統計分析がどうミスリードすることができるかに関する別のイラストを提供します。 アルゴリズムがあるなら、わずかに誤読されて、したがって、連続したビットが対にするその重なることは非オーバーラッピング・ペアの代わりに使用されるだろうにて、与えられた統計分析は同じです。 の代わりにする、しかしながら、無作為の10つの不遍の非相関シリーズであるなら、それは代わりにまさに交互の1と0の完全に予測できる系列を作成します。
5.2.3 Using FFT to De-Skew
5.2.3 反-歪曲する高速フーリエ変換を使用すること。
When real world data consists of strongly biased or correlated bits, it may still contain useful amounts of randomness. This randomness can be extracted through use of the discrete Fourier transform or its optimized variant, the FFT.
本当の世界データが強く偏られたか、または関連しているビットから成るとき、それはまだ役に立つ量の偶発性を含んでいるかもしれません。 離散型フーリエ変換か最適化された異形、FFTの使用でこの偶発性を抽出できます。
Using the Fourier transform of the data, strong correlations can be discarded. If adequate data is processed and remaining correlations decay, spectral lines approaching statistical independence and normally distributed randomness can be produced [BRILLINGER].
データのフーリエ変換を使用して、強い相関関係を捨てることができます。 適切なデータが処理されて、相関関係腐敗のままで残っているなら、統計的独立にアプローチするスペクトル線と通常、分配された偶発性は発生できます[BRILLINGER]。
5.2.4 Using Compression to De-Skew
5.2.4 反-歪曲する圧縮を使用すること。
Reversible compression techniques also provide a crude method of de- skewing a skewed bit stream. This follows directly from the definition of reversible compression and the formula in Section 2 above for the amount of information in a sequence. Since the compression is reversible, the same amount of information must be present in the shorter output than was present in the longer input. By the Shannon information equation, this is only possible if, on average, the probabilities of the different shorter sequences are more uniformly distributed than were the probabilities of the longer sequences. Thus the shorter sequences are de-skewed relative to the input.
また、リバーシブルの圧縮のテクニックは反-歪曲されたビットストリームを歪曲する粗雑な方法を提供します。 これは次々に情報量のために直接リバーシブルの圧縮の定義とセクション2の公式から上に続きます。 圧縮がリバーシブルであるので、同じ情報量は、より長い入力に存在していたより短い出力で存在していなければなりません。 単にシャノン情報方程式で、異なったより短い系列の確率が、より長い系列の確率より平均では、一様に分配されるなら、これは可能です。 したがって、より短い系列は入力に比例して反-歪曲されています。
However, many compression techniques add a somewhat predicatable preface to their output stream and may insert such a sequence again periodically in their output or otherwise introduce subtle patterns of their own. They should be considered only a rough technique compared with those described above or in Section 6.1.2. At a minimum, the beginning of the compressed sequence should be skipped and only later bits used for applications requiring random bits.
いくらか叙述可能な序文をそれらの出力ストリームに追加します。しかしながら、多くの圧縮のテクニックが、再び定期的にそのような系列を彼らの出力に挿入するか、またはそうでなければ、それら自身の微妙なパターンに紹介するかもしれません。 .2の上、または、セクション6.1.2で説明されるそれらと比べて、それらは荒いテクニックだけであると考えられるべきです。 最小限では、圧縮された系列の始まりは無作為のビットを必要とするアプリケーションに使用されるスキップされて、より遅いだけのビットであるべきです。
Eastlake, Crocker & Schiller [Page 13] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[13ページ]RFC1750偶発性推薦
5.3 Existing Hardware Can Be Used For Randomness
5.3 偶発性に既存のハードウェアを使用できます。
As described below, many computers come with hardware that can, with care, be used to generate truly random quantities.
以下で説明されるように、本当に無作為の量を発生させるのに慎重に使用できるハードウェアは多くのコンピュータにはついて来ます。
5.3.1 Using Existing Sound/Video Input
5.3.1 既存の音/ビデオ入力を使用すること。
Increasingly computers are being built with inputs that digitize some real world analog source, such as sound from a microphone or video input from a camera. Under appropriate circumstances, such input can provide reasonably high quality random bits. The "input" from a sound digitizer with no source plugged in or a camera with the lens cap on, if the system has enough gain to detect anything, is essentially thermal noise.
ますます、コンピュータは世界の本当のアナログソースをデジタル化する入力で組立てられています、マイクロホンからの音やカメラからのビデオ入力のように。 適当な事情では、そのような入力は合理的に高品質の無作為のビットを提供できます。 十分が何かを検出するためにシステムによって獲得されるなら、プラグを差し込まれないソースか全くレンズ・キャップがあるカメラがオンの音のディジタイザからの「入力」は本質的には熱の雑音です。
For example, on a SPARCstation, one can read from the /dev/audio device with nothing plugged into the microphone jack. Such data is essentially random noise although it should not be trusted without some checking in case of hardware failure. It will, in any case, need to be de-skewed as described elsewhere.
例えば、SPARCstationでは、人は/dev/audio装置からマイクロホンジャックがプラグを差し込まれない何ででも読むことができます。 何かがハードウェアの故障の場合にチェックしないで、それを信じるべきではありませんが、そのようなデータは本質的にはランダムノイズです。 どのような場合でも、それは、ほかの場所で説明されるように反-歪曲される必要があるでしょう。
Combining this with compression to de-skew one can, in UNIXese, generate a huge amount of medium quality random data by doing
UNIXeseでは、反-1つを歪曲するためにこれを圧縮に結合するのは、することによって、膨大な量の中型の上質の無作為のデータを発生させることができます。
cat /dev/audio | compress - >random-bits-file
猫/dev/audio| 湿布-->無作為のビットはファイルされます。
5.3.2 Using Existing Disk Drives
5.3.2 既存のディスクドライブを使用すること。
Disk drives have small random fluctuations in their rotational speed due to chaotic air turbulence [DAVIS]. By adding low level disk seek time instrumentation to a system, a series of measurements can be obtained that include this randomness. Such data is usually highly correlated so that significant processing is needed, including FFT (see section 5.2.3). Nevertheless experimentation has shown that, with such processing, disk drives easily produce 100 bits a minute or more of excellent random data.
ディスクドライブには、それらの回転数における小さい無作為の変動が混沌の乱気流[DAVIS]のためあります。 低い平らなディスクシーク時間計装をシステムに追加することによって、この偶発性を含んでいる一連の測定値は得ることができます。 そのようなデータが通常非常に関連するので、FFTを含んで、重要な処理が必要です(セクション5.2.3を見てください)。 それにもかかわらず、実験は、ディスクドライブがそのような処理で容易に素晴らしい無作為のデータの1より分あたり100ビットを作り出すのを示しました。
Partly offsetting this need for processing is the fact that disk drive failure will normally be rapidly noticed. Thus, problems with this method of random number generation due to hardware failure are very unlikely.
一部これが気付かれて、処理が通常、ディスクドライブの故障が急速にそうであるという事実であるのでそうしなければならない相殺。 したがって、ハードウェアの故障による乱数発生のこの方法に関する問題は非常にありそうもないです。
6. Recommended Non-Hardware Strategy
6. お勧めの非ハードウェア戦略
What is the best overall strategy for meeting the requirement for unguessable random numbers in the absence of a reliable hardware source? It is to obtain random input from a large number of uncorrelated sources and to mix them with a strong mixing function.
信頼性の高いハードウェアソースがないとき「蹄-可能」乱数のために条件を満たすための最も良い総合的な戦略は何ですか? それは、多くの非相関ソースから無作為の入力を得て、強い混合機能に彼らを混ぜることになっています。
Eastlake, Crocker & Schiller [Page 14] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[14ページ]RFC1750偶発性推薦
Such a function will preserve the randomness present in any of the sources even if other quantities being combined are fixed or easily guessable. This may be advisable even with a good hardware source as hardware can also fail, though this should be weighed against any increase in the chance of overall failure due to added software complexity.
そのような機能は、結合される他の量が固定されていてもソースのいずれの現在の偶発性を保存するか、または容易に推測可能されるでしょう。 また、ハードウェアが失敗できて、これは良いハードウェアソースがあっても賢明であるかもしれません、これが加えられたソフトウェアの複雑さのため総合的な失敗の機会のどんな増加にも比較考量されるべきですが。
6.1 Mixing Functions
6.1 混合機能
A strong mixing function is one which combines two or more inputs and produces an output where each output bit is a different complex non- linear function of all the input bits. On average, changing any input bit will change about half the output bits. But because the relationship is complex and non-linear, no particular output bit is guaranteed to change when any particular input bit is changed.
強い混合機能は2つ以上の入力を結合して、それぞれの出力ビットがすべての入力ビットの異なった複雑な非一次関数である出力を起こすものです。 平均的に、どんな入力ビット変化するも出力ビットの半分に関して変化するでしょう。 しかし、関係が複雑であって、非線形であるので、どんな特定の出力ビットも何か特定の入力ビットがいつ変えられるかを変えるために保証されません。
Consider the problem of converting a stream of bits that is skewed towards 0 or 1 to a shorter stream which is more random, as discussed in Section 5.2 above. This is simply another case where a strong mixing function is desired, mixing the input bits to produce a smaller number of output bits. The technique given in Section 5.2.1 of using the parity of a number of bits is simply the result of successively Exclusive Or'ing them which is examined as a trivial mixing function immediately below. Use of stronger mixing functions to extract more of the randomness in a stream of skewed bits is examined in Section 6.1.2.
0か1への1つのより無作為の、より短い流れに向かって歪曲されているビットの流れを変換するという問題を考えてください、上のセクション5.2で議論するように。 これは単に強い混合機能が望まれていて、混合が、より少ない数の出力ビットを作り出す入力ビットである別のそうです。 セクション5.2多くのビットの同等を.1使用する際に与えられたテクニックが単に相次ぐことの結果である、Exclusive Or'ing、それら、すぐに些細な混合機能として以下で調べられる。 歪曲されたビットの流れで一層の偶発性を抽出するより強い混合機能の使用はセクション6.1.2で調べられます。
6.1.1 A Trivial Mixing Function
6.1.1 些細な混合機能
A trivial example for single bit inputs is the Exclusive Or function, which is equivalent to addition without carry, as show in the table below. This is a degenerate case in which the one output bit always changes for a change in either input bit. But, despite its simplicity, it will still provide a useful illustration.
ただ一つの噛み付いている入力のための些細な例はExclusive Or機能です、以下のテーブルのショーとして。(それは、桁上げなしの加算に同等です)。 これは1回の出力がどちらの入力ビットでも珍しくいつも変化に噛み付いた堕落したそうです。 しかし、簡単さにもかかわらず、それでも、それは役に立つイラストを提供するでしょう。
+-----------+-----------+----------+
| input 1 | input 2 | output |
+-----------+-----------+----------+
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
+-----------+-----------+----------+
+-----------+-----------+----------+ | 入力1| 入力2| 出力| +-----------+-----------+----------+ | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | +-----------+-----------+----------+
If inputs 1 and 2 are uncorrelated and combined in this fashion then the output will be an even better (less skewed) random bit than the inputs. If we assume an "eccentricity" e as defined in Section 5.2 above, then the output eccentricity relates to the input eccentricity
入力1と2がこんなやり方で非相関であって結合されていると、出力は入力よりさらに良い(それほど歪曲されなかった)無作為のビットになるでしょう。 私たちが、セクション5.2で定義される「風変わり」eが上であると思うなら、出力風変わりは入力風変わりに関連します。
Eastlake, Crocker & Schiller [Page 15] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[15ページ]RFC1750偶発性推薦
as follows:
以下の通り:
e = 2 * e * e
output input 1 input 2
2*e*e出力入力1e=入力2
Since e is never greater than 1/2, the eccentricity is always improved except in the case where at least one input is a totally skewed constant. This is illustrated in the following table where the top and left side values are the two input eccentricities and the entries are the output eccentricity:
eが決して1/2以上でないので、少なくとも1つの入力が完全に歪曲された定数であるケースの中を除いて、風変わりはいつも改良されます。 これは先端と左側値が2人の入力風変わりである以下のテーブルで例証されます、そして、エントリーは出力風変わりです:
+--------+--------+--------+--------+--------+--------+--------+
| e | 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.10 | 0.00 | 0.02 | 0.04 | 0.06 | 0.08 | 0.10 |
| 0.20 | 0.00 | 0.04 | 0.08 | 0.12 | 0.16 | 0.20 |
| 0.30 | 0.00 | 0.06 | 0.12 | 0.18 | 0.24 | 0.30 |
| 0.40 | 0.00 | 0.08 | 0.16 | 0.24 | 0.32 | 0.40 |
| 0.50 | 0.00 | 0.10 | 0.20 | 0.30 | 0.40 | 0.50 |
+--------+--------+--------+--------+--------+--------+--------+
+--------+--------+--------+--------+--------+--------+--------+ | e| 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.10 | 0.00 | 0.02 | 0.04 | 0.06 | 0.08 | 0.10 | | 0.20 | 0.00 | 0.04 | 0.08 | 0.12 | 0.16 | 0.20 | | 0.30 | 0.00 | 0.06 | 0.12 | 0.18 | 0.24 | 0.30 | | 0.40 | 0.00 | 0.08 | 0.16 | 0.24 | 0.32 | 0.40 | | 0.50 | 0.00 | 0.10 | 0.20 | 0.30 | 0.40 | 0.50 | +--------+--------+--------+--------+--------+--------+--------+
However, keep in mind that the above calculations assume that the inputs are not correlated. If the inputs were, say, the parity of the number of minutes from midnight on two clocks accurate to a few seconds, then each might appear random if sampled at random intervals much longer than a minute. Yet if they were both sampled and combined with xor, the result would be zero most of the time.
しかしながら、上の計算が、入力が関連されていないと仮定するのを覚えておいてください。 たとえば、入力が数秒に正確な2個の時計における真夜中からの数分の数の同等であるなら、1分より間隔長い間はるかに無作為に抽出されるなら、それぞれが無作為に見えるでしょうに。 しかし、それらが抽出されて、xorに結合されるなら、たいてい結果はゼロでしょうに。
6.1.2 Stronger Mixing Functions
6.1.2 より強い混合機能
The US Government Data Encryption Standard [DES] is an example of a strong mixing function for multiple bit quantities. It takes up to 120 bits of input (64 bits of "data" and 56 bits of "key") and produces 64 bits of output each of which is dependent on a complex non-linear function of all input bits. Other strong encryption functions with this characteristic can also be used by considering them to mix all of their key and data input bits.
米国政府データ暗号化規格[DES]は複数の噛み付いている量のための強い混合機能に関する例です。 それは、最大120ビットの入力(64ビットの「データ」と「キー」の56ビット)を取って、それのそれぞれがすべての入力ビットの複雑な非線形の関数に依存している出力の64ビットを作り出します。 また、それらのキーとデータの入力ビットのすべてを混ぜると考えることによって、この特性がある他の強い暗号化機能を使用できます。
Another good family of mixing functions are the "message digest" or hashing functions such as The US Government Secure Hash Standard [SHS] and the MD2, MD4, MD5 [MD2, MD4, MD5] series. These functions all take an arbitrary amount of input and produce an output mixing all the input bits. The MD* series produce 128 bits of output and SHS produces 160 bits.
混合機能の別の良家は、「メッセージダイジェスト」であるか米国政府Secure Hash Standard[SHS]やMD2などの機能を論じ尽くしています、MD4、MD5[MD2、MD4、MD5]シリーズ。 これらの機能は、任意の量の入力をすべて取って、出力混合をすべての入力ビット生産します。 MD*シリーズは出力の128ビットを作り出します、そして、SHSは160ビットを作り出します。
Eastlake, Crocker & Schiller [Page 16] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[16ページ]RFC1750偶発性推薦
Although the message digest functions are designed for variable amounts of input, DES and other encryption functions can also be used to combine any number of inputs. If 64 bits of output is adequate, the inputs can be packed into a 64 bit data quantity and successive 56 bit keys, padding with zeros if needed, which are then used to successively encrypt using DES in Electronic Codebook Mode [DES MODES]. If more than 64 bits of output are needed, use more complex mixing. For example, if inputs are packed into three quantities, A, B, and C, use DES to encrypt A with B as a key and then with C as a key to produce the 1st part of the output, then encrypt B with C and then A for more output and, if necessary, encrypt C with A and then B for yet more output. Still more output can be produced by reversing the order of the keys given above to stretch things. The same can be done with the hash functions by hashing various subsets of the input data to produce multiple outputs. But keep in mind that it is impossible to get more bits of "randomness" out than are put in.
メッセージダイジェスト関数は可変量の入力のために設計されていますが、また、どんな入力点数も結合するのにDESと他の暗号化機能を使用できます。 出力の64ビットが適切であるなら、必要であるならゼロでそっと歩く64個のビット・データ量と56ビットの連続したキーに入力に詰め込むことができます。(次に、キーはElectronic Codebook Mode[DES MODES]でDESを使用するのにおいて相次ぐコード化するのにおいて使用されています)。 出力の64ビット以上が必要であるなら、より複雑な混合を使用してください。 例えば、入力が3つの量に詰め込まれるなら、A、B、およびCは、出力の最初の部分を生産して、次に、より多くの出力のためにCと次に、Aと共にBをコード化して、必要なら、まだより多くの出力のためにAと次に、Bと共にCをコード化するためにキーとしてのBとそして、Cと共にキーとしてAをコード化するのにDESを使用します。 ものを伸ばすために上に与えられたキーの注文を逆にすることによって、まだより多くの出力を起こすことができます。 複数の出力を起こすためには同じくらいによる処理されて、細切れ肉料理が入力データの様々な部分集合を論じ尽くすことによって機能するということであることができます。 しかし、「偶発性」の、より多くのビットを出すのが入れられるより不可能であることを覚えておいてください。
An example of using a strong mixing function would be to reconsider the case of a string of 308 bits each of which is biased 99% towards zero. The parity technique given in Section 5.2.1 above reduced this to one bit with only a 1/1000 deviance from being equally likely a zero or one. But, applying the equation for information given in Section 2, this 308 bit sequence has 5 bits of information in it. Thus hashing it with SHS or MD5 and taking the bottom 5 bits of the result would yield 5 unbiased random bits as opposed to the single bit given by calculating the parity of the string.
強い混合機能を使用する例はそれのそれぞれがゼロに向かって99%偏られる一連の308ビットのケースを再考するだろうことです。 セクション5.2.1で上に与えられたパリティのテクニックは等しくありそうなaゼロであるか1からこれを1/1000逸脱がある、あるビットまで減少させました。 しかし、セクション2で与えられた情報のために方程式を適用して、この308ビットの系列はそれに5ビットの情報を持っています。 したがって、SHSかMD5と共にそれを論じ尽くして、結果の5ビットの下部を取るのはストリングの同等について計算することによって与えられた単一のビットと対照的に不遍の無作為の5ビットもたらすでしょう。
6.1.3 Diffie-Hellman as a Mixing Function
6.1.3 混合機能としてのディフィー-ヘルマン
Diffie-Hellman exponential key exchange is a technique that yields a shared secret between two parties that can be made computationally infeasible for a third party to determine even if they can observe all the messages between the two communicating parties. This shared secret is a mixture of initial quantities generated by each of them [D-H]. If these initial quantities are random, then the shared secret contains the combined randomness of them both, assuming they are uncorrelated.
ディフィー-ヘルマンの指数の主要な交換は彼らが、2つの間のすべてのメッセージがパーティーを伝えているのを観測できても第三者が決定するのにおいて計算上実行不可能にすることができる2回のパーティーの間の共有秘密キーをもたらすテクニックです。 この共有秘密キーはそれぞれのそれら[D-H]によって発生した初期量の混合物です。 これらの初期量が無作為であるなら、共有秘密キーはそれらの両方の結合した偶発性を含んでいます、それらが非相関であると仮定して。
6.1.4 Using a Mixing Function to Stretch Random Bits
6.1.4 混合機能を伸び無作為のビットまで使用すること。
While it is not necessary for a mixing function to produce the same or fewer bits than its inputs, mixing bits cannot "stretch" the amount of random unpredictability present in the inputs. Thus four inputs of 32 bits each where there is 12 bits worth of unpredicatability (such as 4,096 equally probable values) in each input cannot produce more than 48 bits worth of unpredictable output. The output can be expanded to hundreds or thousands of bits by, for example, mixing with successive integers, but the clever adversary's
混合機能が入力より同じであるか少ないビットを作り出すのは必要でない間、混合ビットが入力の現在の無作為の予測不可能性の量を「伸ばすことができません」。 したがって、それぞれ各入力における、unpredicatability(4,096の等しくありえそうな値などの)の価値が12ビットある32ビットの4つの入力は予測できない出力の価値を48ビット以上生産できません。 例えば、しかし、連続した整数、賢い敵のものと交際することによって、数百か何千ビットにも出力を広げることができます。
Eastlake, Crocker & Schiller [Page 17] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[17ページ]RFC1750偶発性推薦
search space is still 2^48 possibilities. Furthermore, mixing to fewer bits than are input will tend to strengthen the randomness of the output the way using Exclusive Or to produce one bit from two did above.
それでも、検索スペースは2^48の可能性です。 その上、入力であるより少ないビットに混合するのは、Exclusive Orが2を1ビット作り出すのに上で使用された方法で出力の偶発性を強化する傾向があるでしょう。
The last table in Section 6.1.1 shows that mixing a random bit with a constant bit with Exclusive Or will produce a random bit. While this is true, it does not provide a way to "stretch" one random bit into more than one. If, for example, a random bit is mixed with a 0 and then with a 1, this produces a two bit sequence but it will always be either 01 or 10. Since there are only two possible values, there is still only the one bit of original randomness.
セクション6.1.1における最後のテーブルは、Exclusive Orと共に無作為のビットを一定のビットに混ぜると無作為のビットが作り出されるのを示します。 これが本当である間、それは1つ以上に無作為の1ビット「伸びる」方法を提供しません。 例えば、無作為のビットが0とそして、1に複雑であるなら、これは2ビットの系列を作成しますが、それは、いつも01か10になるでしょう。 2つの可能な値しかないので、オリジナルの偶発性の1ビットしかまだありません。
6.1.5 Other Factors in Choosing a Mixing Function
6.1.5 混合機能を選ぶ他の要素
For local use, DES has the advantages that it has been widely tested for flaws, is widely documented, and is widely implemented with hardware and software implementations available all over the world including source code available by anonymous FTP. The SHS and MD* family are younger algorithms which have been less tested but there is no particular reason to believe they are flawed. Both MD5 and SHS were derived from the earlier MD4 algorithm. They all have source code available by anonymous FTP [SHS, MD2, MD4, MD5].
地方の使用において、ハードウェアとソフトウェア実行が利用可能な状態で、DESは欠点がないかどうかテストされて、それが広くそうである利点を持って、広く記録されて、公開FTPで利用可能なソースコードを含んでいて、世界中で広く実行されます。 SHSとMD*家族はそれほどテストされていないより若いアルゴリズムですが、それらが失敗すると信じるどんな特定の理由もありません。 以前のMD4アルゴリズムからMD5とSHSの両方を得ました。 彼らには皆、公開FTP[SHS、MD2、MD4、MD5]で利用可能なソースコードがあります。
DES and SHS have been vouched for the the US National Security Agency (NSA) on the basis of criteria that primarily remain secret. While this is the cause of much speculation and doubt, investigation of DES over the years has indicated that NSA involvement in modifications to its design, which originated with IBM, was primarily to strengthen it. No concealed or special weakness has been found in DES. It is almost certain that the NSA modification to MD4 to produce the SHS similarly strengthened the algorithm, possibly against threats not yet known in the public cryptographic community.
DESとSHSは主として秘密のままで残っている評価基準に基づいて米国国家安全保障局(NSA)に太鼓判を押されました。 これは多くの思惑と疑問の原因ですが、数年間のDESの調査は、IBMの発案であったデザインへの変更におけるNSAかかわり合いが主としてそれを強化することであったのを示しました。 どんな隠されたか特別な弱点もDESで見つけられていません。 同様にSHSを生産するMD4へのNSA変更がアルゴリズムを強化したのは、ほとんど確かです、ことによると公立の暗号の共同体でまだ知られていなかった脅威に対して。
DES, SHS, MD4, and MD5 are royalty free for all purposes. MD2 has been freely licensed only for non-profit use in connection with Privacy Enhanced Mail [PEM]. Between the MD* algorithms, some people believe that, as with "Goldilocks and the Three Bears", MD2 is strong but too slow, MD4 is fast but too weak, and MD5 is just right.
DES、SHS、MD4、およびMD5はすべての目的のためにロイヤルティフリーです。 MD2は非営利の使用のためだけにPrivacy Enhancedメール[PEM]に関して自由に認可されました。 MD*アルゴリズムの間では、何人かの人々が、MD2が「金髪娘と3つの弱気筋」のように強いのですが、遅過ぎると信じています、そして、MD4は速いのですが、弱過ぎます、そして、MD5はただよいです。
Another advantage of the MD* or similar hashing algorithms over encryption algorithms is that they are not subject to the same regulations imposed by the US Government prohibiting the unlicensed export or import of encryption/decryption software and hardware. The same should be true of DES rigged to produce an irreversible hash code but most DES packages are oriented to reversible encryption.
暗号化アルゴリズムの上のMD*か同様の論じ尽くすアルゴリズムの別の利点はそれらが暗号化/復号化ソフトウェアとハードウェアの無免許の輸出か輸入を禁止する米国政府によって課された同じ規則を受けることがないということです。 同じくらいは逆にできない細切れ肉料理コードを作成するために装備されていたDESに関して本当であるはずですが、ほとんどのDESパッケージがリバーシブルの暗号化に適応します。
Eastlake, Crocker & Schiller [Page 18] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[18ページ]RFC1750偶発性推薦
6.2 Non-Hardware Sources of Randomness
6.2 偶発性の非ハードウェア源
The best source of input for mixing would be a hardware randomness such as disk drive timing affected by air turbulence, audio input with thermal noise, or radioactive decay. However, if that is not available there are other possibilities. These include system clocks, system or input/output buffers, user/system/hardware/network serial numbers and/or addresses and timing, and user input. Unfortunately, any of these sources can produce limited or predicatable values under some circumstances.
混合のための入力の最も良い源は乱気流で影響を受けるディスクドライブタイミング、熱雑音に伴う音声入力、または放射性崩壊などのハードウェアの偶発性でしょう。 しかしながら、それが利用可能でないなら、他の可能性があります。 これらはシステムクロック、システムか入力/出力バッファ、ユーザ/システム/ハードウェア/ネットワーク通し番号、そして/または、アドレスと、タイミングと、ユーザ入力を含んでいます。 残念ながら、これらのソースのいずれもいくつかの状況で制限されたか叙述可能な値を生産できます。
Some of the sources listed above would be quite strong on multi-user systems where, in essence, each user of the system is a source of randomness. However, on a small single user system, such as a typical IBM PC or Apple Macintosh, it might be possible for an adversary to assemble a similar configuration. This could give the adversary inputs to the mixing process that were sufficiently correlated to those used originally as to make exhaustive search practical.
上に記載されたソースの何人かが本質では、システムの各ユーザが偶発性の源であるところでマルチユーザーシステムでかなり強いでしょう。 しかしながら、典型的なIBM PCかアップルマッキントッシュなどの小さいシングルユーザーシステムの上では、敵が同様の構成を組み立てるのは、可能であるかもしれません。 これは元々徹底的な検索を実用的にするほど使用されたものに十分関連している混合の過程に敵の入力を与えるかもしれません。
The use of multiple random inputs with a strong mixing function is recommended and can overcome weakness in any particular input. For example, the timing and content of requested "random" user keystrokes can yield hundreds of random bits but conservative assumptions need to be made. For example, assuming a few bits of randomness if the inter-keystroke interval is unique in the sequence up to that point and a similar assumption if the key hit is unique but assuming that no bits of randomness are present in the initial key value or if the timing or key value duplicate previous values. The results of mixing these timings and characters typed could be further combined with clock values and other inputs.
強い混合機能がある複数の無作為の入力の使用は、お勧めであり、どんな特定の入力でも弱点に打ち勝つことができます。 例えば、要求された「無作為」のユーザキーストロークのタイミングと内容は無作為の何百ビットももたらすことができますが、保守的な仮定は、作られている必要があります。 例えば、いくつかを仮定して、偶発性のビットは主要なヒットがユニークであるなら相互キーストローク間隔が系列でそのポイントと同様の仮定までユニークですが、いいえと仮定して、偶発性のビットが初期のキー値で存在しているか、タイミングかキー値であるなら前の値をコピーします。 これらのタイミングとキャラクタがタイプした混合の結果はさらに時計値と他の入力に結合されるかもしれません。
This strategy may make practical portable code to produce good random numbers for security even if some of the inputs are very weak on some of the target systems. However, it may still fail against a high grade attack on small single user systems, especially if the adversary has ever been able to observe the generation process in the past. A hardware based random source is still preferable.
入力のいくつかがいくつかの目標システムの上で非常に弱くても、この戦略は、セキュリティのために良い乱数を作成するために実用的な携帯用のコードを作るかもしれません。しかしながら、まだ、小さいシングルユーザーシステムに対する高いグレード攻撃に対して失敗しているかもしれません、特に敵が過去に今までに発生経過を観測できたことがあるなら。 ハードウェアに基づいている無作為のソースはまだ望ましいです。
6.3 Cryptographically Strong Sequences
6.3、暗号で、強い系列
In cases where a series of random quantities must be generated, an adversary may learn some values in the sequence. In general, they should not be able to predict other values from the ones that they know.
一連の無作為の量が発生しなければならない場合では、敵は系列のいくつかの値を学ぶかもしれません。 一般に、彼らは知っているものから他の値を予測できないべきです。
Eastlake, Crocker & Schiller [Page 19] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[19ページ]RFC1750偶発性推薦
The correct technique is to start with a strong random seed, take cryptographically strong steps from that seed [CRYPTO2, CRYPTO3], and do not reveal the complete state of the generator in the sequence elements. If each value in the sequence can be calculated in a fixed way from the previous value, then when any value is compromised, all future values can be determined. This would be the case, for example, if each value were a constant function of the previously used values, even if the function were a very strong, non-invertible message digest function.
正しいテクニックは、強い無作為の種子から始めて、その種子[CRYPTO2、CRYPTO3]から強い方法を暗号で採って、系列要素でジェネレータの完全な状態を明らかにしないことです。 どんな値も妥協するとき、前の値から系列の各値について固定方法で計算できるなら、すべての将来価値が決定できます。 例えば、これは各値が以前中古の値の定数機能であるならそうでしょうに、機能が非常に強くて、非invertibleのメッセージダイジェスト関数であったとしても。
It should be noted that if your technique for generating a sequence of key values is fast enough, it can trivially be used as the basis for a confidentiality system. If two parties use the same sequence generating technique and start with the same seed material, they will generate identical sequences. These could, for example, be xor'ed at one end with data being send, encrypting it, and xor'ed with this data as received, decrypting it due to the reversible properties of the xor operation.
あなたのテクニックがキー値の系列を発生させるように十分速いなら、秘密性システムの基礎としてそれを些細なことに使用できることに注意されるべきです。 2回のパーティーがテクニックを発生させる同じ系列を使用して、同じ種子の材料から始まると、彼らは同じ系列を発生させるでしょう。 例えば、これらは受け取るようにこのデータでそれ、およびxor'edをコード化して、発信することであるデータでの片端のxor'edであるかもしれません、xor操作のリバーシブルの特性のためそれを解読して。
6.3.1 Traditional Strong Sequences
6.3.1 伝統的な強い系列
A traditional way to achieve a strong sequence has been to have the values be produced by hashing the quantities produced by concatenating the seed with successive integers or the like and then mask the values obtained so as to limit the amount of generator state available to the adversary.
強い系列を達成する伝統的な方法は、連続した整数か同様のもので種子を連結することによって生産された量を論じ尽くすことによって値を生産させて、次に、敵にとって、利用可能なジェネレータ状態の量を制限するために得られた値にマスクをかけることです。
It may also be possible to use an "encryption" algorithm with a random key and seed value to encrypt and feedback some or all of the output encrypted value into the value to be encrypted for the next iteration. Appropriate feedback techniques will usually be recommended with the encryption algorithm. An example is shown below where shifting and masking are used to combine the cypher output feedback. This type of feedback is recommended by the US Government in connection with DES [DES MODES].
また、ランダムキー、コード化する種子値、およびフィードバックがある「暗号化」アルゴリズムを使用するために、出力のいくつかかすべてが次の繰り返しのためにコード化されるべき値に値をコード化したのも、可能であるかもしれません。 通常、適切なフィードバックのテクニックは暗号化アルゴリズムでお勧めになるでしょう。 例は移行とマスキングが暗号化出力フィードバックを結合するのに使用されるところの下に示されます。 このタイプのフィードバックはデス[DES MODES]に関して米国政府によって推薦されます。
Eastlake, Crocker & Schiller [Page 20] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[20ページ]RFC1750偶発性推薦
+---------------+
| V |
| | n |
+--+------------+
| | +---------+
| +---------> | | +-----+
+--+ | Encrypt | <--- | Key |
| +-------- | | +-----+
| | +---------+
V V
+------------+--+
| V | |
| n+1 |
+---------------+
+---------------+ | V| | | n| +--+------------+ | | +---------+ | +--------->|、| +-----+ +--+ | コード化します。| <--、| キー| | +-------- | | +-----+ | | +---------+ +に対するV------------+--+ | V| | | n+1| +---------------+
Note that if a shift of one is used, this is the same as the shift register technique described in Section 3 above but with the all important difference that the feedback is determined by a complex non-linear function of all bits rather than a simple linear or polynomial combination of output from a few bit position taps.
1のシフトが使用されているなら、これがフィードバックが違いですが、シフトレジスタのテクニックがセクション3で重要にもかかわらず、すべて重要で説明したのといくつかのビット位置消灯ラッパからの出力の直線的であるか多項式の簡単な組み合わせよりむしろすべてのビットの複雑な非線形の関数で断固としていた状態で同じであることに注意してください。
It has been shown by Donald W. Davies that this sort of shifted partial output feedback significantly weakens an algorithm compared will feeding all of the output bits back as input. In particular, for DES, repeated encrypting a full 64 bit quantity will give an expected repeat in about 2^63 iterations. Feeding back anything less than 64 (and more than 0) bits will give an expected repeat in between 2**31 and 2**32 iterations!
入力されるように優に出力ビットを与えながら、この種類の移行している部分的な出力フィードバックがかなり弱めるドナルド・W.デイヴィースで、比較されたアルゴリズムがそうするのが示されました。 完全な64ビットをコード化しながら繰り返されたDESに関して特に、量はおよそ2^での予想された反復に63繰り返しを与えるでしょう。 64(そして、0以上)ビット未満について何かをフィードバックすると、31と2**32繰り返しは2**の間の予想された反復に与えられるでしょう!
To predict values of a sequence from others when the sequence was generated by these techniques is equivalent to breaking the cryptosystem or inverting the "non-invertible" hashing involved with only partial information available. The less information revealed each iteration, the harder it will be for an adversary to predict the sequence. Thus it is best to use only one bit from each value. It has been shown that in some cases this makes it impossible to break a system even when the cryptographic system is invertible and can be broken if all of each generated value was revealed.
系列がこれらのテクニックで発生したとき、他のものから系列の値を予測するのは暗号系を壊すか、または部分的な情報だけが利用可能な状態でかかわる「非invertible」の論じ尽くすことを逆にするのに同等です。 より少ない情報が各繰り返しを明らかにすれば明らかにするほど、それは敵が系列をより予測しにくいようになるでしょう。 したがって、各値から1ビットだけを使用するのは最も良いです。 そんなにいくつかの場合、これは暗号のシステムがinvertibleでさえあるときに、システムを壊すのを不可能にして、それぞれの発生している価値のすべてが明らかにされたなら壊すことができるのが示されました。
6.3.2 The Blum Blum Shub Sequence Generator
6.3.2 ブルームブルームシューブ系列ジェネレータ
Currently the generator which has the strongest public proof of strength is called the Blum Blum Shub generator after its inventors [BBS]. It is also very simple and is based on quadratic residues. It's only disadvantage is that is is computationally intensive compared with the traditional techniques give in 6.3.1 above. This is not a serious draw back if it is used for moderately infrequent purposes, such as generating session keys.
現在の、強さの最も強い公共の証拠を持っているジェネレータは発明者[BBS]の後にブルームブルームシューブジェネレータと呼ばれます。 それは、また、非常に簡単であり、平方剰余に基づいています。 唯一の不都合がそれがいるということであるということである、計算上伝統的なテクニックと比べて徹底的である、負けてください、6.3、上の.1 それがセッションキーを発生などにさせることなどの適度に珍しい目的に使用されるなら、これは重大なドローではありません。
Eastlake, Crocker & Schiller [Page 21] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[21ページ]RFC1750偶発性推薦
Simply choose two large prime numbers, say p and q, which both have the property that you get a remainder of 3 if you divide them by 4. Let n = p * q. Then you choose a random number x relatively prime to n. The initial seed for the generator and the method for calculating subsequent values are then
単に2つの大きい素数を選んでください、そして、pとqを言ってください。(ともに、あなたが4にそれらを割るなら、それは、あなたが3の残りを得る特性を持っています)。 nをp*qとの等しさにしてください。 そして、あなたはnに比較的主要な乱数xを選びます。 ジェネレータのための初期の種子とその後の値がそうであると見込むためのそして方法
2
s = ( x )(Mod n)
0
2秒間=(x)(モッズn)0
2
s = ( s )(Mod n)
i+1 i
2秒間は(s)(モッズn)i+1iと等しいです。
You must be careful to use only a few bits from the bottom of each s. It is always safe to use only the lowest order bit. If you use no more than the
あなたはそれぞれのsの下部からのほんの数ビットを使用するのに慎重でなければなりません。 最も低いオーダービットだけを使用するのはいつも安全です。 あなたはいいえをさらに使用します。
log ( log ( s ) )
2 2 i
(ログ(s))2 2iを登録してください。
low order bits, then predicting any additional bits from a sequence generated in this manner is provable as hard as factoring n. As long as the initial x is secret, you can even make n public if you want.
下位のビット、次に、この様に発生する系列からのどんな追加ビットも予測するのはnを因数分解するのと同じくらい一生懸命証明可能です。 初期のxが秘密である限り、あなたは望んでいるならnを公共にすることさえできます。
An intersting characteristic of this generator is that you can directly calculate any of the s values. In particular
このジェネレータのinterstingの特性はあなたが直接s値のどれかについて計算できるということです。 特に
i
( ( 2 )(Mod (( p - 1 ) * ( q - 1 )) ) )
s = ( s )(Mod n)
i 0
i( ( 2 )(モッズ(p--1)*(q--1))sは(s)(モッズn)i0と等しいです。
This means that in applications where many keys are generated in this fashion, it is not necessary to save them all. Each key can be effectively indexed and recovered from that small index and the initial s and n.
これは、多くのキーがこんなやり方で発生するアプリケーションでは、それらを皆、救うのが必要でないことを意味します。 各キーは、事実上、索引をつけて、そのわずかなインデックス、初期のs、およびnを取り戻すことができます。
7. Key Generation Standards
7. キー生成規格
Several public standards are now in place for the generation of keys. Two of these are described below. Both use DES but any equally strong or stronger mixing function could be substituted.
いくつかの公共の規格がキーの世代の間、現在適所にあります。 これらの2は以下で説明されます。 両方がDESを使用しますが、どんな等しく強いか、より強い混合機能も代入するかもしれません。
Eastlake, Crocker & Schiller [Page 22] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[22ページ]RFC1750偶発性推薦
7.1 US DoD Recommendations for Password Generation
7.1 パスワード世代米国のDoD推薦
The United States Department of Defense has specific recommendations for password generation [DoD]. They suggest using the US Data Encryption Standard [DES] in Output Feedback Mode [DES MODES] as follows:
合衆国国防総省には、特定の推薦がパスワード世代[DoD]のためにあります。 彼らは、以下のOutput Feedback Mode[DES MODES]で米国データ暗号化規格[DES]を使用するのを示します:
use an initialization vector determined from
the system clock,
system ID,
user ID, and
date and time;
use a key determined from
system interrupt registers,
system status registers, and
system counters; and,
as plain text, use an external randomly generated 64 bit
quantity such as 8 characters typed in by a system
administrator.
システムクロックから決定している初期化ベクトル、システムID、ユーザID、および日時を使用してください。 システム割込みレジスタ、システムステータスレジスタ、およびシステムカウンタから断固としたキーを使用してください。 そして、プレーンテキストとして、システム管理者によってタイプされた64ビットの外部の手当たりしだいに発生している量の8つのキャラクタなどを使用してください。
The password can then be calculated from the 64 bit "cipher text" generated in 64-bit Output Feedback Mode. As many bits as are needed can be taken from these 64 bits and expanded into a pronounceable word, phrase, or other format if a human being needs to remember the password.
そして、「暗号テキスト」が64ビットのOutput Feedback Modeで発生させた64ビットでパスワードについて計算できます。 人間が、パスワードを覚えている必要があるなら、必要とされるのと同じくらい多くのビットをこれらの64ビットから連れて行って、発音可能な単語、句、または他の形式に広げることができます。
7.2 X9.17 Key Generation
7.2X9.17キー生成
The American National Standards Institute has specified a method for generating a sequence of keys as follows:
American National Standards Institutは以下のキーの系列を発生させるための方法を指定しました:
s is the initial 64 bit seed
0
sは64ビットの初期の種子0です。
g is the sequence of generated 64 bit key quantities
n
gは64ビットの発生している主要な量nの系列です。
k is a random key reserved for generating this key sequence
kはこのキー順を発生させるように予約されたランダムキーです。
t is the time at which a key is generated to as fine a resolution
as is available (up to 64 bits).
tはキーが利用可能であるのと同じくらいよい解決に発生する時(最大64ビット)です。
DES ( K, Q ) is the DES encryption of quantity Q with key K
キーKでDES(K、Q)は量QのDES暗号化です。
Eastlake, Crocker & Schiller [Page 23] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[23ページ]RFC1750偶発性推薦
g = DES ( k, DES ( k, t ) .xor. s )
n n
gが等しい、DES、(k、DES、(k、t) .xor s)n n
s = DES ( k, DES ( k, t ) .xor. g )
n+1 n
sが等しい、DES、(k、DES、(t) .xor k、g)n+1n
If g sub n is to be used as a DES key, then every eighth bit should be adjusted for parity for that use but the entire 64 bit unmodified g should be used in calculating the next s.
g潜水艦nがDESキーとして使用されるつもりであるなら、8番目のビット毎はその使用のための同等ために調整されるべきですが、全体の64ビット変更されていないgは次のsについて計算する際に使用されるべきです。
8. Examples of Randomness Required
8. 偶発性の例が必要です。
Below are two examples showing rough calculations of needed randomness for security. The first is for moderate security passwords while the second assumes a need for a very high security cryptographic key.
以下に、セキュリティのために必要な偶発性の概算を示している2つの例があります。 2番目は非常に高いセキュリティ暗号化キーの必要性を仮定しますが、1番目は適度のセキュリティパスワードのためのものです。
8.1 Password Generation
8.1パスワード世代
Assume that user passwords change once a year and it is desired that the probability that an adversary could guess the password for a particular account be less than one in a thousand. Further assume that sending a password to the system is the only way to try a password. Then the crucial question is how often an adversary can try possibilities. Assume that delays have been introduced into a system so that, at most, an adversary can make one password try every six seconds. That's 600 per hour or about 15,000 per day or about 5,000,000 tries in a year. Assuming any sort of monitoring, it is unlikely someone could actually try continuously for a year. In fact, even if log files are only checked monthly, 500,000 tries is more plausible before the attack is noticed and steps taken to change passwords and make it harder to try more passwords.
ユーザパスワードが1年に一度変化して、敵が特定のアカウントのためのパスワードを推測できたという確率が1,000のうちの1未満であることが望まれていると仮定してください。 パスワードをシステムに送るのが、パスワードを試みる唯一の方法であるとさらに仮定してください。 そして、重要な質問は敵がどれくらいの頻度で可能性を試みることができるかということです。 敵が6秒毎に1つのパスワードを高々試みさせることができるように、遅れがシステムに取り入れられたと仮定してください。 それは、毎時のおよそ600か1日あたり1万5000か1年間でおよそ500万のトライです。 どんな種類のモニターも仮定して、だれかが実際に1年間絶え間なく試みることができたのは、ありそうもないです。 事実上、ログファイルが毎月チェックされるだけであっても、攻撃が気付かれる前に50万のトライが、よりもっともらしく、ステップで、変化パスワードに始めて、より多くのパスワードを試みるのは、より困難になります。
To have a one in a thousand chance of guessing the password in 500,000 tries implies a universe of at least 500,000,000 passwords or about 2^29. Thus 29 bits of randomness are needed. This can probably be achieved using the US DoD recommended inputs for password generation as it has 8 inputs which probably average over 5 bits of randomness each (see section 7.1). Using a list of 1000 words, the password could be expressed as a three word phrase (1,000,000,000 possibilities) or, using case insensitive letters and digits, six would suffice ((26+10)^6 = 2,176,782,336 possibilities).
50万におけるパスワードが試みると推測するという1,000機会で1つを持っているのは少なくとも5億のパスワードかおよそ2^29の宇宙を含意します。 したがって、偶発性の29ビットが必要です。 たぶんそれにはたぶんそれぞれ偶発性の5ビット以上を平均する8つの入力があるので(セクション7.1を見てください)パスワード世代に米国のDoDのお勧めの入力を使用することでこれを達成できます。 1000の単語のリストを使用して、3単語句(10億の可能性)としてパスワードを表すことができたか、または大文字と小文字を区別しない手紙とケタを使用して、6が十分であるだろう、(26、+10、)、^6 = 2,176,782,336可能性)
For a higher security password, the number of bits required goes up. To decrease the probability by 1,000 requires increasing the universe of passwords by the same factor which adds about 10 bits. Thus to have only a one in a million chance of a password being guessed under the above scenario would require 39 bits of randomness and a password
より高いセキュリティパスワードに関しては、必要であるビットの数は上がります。 確率を1,000減少させるのは、およそ10ビットを加えるのと同じ要素から宇宙を増強するのをパスワードを要求します。 したがって、上のシナリオの下で推測されるパスワードの100万機会で1つしか持っていないのは偶発性の39ビットとパスワードを必要とするでしょう。
Eastlake, Crocker & Schiller [Page 24] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[24ページ]RFC1750偶発性推薦
that was a four word phrase from a 1000 word list or eight letters/digits. To go to a one in 10^9 chance, 49 bits of randomness are needed implying a five word phrase or ten letter/digit password.
それは1000単語リストか8手紙/ケタからの4単語句でした。 10^9機会で1つまで行くために、5単語句か10手紙/ケタパスワードを含意して、偶発性の49ビットが必要です。
In a real system, of course, there are also other factors. For example, the larger and harder to remember passwords are, the more likely users are to write them down resulting in an additional risk of compromise.
もちろん、また、実システムには、他の要素があります。 例えば、パスワードが、より大きくて、覚えていにくければ困難であるほど、ユーザは、感染の追加リスクをもたらしながら、彼らをより書き留めそうです。
8.2 A Very High Security Cryptographic Key
8.2 非常に高いセキュリティ暗号化キー
Assume that a very high security key is needed for symmetric encryption / decryption between two parties. Assume an adversary can observe communications and knows the algorithm being used. Within the field of random possibilities, the adversary can try key values in hopes of finding the one in use. Assume further that brute force trial of keys is the best the adversary can do.
非常に高いセキュリティキーが2回のパーティーの間の左右対称の暗号化/復号化に必要であると仮定してください。 敵がコミュニケーションを観測できて、使用されるアルゴリズムを知っていると仮定してください。 無作為の可能性の分野の中では、敵はものが使用中であることがわかるという望みでキー値を試みることができます。 キーの力任せのトライアルが敵が尽くすことができるベストであるとさらに仮定してください。
8.2.1 Effort per Key Trial
8.2.1 主要なトライアルあたりの取り組み
How much effort will it take to try each key? For very high security applications it is best to assume a low value of effort. Even if it would clearly take tens of thousands of computer cycles or more to try a single key, there may be some pattern that enables huge blocks of key values to be tested with much less effort per key. Thus it is probably best to assume no more than a couple hundred cycles per key. (There is no clear lower bound on this as computers operate in parallel on a number of bits and a poor encryption algorithm could allow many keys or even groups of keys to be tested in parallel. However, we need to assume some value and can hope that a reasonably strong algorithm has been chosen for our hypothetical high security task.)
各キーを試すのにどのくらいの取り組みを要するでしょうか? 非常に高いセキュリティアプリケーションに、取り組みの低値を仮定するのは最も良いです。 単一のキーを試すには明確に何万ものコンピュータサイクルか以上かかっても、膨大なブロックのキー値がはるかに少ない1キーあたりの取り組みでテストされるのを可能にする何らかのパターンがあるかもしれません。 したがって、1未満が1キーあたり100サイクルの間結合されると仮定するのはたぶん最も良いです。 (キーの多くのキーかグループさえ平行で検査されるのをコンピュータが平行で多くのビットを作動させるとき、どんな明確な下界もこれになくて、貧しい暗号化アルゴリズムは、許容するかもしれません。 しかしながら、私たちは、何らかの値を仮定するのが必要であり、合理的に強いアルゴリズムが私たちの仮定している高いセキュリティタスクに選ばれたことを望むことができます。)
If the adversary can command a highly parallel processor or a large network of work stations, 2*10^10 cycles per second is probably a minimum assumption for availability today. Looking forward just a couple years, there should be at least an order of magnitude improvement. Thus assuming 10^9 keys could be checked per second or 3.6*10^11 per hour or 6*10^13 per week or 2.4*10^14 per month is reasonable. This implies a need for a minimum of 51 bits of randomness in keys to be sure they cannot be found in a month. Even then it is possible that, a few years from now, a highly determined and resourceful adversary could break the key in 2 weeks (on average they need try only half the keys).
敵が非常に平行なプロセッサかワークステーションの大きいネットワークを命令することができるなら、今日、10ヘルツの間の2*10^はたぶん有用性のための最小の仮定です。 ちょうど2、3の年を楽しみにしていて、改良が少なくとも1桁あるべきです。 したがって、10^を仮定する場合、9個のキーが毎時の2番目か3.6*10^11単位でチェックされるかもしれませんか、または1週間あたりの6*10^13か1カ月あたりの2.4*10^14が妥当です。 これは、必要性はキーの偶発性の最低51ビットが1カ月でそれらを見つけることができないのを確信しているのを含意します。 その時でさえ、現在からの数年、非常に断固として才略にたけた敵が2週間でキーを壊すことができたのは(彼らが必要とする平均では、キーの半分だけを試みてください)、可能です。
Eastlake, Crocker & Schiller [Page 25] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[25ページ]RFC1750偶発性推薦
8.2.2 Meet in the Middle Attacks
8.2.2 中央攻撃では、会ってください。
If chosen or known plain text and the resulting encrypted text are available, a "meet in the middle" attack is possible if the structure of the encryption algorithm allows it. (In a known plain text attack, the adversary knows all or part of the messages being encrypted, possibly some standard header or trailer fields. In a chosen plain text attack, the adversary can force some chosen plain text to be encrypted, possibly by "leaking" an exciting text that would then be sent by the adversary over an encrypted channel.)
暗号化アルゴリズムの構造がそれを許容するなら、「中央で会ってください」攻撃は選ばれているか、または知られているならプレーンテキストと結果として起こる暗号化されたテキストが利用可能であることが可能です。 (知られているプレーンテキスト攻撃では、敵はことによるといくつかの暗号化されたメッセージ、標準のヘッダーまたはトレーラ分野のすべてか一部を知っています。 選ばれたプレーンテキスト攻撃では、敵は強制的にプレーンテキストが選ばれたいくつかを暗号化させることができます、ことによると次に敵によって暗号化されたチャンネルの上に送られるおもしろいテキストが「漏らす」であることによって。)
An oversimplified explanation of the meet in the middle attack is as follows: the adversary can half-encrypt the known or chosen plain text with all possible first half-keys, sort the output, then half- decrypt the encoded text with all the second half-keys. If a match is found, the full key can be assembled from the halves and used to decrypt other parts of the message or other messages. At its best, this type of attack can halve the exponent of the work required by the adversary while adding a large but roughly constant factor of effort. To be assured of safety against this, a doubling of the amount of randomness in the key to a minimum of 102 bits is required.
中央攻撃における、大会の単純化しすぎている説明は以下の通りです: 敵は、すべての可能な前半キーがある知られているか選ばれたプレーンテキストを半分暗号化して、出力を分類して、次に、すべての後半キーでコード化されたテキストを半分解読することができます。 マッチが見つけられるなら、完全なキーを半分から組み立てて、メッセージか他のメッセージの他の部分を解読するのに使用できます。 最善では、このタイプの攻撃は取り組みの大きい、しかし、およそ一定の要素を加えている間に敵によって必要とされた仕事の解説者を半分にできます。 安全をこれに対して保証されるために、最低102ビットのキーの偶発性の量の倍増が必要です。
The meet in the middle attack assumes that the cryptographic algorithm can be decomposed in this way but we can not rule that out without a deep knowledge of the algorithm. Even if a basic algorithm is not subject to a meet in the middle attack, an attempt to produce a stronger algorithm by applying the basic algorithm twice (or two different algorithms sequentially) with different keys may gain less added security than would be expected. Such a composite algorithm would be subject to a meet in the middle attack.
中央攻撃における大会は、このように暗号アルゴリズムを分解できると仮定しますが、私たちはアルゴリズムに関する深い知識なしでそれを除外できません。 基本的なアルゴリズムは中央の大会を受けることがなくても、攻撃してください、生産物のaより強いアルゴリズムへの試みが二度基本的なアルゴリズムを適用して(2つの異なったアルゴリズム、連続して)、異なったキーと共に、予想であるだろうというほど加えられなかったセキュリティは獲得されているかもしれません。 そのような複合法は中央攻撃における大会を受けることがあるでしょう。
Enormous resources may be required to mount a meet in the middle attack but they are probably within the range of the national security services of a major nation. Essentially all nations spy on other nations government traffic and several nations are believed to spy on commercial traffic for economic advantage.
莫大なリソースが中央攻撃における大会を取り付けるのに必要であるかもしれませんが、たぶん大国の国家安全保障サービスの範囲の中にそれらはあります。 本質的には万国はトラフィックと数人の国が経済利点のために商業トラフィックを探ると信じられている他の国の政府を見張ります。
8.2.3 Other Considerations
8.2.3 他の問題
Since we have not even considered the possibilities of special purpose code breaking hardware or just how much of a safety margin we want beyond our assumptions above, probably a good minimum for a very high security cryptographic key is 128 bits of randomness which implies a minimum key length of 128 bits. If the two parties agree on a key by Diffie-Hellman exchange [D-H], then in principle only half of this randomness would have to be supplied by each party. However, there is probably some correlation between their random inputs so it is probably best to assume that each party needs to
以来、私たちは、専用コードがハードウェアを壊す可能性かそれともまさしくいくらが私たちがたぶん、非常に高いセキュリティ暗号化キーのための良い最小限が上では最低128ビットのキー長を含意する偶発性の128ビットであるという私たちの仮定を超えて欲しい安全域可能性であるかを考えてさえいません。 ディフィー-ヘルマンの交換[D-H]で2回のパーティーがキーに同意するなら、原則として半分のこの唯一の偶発性が各当事者によって供給されなければならないでしょう。 しかしながら、彼らの無作為の入力の間には、何らかの相関関係がたぶんあるので、各当事者が、必要であると仮定するのはたぶん最も良いです。
Eastlake, Crocker & Schiller [Page 26] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[26ページ]RFC1750偶発性推薦
provide at least 96 bits worth of randomness for very high security if Diffie-Hellman is used.
ディフィー-ヘルマンが使用されているなら、非常に高いセキュリティに偶発性の価値を少なくとも96ビット提供してください。
This amount of randomness is beyond the limit of that in the inputs recommended by the US DoD for password generation and could require user typing timing, hardware random number generation, or other sources.
この量の偶発性が、パスワード世代のために米国DoDによって推薦された入力におけるその限界を超えていて、ユーザのタイプしているタイミング、ハードウェア乱数発生、または他のソースを必要とするかもしれません。
It should be noted that key length calculations such at those above are controversial and depend on various assumptions about the cryptographic algorithms in use. In some cases, a professional with a deep knowledge of code breaking techniques and of the strength of the algorithm in use could be satisfied with less than half of the key size derived above.
それはそんなに有名なキー長が計算であるなら論議を呼んだ状態で当てにするでしょうに、そして、使用中の暗号アルゴリズムに関する様々な前提を当てにしてください。 いくつかの場合、コードに関する深い知識がテクニックと使用中のアルゴリズムの強さを破っている専門家を上で引き出される主要なサイズの半分未満に満たすことができました。
9. Conclusion
9. 結論
Generation of unguessable "random" secret quantities for security use is an essential but difficult task.
セキュリティ使用のための「蹄-可能」秘密の「無作為」の量の世代は不可欠の、しかし、難しいタスクです。
We have shown that hardware techniques to produce such randomness would be relatively simple. In particular, the volume and quality would not need to be high and existing computer hardware, such as disk drives, can be used. Computational techniques are available to process low quality random quantities from multiple sources or a larger quantity of such low quality input from one source and produce a smaller quantity of higher quality, less predictable key material. In the absence of hardware sources of randomness, a variety of user and software sources can frequently be used instead with care; however, most modern systems already have hardware, such as disk drives or audio input, that could be used to produce high quality randomness.
私たちは、そのような偶発性を生産するハードウェアのテクニックが比較的簡単であることを示しました。 ボリュームと品質は特に、高い必要はないでしょう、そして、ディスクドライブなどのように、既存のコンピュータ・ハードウェアは使用できます。 コンピュータのテクニックは1つのソースから入力されたそのような複数のソースか多く以上の量の低品質から低上質の無作為の量を処理して、よりわずかな量の、より高い品質を作り出すために利用可能です、それほど予測できない主要な材料。 偶発性のハードウェア源がないとき、代わりに頻繁に慎重にさまざまなユーザとソフトウェアソースを使用できます。 しかしながら、ほとんどの現代のシステムには、既に、高品質の偶発性を生産するのに使用できるディスクドライブか音声入力などのハードウェアがあります。
Once a sufficient quantity of high quality seed key material (a few hundred bits) is available, strong computational techniques are available to produce cryptographically strong sequences of unpredicatable quantities from this seed material.
一度、十分な数量の高品質の種子キーの材料(数100ビット)は利用可能で、強いコンピュータのテクニックがこの種子の材料で非叙述可能量の強い系列を暗号で作成するために利用可能であるということです。
10. Security Considerations
10. セキュリティ問題
The entirety of this document concerns techniques and recommendations for generating unguessable "random" quantities for use as passwords, cryptographic keys, and similar security uses.
このドキュメントの全体が使用のためにパスワード、暗号化キー、および同様のセキュリティ用途として「蹄-可能」「無作為」の量を生成するためのテクニックと推薦に関係があります。
Eastlake, Crocker & Schiller [Page 27] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[27ページ]RFC1750偶発性推薦
References
参照
[ASYMMETRIC] - Secure Communications and Asymmetric Cryptosystems, edited by Gustavus J. Simmons, AAAS Selected Symposium 69, Westview Press, Inc.
[ASYMMETRIC]--ガステイバスJ.シモンズ、AAAS Selected Symposium69、Westview Press Inc.によって編集された安全なCommunicationsとAsymmetric Cryptosystems
[BBS] - A Simple Unpredictable Pseudo-Random Number Generator, SIAM Journal on Computing, v. 15, n. 2, 1986, L. Blum, M. Blum, & M. Shub.
[BBS]--Simple Unpredictable Pseudo無作為のNumber Generator、Computingの上のシャムJournal v。 15、n。 2 1986、L.ブルーム、M.ブルーム、およびM.シューブ。
[BRILLINGER] - Time Series: Data Analysis and Theory, Holden-Day, 1981, David Brillinger.
[BRILLINGER]--時系列: データ分析と理論、ホールデン-日、1981、デヴィッドBrillinger。
[CRC] - C.R.C. Standard Mathematical Tables, Chemical Rubber Publishing Company.
[CRC]--C.のR.のC.の標準の数表、化学ゴム出版社。
[CRYPTO1] - Cryptography: A Primer, A Wiley-Interscience Publication, John Wiley & Sons, 1981, Alan G. Konheim.
[CRYPTO1] --暗号、: 入門書とワイリー-Interscience刊行物とジョン・ワイリーと息子、1981、アラン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.
[CRYPTO2] --暗号、: コンピュータのデータセキュリティ、ワイリー-Interscience刊行物、ジョン・ワイリー、および息子の新しい寸法、1982、カールH.マイヤーとスティーブン・M.マーチャーシュ。
[CRYPTO3] - Applied Cryptography: Protocols, Algorithms, and Source Code in C, John Wiley & Sons, 1994, Bruce Schneier.
[CRYPTO3]--暗号を適用します: Cとジョン・ワイリーと息子、1994、ブルース・シュナイアーのプロトコル、アルゴリズム、およびソースコード。
[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.
[DAVIS]--ディスクドライブの乱気流、暗号理論における進歩からの暗号の偶発性--暗号94年、コンピュータ科学#839の追出石-Verlag講演メモ(1984)はデイヴィス、ロスIhaka、およびフィリップ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. (See also FIPS 112, Password Usage, which includes FORTRAN code for performing DES.)
[DES]--データ暗号化規格、アメリカ合衆国、商務省、米国商務省標準技術局連邦情報処理基準(FIPS)46-1。 - データ暗号化アルゴリズム、American National Standards Institut、ANSI X3.92-1981。 (また、FIPS112、Password Usageを見てください。)(Password UsageはDESを実行するためのFORTRANコードを含んでいます)。
[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.
[デスMODES]--DES運転モード、アメリカ合衆国、商務省、米国商務省標準技術局連邦情報処理基準(FIPS)81。 - データ暗号化アルゴリズム--運転モード、American National Standards Institut、ANSI X3.106-1983。
[D-H] - New Directions in Cryptography, IEEE Transactions on Information Technology, November, 1976, Whitfield Diffie and Martin E. Hellman.
[D-H]--暗号に関する新傾向、情報技術の上のIEEEトランザクション、1976年11月、ホイットフィールド・ディフィー、およびマーチン・E.ヘルマン。
Eastlake, Crocker & Schiller [Page 28] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[28ページ]RFC1750偶発性推薦
[DoD] - Password Management Guideline, United States of America, Department of Defense, Computer Security Center, CSC-STD-002-85. (See also FIPS 112, Password Usage, which incorporates CSC-STD-002-85 as one of its appendices.)
[DoD]--パスワード管理ガイドライン、アメリカ合衆国、国防総省、コンピュータセキュリティセンター、CSC-STD-002-85。 (また、FIPS112、Password Usageを見てください。)(Password Usageは付録の1つとしてCSC-STD-002-85を組み込みます)。
[GIFFORD] - Natural Random Number, MIT/LCS/TM-371, September 1988, David K. Gifford
[ギフォード]--自然な乱数、MIT/LCS/TM-371、1988年9月、デヴィッド・K.ギフォード
[KNUTH] - The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Chapter 3: Random Numbers. Addison Wesley Publishing Company, Second Edition 1982, Donald E. Knuth.
[クヌース]--コンピュータ・プログラミング、第2巻の芸術: Seminumericalアルゴリズム、第3章: 乱数。 アディソンウエスリー出版社、第2版1982、ドナルド・E.クヌース。
[KRAWCZYK] - How to Predict Congruential Generators, Journal of Algorithms, V. 13, N. 4, December 1992, H. Krawczyk
[KRAWCZYK]--Congruentialジェネレータ、アルゴリズムのジャーナル、V.13、N.4、1992年12月、H.Krawczykを予測する方法
[MD2] - The MD2 Message-Digest Algorithm, RFC1319, April 1992, B. Kaliski [MD4] - The MD4 Message-Digest Algorithm, RFC1320, April 1992, R. Rivest [MD5] - The MD5 Message-Digest Algorithm, RFC1321, April 1992, R. Rivest
[MD2]--MD2メッセージダイジェストアルゴリズム、RFC1319、1992年4月、B.Kaliski[MD4]--MD4メッセージダイジェストアルゴリズム、RFC1320、1992年4月、R.Rivest[MD5]--MD5メッセージダイジェストアルゴリズム、RFC1321、1992年4月、R.Rivest
[PEM] - RFCs 1421 through 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
[PEM]--RFCs1421年から1424: - RFC1424、インターネット電子メールのためのプライバシー増進: パートIV: 主要な証明と関連サービス、02/10/1993、B.Kaliski--RFC1423、インターネット電子メールのためのプライバシー増進: パートIII: アルゴリズム、モード、および識別子、02/10/1993、D.Balenson--RFC1422、インターネット電子メールのためのプライバシー増進: パートII: 証明書ベースのKey Management、02/10/1993、S.ケント--RFC1421、インターネット電子メールのためのプライバシー増進: 部分I: メッセージ暗号化と認証手順、02/10/1993、J.リン
[SHANNON] - The Mathematical Theory of Communication, University of Illinois Press, 1963, Claude E. Shannon. (originally from: Bell System Technical Journal, July and October 1948)
[シャノン]--コミュニケーションの数学の理論、イリノイプレス大学、1963、クロード・E.シャノン。 (元々: ベルSystem Technical Journal、1948年7月、および10月からの)
[SHIFT1] - Shift Register Sequences, Aegean Park Press, Revised Edition 1982, Solomon W. Golomb.
[SHIFT1]--レジスタ系列、エーゲ海の公園プレス改訂版1982、ソロモンW.Golombを移動させてください。
[SHIFT2] - Cryptanalysis of Shift-Register Generated Stream Cypher Systems, Aegean Park Press, 1984, Wayne G. Barker.
[SHIFT2]--ウェイン・G.バーカー、シフトレジスタの暗号文解読術はストリーム暗号化システム、エーゲ海の公園プレス、1984を生成しました。
[SHS] - Secure Hash Standard, United States of American, National Institute of Science and Technology, Federal Information Processing Standard (FIPS) 180, April 1993.
[SHS]--ハッシュ規格、科学技術のアメリカの、そして、国家の研究所の合衆国を確保してください、連邦情報処理基準(FIPS)180、1993年4月。
[STERN] - Secret Linear Congruential Generators are not Cryptograhically Secure, Proceedings of IEEE STOC, 1987, J. Stern.
[スターン]--J.スターン、秘密のLinear Congruential GeneratorsはCryptograhically Secure、IEEE STOC、1987年のProceedingsではありません。
Eastlake, Crocker & Schiller [Page 29] RFC 1750 Randomness Recommendations for Security December 1994
イーストレーク、セキュリティ1994年12月のためのクロッカーとシラー[29ページ]RFC1750偶発性推薦
[VON NEUMANN] - Various techniques used in connection with random digits, von Neumann's Collected Works, Vol. 5, Pergamon Press, 1963, J. von Neumann.
[VON NEUMANN]--様々なテクニックは乱数、フォンノイマンのCollected WorksでVol.5、Pergamon Press、1963を使用しました、J.フォンノイマン。
Authors' Addresses
作者のアドレス
Donald E. Eastlake 3rd Digital Equipment Corporation 550 King Street, LKG2-1/BB3 Littleton, MA 01460
DEC550キング・ストリート、ドナルドE.イーストレーク第3LKG2-1/BB3リトルトン、MA 01460
Phone: +1 508 486 6577(w) +1 508 287 4877(h) EMail: dee@lkg.dec.com
以下に電話をしてください。 +1 508 486 6577(w)+1 508 287 4877(h)メール: dee@lkg.dec.com
Stephen D. Crocker CyberCash Inc. 2086 Hunters Crest Way Vienna, VA 22181
スティーブンD.医者サイバーキャッシュ株式会社2086のハンターは道ウィーン(ヴァージニア)22181の前立てを付けます。
Phone: +1 703-620-1222(w) +1 703-391-2651 (fax) EMail: crocker@cybercash.com
以下に電話をしてください。 +1 703-620-1222 (w) +1 703-391-2651(ファックス)はメールされます: crocker@cybercash.com
Jeffrey I. Schiller Massachusetts Institute of Technology 77 Massachusetts Avenue Cambridge, MA 02139
マサチューセッツ通りケンブリッジ、ジェフリーI.シラーマサチューセッツ工科大学77MA 02139
Phone: +1 617 253 0161(w) EMail: jis@mit.edu
以下に電話をしてください。 +1 617 253 0161(w)メール: jis@mit.edu
Eastlake, Crocker & Schiller [Page 30]
イーストレーク、クロッカー、およびシラー[30ページ]
一覧
スポンサーリンク
