疑似乱数評価ツールについて

質問

現在、大学の研究室でストリーム暗号の研究をしています。
ストリーム暗号の鍵は疑似乱数列が用いられるため、
各アルゴリズムの評価には疑似乱数評価ツールが用いられています。
疑似乱数評価ツールとしてNISTのSP-800 22というツールが
一般的です。
http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html

しかしこの評価ツールには計算式のパラメータに不適切なものが
いくつかあることがCRYPTRECの調査で指摘され、
プログラム自身にも致命的なバグがあるようです。
↓情報ソース
http://www2.nict.go.jp/y/y213/cryptrec_publicity/rep_ID0211.pdf
http://cryptrec.nict.go.jp/rep_ID0037.pdf
http://www.chaosware.com/ransure/pdf/ransure2.pdf
実際、私が評価ツールを試したときはプログラムが途中でフリーズしたり
デタラメな結果が出たりと散々でした。
マニュアルがとても不親切だしREADMEすらついていないプログラムは全く信用できません。

そのため東芝ソリューションが問題を修正した評価ツールを作成したようですが
プログラムはIPA専有となっており、暗号開発者はIPAに評価を委託しなければならないようです。
(しかも法人向きのサービスで、個人だと無理っぽいです)
http://www.ipa.go.jp/security/fy17/development/random/documents/rand.pdf

市販されているツールもありますが価格が50万円もします。
+保守料金が年間10万円とありますが
そんな大金で何を保守するのか謎です。
http://www.chaosware.com/ransure/ransure.html

私が自分で考案したアルゴリズムを評価するための選択肢は
1.高額な評価ツールを購入する。
2.評価のための計算式は公表されているので自作する。
しかないように思います。
購入してしまえば楽ですがオープンソースではないのでそのツールにもバグが無いことを証明できません。
自作したとしてもそのツールの正統性の証明も困難と思われます。

こういうのは然るべき場所でキチンと議論して
オープンソースな開発をしなきゃならないと思うんですが
（っていうかNISTがそういう所であるべきなんですが）
論文の〆切も迫ってきていますのでどうしたものかと途方に暮れております。

長くなりましたが何か良い案があれば
教えていただきたいです。

回答No.3

exact_time

流通しているプログラム(NIST SP 800-22)の乱数検定能力を疑わせるバグが依然存在しているので、現状検定プログラムの
ロジック自体にバグが無いと保証する、またそこに責任を持つ
RanSureで評価するのが、一番確実と思われます。

