Perl 的 srand() 默认种子(5.004 版本后)有哪些弱点?

2023-12-03

我可以找到大量有关使用问题的文档time()Perl 版本 5.004 之前的版本,但没有后续版本。

对于家庭作业,我们被要求基于默认 Perl 的假设对程序的结果进行逆向工程srand()默认播种仍然存在缺陷。这perl 5.004 版本的变更日志指出srand()默认种子现在基于“难以预测的系统相关值的大量组合”。

是这样吗?如果是这样,这些价值观是什么?它们是否有任何固有的弱点?


(我不是密码学家,但多年来我吸收了很多东西。几年前我必须帮助检查客户的随机数生成,这就是导致发现下面提到的 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() exists.
  • 进程 ID,PerlProc_getpid().
  • 当前堆栈指针的内存位置,PTR2UV(PL_stack_sp).

What it should处理这些信息,这就是一开始的大评论,就是使用真正的哈希算法将它们混合在一起。相反,它将它们乘以各种常数(SEED_C1, SEED_C2等等)并将它们相加。这肯定是有缺陷的。

理论上,所有这些信息都是可预测的。我不知道预测系统信息的最新技术是什么,但是时间 + pid + 堆栈指针是获取熵的相当常见的方法,并且肯定会有关于该主题的论文。

所有 Perl 方法还有一个共同的缺陷,即使在 64 位机器上,它也仅使用 32 位来完成这一切。它不会拉出 64 位/dev/urandom,只有 32 位。即使有 64 位信息,它也只会查看 32 位进程 ID、堆栈指针或时间信息。

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

  • 它仅使用 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 已过时.

自 90 年代末以来,该功能就再也没有被触及过。它已移至 util.c,但尚未受到严重影响。git blame 132efe8bfb7cd0fb1beb15aaf284e33bf44eb1fa^ pp.c显示真实历史,寻找S_seed。也许它需要一些爱。大多数其他语言都有更先进的随机数生成器.

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

Perl 的 srand() 默认种子(5.004 版本后)有哪些弱点? 的相关文章

随机推荐