这是一个关于 /dev/urandom
的 Linux 内核实现的问题。如果用户要求读取非常大量的数据(千兆字节)并且没有将熵添加到池中,是否可以根据当前数据预测从 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 是多少吗?
最佳答案
原则上,是的,您可以预测。当没有可用的熵时,dev/urandom 变为 PRNG,一旦知道其内部状态,原则上就可以预测其输出。实际上并不是那么简单,因为内部状态相当大,而且哈希函数阻止我们从输出向后工作。它可以通过反复试验来确定,但这可能需要很长时间。
关于random - linux/dev/urandom 前向预测,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/6929320/