安全な擬似乱数生成ルーチンSHRAND（SecureHashRANDom）　　by　とつげき東北　　トップページに戻る


現在研究開発中です。不足な点やお気づきの点がありましたらメールでお知らせください。
特に情報数学に強い人からのお便りをお待ちしています。


再現可能で、かつ安全な乱数を得る

導入：

擬似乱数には様々なものがある。
C標準関数のrand（）から、MersenneTwisterにいたるまで、その周期や乱数の性質は多岐にわたる。
ストリーム暗号では、一般に、擬似乱数の性質が強度に強く影響を与える。
多くのストリーム暗号においては、基本的に「再現可能で、予測・探索不可能な擬似乱数」を用いて、原文とのXORを取る方法が用いられる。
近年では、カオス関数を利用したもの（GCC）などもある。
ストリーム暗号はDESなどのブロック暗号に比較して非常に高速なのが特徴だが、「再現可能で、予測・探索不可能な擬似乱数」を実現することが課題となっている。
カオス関数は未だ、できてまもなく、まだまだその安全性が確かめられたわけではなく、MD5のように後になって危険が見つかる可能性もあるわけだ。
いかに「良い」、安全な擬似乱数を使うかということが重要になる。

ここで、「安全な擬似乱数」というものについて少し考察する。
例えば2^32周期の擬似乱数の中に、特定のパターンの連続した32ビット列は1つ程度しかない。
原文と擬似乱数のXORを順に取る「暗号」があるとして、原文に000000・・・を与えると、暗号文はそのまま擬似乱数の出力値となる。
したがって、ある特定の原文に対しては、擬似乱数の出力値自体がすぐに盗聴者に知れることになる。
もしも、ある擬似乱数列が、その擬似乱数生成システムのどこから生成される可能性があるかを一気に絞り込む方法があったとすると、ごくわずかな暗号文と原文との対比から、その先の原文を解読できてしまうことになる。
例えば、rand（）は2^32周期しかないため、出力値列が32ビット（全角文字「よろしく」程度が）盗聴者に知れると、大した手間もなくその後の出力値列が予測できてしまう。
MTはおよそ2^19937もの周期を持つため、仮に出力値が知られても、その位置を「総当りで検索することは」事実上不可能である。
しかし、MT開発者のホームページに
「この生成法は、計算量理論的に安全な乱数をそのままでは生成しません。しかし、Secure Hashing Algorithm（数ワードを圧縮して１ワードを生成する、非可逆的なアルゴリズム）と組み合わせれば使えます。 」（こちらから引用）
との記述があるように、MTの出力値をそのまま暗号に用いることは好ましくないようだ。
計算量理論的に安全でないということは、つまり、19937ビットに対する総当たり以外の何らかの「出力値絞り」方法が存在し得ることを意味する。
その方法がどうであるかはともかく、ここでは以後、2^32周期の擬似乱数でそうであったように「MTのうち一部のユニークな（MT上に1つ程度しかない）出力が明らかになったとき、その後の出力が明らかになる」ことを前提として話を進めたい。

安全な擬似乱数とは「その擬似乱数出力値のビット列が、その擬似乱数発生装置のどのような状態から作られたものかをユニークに定めることが計算量的にひどく困難な擬似乱数」を意味する。
ここでは、これまでコンピュータ上で伝統的に安全性が示されてきた方法を組み合わせて、長周期で安全な擬似乱数を生成することを考えよう。


つまりここで実現するのは、

MTの擬似乱数　→　MTとは一見関係のない、MTと同じ周期を持つ、良質な擬似乱数SHRAND

という変換関数の構築と実装である。

なお、SHRANDの値からMTの出力値自体を解読する困難さは、MTの擬似乱数出力から、総当りでMTの次の出力値を予測することと同程度の困難さにすることを目指す。
また計算時間がなるべく小さくなるように配慮する。



簡単な方法：

MTの出力値が推測できない形で、それとは一見無関係な擬似乱数を生成する方法はいくつか考え得る。
ここでその例を挙げてみる。

