linux 的 /dev/urandom 前向预测

Question

这是一个关于 Linux 内核实现的问题/dev/urandom。如果用户要求读取大量数据（千兆字节）并且熵没有添加到池中，是否可以根据当前数据预测从 urandom 生成的下一个数据？

通常的情况是当熵经常被添加到池中时，但在我的情况下我们可以考虑，没有额外的熵（例如，添加它被内核补丁禁用）。所以在我的情况下，问题是关于 urandom 算法本身。

来源是 /drivers/char/random.c 或http://www.google.com/codesearch#KMCRKdMbI4g/drivers/char/random.c&q=urandom%20linux&type=cs&l=116

或http://lxr.linux.no/linux+v3.3.3/drivers/char/random.c

 // data copying loop
    while (nbytes) {
            extract_buf(r, tmp);

            memcpy(buf, tmp, i);
            nbytes -= i;
            buf += i;
            ret += i;
    }

static void extract_buf(struct entropy_store *r, __u8 *out)
{
        int i;
        __u32 hash[5], workspace[SHA_WORKSPACE_WORDS];
        __u8 extract[64];

        /* Generate a hash across the pool, 16 words (512 bits) at a time */
        sha_init(hash);
        for (i = 0; i < r->poolinfo->poolwords; i += 16)
                sha_transform(hash, (__u8 *)(r->pool + i), workspace);

        /*
         * We mix the hash back into the pool to prevent backtracking
         * attacks (where the attacker knows the state of the pool
         * plus the current outputs, and attempts to find previous
         * ouputs), unless the hash function can be inverted. By
         * mixing at least a SHA1 worth of hash data back, we make
         * brute-forcing the feedback as hard as brute-forcing the
         * hash.
         */
        mix_pool_bytes_extract(r, hash, sizeof(hash), extract);

        /*
         * To avoid duplicates, we atomically extract a portion of the
         * pool while mixing, and hash one final time.
         */
        sha_transform(hash, extract, workspace);
        memset(extract, 0, sizeof(extract));
        memset(workspace, 0, sizeof(workspace));

        /*
         * In case the hash function has some recognizable output
         * pattern, we fold it in half. Thus, we always feed back
         * twice as much data as we output.
         */
        hash[0] ^= hash[3];
        hash[1] ^= hash[4];
        hash[2] ^= rol32(hash[2], 16);
        memcpy(out, hash, EXTRACT_SIZE);
        memset(hash, 0, sizeof(hash));
}

有一个回溯预防机制，但是“向前追踪”呢？

例如：我从 urandom 中对 500 MB 进行了一次读取系统调用，并且已知所有数据高达第 200 MB 且池中没有额外的熵，我能预测第 201 MB 是多少吗？

Answer 1

原则上，是的，您可以预测。当没有可用的熵时，dev/urandom 变为 PRNG，一旦知道其内部状态，原则上就可以预测其输出。实际上并不是那么简单，因为内部状态相当大，而且哈希函数阻止我们从输出向后工作。它可以通过反复试验来确定，但这可能需要很长时间。

Answer 2

“加密强伪随机数生成器”的定义是，将其输出与真随机数生成器的输出区分开在计算上是不可行的。如果您可以从过去的输出中预测未来的输出，那么您就可以区分；因此，除非 Linux urandom 算法很弱，否则您不能这样做。

对我来说，该代码看起来不像任何标准的伪随机生成器——Linux 人员有一个不幸的习惯是“滚动他们自己的”——但无论如何破坏它可能是一个可发布的结果。所以如果它是易碎的，我怀疑这并不容易。

当然，设计的目的是让“不”成为您问题的答案。

[编辑]

当然，在信息论意义上，答案是肯定的，因为你不能从有限熵中得到无限熵。但在信息论意义上，除了一次性密码外，没有其他安全密码。我假设您正在询问实用/密码学意义。

[编辑 2]

稍微搜索一下就会发现这篇论文，它声称演示了针对 Linux 的 /dev/urandom 中的“前向安全性”的攻击。（也就是说，给定生成器的状态，尝试重建较早的状态。）

这就是为什么程序员永远不应该尝试发明自己的密码学。不管你自认为多么聪明，一些以这种东西为生的以色列学者会让你看起来很愚蠢。

也就是说，我没有看到对生成器输出的任何攻击，这就是您要问的。