218

私のチームは、ランダムトークンを生成するサーバー側のコード（Java）を渡されましたが、同じことについて質問があります-

これらのトークンの目的はかなり機密性が高く、セッションID、パスワードリセットリンクなどに使用されます。したがって、誰かがトークンを推測したり、ブルートフォース攻撃を実行したりしないように、暗号的にランダムである必要があります。トークンは「長い」ので、64ビット長です。

コードは現在、java.util.Randomクラスを使用してこれらのトークンを生成しています。のドキュメントにjava.util.Randomは、次のことが明確に記載されています。

java.util.Randomのインスタンスは、暗号的に安全ではありません。代わりに、SecureRandomを使用して、セキュリティに敏感なアプリケーションで使用するための暗号的に安全な疑似乱数ジェネレーターを入手することを検討してください。

ただし、コードが現在使用している方法は次のとおりです。クラスをjava.util.Randomインスタンス化java.security.SecureRandomし、SecureRandom.nextLong()メソッドを使用して、クラスのインスタンス化に使用されるシードを取得しますjava.util.Random。次に、java.util.Random.nextLong()メソッドを使用してトークンを生成します。

だから私の質問は今-java.util.Randomを使用してシードされていることを考えると、それはまだ安全ではありjava.security.SecureRandomませんか？java.security.SecureRandomトークンの生成にのみ使用するようにコードを変更する必要がありますか？

現在、コードシードRandomは起動時に1回です

4

7 に答える 7

247

標準の Oracle JDK 7 実装では、線形合同ジェネレーターと呼ばれるものを使用して、java.util.Random.

ソースコード (JDK 7u2)から取られ、ランダム値を生成するjava.util.Randommethod のコメントから:protected int next(int bits)

これは、DH Lehmer によって定義され、Donald E. Knuth によって The Art of Computer Programming、 Volume 3: Seminumerical Algorithms、セクション 3.2.1 で説明されている、線形合同疑似乱数ジェネレーターです。

線形合同ジェネレーターの予測可能性

Hugo Krawczyk は、これらの LCG を予測する方法について非常に優れた論文を書きました (「合同ジェネレーターの予測方法」)。運が良ければ、ウェブ上で無料でダウンロード可能なバージョンを見つけることができます。また、セキュリティが重要な目的で LCG を使用してはならないことを明確に示している調査は他にもたくさんあります。これは、乱数が現在予測可能であることも意味します。これは、セッション ID などには望ましくありません。

線形合同ジェネレーターを破る方法

攻撃者が完全なサイクルの後に LCG が繰り返されるのを待たなければならないという仮定は間違っています。最適なサイクル (再帰関係におけるモジュラス m) を使用しても、完全なサイクルよりもはるかに短い時間で将来の値を予測することは非常に簡単です。結局のところ、解く必要があるのはモジュラー方程式の集まりであり、LCG の十分な出力値を観察するとすぐに簡単になります。

「より良い」シードではセキュリティは向上しません。SecureRandomサイコロを数回転がすことによって生成されたランダムな値をシードするか、値を生成するかは問題ではありません。

攻撃者は、観測された出力値からシードを計算するだけです。の場合、これは 2^48 よりも大幅に時間がかかりませんjava.util.Random。信じられない人はこの実験を試すことができます。この実験Randomでは、約 2^16 の時間内に 2 つ (!) の出力値のみを観察して、将来の出力を予測できることが示されています。現在の乱数の出力を予測するのに、最新のコンピューターでは 1 秒もかかりません。

結論

現在のコードを置き換えます。SecureRandom排他的に使用します。そうすれば、少なくとも、結果を予測するのが難しいという保証が少し得られます。暗号的に安全なPRNGのプロパティが必要な場合（あなたの場合、それが必要です）、SecureRandomのみを使用する必要があります。本来の使用方法を賢く変更すると、ほとんどの場合、安全性が低下します...

于 2012-06-15T14:32:29.463 に答える
77

ランダムには48ビットしかありませんが、SecureRandomには最大128ビットを含めることができます。したがって、securerandomで繰り返す可能性は非常に低いです。

Randomは、system clockをシードとして使用します/またはシードを生成します。したがって、攻撃者がシードが生成された時刻を知っていれば、それらを簡単に再現できます。しかし、SecureRandomはRandom Dataあなたからos取得し（キーストローク間の間隔などである可能性があります-ほとんどのOSはこれらのデータを収集してファイルに保存します- /dev/random and /dev/urandom in case of linux/solaris）、それをシードとして使用します。
したがって、小さいトークンサイズで問題がない場合（ランダムの場合）、SecureRandomを使用してシードを生成しているため、コードを変更せずに引き続き使用できます。ただし、より大きなトークン（対象となることはできませんbrute force attacks）が必要な場合は、SecureRandomを使用してください-
ランダムな2^48試行が必要な場合、今日の高度なCPUを使用すると、実用的な時間でそれを破ることができます。しかし、セキュアランダムの2^128試行が必要になります。これは、今日の高度なマシンでも損益分岐点に達するまでに何年もかかります。