１）SHA
MTの生成したビット列からSHAを用いて各ビットを処理して、SHAの出力値を擬似乱数とすることがもっとも簡単な方法である。
例えば、MTの512ビット出力をSHAに放り込んで、SHAの出力を適当にxorして出力してやれば、相当安全な擬似乱数が得られるだろう。
しかし、この場合ビット列を生成する度にSHAを用いる必要があり、計算時間がかなり大きくなってしまう。
擬似乱数1つを得るためにMTの擬似乱数生成を16回も行わねばならず、またハッシュにかかる時間も無視できない。

２）適当な「間引き」
MTの出力値から、いくつかのMTをランダムに間引いたり、逆に付け加えたり、xorを取る方法もある。
しかし、それらの方法はアルゴリズムが知られてしまうとあまり強力ではない。
また1つの擬似乱数出力に対してMTを複数回呼び出す必要があるなど、効率が良くない。

他にもいくつか考え得るだろうが、話を進めよう。



安全なハッシュプール（S-POOL）の開発：

ここでは、MTの出力値から、それとは関係のないような良質の擬似乱数を高速に出力するためのシステム「ハッシュプール」を考える。

原型

前回のMT値（BM）、今回のMT値（MT）と、状態（S-POOLを呼ぶたびに変化）から、出力と状態遷移が決定されるようなプールを考えよう。

ここで安全なハッシュプールの仕様は次のようでなければならない。
１）入力に使われるMTと出力値との間の相関ないこと
２）出力値列から入力値列を予測できないこと

上記を満たすために、次のような真理値表を満たすシステム（S-POOL）を考えよう。

表：S-POOLの各ビットの演算の真理値表

状態（S1,S2）　BM　MT　出力　次の状態（S1',S2'）
　　　00　　　　　0　　0　　　0　　　　00
　　　00　　　　　0　　1　　　0　　　　01
　　　00　　　　　1　　0　　　0　　　　10
　　　00　　　　　1　　1　　　0　　　　11
　　　01　　　　　0　　0　　　1　　　　10
　　　01　　　　　0　　1　　　0　　　　11
　　　01　　　　　1　　0　　　0　　　　00
　　　01　　　　　1　　1　　　1　　　　01
　　　10　　　　　0　　0　　　0　　　　01
　　　10　　　　　0　　1　　　1　　　　00
　　　10　　　　　1　　0　　　1　　　　11
　　　10　　　　　1　　1　　　0　　　　10
　　　11　　　　　0　　0　　　1　　　　11
　　　11　　　　　0　　1　　　1　　　　10
　　　11　　　　　1　　0　　　1　　　　01
　　　11　　　　　1　　1　　　1　　　　00

S-POOLは、その状態によって
00：入力されたMT値によらず0
01：入力されたMT値と、前回そのプールに入力されたMT値（BM）が違っていれば0、同じなら1
10：入力されたMT値と、前回そのプールに入力されたMT値（BM）が違っていれば1、同じなら0
11：入力されたMT値によらず1
を出力するような変換関数である。

真理値表から、
S-POOL：
出力＝(S1&(S2|(BM^MT)))|(S2&((~BM)^MT))
S1'=S2^BM
S2'=S1^MT
を得る。

状態が未知のとき、今回の入力のいかなる値に対しても出力値は0か1が半々で現れるし、また別のどの状態にも半々で遷移する。遷移先の分布は出力値によらない。
出力値に0が連続していることは、MTの出力に0が連続していることによるのか、1が連続していることによるのか、0101が交互に現れていることによるのか、あるいはほとんど乱雑な値が現れていることによるのか、偶然以上に予測することができない。1の連続や他の規則正しい出力についても同様のことが言える。
結局、第三者には、今回のMT値と前回のMT値が同じであったか違っていたかということさえ、（プールの状態などが未知であれば）偶然以上に当てる術がない。

このシステムに対してMTの値を解読する方法について考える。初期のBMや各状態をある値に仮定することによって、出力値からMTを一意に定めることができる。
1つの32ビット出力に対して、状態とBMを正しく決定するには、32*3=96ビットの仮定が必要である。
もしもこのプールを1つだけ、かつ一度だけ利用したならば、およそ96ビットの仮定に基づいて、MTの真の値を得ることができる。
それはMTの値を偶然にたよって（1/2^32で）当てることより難しいから、結局MTの真の値を得ることは32ビットレベルで困難である。


