random.choice并非随机的

16

我在Linux上使用Python 2.5,在多个并行的FCGI进程中使用。

    chars = string.ascii_letters + string.digits
    cookie = ''.join([random.choice(chars) for x in range(32)])

生成独特的Cookie。假设随机数生成器是从/dev/urandom中获取的种子,并且随机数序列来自Mersenne扭曲器,我认为碰撞的几率几乎为零。

然而,我发现经常会出现碰撞,即使只有很少的(<100)用户同时登录。

为什么这些随机数不够随机?


4
什么是“chars”?如果里面只有一个字符,你总是会出现冲突(为了说明这一点)。 - Vinko Vrsalovic
字符列表的长度是多少? - Nick Dandoulakis
我已经解决了这个问题(希望如此),通过使用os.random - 这也是uuid4使用的选项之一;另一个选项是使用random.randrange,在这种情况下,我想知道uuid4是否会生成唯一的ID。我的问题真正在于为什么我的代码不起作用。 - Martin v. Löwis
如果可能的话,您应该始终发布演示问题的代码。 - Glenn Maynard
1
使用os.random生成cookie可能不是一个好主意——如果你一次生成了一堆cookie,它会阻塞直到接收到更多的熵;即使你的流量很低,这也是一种简单的DOS攻击。在几乎所有的应用程序中,os.urandom都可以胜任此任务。 - Glenn Maynard
显示剩余4条评论
5个回答

13

它不应该生成重复项。

import random
chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
def gen():
    return ''.join([random.choice(chars) for x in range(32)])

test = [gen() for i in range(100000)]
print len(test), len(set(test)) # 100000 100000

使用字符串 chars = "ab" 生成的随机数,在 1000000 次迭代中有 126 次重复。如果使用62个字符,则几乎没有重复的概率。

尽管如此,这并不是生成 cookie 的好方法,因为会话 cookie 需要是不可预测的,以避免涉及窃取其他人会话 cookie 的攻击。Mersenne Twister 不适用于生成安全的随机数。以下是我建议的方法:

import os, hashlib
def gen():
    return hashlib.sha1(os.urandom(512)).hexdigest()

test = [gen() for i in range(100000)]
print len(test), len(set(test))

…应该是非常安全的(也就是说,难以根据会话cookie字符串猜测其他现有的会话cookie)。


