ハッシュを使った擬似乱数

質問

予測不能な擬似乱数列を生成する際に、よく一方向ハッシュの性質を利用する
場合があります。一方向ハッシュの生成源として内部状態が与えられますが、
内部状態のbitサイズはどの程度にしたらよいでしょうか？

　 [種（カウンタの初期値）]
　　　　　　　｜
　　　　　　　｜
　　　　　　　↓
┌→[内部状態（カウンタ）]―┬―→(一方向ハッシュ)――→擬似乱数列
｜　　　　　　　　　　　　　　　　　｜
｜　　　　　　　　　　　　　　　　　↓
｜　　　　　　　　　　　　　　　[1増加]
｜　　　　　　　　　　　　　　　　　｜
└―――――――――――┘

※　暗号技術入門　秘密の国のアリス　結城　浩　著
　　　　　――第12章　乱数　Fig.12.5　より

極端な例として鍵（種）のサイズを32bit(C言語でunsigned long型)、値を0とします。

|0000 0000|0000 0000|0000 0000|0000 0000|

上記の値でハッシュ値を取ります。ハッシュアルゴリズムがSHA1の場合、
以下のような値が得られます（と思います）。

a = -1099956234
b = -343932961
c = -1287651379
d = -84150665
e = -1099170433

これらの値から鍵の値を得ることは困難なので、ハッシュ値によって生成された
擬似乱数は予測不能であるといえます。また、鍵の値を1だけ加算させて次の擬似乱数
を生成します。一般的にこのようにして乱数列は生成されます。

上記の例では32bitのとり得る値は0～4294967295です。鍵の値を一つずつ試し
ていけば、それほど時間をかけることなく乱数の予測不能性は破られてしまいます。
ここで鍵の値を256bitとしました。

|0000 0000|0000 0000|0000 0000|0000 0000|
|0000 0000|0000 0000|0000 0000|0000 0000|
|0000 0000|0000 0000|0000 0000|0000 0000|
|0000 0000|0000 0000|0000 0000|0000 0000|
|0000 0000|0000 0000|0000 0000|0000 0000|
|0000 0000|0000 0000|0000 0000|0000 0000|
|0000 0000|0000 0000|0000 0000|0000 0000|
|0000 0000|0000 0000|0000 0000|0000 0000|

しかしこれだと1加算しただけではビット全体に対して変化が少なすぎます。

|0000 0000|0000 0000|0000 0000|0000 0000|
|0000 0000|0000 0000|0000 0000|0000 0000|
|0000 0000|0000 0000|0000 0000|0000 0000|
|0000 0000|0000 0000|0000 0000|0000 0000|
|0000 0000|0000 0000|0000 0000|0000 0000|
|0000 0000|0000 0000|0000 0000|0000 0000|
|0000 0000|0000 0000|0000 0000|0000 0000|
|0000 0000|0000 0000|0000 0000|0000 0001|←

2005年に中国の大学の研究チームによってSHA1の弱衝突耐性が破られてしまいました。
現段階ではSHA1に変わる新しいアルゴリズムは発見されていません。（SHA2が作られましたが、
これはSHA1のbit数を拡張しただけで基本設計は変わっていません）なのでハッシュ値を
生成させる値もなるべく変化に富んだ値を与えることが推奨されています。

まとめると、

　　・鍵（種）を総当り攻撃されないようにbit数を大きくしなけらばならない。

　　・bit数を大きくすると1加算したときに変化が小さすぎる。

　　・最初の図の手法は同記の文献に書いてあったもので、なるべく変えたくない。
　　　（実際に使われる手法はある程度保障されているから）

の制約があります。なので”bit数をどの程度にしたら適当か？？？”というのが質問です。
また、これらの問題を打開する方法もあればよいのですが、、、

回答No.1

Rice-Etude · ベストアンサー

まず、SHA1の安全性については「（弱衝突ではなく）強衝突に対する脆弱性が見つかった」というもので、m1≠m2かつSHA-1(m1)=SHA-1(m2)となるm1とm2の組が2^(-80)よりも高い確率で見つかることが理論的に示されました。ただし、現時点でこの条件を満たすm1とm2が見つかったわけではありません。また、SHA2が同じような脆弱性の危険性が言われたりしますが、現時点では実際に脆弱性が見つかったわけではありません。

さらにSHA1に変わるアルゴリズムとして、NISTでSHA3コンペティションというのが開催されており、様々なアルゴリズムが提案されております。

さて、ご質問の「bit数をどの程度にしたら適当か？」という問いに対する答えとしては「一方向性ハッシュ関数の脆弱性が見つかるかどうかに依存するが、今のところ脆弱性が見つかっていないのであれば共通鍵暗号における鍵の全数探索の耐性と同等（今なら128ビット）以上であれば」となるのかなと思います。

「鍵（種）を総当り攻撃されないようにbit数を大きくしなけらばならない」はその通りですが、「bit数を大きくすると1加算したときに変化が小さすぎる」については、安全な一方向性ハッシュ関数であればここは問題にはなりません。なぜならば、もしある特定のビットを固定した複数のメッセージを一方向性ハッシュ関数に入力し、その出力に相関があるのであれば原像攻撃に弱いことになる（すなわち脆弱性がある）ことから、安全な一方向性ハッシュ関数であれば当然その脆弱性は（見つかって）ないということになるからです。

よって、あとは一方向性ハッシュ関数しだいということになります。そして、その脆弱性が見つけられていないのであれば、あとは入力値である鍵（種）の全数探索の耐性があればよく、共通鍵暗号の鍵長と同じ考えになるかと思います。

お礼

ありがとうございます。確かに現時点でSHA1のアルゴリズムを使用している例は
たくさんあるようですね。SHA1の強衝突（質問の文章で間違えてましたね^^;）
に対する脆弱性が見つかったということについては過剰に認識していたようです。

鍵の長さは128bitがよく使われているようですね。最近ではコンピュータの計算速度が
とても早くなり、並列計算も増えてきたということで160bitや256bitもあるみたいです。
bit長をのばしても問題ないということで、今回は128bit以上で決定しようと思います。