安全度の強化パラメータの決定

このプールを複数個用意して、より安全性を強化することを考える。
S-POOLを複数個導入し、時々乱数を使って使用位置を変える。
ある「セット」で使うプールの個数自体をMTを元にS-POOLから取った乱数で決定する。開始点と終了点は別々に取り、プールの最後と最初は連結する。
最初に使い始める時と、終了点に達したときに、MTを元にS-POOLから次の開始点と終了点を選び、終了点に達するまで、プールは順に使用していく。

これによって、S-POOLをm個集めたシステムの場合、平均的に1セットあたりm/2個のプールが使われることになり、特定の1つのS-POOLから情報を集中的に集めることがひどく困難になる。
たまたまあるプールが解読を試みるためのS-POOLである確率は1/mになるから、毎回のS-POOL情報収集のためにm通りの組み合わせを考える必要が出てくる。

まずは「m通りの初期状態と初期BMを仮定して、プールの変化を追う」という方法でどの程度までMTを推測できるのかを考察する必要がある。
前提に従い、MT列からの素の出力値が、合計19937ビット、つまり32ビットで約623個分集まるとMT列上のユニークなビット列が特定でき、その後の予測が可能になるものとしよう。
まず解読者がすることは、最初の「開始点」「終了点」を仮定してみて、次にプールの状態を仮定し、それに対応する平均m/2個の「初期状態」と「BM」を仮定することである。
最初に「開始点」「終了点」を仮定するのだが、プールの個数はmだから、logm*logm程度の困難さがあるが、これは大きな値ではないので無視しよう。これによってMTの値の情報も与えないものとする。
初めの1つのプールの状態とBMを定めるには96ビットの情報が必要である。
これらを正しく仮定できたとしよう。このとき、MTは3個つまり96ビット解読されたことになる。96ビットの仮定（総当り）でMTが96ビット定まるのはごく当然であり、この時点では効率よく解読されたとは言えない。
次に、開始点～終了点の間に含まれる平均m/2個のプールの初期BMを正しく仮定することは
2^32^m/2＝16mビット
の困難さがある。
これらを正しく仮定できたとする。
次に、再び「開始点」と「終了点」を仮定するが、これは先に述べた通り情報量が少ないので無視する。
今回はBMについて、平均半分は既知（既に仮定した値）となっているので、平均的にm/4個だけ「初期状態」と「BM」を仮定すればよい。
これは
2^32^m/4＝8mビット
の難易度である。
同様にして、その後続けると、
（16m）＋（8m）＋（4m）＋･･･ビット
の困難さを得ることができ、解読者は
（m/2）+（m/2）+（m/2）+・・・
個のMT列を知ることができる。
解読者は、既に既知の部分が増えれば増えるほど、より効率的に既知の部分を見つけることができる。

明らかに、解読困難さを効率よく増加させるためには、（16m）＋（8m）＋（4m）＋･･･のうちの、（16m）の部分でビット数を稼ぐことが望ましい。
目的とする解読困難さをEビットに設定したい場合、この条件からは、
16m>=E
になるようにmを取ればよく、例えばE=19936ならm=>1246とすればよいことになる。

では他の解読方法を考えよう。
プールの初期状態を多く仮定してMT列の解読を試みることは、解読者にとって効率のよい作業ではない（充分なmを選べば、MTに対する総当たり攻撃と同程度の困難さになる）。
そこで解読者は、1つだけのプールの初期状態についてだけ着目して、「運良く」何度も連続してそのプールが使われる時を待つという方法で解読にあたるとする。
もしも我々にとって非常についていないことが起きて、例えば1246回に1回しか起きないことだが、連続で同じプールが呼ばれたとしたらどうだろうか？
しかもこれが何度も続いたらどうだろうか？
例えばプールサイズが2^10とすると、1/（2^10）*1/（2^10）の確率で連続して同じプールが選択され、しかもその次の出力も同じプールになる。
同じプールの状態やBMについては、前回の「仮定」ですでにわかっているものと考えるから、この場合1回あたりで20ビットの困難さは増すが、それに対して解読者が得る情報量はMTの出力値1つ分（32ビット）になってしまう。
一般にプールサイズがm=2^nと表されるとすると、2nビットごとに32ビットの情報量が解読者に知られる。
約19936ビットの情報が知られるとMTの出力値が予測可能になるという前提で考えると、プールサイズがm=2^nのとき、この解読法に対するS-POOLの解読困難さFはF<=19936*（2n/32）ビットつまり
F<=1246n
と評価できる。