3
来自维基百科:"原生形式的梅森旋转算法不适用于密码学(不像Blum Blum Shub)。观察足够数量的迭代次数(在MT19937的情况下为624)可预测所有未来的迭代。" (http://en.wikipedia.org/wiki/Mersenne_twister) - Chris Lutz
10
仅仅因为一个随机数生成器有一个长的周期,并不意味着难以在循环中找出序列的位置。如果我给你序列0,1,2,3......它有一个非常长的周期(无限),但是确定下一个值非常简单。你需要一个密码安全的序列——从其输出中确定引擎状态很困难。这就是安全哈希函数的作用。我更喜欢将urandom哈希通过SHA-1,但是通过SHA-1哈希MT也可能没问题。 - Glenn Maynard
1
实际上,我认为urandom在内部使用SHA-1来生成数据,至少在Linux上是这样。 urandom的输出本身应该具有加密强度。通过直接对数据进行哈希处理,可以显式地确保这一点,而且非常简单和便宜。 - Glenn Maynard
2
我刚才检查了一下:在Linux上,/dev/urandom确实对其输出进行哈希处理。 - Martin v. Löwis
1
考虑到对SHA-1(和MD5)已经取得的进展,我会开始寻找其他哈希算法。新设计中不应使用MD5或SHA-1。 - derobert
显示剩余8条评论

4

这绝对不是一个普通的冲突场景:

  • 每个字符有62个选项,32个字符相当于190位(log2(62) * 32)
  • 根据生日悖论,您应该每2 ** 95个cookie自然地收到一次冲突,这意味着永远不会发生

这可能是并发问题吗?

  • 如果是这样,请为每个线程使用不同的random.Random实例
  • 可以将这些实例保存在线程本地存储中(threading.local()
  • 在Linux上,Python应使用os.urandom()进行种子处理,而不是使用系统时间,因此您应该为每个线程获取不同的流。

1
他说的是多个FCGI进程,而不是线程。马丁,这样说对吗?还是你的意思是线程? - Glenn Maynard

1
  1. 我不知道你的FCGI进程是如何生成的,但是否有可能在Python解释器启动后(并且随机模块已被某些东西导入)使用fork(),从而有效地从同一源种子化两个进程的random._inst

  2. 也许可以添加一些调试来检查它是否正确地从urandom进行了种子化,而没有回退到不太严格的基于时间的种子?

关于评论的估计:天哪!那就让我困惑了;如果RNG在启动时总是具有不同的状态,我看不出你怎么可能会发生碰撞。奇怪。我猜需要放入大量状态日志来调查导致碰撞的特定情况,这听起来像是通过日志进行大量工作的挖掘。可能是(1a)FCGI服务器通常不分叉,但偶尔会分叉(也许是在负载下或其他什么情况下)?

还是(3)一些更高级别的问题,例如损坏的HTTP代理将相同的Set-Cookie传递给多个客户端?


感谢您的建议:
  1. 我已经在启动时转储了RNG的状态,并且它们都是不同的。
  2. 我让它创建了好的文件(使用urandom)和坏的文件(使用时间);“好”的文件已经被创建了;而坏的文件则没有。
- Martin v. Löwis

0

我不得不删除我的原始答案,因为它暗示生成器不是从/dev/urandom中种子化的,因为它的源代码(适用于Python 3.x)明确表示它是:

def seed(self, a=None):
    """Initialize internal state from hashable object.

    None or no argument seeds from current time or from an operating
    system specific randomness source if available.

    If a is not None or an int or long, hash(a) is used instead.
    """

    if a is None:
        try:
            a = int(_hexlify(_urandom(16)), 16)
        except NotImplementedError:
            import time
            a = int(time.time() * 256) # use fractional seconds

    super().seed(a)
    self.gauss_next = None

因此,我谦卑地接受这个世界上可能有些谜团我无法解开。


1
你在哪里看到它从一些哈希()中生成的?在random.py中,大约在第108行,它从long(_hexlify(_urandom(16)), 16)中生成。 - Martin v. Löwis
1
如果你真的在深入研究这个问题,也许下一步就是检查代码中 a = int(_hexlify(_urandom(16)), 16) 这一行是否因为某种奇怪的原因而导致 NotImplementedError 错误? - ilya n.
1
谢谢你的想法。不幸的是,我已经尝试过了,一切都按照预期工作(即从urandom中获取种子)。 - Martin v. Löwis

-4
为避免这个问题,您可以使用一系列cookie,这些cookie保证是不同的(例如,您可以使用一个集合)。 每次将cookie分配给某人时,从序列中取出一个cookie并将其添加到其中。 另一种选择是生成UUID并将其用作cookie。
另一种避免该问题的方法是持有私钥,并使用与计数器值连接的(例如MD5)私钥校验和。 碰撞的概率将非常低。 为了更安全,可以将几个变量添加到校验和中,例如当前时间,用户的IP地址等。
生成cookie的库已经存在。 任何WSGI实现可能都包含cookie生成器。
如果您只对字符串的随机性感兴趣,则可以生成一个文件,例如,生成一百万个cookie并对该文件执行随机性检查。 但是,这不是我推荐的方法。

这并不是我的问题 - 我不想要一个变通方法,我想要理解发生了什么。我的变通方法是使用os.urandom。至于使用序列 - 那是不好的,因为cookie可以被猜测。使用uuids:如果UUID生成器使用随机模块,则可能不是唯一的。 - Martin v. Löwis
UUID不能保证唯一性。理论上,因为只有2 ** 128个,实际上,可能是由于生成它们的代码存在缺陷 - 特别是如果它非常类似于我发布的代码,应该也会生成唯一值,但实际上并没有。 - Martin v. Löwis
最好使用别人的“有缺陷”的代码,因为它可能在未来变得更好,而不是尝试自己的东西,你不知道它实际上做了什么。 - pvoosten
1
仅使用2 ** 128个UUID,您可以为地球上每一粒沙子分配唯一的UUID。因此,我猜最多对于一千个用户,您不会因UUID而遇到麻烦。 - pvoosten
最好使用你不理解的有缺陷的东西,因为它可能会变得更好?没错... - Glenn Maynard

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接