5

time()Perl バージョン 5.004 より前のバージョンを使用した場合の問題に関するドキュメントはたくさんありますが、それ以降のものはありません。

宿題として、デフォルトの Perlsrand()にはデフォルトのシード処理にまだ欠陥があるという前提に基づいて、プログラムの結果をリバース エンジニアリングするよう求められます。perl 5.004 リリースの変更ログには、srand()デフォルトのシードが「予測が困難なシステム依存値の大量混合」に基づいていると記載されています。

もしそうなら、それらの価値は何であり、固有の弱点はありますか?

4

1 に答える 1

3

(私は暗号学者ではありませんが、何年にもわたって多くのことを吸収してきました。クライアントの乱数生成を何年も前に精査するのを手伝わなければなりませんでした。その結果、以下で説明する Crypt::Random バグが見つかりました。)

これらすべての ifdef を適切にインデントすると、シード コードはより意味のあるものになります。これは 5.16.0 のコードです。

U32
Perl_seed(pTHX)
{
    dVAR;
    /*
     * This is really just a quick hack which grabs various garbage
     * values.  It really should be a real hash algorithm which
     * spreads the effect of every input bit onto every output bit,
     * if someone who knows about such things would bother to write it.
     * Might be a good idea to add that function to CORE as well.
     * No numbers below come from careful analysis or anything here,
     * except they are primes and SEED_C1 > 1E6 to get a full-width
     * value from (tv_sec * SEED_C1 + tv_usec).  The multipliers should
     * probably be bigger too.
     */
#if RANDBITS > 16
#  define SEED_C1   1000003
#  define SEED_C4   73819
#else
#  define SEED_C1   25747
#  define SEED_C4   20639
#endif

#define   SEED_C2   3
#define   SEED_C3   269
#define   SEED_C5   26107

#ifndef PERL_NO_DEV_RANDOM
    int fd;
#endif

    U32 u;

#ifdef VMS
#  include <starlet.h>
    /* when[] = (low 32 bits, high 32 bits) of time since epoch
     * in 100-ns units, typically incremented ever 10 ms.        */
   unsigned int when[2];
#else
#  ifdef HAS_GETTIMEOFDAY
       struct timeval when;
#  else
       Time_t when;
#  endif
#endif

/* This test is an escape hatch, this symbol isn't set by Configure. */
#ifndef PERL_NO_DEV_RANDOM
#    ifndef PERL_RANDOM_DEVICE
         /* /dev/random isn't used by default because reads from it will block
          * if there isn't enough entropy available.  You can compile with
          * PERL_RANDOM_DEVICE to it if you'd prefer Perl to block until there
          * is enough real entropy to fill the seed. */
#        define PERL_RANDOM_DEVICE "/dev/urandom"
#    endif
     fd = PerlLIO_open(PERL_RANDOM_DEVICE, 0);
     if (fd != -1) {
        if (PerlLIO_read(fd, (void*)&u, sizeof u) != sizeof u)
        u = 0;
    PerlLIO_close(fd);
    if (u)
        return u;
    }
#endif

#ifdef VMS
    _ckvmssts(sys$gettim(when));
    u = (U32)SEED_C1 * when[0] + (U32)SEED_C2 * when[1];
#else
#  ifdef HAS_GETTIMEOFDAY
        PerlProc_gettimeofday(&when,NULL);
        u = (U32)SEED_C1 * when.tv_sec + (U32)SEED_C2 * when.tv_usec;
#  else
        (void)time(&when);
        u = (U32)SEED_C1 * when;
#  endif
#endif

    u += SEED_C3 * (U32)PerlProc_getpid();
    u += SEED_C4 * (U32)PTR2UV(PL_stack_sp);

#ifndef PLAN9           /* XXX Plan9 assembler chokes on this; fix needed  */
    u += SEED_C5 * (U32)PTR2UV(&when);
#endif

    return u;
}

