乱数テストの方法

Burp Sequencerは、標準的な統計的テストによりランダム性を確認します。証拠のサンプルに対して仮説をテストする原則に基づき、仮説が正しいと仮定した上で観測データの発生確率を計算します:

• テストされる仮説は: トークンがランダムに生成されている、です。
• 各テストでは、トークンがランダムに生成されている場合に発生すると考えられる、サンプルの特性を観測します。
• その仮説が正しいと仮定して、特性の発生が観測された確率を計算します。
• この確率が一定レベル(これを"有意水準"という)を下回る場合は、仮説が否定され、トークンはランダムに生成されたものではないと見なされます。

有意水準は、この方法の鍵となるパラメータです。有意水準を低くすると、トークンがランダムに生成されたという仮説を否定するためにはより強力な証拠が必要となり、ランダムではないデータがランダムとして扱われる可能性が高まります。あらゆる目的に使用できる"正しい"有意水準は存在しません: 科学実験では、1%から5%の範囲の有意水準がよく使用されます; ランダム性についての標準的FIPSテスト(これはBurp Sequencer内で実装されている)では、0.002%から0.03%の範囲の有意水準を使用します。Burp Sequencerでは、その結果の解釈に使用する有意水準を選択できます:

• それぞれのテストは、仮説が正しいと仮定したうえで、観測データが発生した確率の計算結果を報告します。この確率は、このテスト単独で考えた場合に、仮説が否定される境界有意水準を表します。
• 複数のテストを集約した結果から、さまざまな有意水準(0.01%から10%の範囲)における、トークン内の有効エントロピーのビット数がわかります。このサマリーから、有意水準の選択によって、サンプル内に存在すると見なされるランダム性の"量"にどのように影響するかが確認できます。ほとんどのケースで適当に選択した有意水準でも、ランダム性の量が明らかに十分か、明らかに足りないかのいずれかを示すため、有意水準を厳密に考える必要はありません。

ランダム性に対する統計的テストでは、いつかの重要な警告が発生します。この結果には次の理由により、検知漏れや過剰検知が含まれる可能性があります:

• 完全に再現できるデータでも、統計的テストによってランダムであると見なされることがあります。たとえば、適切に設計された線形合同擬似乱数生成器や、連続値のハッシュ計算アルゴリズムは、一見ランダムな結果を生成しているように見えるかもしれませんが、その乱数生成器の初期状態を知る攻撃者は、前後にどのような出力がされるか完全に予測できます。
• 統計的テストによってランダムではないと判断されたデータでも、実際にはそうでないかもしれません。与えられたデータから認識できるパターンだけでは、将来発生し得るあらゆる出力を実際にテストできるわけではないからです。

これらの注意点があるので、Burp Sequencerを使用して得られた結果は、サンプルデータのランダム性の参考情報としてのみ扱うことを推奨します。

Burp Sequencerによって実行されたテストは文字レベルとビットレベルに分けられます。

文字レベル分析

文字レベル分析はトークンに書かれた文字をそのままの形式でテストを行います。まず、各位置での文字集合のサイズが計測されます。文字集合のサイズとは、サンプルデータ内の各位置に現れる異なる文字種数です。以降のテストは、この情報を使用して行われます:

• 文字カウント分析。トークン内の各位置で使用される文字の分布を分析します。もしサンプルがランダムに生成されているならば、使用される文字はほぼ均一に分布するはずです。このテストでは、各位置について、トークンがランダムである場合に観測されるはずの、分布の確率を計算します。
• 文字遷移分析。サンプル内の連続したトークン間の、遷移を分析します。もしサンプルがランダムに生成されているならば、ある位置について、過去に同じ位置で使用された文字が何であっても、次のトークンで同じ位置に出現する文字の確率は同程度になるはずです。このテストでは、各位置について、トークンがランダムな場合に観測されるはずの、遷移の確率を計算します。

文字レベル分析では、上記のテストに基づき、それぞれの文字位置について総合スコアを計算します - これはそれぞれの文字レベルテストで、各位置で計算された最小の確率です。それからこの分析は、さまざまな有意水準における、有効エントロピーのビット数をカウントします。トークン内の文字集合の大きさに基づき、各位置にエントロピーのビット数を割り当てます (もし4文字ならば2bit、8文字ならば3bit)。そして、各有意水準以上になった総ビット数が計算されます。

ビットレベル分析

ビットレベルテストは文字レベルテストよりも強力です。ビットレベル分析を有効にするために、それぞれのトークンをビット集合に変換する必要があります。各文字位置の文字集合のサイズから総ビット数が求められます。いずれかの位置で、2のべき乗ちょうどではないサイズの文字集合が使用されていた場合は、その位置でのサンプルデータは、もとの集合のサイズよりも小さく元の値に最も近い2のべき乗ちょうどに変換されます。その位置でのデータの部分的なビットは、その位置から派生した全ビットに効率的にマージされます。この変換は、もともとの標本のランダム性についての特徴を保存し、どのような偏りの追加、削除も行われないように設計された方法で行われます。しかし、この方式での変換は完璧ではなく、もしかしたら不完全な文字集合サイズの標本を分析する過程で、分析結果にある種の不正確さをもたらすかもしれません。

