9

この記事は次のように述べています

メルセンヌツイスターは非常に優れた疑似乱数ジェネレーターであるという事実にもかかわらず、非常に単純な理由から、それ自体では暗号的に安全ではありません。ジェネレータの将来のすべての状態は、ジェネレータが常に持つ状態から判断でき、その状態を提供するには、624個の32ビット出力または19,937個の1ビット出力で十分です。暗号化に役立つキーストリームを取得する1つの方法として、メルセンヌツイスターの出力でSHA-1などの暗号的に安全なハッシュ関数を使用することが推奨されています。

しかし、出力をダイジェストすると安全性が高まる理由については言及されていません。そして正直なところ、なぜそうなのかわかりません。メルセンヌツイスターの周期は2^19937-1ですが、私の推論は、線形合同法などの定期的なPRNGにも当てはまると思います。安全な一方向性関数hの特性により、hは単射関数と考えることができます（そうでない場合は衝突が発生する可能性があります）。したがって、定義域から範囲に値を1対1でマッピングするだけです。

この考えを念頭に置いて、ハッシュ値は元のメルセンヌツイスターが行ったのとまったく同じ定期的な動作を生成すると主張します。これは、1つの期間のすべての値を観察し、値が繰り返し開始された場合、将来のすべての値を完全に予測できることを意味します。

これは、パスワードベースの暗号化（ PKCS＃5 ）に適用されるのと同じ原則に関連していると思います-パスワードのドメインは十分なエントロピーを提供しないため、パスワードをハッシュするだけでは追加のエントロピーは追加されません-それが必要な理由ですパスワードをハッシュする前にソルトします。ここでもまったく同じ原理が当てはまると思います。

最終的に私を納得させた1つの簡単な例：常に1の「乱数」を生成する非常に悪いPRNGがあるとします。次に、SHA-1が完全な一方向性関数であっても、SHA-1を出力に適用すると常に同じ値を生成するため、出力は以前と同じように予測可能になります。

それでも、その記事には真実があると信じたいので、確かに何かを見落としていたに違いありません。あなたは私を助けることができます？大部分、私は私の議論からシード値を省略しました-多分これは魔法が起こる場所ですか？

4

2 に答える 2

15

メルセンヌツイスターの状態は、前のn出力によって定義されます。ここnで、は再発の程度（定数）です。そのためn、メルセンヌツイスターから直接攻撃者に出力を与えると、攻撃者はすぐにすべての将来の値を予測できるようになります。

SHA-1を介して値を渡すと、攻撃者はRNGを逆にしようとする必要があるため、より困難になります。ただし、32ビットのワードサイズの場合、これが断固とした攻撃者にとって深刻な障害になる可能性はほとんどありません。レインボーテーブルを作成するか、SHA-1を反転させるための他の標準的なアプローチを使用し、衝突が発生した場合は、観測されたRNGストリームを生成するかどうかで候補をフィルタリングできます。そのため、メルセンヌツイスターは、暗号に敏感なアプリケーション、SHA-1マスキング、またはそのようなアプリケーションには使用しないでください。代わりに使用できる標準のCSPRNGがいくつかあります。

于 2011-07-08T00:59:55.083 に答える
5

攻撃者は、比較的少数の出力に基づいてMTの出力を予測できます。これは、MTがこのように短い期間で繰り返されるためではなく（繰り返されないため）、出力がPRNGの内部状態に関する情報をリークするためです。出力をハッシュすると、漏洩した情報がわかりにくくなります。ただし、@ bdonlanが指摘しているように、出力サイズが小さい場合（たとえば、32ビット）、攻撃者はすべての有効な平文を簡単に列挙してハッシュを事前計算できるため、これは役に立ちません。

ハッシュへの入力として32ビットを超えるPRNG出力を使用すると、これは実用的ではありませんが、このプロパティが必要な場合は、暗号的に安全なPRNGの方がはるかに適しています。

于 2011-07-08T02:28:18.997 に答える