エントロピーを取得するいくつかの異なる方法がすべて一緒にインターリーブされているため、コードは非常に紛らわしいです。基本的に 2 つのパスがあります。システムのランダム デバイスと、インタプリタと環境の状態からの収集です。

  • システムのランダム デバイス。

これは最も簡単で、おそらく最も強力な方法です。OSにブロックしないランダムデバイスがある場合、つまり. /dev/urandomそこから 32 ビットを読み取ります。終わり！ #ifndef PERL_NO_DEV_RANDOM(素敵な二重否定) そのビットを制御します。これは、ほぼすべての Unix システムで行われます。この時点で、Perl のランダム シードの分析は、特定の OS の実装に切り替わります/dev/urandom。

  • クロック、pid、およびスタック ポインターから何かを導出します。

システムにランダムなデバイスがない場合 (基本的には Windows)、Perl はフォールバックして、システム値を予測するのが難しいと思われるいくつかのシステム値を混ぜ合わせてシードを導出します。

  • マイクロ秒単位または秒単位の時間は、gettimeofday()存在するかどうかによって異なります。
  • プロセス ID PerlProc_getpid()、.
  • 現在のスタック ポインターのメモリ位置PTR2UV(PL_stack_sp)。

その情報で何をすべきか、そしてこれが最初の大きなコメントが何であるかは、実際のハッシュアルゴリズムを使用してそれらを一緒にマッシュアップすることです. 代わりに、さまざまな定数 (SEED_C1などSEED_C2) を掛けて加算します。これは間違いなく欠陥です。

その情報はすべて、理論上は予測可能です。システム情報を予測する際の最新技術が何であるかはわかりませんが、時間 + pid + スタック ポインターはエントロピーを取得するためのかなり一般的な方法であり、この件に関する論文は必ずあります。

Perl のすべての方法に共通する追加の欠陥があります。これは、64 ビット マシンでも 32 ビットのみを使用して行われます。から 64 ビットをプルするのでは/dev/urandomなく、32 ビットだけをプルします。64 ビットの情報がある場合でも、32 ビットのプロセス ID、スタック ポインター、または時間情報のみを調べます。

コードを読んだ後、私は 3 つの懸念があります。

  • わずか 32 ビットの乱数の使用。

マルチGPUシステムがそれをブルートフォースする可能性があります。

  • (Unix) あなたの はいかがですか/dev/urandom。

/dev/urandomあまりにも速く引きすぎると、エントロピーが不足する可能性があります。ブロックする代わりに、より弱いエントロピーを生成します。これは Perl の制御範囲外ですが、システム全体の弱点です。さらに、一部のプログラムは、必要以上にエントロピーを引き出す可能性があり/dev/urandomます。何年も前に Crypt::Random でまさにそれを行っていたバグを発見しました。

  • (Windows) その弱いハッシュ アルゴリズム。

32 ビットの問題に次いで、これがおそらく最も弱いリンクです。

  • どのランダム関数を使用していますか?

シードが提供されると、それはどの乱数関数に渡されますか? rand 関数が貧弱であると、シードの推測が容易になります。Perl はいくつかを探しますが、通常はdrand48. で何を使用しているかを確認できますuse Config; print $Config{randfunc}'。それがどれほどうまく機能するかはわかりませんが、OS X drand48 の man ページrandom(3)にはより強力であると書かれており、Linux の man ページにはdrand48 is obsoleteと書かれています。

この機能はそれ以来変更されていません...ああ、90年代後半です。これは util.c に移動されましたが、深刻な変更は加えられていません。 git blame 132efe8bfb7cd0fb1beb15aaf284e33bf44eb1fa^ pp.c実際の履歴を表示します。 を探しますS_seed。愛情が必要なのかもしれません。他のほとんどの言語には、より高度な乱数ジェネレーターがあります。

于 2012-10-20T23:48:58.487 に答える