それぞれのトークンがビット列に変換されると、各ビット位置で、次のテストが行われます:

• FIPS一次元度数検定。各ビット位置での1と0の分布を分析します。もしサンプルがランダムに生成されているならば、1と0はほぼ均一に分布するはずです。このテストでは、各位置について、トークンがランダムである場合に観測されるはずの、分布の確率を計算します。各FIPSテストでは、観測データの発生確率の報告に加えて、ビットごとのFIPSテスト成功/失敗も記録します。FIPSの正式なテスト仕様ではちょうど20,000トークンのサンプルを前提としていますが、Burp Sequencerは任意のサンプルサイズで動作するよう、FIPS合格基準が再調整されることに注意してください。したがって、FIPS仕様に厳密に準拠した結果を取得したい場合は、20,000トークンのサンプルを使用してください。
• FIPSポーカー検定。各位置のビット列を、連続する4つの非重複グループに分割し、各グループから4ビットの値を導出します。次に、出現する可能性のある16の数値の出現回数を数え、カイ二乗計算を行いこの分布を評価します。もしサンプルがランダムに生成されているならば、4ビット数値はほぼ均一に分布するはずです。このテストでは、各位置について、トークンがランダムである場合に観測されるはずの、分布の確率を計算します。
• FIPS連検定。各位置のビット列を、同じ値を持つ連続したビットの連に分割します。そして長さが1, 2, 3, 4, 5, 6, それ以上の連の個数を数えます。もしサンプルがランダムに生成されているならば、これらの各長さの連の個数は、サンプルセットのサイズで決定される個数の範囲にほぼ収まるはずです。このテストでは、各位置について、トークンがランダムな場合に観測されるはずの、連の確率を計算します。
• FIPS最長連検定。各ビット位置で、同じ値を持つビットの最長連を計測します。もしサンプルがランダムに生成されているならば、最長連の長さは、サンプルセットのサイズで決定される長さの範囲にほぼ収まるはずです。このテストでは、各位置について、トークンがランダムである場合に観測されるはずの、最長連の確率を計算します。このテストのFIPS仕様では、ビットの最長連が長すぎる場合にのみ、失敗となることに注意してください。しかしながら、短すぎるビットの最長連も、サンプルがランダムでないことを示します。したがって一部のビットでは、厳密なFIPSテストに不合格でないにもかかわらず、FIPS合格レベルを下回る有意水準になる場合があります。
• スペクトルテスト。各位置のビットシーケンスの高度な分析をし、他の統計的テストに合格した一部のサンプルの、非ランダム性の証拠を発見します。このテストではビット列を処理し、一連の連続する数値を多次元空間の座標として扱います。これらの座標によって決定された場所ごとに、空間内の点をプロットします。もしサンプルがランダムに生成されているならば、この空間内の点はほぼ均一に分布するはずです; 空間内に偏りができた場合は、データがランダムではない可能性が高いです。このテストでは、各位置について、トークンがランダムな場合に観測されるはずの、分布の発生確率を計算します。このテストは、複数サイズの数(1から8ビット)と、複数の次元(2から6)で繰り返されます。
• 相関テスト。他のビットレベルテストは、サンプリングされたトークンのそれぞれのビット位置を分析し、各ビット位置ごとのランダム性を独立して計算します。このタイプのテストのみを実行していると、トークン全体のランダム性の量を有意義に評価できなくなります: 短いけれども各位置で異なる値になるトークンよりも、長いけれども各位置で同じ値になるトークンの方が、よりエントロピーが大きいように見えてしまうかもしれません。したがって、トークン内の異なるビット位置の値の間に、統計的に有意な関係があるかどうかのテストが必要です。もしサンプルがランダムに生成されているならば、特定ビットの値は、他のビット位置が0または1になる確率とほぼ等しくなるはずです。このテストでは、各位置について、トークンがランダムである場合に観測されるはずの、他の位置のビットの確率を計算します。恣意的な結果を防ぐために、2ビットの間で相関性が観察された場合、その他のビットレベルテストでより有意水準が低いビットについて、ビットの有意水準を調整します。
• 圧縮テスト。このテストは、他のテストで使用されている統計的手法を使用せず、それでも各ビット位置でのエントロピー量を簡単に直感的に示します。このテストは、標準的なZLIB圧縮を使用して各位置でビット列を圧縮してみます。圧縮されると、ビット列のサイズが比例減少します。圧縮率が高い場合は、データがランダムに生成されていないこと示しています。

ビットレベル分析では、上記のテストに基づき、それぞれのビット位置について総合スコアを計算します - これはそれぞれのビットレベルテストで、各位置で計算された最小の確率です。それからこの分析は、さまざまな有意水準における、有効エントロピーのビット数をカウントします。