random之linux/dev/urandom 前向预测

zhujiabin 阅读:8 2024-06-20 12:54:19 评论:0

这是一个关于/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,一旦知道其内部状态,原则上就可以预测其输出。实际上并不是那么简单,因为内部状态相当大,散列函数阻止我们从输出向后工作。它可以通过反复试验来确定,但这可能需要很长时间。


标签:linux
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

关注我们

一个IT知识分享的公众号