Perl的5.004版默认种子srand()的弱点是什么? [英] What are the weaknesses of Perl's srand() default seed, post version 5.004?

问题描述

在Perl 5.004版之前，我可以找到许多有关使用time()的问题的文档，但后面没有任何内容.

I can find plenty of documentation as to issues with use of time() prior to Perl version 5.004, but nothing following.

对于一项家庭作业，我们被要求对默认的Perl srand()在默认播种中仍存在缺陷的假设进行逆向工程. 更改日志指出srand()默认种子现在基于大量难以预测的系统相关值的组合".

For a homework assignment, we are asked to reverse-engineer a program's results based on the assumption that the default Perl srand() is still flawed in default seeding. The changelog for the perl 5.004 release states that the srand() default seed is now based on "a heavy mix of difficult-to-predict system-dependent values."

是这种情况吗?如果是的话，这些价值观是什么?它们是否有内在的弱点?

Is that the case, and, if so, what are those values and do they have any inherent weaknesses?

推荐答案

(我不是密码专家，但多年来我已经投入了大量精力.我不得不帮助仔细审查客户的随机数生成年份，这是导致找到下面提到的Crypt :: Random错误.)

(I am not a cryptographer but I've absorbed a lot over the years. I had to help scrutinize a client's random number generation years back which is what lead to finding that Crypt::Random bug mentioned below.)

如果适当缩进所有这些ifdef，则种子代码更有意义.这是5.16.0中的代码.

The seed code makes more sense if you properly indent all those ifdefs. This is the code in 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;
}

代码是如此混乱，因为它实际上是使熵相互交织在一起的几种不同方式.基本上有两条路径:系统随机设备以及从解释器的状态和环境中收集信息.

The code is so confusing because it's really several different ways of getting entropy all interleaved together. There's basically two paths: the system random device and gathering from the state of the interpreter and environment.

• 系统随机设备.

这是最简单且可能最强的方法.如果您的操作系统具有不阻塞的随机设备，即. /dev/urandom从中读取32位.完毕！ #ifndef PERL_NO_DEV_RANDOM(双精度负数)控制该位.几乎在每个Unix系统上都可以做到这一点.此时，对Perl的随机种子的分析将切换到特定OS的/dev/urandom的实现.

This is the simplest and probably strongest method. If your OS has a random device which does not block, ie. /dev/urandom read 32 bits from it. Done! #ifndef PERL_NO_DEV_RANDOM (nice double negative) controls that bit. This is done on pretty much every Unix system. At this point the analysis of Perl's random seed switches to the implementation of your particular OS' /dev/urandom.

• 从时钟，pid和堆栈指针派生一些东西.

如果您的系统没有随机设备(基本上是Windows)，则Perl会通过混合一些希望难以预测的系统值来返回种子.

If your system does not have a random device, basically Windows, Perl falls back to deriving a seed by mixing up some hopefully hard to predict system values.

• 时间(以微秒为单位或以秒为单位)取决于gettimeofday()是否存在.
• 进程ID，PerlProc_getpid().
• 当前堆栈指针PTR2UV(PL_stack_sp)的内存位置.

• The time in microseconds or just seconds, depends on if gettimeofday() exists.
• The process id, PerlProc_getpid().
• The memory location of the current stack pointer, PTR2UV(PL_stack_sp).

该信息应该应该做什么，这就是开始时最受关注的事情，那就是使用真正的哈希算法将它们融合在一起.而是将它们乘以各种常数(SEED_C1，SEED_C2等)并将它们相加.这肯定是有缺陷的.

What it should do with that information, and this is what the big comment at the start is about, is mash them together using a real hashing algorithm. Instead it multiplies them by various constants (SEED_C1, SEED_C2 and so on) and adds them up. This is sure to be flawed.

从理论上讲，所有这些信息都是可以预测的.我不知道预测系统信息的最新状态，但是时间+ pid +堆栈指针是获取熵的一种相当普遍的方法，并且肯定有关于该主题的论文.

All of that information is, in theory, predictable. I don't know what the state of the art is in predicting system information, but time + pid + stack pointer is a fairly common method of getting entropy and there's sure to be papers on the subject.

Perl的所有方法都有一个共同的缺点，即使在64位机器上，它也只使用32位来完成所有这些工作.它不会从/dev/urandom中提取64位，而只会提取32位.即使有64位信息，它也只会查看进程ID，堆栈指针或时间信息的32位.

There is an additional flaw in common with all of Perl's methods, it does this all using only 32 bits even on 64 bit machines. It will not pull 64 bits out of /dev/urandom, just 32. It will only look at 32 bits of the process id, stack pointer or time information even if there's 64 bits of information.

通读代码后，我会关注三个方面.

After reading through the code I three concerns.

• 它仅使用32位随机性.

多GPU系统可能会对此施加暴力.

It's possible multi-GPU system could brute force that.

• (Unix)您的/dev/urandom有多好.

• (Unix) How good is your /dev/urandom.

/dev/urandom太快地从熵中耗尽，它可能会耗尽熵.而不是阻止它会产生较弱的熵.这是Perl无法控制的，但它是系统范围的弱点.此外，某些程序可能会拉出更多的熵，而不是用尽/dev/urandom所需的熵.我们几年前在Crypt :: Random 中发现了一个错误.就是这样.

/dev/urandom can run out of entropy if you pull too much from it too fast. Instead of blocking it will generate weaker entropy. This is out of Perl's control but is a system wide weakness. In addition, some programs may pull more entropy than they need exhausting /dev/urandom. We found a bug years ago in Crypt::Random which was doing just that.

• (Windows)弱哈希算法.

在32位问题旁边，这可能是最弱的链接.

Next to the 32 bit issue, this is probably the weakest link.

• 它使用什么随机函数?

一旦提供了种子，它将传递给什么随机数函数?较差的rand函数使更容易猜测种子. Perl寻找几种，通常以drand48结尾.您可以看到它的用途:use Config; print $Config{randfunc}'.我不知道它的工作原理如何，但是OS X drand48手册页说random(3)更强大，而Linux手册页说 drand48已过时.

Once a seed has been provided, what random number function is it passing it to? A poor rand function makes it easier to guess the seed. Perl looks for several, usually winding up with drand48. You can see what its using with: use Config; print $Config{randfunc}'. I have no idea how well that works, but the OS X drand48 man page says random(3) is more powerful and the Linux man page says drand48 is obsolete.

此功能自……以来一直没有被使用过.哦，亲爱的90年代后期.它已移至util.c，但并未受到严重影响. git blame 132efe8bfb7cd0fb1beb15aaf284e33bf44eb1fa^ pp.c显示了真实的历史记录，请查找S_seed.它可能需要一些爱.其他大多数语言都有更高级的随机数生成器.

The function hasn't been touched since... oh dear the late 90s. It was moved to util.c but hasn't been seriously touched. git blame 132efe8bfb7cd0fb1beb15aaf284e33bf44eb1fa^ pp.c shows the real history, look for S_seed. It probably needs some love. Most other languages have more advanced random number generators.

这篇关于Perl的5.004版默认种子srand()的弱点是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！