NIST IR 6390 日本語訳
英語タイトル : Randomness Testing of the Advanced Encryption Standard Candidate Algorithms日本語タイトル : 次世代暗号標準(Advanced Encryption Standard)候補アルゴリズムのランダムネス検定
公開日 : 1999-09-01
原文URL : https://csrc.nist.gov/pubs/ir/6390/final
翻訳編集 : 自動生成(有志による非公式の日本語訳), 原文取得日 : 2026-10-31, 訳文 : 97 / 97 ブロック
[要約] NIST IR 6390 は、次世代暗号標準(AES)の候補アルゴリズムの出力を、乱数生成器としての適性という観点からランダムネスについて評価した内部報告書です。15 の候補アルゴリズムのそれぞれについて 9 種類のデータセット(合計 135)を取り込み、128 ビット鍵に焦点を当てて NIST の統計的検定を適用しています。報告書は、ランダムな振る舞いを示す暗号アルゴリズムが備えているべき特性を挙げ、データの種別、経験的な結果、結果の解釈を順に説明しています。結果として、HPC はランダムでないように見え、Crypton、DEAL、Frog、RC6、Twofish は結論に至らず、残りのアルゴリズムはランダムネスからの逸脱がないことを示唆するとしています。
NISTIR 6390
NISTIR 6390
Randomness Testing of the Advanced Encryption Standard Candidate Algorithms
次世代暗号標準(Advanced Encryption Standard)候補アルゴリズムのランダムネス検定
Juan Soto, Jr.
Juan Soto, Jr.
U.S. DEPARTMENT OF COMMERCE
Technology Administration
National Institute of Standards and Technology
100 Bureau Drive, Stop 8930
Gaithersburg, MD 20899-8930
米国商務省
技術管理局
国立標準技術研究所
100 Bureau Drive, Stop 8930
Gaithersburg, MD 20899-8930
September 1999
1999年9月
U.S. DEPARTMENT OF COMMERCE
William M. Daley, Secretary
TECHNOLOGY ADMINISTRATION
Gary R. Bachula, Acting Under Secretary for Technology
NATIONAL INSTITUTE OF STANDARDS AND TECHNOLOGY
Raymond G. Kammer, Director
米国商務省
William M. Daley 長官
技術管理局
Gary R. Bachula、商務次官代行(技術担当)
国立標準技術研究所
Raymond G. Kammer、所長
Randomness Testing of the Advanced Encryption Standard Candidate Algorithms
次世代暗号標準(Advanced Encryption Standard)候補アルゴリズムのランダムネス検定
Affiliation
所属
Juan Soto, Jr.
National Institute of Standards and Technology
100 Bureau Drive, Stop 8930
Gaithersburg, MD 20899-8930
(301) 975-4641 (Voice)
(301) 948-1233 (Fax)
soto@nist.gov
Juan Soto, Jr.
国立標準技術研究所
100 Bureau Drive, Stop 8930
Gaithersburg, MD 20899-8930
(301) 975-4641 (Voice)
(301) 948-1233 (Fax)
soto@nist.gov
Abstract
概要
One of the criteria used to evaluate the Advanced Encryption Standard candidate algorithms was their demonstrated suitability as random number generators. That is, the evaluation of their output utilizing statistical tests should not provide any means by which to computationally distinguish them from a truly random source. This internal report lists several characteristics which an encryption algorithm exhibiting random behavior should possess, describes how the output for each candidate algorithm was evaluated for randomness, discusses what has been learned utilizing the NIST statistical tests, and finally provides an interpretation of the results.
次世代暗号標準(AES)の候補アルゴリズムを評価するために用いられた基準の 1 つは、乱数生成器としての適性が実証されていることでした。すなわち、統計的検定を用いて候補アルゴリズムの出力を評価しても、それらを真にランダムな発生源から計算量的に区別する手段が得られてはなりません。この内部報告書は、ランダムな振る舞いを示す暗号アルゴリズムが備えているべき特性をいくつか挙げ、各候補アルゴリズムの出力をランダムネスについてどのように評価したかを説明し、NIST の統計的検定を用いて分かったことを論じ、最後に結果の解釈を示します。
1. Introduction
1. はじめに
One of the criteria used to evaluate the Advanced Encryption Standard (AES) candidate algorithms was their demonstrated suitability as random number generators. That is, the evaluation of their outputs utilizing statistical tests should not provide any means by which to computationally distinguish them from truly random sources. The evaluation reported on here focused on 128-bit keys. Future work will address the 192-bit and 256-bit key sizes.
次世代暗号標準(AES)の候補アルゴリズムを評価するために用いられた基準の 1 つは、乱数生成器としての適性が実証されていることでした。すなわち、統計的検定を用いて出力を評価したときに、それらを真にランダムな発生源から計算量的に区別できる手段が得られてはなりません。ここで報告する評価は、128 ビット鍵に焦点を当てました。今後の作業では、192 ビットと 256 ビットの鍵長を扱います。
This paper lists several characteristics that an encryption algorithm exhibiting random behavior should possess, describes how the output for each candidate algorithm was evaluated for randomness, discusses what has been learned utilizing the NIST statistical tests, and finally provides an interpretation of the results.
本稿は、ランダムな振る舞いを示す暗号アルゴリズムが備えているべき特性をいくつか挙げ、各候補アルゴリズムの出力をランダムネスについてどのように評価したかを説明し、NIST の統計的検定を用いて分かったことを論じ、最後に結果の解釈を示します。
At least 135 distinct data sets were obtained, analyzed and re-analyzed to ensure accuracy. In all, a total of 226,106,880 128-bit blocks (28,941,680,640 bits) were stored, processed and analyzed. File management and data management for this amount of data was always a major concern.
少なくとも 135 の異なるデータセットを入手し、精度を確保するために分析と再分析を行いました。全体で、合計 226,106,880 個の 128 ビットブロック(28,941,680,640 ビット)を保存、処理、分析しました。この量のデータに対するファイル管理とデータ管理は、常に大きな懸念事項でした。
The NIST statistical tests were executed on several platforms in order to manage the volume of data. On many occasions, testing was discontinued due to seemingly non-random behavior. Such behavior could be attributed to any number of factors, which include the data, the data extraction source codes, the cryptographic algorithm source codes, and the statistical tests.
NIST の統計的検定は、データ量を管理するために複数のプラットフォームで実行しました。多くの場合、ランダムでないように見える振る舞いのために、検定を中止しました。そのような振る舞いは、データ、データ抽出のソースコード、暗号アルゴリズムのソースコード、統計的検定など、さまざまな要因に起因し得ます。
In Section 2.0, the categories of data are defined and described. In Section 3.0, the empirical results compiled to date are discussed. In Section 4.0, a summary of lessons learned and an interpretation of the test results is presented. Lastly, an appendix that briefly describes the individual statistical tests has been included.
2.0 節では、データの種別を定義し説明します。3.0 節では、これまでにまとめた経験的な結果を論じます。4.0 節では、得られた教訓のまとめと、検定結果の解釈を示します。最後に、個々の統計的検定を簡潔に説明する付録を含めています。
2. AES Data
2. AES のデータ
Fifteen encryption algorithms were selected as candidates for the AES. NIST harnessed and analyzed nine different sets of data for each of these algorithms (135 data sets in all). These data sets were selected because it was believed that they would be useful in evaluating the randomness of cryptographic algorithms. Table 1 highlights these categories of data.
15 の暗号アルゴリズムが、AES の候補として選ばれました。NIST は、これらのアルゴリズムのそれぞれについて、9 種類の異なるデータセットを利用して分析しました(合計 135 のデータセット)。これらのデータセットは、暗号アルゴリズムのランダムネスを評価するのに役立つと考えられたため、選ばれました。表 1 に、これらのデータの種別を示します。
Table 1. Categories of Data
表 1. データの種別
| 1. 128-Bit Key Avalanche |
| 2. Plaintext Avalanche |
| 3. Plaintext/Ciphertext Correlation |
| 4. Cipher Block Chaining Mode |
| 5. Random Plaintext/Random 128-Bit Keys |
| 6. Low Density Plaintext |
| 7. Low Density 128-Bit Keys |
| 8. High Density Plaintext |
| 9. High Density 128-Bit Keys |
| 1. 128ビット鍵のアバランシェ |
| 2. 平文のアバランシェ |
| 3. 平文と暗号文の相関 |
| 4. 暗号ブロック連鎖モード |
| 5. ランダムな平文/ランダムな128ビット鍵 |
| 6. 低密度平文 |
| 7. 低密度128ビット鍵 |
| 8. 高密度平文 |
| 9. 高密度128ビット鍵 |
2.1 128-Bit Key Avalanche and Plaintext Avalanche
2.1 128 ビット鍵の Key Avalanche と Plaintext Avalanche
To examine the sensitivity of individual algorithms to changes in input parameters (i.e., the key or the plaintext), 384 binary sequences were analyzed in each case. In the key avalanche case, 384 sequences (1,048,576 bits per sequence) were parsed from the resulting string, constructed as follows: given 24,576 random 128-bit keys, and a plaintext of all zeroes, 3,145,728 derived blocks were concatenated. Each derived block is based on the XOR of the “ciphertext formed using the fixed plaintext and a random 128-bit key,” and the “ciphertext formed using the fixed plaintext and the perturbed random 128-bit key with the ith bit changed, for \(1 \le i \le 128\).” In the case of the plaintext avalanche property, substitute “random plaintext(s)“ for “random 128-bit key(s)” in the above description, “128-bit key of all-zeroes” for “plaintext of all zeroes” and “fixed 128-bit key” for “fixed plaintext.”
入力パラメータ(すなわち、鍵または平文)の変化に対する個々のアルゴリズムの感度を調べるため、それぞれのケースで 384 個の 2 値系列を分析しました。Key Avalanche の場合、384 個の系列(1 系列あたり 1,048,576 ビット)は、次のように構成した文字列から切り出しました。24,576 個のランダムな 128 ビット鍵と、すべてゼロの平文が与えられたとき、3,145,728 個の派生ブロックを連結しました。各派生ブロックは、「固定の平文とランダムな 128 ビット鍵を用いて形成した暗号文」と、「固定の平文と、摂動を加えたランダムな 128 ビット鍵を用いて形成した暗号文(\(1 \le i \le 128\) に対して i 番目(ith)のビットを変更)」との XOR に基づいています。Plaintext Avalanche 特性の場合は、上記の説明の「ランダムな 128 ビット鍵」を「ランダムな平文」に、「すべてゼロの平文」を「すべてゼロの 128 ビット鍵」に、「固定の平文」を「固定の 128 ビット鍵」に置き換えます。
2.2 Plaintext/Ciphertext Correlation
2.2 Plaintext/Ciphertext Correlation
In order to study the correlation of plaintext/ciphertext pairs, 128 sequences (1,048,576 bits per sequence) were examined for each algorithm. Given a random 128-bit key and 8,128 random plaintext blocks, a binary sequence was constructed concatenating 8,128 derived blocks (where a derived block is the result of applying the XOR operator on the plaintext block and its corresponding ciphertext block computed in the ECB mode).
平文と暗号文のペアの相関を調べるため、各アルゴリズムについて 128 個の系列(1 系列あたり 1,048,576 ビット)を検査しました。ランダムな 128 ビット鍵と 8,128 個のランダムな平文ブロックが与えられたとき、8,128 個の派生ブロック(派生ブロックとは、平文ブロックと、ECB モードで計算したそれに対応する暗号文ブロックに XOR 演算子を適用した結果)を連結して、2 値系列を構成しました。
Using the 8,128 (previously selected) plaintext blocks, the procedure was repeated 127 times, i.e., once for each (additional) random 128-bit key.
8,128 個の(先に選んだ)平文ブロックを使って、この手順を 127 回、すなわち(追加の)ランダムな 128 ビット鍵ごとに 1 回ずつ繰り返しました。
2.3 Cipher Block Chaining Mode
2.3 Cipher Block Chaining Mode
Given a random 128-bit key, a 128-bit initialization vector (IV) of all zeroes, and a 128-bit plaintext block (PT) of all zeroes, a binary sequence of 1,048,576 bits was constructed using ciphertext computed in the CBC mode. That is, a binary sequence consisted of 8,192 concatenated 128-bit ciphertext blocks. The first ciphertext block (\(\mathrm{CT}_1\)) is defined by \(\mathrm{CT}_1 = E_k(\mathrm{IV} \oplus \mathrm{PT})\). Subsequent ciphertext blocks were defined by \(\mathrm{CT}_{i+1} = E_k(\mathrm{CT}_i \oplus \mathrm{PT})\) for \(1 \le i \le 8{,}191\). In all, 300 binary sequences were constructed, each with a different random 128-bit key.
ランダムな 128 ビット鍵、すべてゼロの 128 ビットの初期化ベクトル(IV)、およびすべてゼロの 128 ビット平文ブロック(PT)が与えられたとき、CBC モードで計算した暗号文を用いて、1,048,576 ビットの 2 値系列を構成しました。すなわち、2 値系列は、連結した 8,192 個の 128 ビット暗号文ブロックで構成されます。最初の暗号文ブロック(\(\mathrm{CT}_1\))は、\(\mathrm{CT}_1 = E_k(\mathrm{IV} \oplus \mathrm{PT})\) で定義されます。それ以降の暗号文ブロックは、\(\mathrm{CT}_{i+1} = E_k(\mathrm{CT}_i \oplus \mathrm{PT})\)(\(1 \le i \le 8{,}191\))で定義されました。全体で 300 個の 2 値系列を構成し、それぞれに異なるランダムな 128 ビット鍵を使いました。
2.4 Random Plaintext/Random 128-Bit Keys
2.4 Random Plaintext/Random 128-Bit Keys
In order to examine the randomness of ciphertext (based on random plaintext and random 128-bit keys), 128 sequences were constructed. Each sequence was a result of the concatenation of 8,128 ciphertext blocks using 8,128 random plaintexts and a random 128-bit key in the ECB mode.
(ランダムな平文とランダムな 128 ビット鍵に基づく)暗号文のランダムネスを調べるため、128 個の系列を構成しました。各系列は、ECB モードで 8,128 個のランダムな平文とランダムな 128 ビット鍵を使って得た、8,128 個の暗号文ブロックを連結した結果です。
2.5 Low Density Plaintext and Low Density 128-Bit Keys
2.5 Low Density Plaintext と Low Density 128-Bit Keys
Two data sets were created based on low-density blocks used as either plaintext or 128-bit keys. Each data set consisted of 128 sequences. Each sequence consisted of 8,257 ciphertext blocks computed in the ECB mode. These ciphertext blocks were formed from one all zero plaintext block (128-bit key), 128 plaintext blocks (128-bit keys) of a single one and 127 zeroes (the one appearing in each of the possible 128 bit positions), and 8,128 plaintext blocks (128-bit keys) of two ones and 126 zeroes (the two ones appearing in each combination of two bit positions within the 128-bit positions).
平文または 128 ビット鍵のいずれかとして使う低密度ブロックに基づいて、2 つのデータセットを作成しました。各データセットは 128 個の系列で構成されました。各系列は、ECB モードで計算した 8,257 個の暗号文ブロックで構成されました。これらの暗号文ブロックは、すべてゼロの平文ブロック(128 ビット鍵)1 個、1 が 1 つと 0 が 127 個からなる平文ブロック(128 ビット鍵)128 個(この 1 は、取り得る 128 のビット位置のそれぞれに現れます)、および 1 が 2 つと 0 が 126 個からなる平文ブロック(128 ビット鍵)8,128 個(この 2 つの 1 は、128 のビット位置のうち 2 つのビット位置のあらゆる組み合わせに現れます)から形成しました。
2.6 High Density Plaintext and High Density 128-Bit Keys
2.6 High Density Plaintext と High Density 128-Bit Keys
Two data sets were created based on high-density blocks used as either plaintext or 128-bit keys. Each data set consisted of 128 sequences. Each sequence consisted of 8,257 ciphertext blocks computed in the ECB mode. These ciphertext blocks were formed from one all ones plaintext block (128-bit key), 128 plaintext blocks (128-bit keys) of a single zero and 127 ones (the zero appearing in each of the possible 128 bit positions), and 8,128 plaintext blocks (128-bit keys) of two zeroes and 126 ones (the two zeroes appearing in each combination of two bit positions within the 128-bit positions).
平文または 128 ビット鍵のいずれかとして使う高密度ブロックに基づいて、2 つのデータセットを作成しました。各データセットは 128 個の系列で構成されました。各系列は、ECB モードで計算した 8,257 個の暗号文ブロックで構成されました。これらの暗号文ブロックは、すべて 1 の平文ブロック(128 ビット鍵)1 個、0 が 1 つと 1 が 127 個からなる平文ブロック(128 ビット鍵)128 個(この 0 は、取り得る 128 のビット位置のそれぞれに現れます)、および 0 が 2 つと 1 が 126 個からなる平文ブロック(128 ビット鍵)8,128 個(この 2 つの 0 は、128 のビット位置のうち 2 つのビット位置のあらゆる組み合わせに現れます)から形成しました。
3. Empirical Analysis
3. 経験的分析
Table 2 describes the breakdown of the simulation-input parameters per data category. The number of sequences utilized in the samples varied from 128 to 384. Based on earlier experiments conducted on pseudo-random number generators with sequences consisting of 1,000,000 bits, sequences consisting of \(2^{20}\) (i.e., 1,048,576) bits were chosen. In four instances, sequences consisting of 1,056,896 bits were chosen, which corresponded to the number of bits in 8,257 ciphertexts. The number of statistical tests applied varied from 59 to 187. The difference was due to the specification of alternative input parameters such as the number of templates to be used.
表 2 は、データ種別ごとのシミュレーション入力パラメータの内訳を示しています。標本に用いた系列の数は 128 から 384 までさまざまでした。1,000,000 ビットからなる系列を用いた擬似乱数生成器に対する以前の実験に基づき、\(2^{20}\)(すなわち 1,048,576)ビットからなる系列を選びました。4 つのケースでは、8,257 個の暗号文のビット数に相当する、1,056,896 ビットからなる系列を選びました。適用した統計的検定の数は 59 から 187 までさまざまでした。この違いは、使用するテンプレートの数などの、代替の入力パラメータの指定によるものでした。
For each experiment, the significance level was fixed at 0.01, which implies that, ideally, no more than one binary sequence should be rejected for each sample of 100 binary sequences evaluated by a statistical test. However, in all likelihood, any given data set will deviate from this ideal case. A more realistic interpretation is to use a confidence interval (CI) for the “proportion of binary sequences” that should pass at the 0.01 level. Thus, a data set that fails more than 5% of the sequences is flagged as suspect.
各実験で、有意水準は 0.01 に固定しました。これは、理想的には、統計的検定で評価する 2 値系列 100 個の標本ごとに、棄却される 2 値系列は 1 個以下となることを意味します。しかし、実際には、どのデータセットもこの理想的なケースから逸脱する可能性が高いです。より現実的には、有意水準 0.01 で合格するはずの「2 値系列の割合」に対して信頼区間(CI)を用いて解釈します。したがって、系列の 5% を超えて不合格となるデータセットは、疑わしいものとして印を付けます。
Table 2. Breakdown of the Numerical Simulation Input Parameters
表 2. 数値シミュレーション入力パラメータの内訳
| Data Category | Sample Size/ Sequence Length | Number of Tests Applied |
|---|---|---|
| 128-Bit Key Avalanche | 384/1,048,576 | 187 |
| Plaintext Avalanche | 384/1,048,576 | 187 |
| Plaintext/Ciphertext Correlation | 128/1,048,576 | 59 |
| Cipher Block Chaining Mode | 300/1,048,576 | 59 |
| Random Plaintext/Random 128-Bit Key | 128/1,048,576 | 59 |
| Low Density Plaintext Input | 128/1,056,896 | 59 |
| Low Density 128-Bit Key Input | 128/1,056,896 | 59 |
| High Density Plaintext Input | 128/1,056,896 | 59 |
| High Density 128-Bit Key Input | 128/1,056,896 | 59 |
| データ種別 | 標本サイズ/ 系列長 | 適用した 検定の数 |
|---|---|---|
| 128ビット鍵のアバランシェ | 384/1,048,576 | 187 |
| 平文のアバランシェ | 384/1,048,576 | 187 |
| 平文と暗号文の相関 | 128/1,048,576 | 59 |
| 暗号ブロック連鎖モード | 300/1,048,576 | 59 |
| ランダムな平文/ランダムな128ビット鍵 | 128/1,048,576 | 59 |
| 低密度平文入力 | 128/1,056,896 | 59 |
| 低密度128ビット鍵入力 | 128/1,056,896 | 59 |
| 高密度平文入力 | 128/1,056,896 | 59 |
| 高密度128ビット鍵入力 | 128/1,056,896 | 59 |
Table 3 highlights the maximum number of binary sequences that are expected to be rejected at the chosen significance level. For example, if the sample consists of 128 sequences, the rejection rate should not exceed 4.657, or simply expressed, 4 sequences. The maximum number of rejections was computed using the formula:
表 3 は、選んだ有意水準で棄却されると予想される 2 値系列の最大数を示しています。たとえば、標本が 128 個の系列で構成される場合、棄却率は 4.657 を超えないはずであり、単純に表すと 4 系列です。棄却の最大数は、次の式で計算しました。
where s is the sample size and \(\alpha\) is the significance level.
ここで、s は標本サイズ、\(\alpha\) は有意水準です。
Table 3. Decision Rules for the Determination of Non-Randomness
表 3. ランダムでないことを判定するための決定規則
| Number of Sequences | Significance Level \(\alpha = 0.01\) | Significance Level \(\alpha = 0.01\) with CI |
|---|---|---|
| 128 | 1.28 | 4.657 |
| 300 | 3.00 | 8.170 |
| 384 | 3.84 | 9.689 |
| 系列の数 | 有意水準 \(\alpha = 0.01\) | 信頼区間(CI)を用いた有意水準 \(\alpha = 0.01\) |
|---|---|---|
| 128 | 1.28 | 4.657 |
| 300 | 3.00 | 8.170 |
| 384 | 3.84 | 9.689 |
Based on the current version of the NIST statistical tests, each of the algorithms was evaluated. Those algorithms that did not demonstrate deviation from randomness include CAST-256, DFC, E2, LOKI-97, MAGENTA, MARS, RIJNDAEL, SAFER+, and SERPENT. The remaining algorithms appeared to have displayed1 deviation from randomness. A case by case description follows.
NIST の統計的検定の現行版に基づいて、各アルゴリズムを評価しました。ランダムネスからの逸脱を示さなかったアルゴリズムは、CAST-256、DFC、E2、LOKI-97、MAGENTA、MARS、RIJNDAEL、SAFER+、SERPENT です。残りのアルゴリズムは、ランダムネスからの逸脱を示した1ように見えました。以下に個別のケースを説明します。
CRYPTON
CRYPTON
(a) 128-Bit Key Avalanche: Preliminary analysis suggests too many rejections of the 001001111 non-periodic template. A total of 11 rejections was reported when the expected number should be no more than 9.
(a) 128-Bit Key Avalanche: 予備的な分析は、001001111 の非周期テンプレートの棄却が多すぎることを示唆しています。予想される数は 9 以下であるはずのところ、合計 11 個の棄却が報告されました。
(b) Random Plaintext/Random 128-Bit Keys: Preliminary analysis suggests a problem given an excessive number of visits to the states x = -3 and x = -4 in the random excursion test. In both instances, there were 4 rejections out of 76 sequences processed when the expected number should be no more than 3.
(b) Random Plaintext/Random 128-Bit Keys: 予備的な分析は、ランダムエクスカーション検定で状態 x = -3 と x = -4 への訪問回数が過度に多いことから、問題があることを示唆しています。どちらの場合も、処理した 76 個の系列のうち 4 個が棄却されましたが、予想される数は 3 以下であるはずです。
DEAL
DEAL
(a) Random Plaintext/Random 128-Bit Keys: Preliminary analysis suggests a problem given an excessive number of visits to the state x = +2 in the random excursions test. In this instance, there were 4 rejections out of the 76 sequences processed when the expected number should be no more than 3.
(a) Random Plaintext/Random 128-Bit Keys: 予備的な分析は、ランダムエクスカーション検定で状態 x = +2 への訪問回数が過度に多いことから、問題があることを示唆しています。この場合、処理した 76 個の系列のうち 4 個が棄却されましたが、予想される数は 3 以下であるはずです。
FROG
FROG
(a) Low Density 128-Bit Keys: Preliminary analysis suggests a problem given an excessive number of visits to the state x = +3 in the random excursions test. In this instance, there were 4 rejections out of the 71 sequences processed when the expected number should be no more than 3.
(a) Low Density 128-Bit Keys: 予備的な分析は、ランダムエクスカーション検定で状態 x = +3 への訪問回数が過度に多いことから、問題があることを示唆しています。この場合、処理した 71 個の系列のうち 4 個が棄却されましたが、予想される数は 3 以下であるはずです。
HPC
HPC
(a) 128-Bit Key Avalanche: Preliminary analysis suggests that this algorithm dramatically fails many statistical tests. The specific tests that rejected the sample of 384 sequences follows, with the number of sequences rejected specified in parenthesis (in each case, the expected number of rejections should not exceed 9): frequency (75), block frequency (91), cumulative sum forward (71), cumulative sum reverse (75), runs (77), rank (29), universal statistical (92), approximate entropy (92), and Lempel-Ziv complexity (91). It has been determined that 1 in 256 (128-bit) keys is an equivalent key2. NIST’s experiments support this theoretical finding. Clearly, a rejection of 23.96% in one test (the largest rejection by any statistical test) is far too large. Hence, this algorithm failed, given the statistically significant results at the 0.01 level.
(a) 128-Bit Key Avalanche: 予備的な分析は、このアルゴリズムが多くの統計的検定で劇的に不合格となることを示唆しています。384 個の系列の標本を棄却した具体的な検定を、棄却された系列の数を括弧内に示して次に挙げます(いずれの場合も、棄却の予想される数は 9 を超えないはずです)。frequency (75)、block frequency (91)、cumulative sum forward (71)、cumulative sum reverse (75)、runs (77)、rank (29)、universal statistical (92)、approximate entropy (92)、Lempel-Ziv complexity (91) です。256 個に 1 個の(128 ビットの)鍵が等価鍵2であることが判明しています。NIST の実験は、この理論的な知見を裏付けています。1 つの検定で 23.96%(いずれの統計的検定による棄却でも最大)が棄却されるのは、明らかに大きすぎます。したがって、このアルゴリズムは、0.01 の水準で統計的に有意な結果が得られたことから、不合格となりました。
RC6
RC6
(a) 128-Bit Key Avalanche: Preliminary analysis suggests that there were too many rejections for the non-periodic templates test. There were three templates (01011011, 010111011, 110001010) which rejected 10, 10, and 11 binary sequences respectively. The expected number of rejections should not exceed 9.
(a) 128-Bit Key Avalanche: 予備的な分析は、非周期テンプレート検定で棄却が多すぎたことを示唆しています。3 つのテンプレート(01011011、010111011、110001010)が、それぞれ 10 個、10 個、11 個の 2 値系列を棄却しました。棄却の予想される数は 9 を超えないはずです。
(b) High Density Plaintext: Preliminary analysis suggests a problem given 6 rejections for both the frequency test, and the cumulative sum forward test. The expected number of rejections should not exceed 4.
(b) High Density Plaintext: 予備的な分析は、frequency 検定と cumulative sum forward 検定の両方で 6 個の棄却があったことから、問題があることを示唆しています。棄却の予想される数は 4 を超えないはずです。
TWOFISH
TWOFISH
(a) Random Plaintext/Random 128-Bit Keys: Preliminary analysis suggests a problem given an excessive number of visits to the state x = +9 in the random excursions variant test. In this instance there were 4 rejections out of the 83 sequences processed when the expected number should not exceed 3.
(a) Random Plaintext/Random 128-Bit Keys: 予備的な分析は、ランダムエクスカーションバリアント検定で状態 x = +9 への訪問回数が過度に多いことから、問題があることを示唆しています。この場合、処理した 83 個の系列のうち 4 個が棄却されましたが、予想される数は 3 を超えないはずです。
(b) Low Density Plaintext: Preliminary analysis seems to indicate sensitivity to the cumulative sums forward test. The total number of rejections was 7, which represents over 5% of the sample. The expected number of rejections should not exceed 4.
(b) Low Density Plaintext: 予備的な分析は、cumulative sums forward 検定に対する感度があることを示しているようです。棄却の総数は 7 個で、標本の 5% を超えています。棄却の予想される数は 4 を超えないはずです。
4. Conclusion
4. 結論
During round one testing, numerous statistical tests were applied on 135 sets of data, which collectively span many well-known properties that any good cryptographic algorithm should satisfy. These properties include any detectable correlation between plaintext/ciphertext pairs, any detectable bias due to single bit changes to either a plaintext or a 128-bit key, in addition to many others.
第 1 ラウンドの検定では、135 組のデータに多数の統計的検定を適用しました。これらは全体として、優れた暗号アルゴリズムが満たすべき多くのよく知られた性質を網羅しています。これらの性質には、平文と暗号文のペアの間に検出可能な相関がないこと、平文または 128 ビット鍵の 1 ビットの変化に起因する検出可能な偏りがないことなどが含まれ、そのほかにも多くあります。
It appears that the HPC algorithm is non-random given the statistically significant results obtained at the 0.01 level for the 128-bit key avalanche data set. Unfortunately, the results for five algorithms, Crypton3, DEAL4, Frog5, RC66 and Twofish7 are inconclusive. Although preliminary testing suggests minor deviations from randomness8 for these five algorithms, one sample alone cannot provide sufficient evidence. In each case more samples should be evaluated to determine whether statistically significant results are consistently present.
HPC アルゴリズムは、128 ビット鍵の Key Avalanche データセットで 0.01 の水準で統計的に有意な結果が得られたことから、ランダムでないように見えます。残念ながら、5 つのアルゴリズム、Crypton3、DEAL4、Frog5、RC66、Twofish7 の結果は、結論に至りません。予備的な検定は、これら 5 つのアルゴリズムにランダムネスからのわずかな逸脱8があることを示唆していますが、標本が 1 つだけでは十分な証拠にはなりません。いずれの場合も、統計的に有意な結果が一貫して存在するかどうかを判定するために、より多くの標本を評価すべきです。
It is worth noting that the specific statistical tests that predominantly flagged several algorithms as suspect were the cumulative sums (cusum) test and the random excursion test. To further evaluate the cusum test, extensive simulations were conducted on the SHA-1 generator and the Twofish algorithm. The results suggest that data flagged as non-random for the Twofish and RC6 algorithms should be treated as statistical anomalies. Similarly, due to the natural filtering process for the random excursion test, small sample sizes may incorrectly lead one to commit a type I error, i.e., labeling data as nonrandom when it truly appears to be random.
いくつかのアルゴリズムを疑わしいものとして主に指摘した具体的な統計的検定は、累積和(cusum)検定とランダムエクスカーション検定であったことは注目に値します。cusum 検定をさらに評価するため、SHA-1 生成器と Twofish アルゴリズムに対して大規模なシミュレーションを実施しました。その結果は、Twofish と RC6 のアルゴリズムでランダムでないと指摘されたデータは、統計的な異常として扱うべきであることを示唆しています。同様に、ランダムエクスカーション検定の自然なフィルタリング過程のため、標本サイズが小さいと、第一種の過誤、すなわち、データが真にランダムに見えるときにランダムでないとラベル付けする誤りを犯す場合があります。
For all of the remaining algorithms: CAST-256, DFC, E2, LOKI97, MAGENTA, MARS, RIJNDAEL, SAFER+, and SERPENT, the results to date suggest that there is no deviation from randomness.
残りのすべてのアルゴリズム、すなわち CAST-256、DFC、E2、LOKI97、MAGENTA、MARS、RIJNDAEL、SAFER+、SERPENT については、これまでの結果は、ランダムネスからの逸脱がないことを示唆しています。
Acknowledgments
謝辞
In particular, I would like to acknowledge the efforts of the RNG Technical Working Group, especially Dr. Andrew Rukhin who derived the statistical tests and Dr. Jim Nechvatal who proposed the categories of data to be analyzed. Additionally, I’d like to express my gratitude to Larry Bassham, Sharon Keller, Neil Molino and Murugiah Souppaya who have always provided their technical assistance.
特に、RNG Technical Working Group の尽力に感謝いたします。とりわけ、統計的検定を導出した Dr. Andrew Rukhin と、分析するデータの種別を提案した Dr. Jim Nechvatal に感謝いたします。さらに、常に技術的な支援を提供してくださった Larry Bassham、Sharon Keller、Neil Molino、Murugiah Souppaya に感謝の意を表します。
References
参考文献
[1] William Caelli, et. al., Crypt X Package Documentation, Information Security Research Centre and School of Mathematics, Queensland University of Technology, 1992.
[1] William Caelli, et. al., Crypt X Package Documentation, Information Security Research Centre and School of Mathematics, Queensland University of Technology, 1992.
[2] Carl D'Halluin, et. al., “Equivalent Keys of HPC,” Katholieke Universiteit Leuven, ESAT-COSIC, April 1999.
[2] Carl D'Halluin, et. al., “Equivalent Keys of HPC,” Katholieke Universiteit Leuven, ESAT-COSIC, April 1999.
[3] Helen Gustafson, et. al., "A computer package for measuring the strength of encryption algorithms," Computers & Security, Volume 13, pp. 687-697, 1994.
[3] Helen Gustafson, et. al., "A computer package for measuring the strength of encryption algorithms," Computers & Security, Volume 13, pp. 687-697, 1994.
[4] Alfred Menezes, et. al., Handbook of Applied Cryptography, CRC Press, 1997.
[4] Alfred Menezes, et. al., Handbook of Applied Cryptography, CRC Press, 1997.
[5] Andrew Rukhin, et. al., "A Statistical Test Suite for the Validation of Cryptographic Random Number Generators," NIST Computer Security Division/Statistical Engineering Division Internal Document, September 1999.
[5] Andrew Rukhin, et. al., "A Statistical Test Suite for the Validation of Cryptographic Random Number Generators," NIST Computer Security Division/Statistical Engineering Division Internal Document, September 1999.
Appendix: Description of the Statistical Tests
付録: 統計的検定の説明
Frequency Test: The purpose of this test is to determine whether the number of ones and zeros in a sequence are approximately the same as would be expected for a truly random sequence.
Frequency Test: この検定の目的は、系列中の 1 と 0 の数が、真にランダムな系列で期待される数とほぼ同じかどうかを判定することです。
Block Frequency Test: The purpose of this test is to determine whether the frequency of m-bit blocks in a sequence appears as often as would be expected for a truly random sequence.
Block Frequency Test: この検定の目的は、系列中の m ビットブロックの頻度が、真にランダムな系列で期待されるのと同じ頻度で現れるかどうかを判定することです。
Cumulative Sums Forward (Reverse) Test: The purpose of this test is to determine whether the maximum of the cumulative sums in a sequence is too large or too small; indicative of too many ones or zeroes in the early (late) stages.
Cumulative Sums Forward (Reverse) Test: この検定の目的は、系列中の累積和の最大値が大きすぎるか小さすぎるかを判定することです。これは、前(後)の段階で 1 または 0 が多すぎることを示します。
Runs Test: The purpose of this test is to determine whether the number of runs of ones and zeros of various lengths is as expected for a random sequence. In particular, this test determines whether the oscillation between such substrings is too fast or too slow.
Runs Test: この検定の目的は、さまざまな長さの 1 と 0 のランの数が、ランダムな系列で期待されるとおりかどうかを判定することです。特にこの検定は、そのような部分文字列の間の振動が速すぎるか遅すぎるかを判定します。
Long Runs of Ones Test: The purpose of this test is to determine whether the distribution of long runs of ones agrees with the theoretical probabilities.
Long Runs of Ones Test: この検定の目的は、1 の長いランの分布が理論的な確率と一致するかどうかを判定することです。
Rank Test: The purpose of this test is to determine whether the distribution of the rank of 32x32 bit matrices agrees with the theoretical probabilities.
Rank Test: この検定の目的は、32x32 ビット行列のランクの分布が理論的な確率と一致するかどうかを判定することです。
Spectral (Discrete Fourier Transform) Test: The purpose of this test is to determine whether the spectral frequency of the binary sequence agrees with what would be expected for a truly random sequence.
Spectral (Discrete Fourier Transform) Test: この検定の目的は、2 値系列のスペクトル周波数が、真にランダムな系列で期待されるものと一致するかどうかを判定することです。
Non-periodic Templates Test: The purpose of this test is to determine whether the number of occurrences for a specified nonperiodic template agrees with the number expected for a truly random sequence.
Non-periodic Templates Test: この検定の目的は、指定した非周期テンプレートの出現数が、真にランダムな系列で期待される数と一致するかどうかを判定することです。
Overlapping Template Test: The purpose of this test is to determine whether the number of occurrences for a template of all ones agrees with what is expected for a truly random sequence.
Overlapping Template Test: この検定の目的は、すべて 1 のテンプレートの出現数が、真にランダムな系列で期待される数と一致するかどうかを判定することです。
Universal Statistical Test: The purpose of this test is to determine whether a binary sequence does not compress beyond what is expected of a truly random sequence.
Universal Statistical Test: この検定の目的は、2 値系列が、真にランダムな系列で期待される程度を超えて圧縮できないかどうかを判定することです。
Approximate Entropy Test: The purpose of this test is to compare the frequency of overlapping blocks of two consecutive/adjacent lengths (m and m+1) against the expected result for a normally distributed sequence. In short, it determines whether a sequence appears more regular than is expected from a truly random sequence.
Approximate Entropy Test: この検定の目的は、連続する(隣り合う)2 つの長さ(m と m+1)の重なるブロックの頻度を、正規分布に従う系列に対して期待される結果と比較することです。要するに、系列が、真にランダムな系列から期待されるよりも規則的に見えるかどうかを判定します。
Random Excursion Test: The purpose of this test is to examine the number of cycles within a sequence and determine whether the number of visits to a given state, [-4, -1] and [1, 4], exceeds the expected for a truly random sequence.
Random Excursion Test: この検定の目的は、系列内のサイクル数を調べ、与えられた状態 [-4, -1] と [1, 4] への訪問回数が、真にランダムな系列で期待される回数を超えているかどうかを判定することです。
Random Excursion Variant Test: The purpose of this test is to determine if the total number of visits to states, between [-9, -1] and [1, 9] exceeds the expected for a truly random sequence.
Random Excursion Variant Test: この検定の目的は、[-9, -1] と [1, 9] の間の状態への訪問の総数が、真にランダムな系列で期待される数を超えているかどうかを判定することです。
Lempel-Ziv Complexity Test: The purpose of this test is to determine whether or not the sequence compresses no more than a truly random sequence.
Lempel-Ziv Complexity Test: この検定の目的は、系列が、真にランダムな系列以上には圧縮されないかどうかを判定することです。
Linear Complexity Test: The purpose of this test is to determine whether or not the sequence is complex enough to be considered truly random.
Linear Complexity Test: この検定の目的は、系列が、真にランダムと見なせるほど複雑かどうかを判定することです。