詳細については、このリンクを参照してください。
編集
@embossによって提供されたリンクを読んだ後、シードは、たとえランダムであっても、java.util.Randomで使用すべきではないことは明らかです。出力を観察することでシードを計算するのは非常に簡単です。

SecureRandomを選択-ネイティブPRNGを使用します（上記のリンクに示されているように）。これは、/dev/randomへの呼び出しごとにファイルからランダムな値を取得するためです。nextBytes()。このように、出力を監視している攻撃者は、ファイルの内容を制御していない限り、何も理解できません/dev/random（これはほとんどありません）。sha1prng
アルゴリズムは、シードを1回だけ計算し、VMが同じものを使用して数か月間実行されている場合シード、出力を受動的に監視している攻撃者によってクラックされる可能性があります。注-OSがランダムなバイト（エントロピー）をに書き込むことができるよりも速く呼び出している場合、 NATIVEPRNGを使用すると問題が発生する可能性があります 。その場合、SecureRandomのSHA1 PRNGインスタンスを使用し、数分（または一定の間隔）ごとに、このインスタンスに次の値をシードします。

nextBytes()/dev/randomnextBytes()SecureRandomのネイティブPRNGインスタンスの。これらの2つの並列処理を実行すると、オペレーティングシステムによって取得されたエントロピーを使い果たすことなく、真のランダム値を定期的にシードすることが保証されます。

于 2012-06-16T03:27:20.827 に答える
12

同じシードで2 回実行java.util.Random.nextLong()すると、同じ数が生成されます。セキュリティ上の理由からjava.security.SecureRandom、予測可能性がはるかに低いため、そのままにしておく必要があります。

2 つのクラスは似ています。リファクタリング ツールを使用して変更Randomするだけで、既存のコードのほとんどが機能すると思います。SecureRandom

于 2012-06-15T13:10:37.163 に答える
3

既存のコードを変更するのが手頃な作業である場合は、Javadoc で提案されているように SecureRandom クラスを使用することをお勧めします。

Random クラスの実装が SecureRandom クラスを内部で使用している場合でも。次のことを当然のことと考えるべきではありません。

  1. 他の VM 実装も同じことを行います。
  2. JDK の将来のバージョンでの Random クラスの実装では、引き続き SecureRandom クラスを使用します。

したがって、ドキュメントの提案に従い、SecureRandom を直接使用することをお勧めします。

于 2012-06-15T13:11:57.007 に答える
2

の現在の参照実装は、現在のシードの 32 ビットを直接java.util.Random.nextLong()公開するメソッドに対して 2 つの呼び出しを行います。next(int)

protected int next(int bits) {
    long nextseed;
    // calculate next seed: ...
    // and store it in the private "seed" field.
    return (int)(nextseed >>> (48 - bits));
}

public long nextLong() {
    // it's okay that the bottom word remains signed.
    return ((long)(next(32)) << 32) + next(32);
}

の結果の上位 32 ビットは、そのnextLong()時点でのシードのビットです。シードの幅は 48 ビットなので (javadoc によると)、2 番目の 32 ビットを生成したシードを決定するには、残りの 16 ビット (つまり 65.536 回の試行のみ) を反復処理するだけで十分です*。

シードが分かれば、後続のすべてのトークンを簡単に計算できます。

PNG のシークレットの一部を直接出力を使用してnextLong()、シークレット全体をほとんど手間をかけずに計算できる程度にします。危険！

* 2 番目の 32 ビットが負の場合、多少の努力が必要ですが、それを見つけることができます。

于 2012-06-21T14:49:49.037 に答える
2

種は無意味です。良い乱数発生器は、選択した素数が異なります。すべての乱数発生器は数値から始まり、「リング」を反復します。つまり、古い内部値を使用して、ある数値から次の数値に移動します。しかし、しばらくするとまた最初に到達し、最初からやり直します。したがって、サイクルを実行します。(乱数発生器からの戻り値は内部値ではありません)

リングを作成するために素数を使用する場合、すべての可能な数の完全なサイクルを完了する前に、そのリング内のすべての数が選択されます。非素数を取ると、すべての数が選択されるわけではなく、サイクルが短くなります。

素数が大きいほど、最初の要素に戻る前のサイクルが長くなります。したがって、安全な乱数生成器は、再び最初に到達するまでのサイクルが長いだけであり、それがより安全な理由です。より短いサイクルほど簡単に数の生成を予測することはできません。

言い換えれば、すべてを交換する必要があります。

于 2012-06-24T22:22:59.473 に答える