またRanSureが高いということですが、
アカデミックライセンス価格で購入した大学を知っており、
大学の場合、安価で購入できる（た）
のではないのでしょうか？
また、そのNIST SP 800-22 version 1.8とRanSure違いの有無についても議論されてましたが、RanSureは
Vistaで動作するのに対し、NIST SP 800-22は動作しないという動作
環境以外の本質的な乱数検定能力における違いがあり、
RanSureでは全然パスせず、NIST SP 800-22 version 1.8に全ての
項目パスする乱数列が存在し、NIST SP 800-22の方が、RanSureよりも
かなり甘い結果となっていることが、昨年の夏の統計数理研究所
開催の乱数の研究会で発表され公表されてましたので、それが
乱数の専門家の見解とみなしても良いと思われます。
http://www.chaosware.com/ransure/pdf/ransure2.pdf
又、よくある誤りですがNIST自身は、乱数の検定結果に関して決して認定していない（使用の責任は持たないと明言）ので、NIST SP 800-22で
パスしたことを"NISTから認定も受けた"とプレス・論文等で公開するのせっかくの研究成果が２重の詐欺行為となってしまい、危険だと思いますので、論文執筆時、及び公表の段階では、テスト方法(利用ソフト）、テスト結果だけを淡々と述べる、という様な工夫が必要と思われました。現状では、乱数のランダム性を保証する機関はどこにもありません。

お礼

問い合わせたところ御指摘のとおり、アカデミック版がありました。
（それでも予想以上の価格ではありましたが）

NIST SP800-22の結果が甘い、ということですが
評価論文に記載されている実験を再現しようとした場合に
それらの結果とは大きく異なる場合が何度かありました。
よく甘めの傾向が出ていたので疑問には思っていましたが
そのような見解もあるのですね。

評価ツールはあくまで参考程度にとどめておくことを
心がけたほうがよさそうですね。

回答どうもありがとうございました。

回答No.2

neetexceed

＞FFTとLampel ziv検定についての議論は
＞あちこちで見かけられますね。

　Lampel ziv検定は、臨床的興味としては面白いですが、
学術的にはどうか、、、その存在が疑問ですね。

　圧縮したデータは乱数に近づくという性質を知っている人は思わずニヤリとするのですが、それを数値としてあらわすと、あるいは、自然に発生する冗長性というものを考えると評価の確立が難しいというのもわかります。

＞今回は時間の都合上、やむなくRanSureの導入を決めましたが

　RanSureは確か１．８ベースと記憶します。
導入されたならば、１．８との検定比較をお勧めします。

　私が実施したとき、テンプレートエラーだけだったと思いますが、同一の結果がでました。

１．FFT検定は改良されていると思います。
２．それ以外については、わかりません。同一の可能性があります。

　　　　　　　＊＊＊

　それでも通算すると見えないものも見えてくるようです。
１．８にてメルセンヌツイスタを２５ファイル検定した結果を
Upします。結果は、自作の集計ソフトで自動生成しています。

　ファイル失格率・失格エラー発生率として目に見える
数字がでてくるのでだいたい分かります。

PS.
　１０ファイルで検定というのがそもそも茶番というのが私の臨床的見解です。可能なら１００ファイル検定をし、その中で統計的評価の良いものが良いというのが現状現実的と思います。

==========================================================
■ 本Reportの見方
　1.「1～g」の意味
　　SP800-22の定める合格値は検定値は0.980561以上です。
　　例外としてrandom-excursions(variant)テストは0.977944以上です。

　2.「8」「$」の意味
　 テンプレートテストで、0.977944未満。0.96以上の項目に付けます。
　 0.96未満の時、「$」を付けます。
　 このテストは148のテンプレートについてテストします。
　 このテストは正しい乱数においても1項目につき0.0028(百分率で0.28)のエラーが発生します。
　 従い、148の一つづつに0.28の確率でエラーが発生します。
　 148×0.28=39.96の確率「8」を付けるのが期待値です。
　 本検定では独立行政法人カオスウェアのガイドラインに従い、「8」が数個でる場合は合格とします。
　 1ファイルで@が一つ出る確率は39.96。
　 @が二つ出る確率は15.96。
　 @が三つ出る確率は6.38。
　 ※他のエラーが発生した場合はエラーとします。
==========================================================
ファイル名 判定
==========================================================
Report0.txt 88d p-value平均=0.480788 proportion平均=0.989535
Report1.txt p-value平均=0.514770 proportion平均=0.989486
Report2.txt p-value平均=0.493146 proportion平均=0.989819
Report3.txt 8 p-value平均=0.490573 proportion平均=0.989819
Report4.txt 88 p-value平均=0.482893 proportion平均=0.989693
Report5.txt 7 p-value平均=0.490304 proportion平均=0.989219
Report6.txt p-value平均=0.520369 proportion平均=0.990287
Report7.txt p-value平均=0.514605 proportion平均=0.990189
Report8.txt p-value平均=0.498834 proportion平均=0.989809
Report9.txt 8 p-value平均=0.504614 proportion平均=0.989668
Report11.txt df p-value平均=0.508623 proportion平均=0.990068
Report12.txt p-value平均=0.477115 proportion平均=0.989641
Report13.txt 88 p-value平均=0.497716 proportion平均=0.989607
Report14.txt p-value平均=0.513167 proportion平均=0.990078
Report15.txt 8 p-value平均=0.481148 proportion平均=0.989790
Report16.txt p-value平均=0.494437 proportion平均=0.990109
Report17.txt 8 p-value平均=0.516425 proportion平均=0.989864
Report18.txt 8 p-value平均=0.500440 proportion平均=0.990121
Report19.txt 8 p-value平均=0.453701 proportion平均=0.989414
Report20.txt 8 p-value平均=0.460209 proportion平均=0.989729
Report21.txt 8 p-value平均=0.483010 proportion平均=0.989586
Report22.txt p-value平均=0.533587 proportion平均=0.990283
Report23.txt 89 p-value平均=0.511535 proportion平均=0.989759
Report24.txt 78 p-value平均=0.493956 proportion平均=0.989115
Report25.txt 8d p-value平均=0.495859 proportion平均=0.989364
==========================================================
Total p-value平均=0.496473 proportion平均=0.989762
テンプレートエラー発生期待値=9.990000 : 実発生数=17 差分=7.010000 発生誤差=70.170170%
==========================================================
■総合判定結果。
評価ファイルNo=25 失格ファイル数=6 エラー合計=7
ファイル失格率=0.240000 (テンプレートエラーは除外する)
失格エラー発生率=0.280000 (テンプレートエラーは除外する)
1. Frequency エラー発生率=0.000000
2. BlockFrequency エラー発生率=0.000000
3. CumulativeSums エラー発生率=0.000000
4. Runs エラー発生率=0.000000
5. LongestRun エラー発生率=0.000000
6. Rank エラー発生率=0.000000
7. FFT エラー発生率=0.080000
8. NonOverlappingTemplate エラー発生率=0.680000
9. OverlappingTemplate エラー発生率=0.040000
a. ------------------
b. Universal エラー発生率=0.000000
c. ApproximateEntropy エラー発生率=0.000000
d. RandomExcursions エラー発生率=0.120000
e. RandomExcursionsVariant エラー発生率=0.000000
f. Serial エラー発生率=0.040000
g. LinearComplexity エラー発生率=0.000000
==========================================================

お礼

お礼が遅れて申し訳ありません。

現在はRanSureも到着し、実験を進めています。
ver1.8との比較は後回しになってしまいそうですが
後ほど実施してみたいと思います。
評価を進めてみるとやはり10件程度の調査では
なんとも言えない感じですね。

---

具体的な評価結果をわざわざ掲載していただきありがとうございます。
大変参考になりました。

回答No.1

neetexceed

NIST SP800-22はいろいろと問題があるようです。
ただ、全然ダメというわけではなく回避して使えるように思います。

　注意点としてはつぎのことでしょうか。

■ FFT検定は使用しない。あるいは、使用しても参考どまりとする。
＞http://www2.nict.go.jp/y/y213/cryptrec_publicity/rep_ID0211.pdf

　この資料によれば、FFT検定は信頼性に難ありとしています。
他の検定は、信頼できるという解釈は成立しそうです。

　うろ覚えですが、RANDOM検定も数式が間違っているのではないかという
レポートが出ていたように思います。

　基本的に甘い結果がでるように感じています。

■ SP 800-22は、現行のVer２．０の使用は避けて、以前の１．８を
　使用すると良いと思います。
　各種レポートも１．８以前の物に対して行った物のようです。
　おそらく先輩、教授は１．８をもっていると思いますのでこれを
　使用する事をお勧めします。

■　Ver1.8で検定するにあたり注意事項を述べて置きます。
　・検定は１Gビット以上のファイルで行うこと。
　・ストリーム長さは1000,000が良いようです。
　・このストリームを1000本指定する事。
　・検定は１Gビット以上のファイルは、最低でも２０本以上は
　　用意し検定すること。
　　欲を言うと５０～１００本ほど検定しないときちんとした
　　評価はできません。
　・ノンオーバーラッピングテンプレートテストは、１ファイルで
　　約４０％程度のエラーの発生率が統計学上あるようですので
　　エラーがでても気にしないこと。２０本以上のファイルを検定
　　してようやく、収束するという印象です。
　・私はWin版しか使った事はありませんが、自分でコンパイルは
　　せず、NIST提供のバイナリを使うこと。１．８はVC6++でコンパイル
　　できますが、コンパイルオプションで動かない検定があります。
　　ちなみに、Ver2.0は、VC6++でコンパイルすると数学関数が正常に
　　動作しないという現象を体験しています。
　・ブロックフレケンシーはブロック長さ20000を指定。
　・シリアルはブロック長１０を指定。これ以外の設定はデフォルト
　　で良いようです。
　・大体、２０ファイルを検定する前後でPCがクラッシュしますので
　　注意してください。色々と不安定なところがあります。

　　　　　　　　＊＊＊
　　　　　　　　　　＊＊＊

　信頼性のおけない検定を避ける。パラメータを良く確認すること。そして、２０本以上の検定を行うことがポイントです。

　カオスウェアのRanSureは、SP800-22 Ver1.8をベースにしていたと記憶します（バージョンにもよりますが）。カオスウェアは問題のある検定を改良しています。逆に言うと、それ以外の検定はVer1.8と同じと思って良いと思います。

　参考にしてください。

お礼

丁寧な回答ありがとうございます。

FFTとLampel ziv検定についての議論は
あちこちで見かけられますね。

NISTのVer.についてですがVer.1.5、1.8、2.0の３つを
実験を用いたことがあります。
1.5は相当古いようでbig endianベースでありintel系マシンでの実行が難しく
現在のgccには標準で含まれるが当時は含まれない関数を自己定義しているため
定義の重複エラーが多発する状況です。

1.8は仰るとおり、ある程度検定が進むとプログラムがクラッシュ、または
最後まで進んでも胡散臭い結果が出ています。
(単純なLFSRの出力すら全ての検定に通ってしまう、など）
多くの論文ではサンプルデータは10本程度での評価が多いようですが
正確な評価に最低でも20、できれば50～100本必要だとすると
それらの評価も不完全なのですね…

2.0では変更箇所などが一切通知されていません。
一応1.8のように途中でクラッシュはしませんが結果は1.8同様の胡散臭さです。

元々暗号をやっている研究室ではなく
個人的な研究としてスタートし勉強してきましたが
ストリーム暗号は各々一般性に欠ける我流の評価方法で安全性を主張し、
すぐに解読されたり評価方法の問題点を指摘されてるケースが多い印象を受けます。
この辺りは暗号の歴史の浅さが伺える気がしますね。

今回は時間の都合上、やむなくRanSureの導入を決めましたが
これらの問題はもっと広く認知されて修正されて欲しいと思います。