さらに、1つだけではなくいくつかのプールにだけ着目する解読法についても考えよう。
着目するプール数がm/2以上になった場合に、安全性を満たすようなmの値は既に評価した。
では例として、2つの連続するプールに着目した場合はどうだろうか。
連続する、プールAとプールBの初期状態と初期BMを仮定し、「運良く」何度も連続してそれらのプールが使われる時を待つとどうだろうか。
プールA、プールBだけが繰り返し呼び出されるのは、2nビットの困難さである。
プールA、BのBMと状態は明らかになっている場合、出力値から64ビットの情報を得ることができてしまう。
これは、プールAの仮定から得られた「状態」がプールBにも流用できることによる。
プールをt個連続で観察するとして、そこから19936ビットのMTの情報を得るためにもっとも効率の良いtを考えてみる。



もしもこのように「状態」を連続的に定めることができない程度に長い連続したプールを使うなら、この問題は避けられる。
状態などを一意に仮定することができなくなる長さのプールとは、先にEの値を算出したときに求めたm/2である。




★状態が、MTやBMによらず0になるようになってしまっていて、そこから開始点終了点を決めると常に同じ開始点終了点になってしまうとするとどうか？
→開始点終了点の決定はプールの出力値とgenrand値をxorする。

m/2～m周期にすると、プールの移動が2＾10*2^10の組み合わせではなくなるので計算しなおし。

1つ飛ばしに状態を仮定したらどうか？
プール1　状態S1=0　S2=0　BM=1　　MT=1　　　S1　S2　BM　MTを仮定
　　　　2　状態S1=?　S2=?　BM=?　MT=?
　　　　3　状態S1=1　S2=0　BM=？
この状態から、何がわかるか？
プール1より、プール2でのS1’＝S2^BM＝1　S2’＝S1^MT＝1　がわかる。
さらにプール3の状態より、プール2でのBM=0　MT=1がわかる。
プール1を仮定し、プール3を仮定すると、プール2が既知になる。






結局この場合でも、それらのプールが選択される確率を考えると、「プールサイズがm=2^nと表されるとすると、2nビットごとに32ビットの情報量が解読者に知られる」ということに変化はない（むしろ、着目しているうちのどちらのプールが選ばれたかの選択）。
ゆえに、一定以上にmが大きい場合、上で考察した「1つのプールの状態に着目する」ことが解読者にとって最良の解読法である。

E、Fのうち小さい方の値が全体の強度になる。
n<=9においてはF>=E、n>=10においてはE>=Fであり、プールサイズと解読困難さ、使用メモリ総量の関係は以下の表のようになる

図：S-POOLのプールサイズと解読困難さ、使用メモリ総量の関係

使用目的に応じて解読困難さを想定し、メモリとの関係を考慮して実装できる。
なお、解読困難さとは、例えば1024ビットであれば「2^1024回の総当り攻撃をすると、MTの出力値19936ビット分が解読者に知られる」ということを意味する。「2^1024回の総当り攻撃でその後の出力がわかる」わけではない。
ここでは「MTの出力値が19936ビット知られると、即座にその後のMTの出力値が予測できる」という前提で議論しているが、もしMTの出力値からの先読みにも困難さがあるならば、その困難さを単純に加えることができる。
m=65536に取ると、プールの出力値からMTの出力値を見つける方法が、総当たり以外ないことになる。それは「S-POOLの出力値からは、MTの出力値について何もわからない」ことを意味し、ここでの目的を達成する。


このシステムのメリット

このシステムは果たして、MTの複数の出力値を単にXORすることや、MTの出力から「まばらに」乱数を得ることや、MTの値をハッシュして乱数値にする方法と比較して何が良いのだろうか？

