FPGAで作った真正乱数をSP800-90BとAIS31で検定してみる

はじめに

前回、PYNQ-Z2のFPGA上にリングオシレータTRNGを実装し、AXI DMA経由でPS側へ乱数ビット列を流してみた。

前回の記事: https://www.mimoex.net/260522-fpga-ring-oscillator-trng-pynq/

前回は、生のbit列には0寄りの偏りがあること、2bitごとに見ると 01 と 10 はほぼ同程度に出ていること、ノイマン抽出によって1の比率が約0.5に近づくことを確認した。

今回は、そのノイマン抽出後のビット列を、乱数検定ツールにかけてみる。

評価には、

• NIST SP800-90B EntropyAssessment
• AIS31 Test Suite v1.0

を用いた。

なお、検定にはWindows11にWSL2をインストールし、WSL2上のKali Linuxで検証を行った。
以前にCTFでKaliを使っていたのでセットアップ済みで使いやすかった為であり、Linux系ならば何でもいいと思う。

評価用データの作成

前回のPYNQコードを少し拡張し、ノイマン抽出後のビット列を指定したビット数だけ収集するようにした。

今回、評価に用いるデータは1600万bitのノイマン抽出後のデータを用いる。

保存形式は2種類用意した。

np.packbits() でpackしたbinaryは、普通の乱数バイト列として扱える。一方、SP800-90Bで bits_per_symbol=1 として評価する場合は、各bitを1byteで表した *_01.bin を使う方が扱いやすい。

vn_all = vn_all[:TARGET_BITS].astype(np.uint8)

# SP800-90B: 1bit symbol用
vn_all.tofile(base + "_01.bin")

# AIS31 / 8bit symbol用
vn_bytes = np.packbits(vn_all, bitorder="big")
vn_bytes.tofile(base + "_packed.bin")

バイナリエディタで確認

0x00, 0x01のみ

バイナリがHEX値になっている。

SP800-90B EntropyAssessment

NIST SP800-90B EntropyAssessmentには、IID用とnon-IID用の評価プログラムがある。
TRNGの出力にIIDを仮定するのは強いので、今回はまずnon-IID推定を使った。

GithubのREADMEにあるとおりにmakeするとea_non_iid等のバイナリが生成される。

./ea_non_iid -i -v vn_16000000bits_01.bin 1
./ea_non_iid -i -v vn_16000000bits_packed.bin 8

1bitシンボルを評価

vn_16000000bits_01.binを1bitシンボルとして評価した結果は以下。

Loaded 16000000 samples of 2 distinct 1-bit-wide symbols
...
H_original: 0.915555

この乱数データ1600万bitについて、SP800-90B non-IID推定では 0.915555[bit/bit]と評価された。

bit/bitというあまり見ない単位であるが、これは「出力された1bitあたりに、どれだけの最小エントロピーが含まれているか」を表している。
1bitの値は 0 または 1 の2通りしかないため、理想的な乱数ビットであれば次の1bitを当てられる確率は最大でも1/2になる。このとき最小エントロピーは

$$ -\log_2(1/2) = 1.0 $$

となる。（学生時代にエントロピーを求めるテストがありました）

単純換算すると、1600万bit全体の推定最小エントロピーは、 $$1600万 \times 0.915555 = 14648880$$ となり、1600万bit中1464万bit分の予測困難性があると見積もれる。

8bitシンボルを評価

次に、同じビット列をバイト型にして整えたデータをvn_16000000bits_packed.binとして評価した。

Loaded 2000000 samples of 256 distinct 8-bit-wide symbols
Number of Binary Symbols: 16000000
...
H_original: 6.888988
H_bitstring: 0.915555
min(H_original, 8 X H_bitstring): 6.888988

この場合、最終的な推定値は6.888988[bit/B] だった。

1bit評価では0.915555[bit/bit]だったので、単純に8倍すると 7.32444[bit/B]になる。
しかし、8bitシンボルとして見た場合のLag Prediction Estimateがより低い値を出した。

Lag Prediction Test Estimate = 6.888988 / 8 bit(s)

つまり、bit単位ではかなり良好に見えるが、バイト列として見ると、局所的な予測可能性が少し検出されたと考えられる。

AIS31 Test Suite

次に、AIS31 Test Suite v1.0を使って検定した。

コンパイル

javac -encoding Latin1 Evaluator.java
java Evaluator

P1/T0

GUI上では、バイト型のデータを入力し、次の設定にして、P1/T0テストを行った。

画像ではラジオボタンがP1/T1-T5になっているが、そこは臨機応変に捉えてください…

TEST-SUITE: P1/T0
DATEINAME: /home/user/SP800-90B_EntropyAssessment/cpp/vn_16000000bits_packed.bin
DATENFORMAT: 1 Dateibyte enthält 8 Random-Bits.
RND-BITBREITE: 8 bit.
...
3145728 Elemente in RAM kopiert.
...
Test T0 bestanden.

P1/T0は合格した。

P1/T1-T5

続いて、T0実行後に生成された _rest ファイルに対して、P1/T1-T5を実行した。

TEST-SUITE: P1/T1-T5
DATEINAME: /home/user/SP800-90B_EntropyAssessment/cpp/vn_16000000bits_packed.bin_rest
DATENFORMAT: 1 Dateibyte enthält 8 Random-Bits.
RND-BITBREITE: 8 bit.
...
5220000 Elemente in RAM kopiert.

T1〜T5では、257回のDurchlaufが実行された。

最初のDurchlaufでは、T1〜T5すべてが合格した。

Test T1 bestanden.
Test T2 bestanden.
Test T3 bestanden.
Test T4 bestanden.
Test T5 bestanden.

最後のDurchlaufも合格している。

Durchlauf 257 bestanden.
Durchlauf erfolgreich beendet, Restdatei zum Test ausgewählt.

したがって、AIS31 P1/T1-T5も合格である。

結果まとめ

AIS31では、P1/T0およびP1/T1-T5に合格した。
少なくともこのデータセットでは、monobit、poker、run、long run、autocorrelationといった基本的な統計検定では異常は検出されなかった。

一方、SP800-90Bでは、1bitシンボル評価では0.915555[bit/bit]だったが、8bitシンボル評価では6.888988[bit/B]となった。
特に8bitでの評価ではLag Prediction Estimateが最小値を出しており、バイト列として見た場合には局所的な相関が残っている可能性がある。

考察

前回の記事では、生のリングオシレータTRNGの出力は1の比率が約0.428であり、そのままでは明確に偏っていた。
ノイマン抽出後は1の比率が約0.5に近づいた。

今回の結果を見ると、ノイマン抽出後の出力はAIS31 P1/T0〜T5を通過し、SP800-90Bでも1bitあたり0.915555[bit]の最小エントロピーが得られた。

ただし、ノイマン抽出は主に統計学的なバイアス除去の方法のようであり、入力bit間の相関まで完全に消すものではないと思われる。
SP800-90Bの8bit評価でLag Prediction Estimateが最小値になったことから、何らかの周期性・局所的相関・byte単位の偏りが残っている可能性はある。

しかし、AIS31の検定が通ったため、そこそこの品質の乱数であることは分かった。

これを暗号に利用する場合は更にSHA256などのハッシュにかけてランダム化させれば良いかもしれない。