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;
}

代码是如此令人困惑，因为它实际上是几种不同的方式将熵全部交错在一起。基本上有两条路径：系统随机设备和从解释器和环境的状态中收集。

  • 系统随机设备。

这是最简单也可能是最强的方法。如果您的操作系统有一个不阻塞的随机设备，即。/dev/urandom从中读取 32 位。完毕！ #ifndef PERL_NO_DEV_RANDOM（漂亮的双重否定）控制该位。这几乎在每个 Unix 系统上都完成了。此时，Perl 随机种子的分析切换到您特定操作系统的实现/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 位信息，它也只会查看进程 ID、堆栈指针或时间信息的 32 位。

通读代码后，我担心三个问题。

  • 它仅使用 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 手册页说random(3)更强大，Linux 手册页说drand48 is obsolete。

自从......哦，天哪，90 年代后期，这个功能就没有被触及过。它已移至 util.c，但尚未被认真对待。 git blame 132efe8bfb7cd0fb1beb15aaf284e33bf44eb1fa^ pp.c显示真实历史，寻找S_seed。它可能需要一些爱。大多数其他语言都有更高级的随机数生成器。

于 2012-10-20T23:48:58.487 回答