MTの複数出力値のXORは、実行速度上の問題がある。毎回の乱数出力に、MT擬似乱数を何度も呼び出す必要があるからだ。
それに対してこのシステムでは1つのMT値から、1つのSHRAND値を得るために行う演算は、通常
出力＝(S1&(S2|(BM^MT)))|(S2&((~BM)^MT))
S1'=S2^BM
S2'=S1^MT
であり、
xor　4回
and　2回
not　1回
or　2回
だけである。
（ただしプールの周期の判定等のために加算・減算を行う。また2回程度比較を行い、プールサイズをmとしてm/2回に1回、SHRANDが2度呼びされる）
ほとんど、MTの出力1回に対して1つのリアルタイムレベルで1出力行うことができる。
また安全性の面から見ても、単純なXORよりもS-POOLの方が優れていることは明らかだろう。

「まばらに」乱数を得る方法はどうだろうか。
これも同様に、速度の問題がある。
MTのいくつかの出力値を捨て去るのだから、その分余分にMT出力が必要である。
しかも、速度を重視して捨て去る個数を減らしたり周期を長くすると、さほど困難なく解読されてしまう危険がある。

では、毎回ハッシュを使う方法はどうか。
これも明らかに、実行速度を無視した方法である。この方法は過去にVNCryptのメインアルゴリズムとして用いていたが、S-POOLの方法より実行時間が4倍程度かかった。

ある安全性が危機にさらされたときに、他の安全性を保つためには複数の安全性対策を講じる必要があるのが一般的である（例えばMTの出力値をSHAでハッシュする方法）。
通常、講じた安全性対策の数だけ実行ステップが増加するものだ。
このプールの特長は、ほとんどMT擬似乱数生成のCPU負荷を変化させることなく、MTの周期と乱数性を落とすことなく、MTの強度を充分に増加させられることにある。
SHRANDで生成した擬似乱数は、乱数評価の有名なテストDIEHARDテストに合格した（MTのDIEHARD結果はこちら）。


S-POOL初期状態の決定方法に関して

S-POOLの初期状態、初期BMの決定には、MTの出力をSHAを用いてハッシュして得られたビット列を用いる。
初めに生成した数字列ＡからSHAを取ったとき、そのSHAのビット並びからMTを推測することはできない。
衝突しない性質から、Ａにさらに数ビットMT乱数を加えた新しいＡ’のSHA値は、Ａから得られたSHA値に対して「でたらめな」ビット列になる。
ただし、最初のＡのサイズが小さい場合は、実際にSHAを取ることで乱数列が知られてしまうので、Aのサイズは充分に大きく取ることが重要である。
これを繰り返すことで、MTとは一見無関係な、その数字列からMTのビット列を推測することが非常に困難な数字列Ｐを得ることができる。
Ｐのうちどの一部分も、常にSHAによって生成されたビット列であって、それ自体からMTの部分を予測することは不可能である。
Ｐと一致するように実際にMT擬似乱数をハッシュして繰り返す作業は、Ａのサイズに依存する困難さを持つ。
したがって例えば、Ａが19936ビットであれば、困難さは2^19936の試行を要するレベルになる。
（仮に結果的に同じハッシュ値Ａを生成しても、それ自体はMTを推測する何の手がかりにもならないことに注意せよ）



実装：

（現在非公開。VNCrypt.dllに実装する）



関数：

void SHRAND_init(unsigned long init_key[], unsigned long key_length)

MT擬似乱数と完全に同じ形の初期化。
つまりMT擬似乱数をinit_by_array（）で初期化するかわりに、これを呼び出すことで、MTと全く同じ感覚で安全な擬似乱数列を得ることができる。
基本的に、周期はMTの周期と同程度になる（実際は周期は増加するが、安全性の面から言えばMTと同じ周期と考えるべきである）。

int SHRAND(void)

32ビットの安全な擬似乱数を返す。
MTのgenrand（）の代わりに用いる。



応用

hdrand.cと組み合わせれば、必要なビット数の安全性を持つ、再現可能な擬似乱数を高速に出力できる。
hdrand自体の出力値とこれを組み合わせれば、hdrandの安全性もさらに高まる。