UUID碰撞

Question

有没有人真正研究过UUID碰撞的概率，特别是与版本4(随机)UUID，因为我们使用的随机数生成器并不是真正的随机，而且我们可能有数十或数百台相同的机器运行相同的代码来生成UUID？

我的同事认为对UUID冲突的测试完全是浪费时间，但是我总是输入代码从数据库捕获一个重复的关键异常，然后用一个新的UUID再试一次。但是，如果UUID来自另一个进程并引用一个真实的对象，那么这并不能解决问题。

Answer 1

维基百科有一些细节：

http://en.wikipedia.org/wiki/Universally_独一无二_标识符

http://en.wikipedia.org/wiki/Universally_独一无二_identifier#Random_UUID_概率_的_复本

但是，只有在比特是完全随机的情况下，概率才成立。但是，在另一个答案中链接的RFC https://www.rfc-editor.org/rfc/rfc4122#page-14为版本4定义了以下内容：

"4.4. ...版本4 UUID用于从真正随机或伪随机数生成UUID。...将所有其他位设置为随机(或伪随机)选择的值。“

这几乎允许任何东西，从xkcd随机生成器http://xkcd.com/221/到使用量子噪声的硬件设备。RFC中的安全考虑因素：

"6.在各种主机上生成UUID的分布式应用程序必须愿意依赖所有主机上的随机数源。如果这不可行，则应该使用命名空间变量。

我读到这句话:你得靠自己了。您在自己的应用程序中负责随机生成器，但是这和其他任何事情都是基于信任的。如果你不相信你自己有能力正确理解和使用你选择的随机生成器，那么检查碰撞确实是个好主意。如果您不信任其他进程的程序员，那么检查冲突或使用不同的UUID版本。

Answer 2

当然，您应该检测是否发生了冲突，如果发生了冲突，应用程序应该抛出异常。例如，如果UUID被用作数据库中的主键，那么数据库在插入冲突ID时会抛出一个错误。

但是，我相信在发生碰撞时编写代码来生成新的UUID，并再次尝试是浪费时间。发生碰撞的可能性很小，因此抛出一个例外将是一种完全合理的处理方法。

请记住，这不仅浪费了您自己编写代码的时间，而且还使代码更加复杂，使下一个人更难阅读，几乎没有任何收获。

Answer 3

这是一个很好的问题。我认为在到处使用UUID的过程中，还没有充分考虑到这一点。我还没找到任何可靠的研究。

建议:在这里非常小心地处理，并且非常了解你的密码学。如果使用128位UUID，“生日效应”告诉我们，如果每个键中都有128位熵，那么在生成大约2^64个键后，可能会发生碰撞。

要确保情况确实如此，其实是相当困难的。真正的随机性可由(a)放射性衰变(b)随机背景无线电噪声产生，除非你小心地(c)适当选择电子噪声，例如从反向偏置齐纳二极管中提取，否则经常受到污染。(我玩过最后一个，它的作用就像一个魅力，BTW)。

我不会相信像“我在一年的使用中没有见过这个”这样的声明，除非用户已经生成了接近2^64的东西(即。大约10^19)键，并相互核对，这是一个很重要的练习。

问题是这个。假设你只有100位熵，当你把你的键和其他人在一个公共密钥空间中生成的其他键进行比较的时候。你将在大约2^50秒内开始看到碰撞。大约10^15把钥匙。如果您仅用1000亿个密钥填充了数据库，则您看到碰撞的可能性仍然可以忽略不计。如果您不检查，那么稍后您将得到意外的错误，这些错误会蔓延到peta行大小的数据库中。这会咬得很厉害。

生成这类UUID的方法有多种，这一事实应该引起人们的关注。当您意识到很少的生成器使用具有足够熵的“真正随机”过程来处理4UUID时，除非您仔细检查了生成器的熵内容，否则您应该过度关注。(大多数人都不会这么做，甚至不知道如何做；您可以从DieHarder套件开始)。不要混淆伪随机数生成和真实随机数生成。

关键是你要意识到你所投入的熵就是你所拥有的熵，简单地通过应用密码函数来扰乱密钥并不会改变熵。如果我的整个空间包含数字0和1，那么熵内容与下面两个字符串的熵内容是相同的，只要它们是唯一的两个选项：“这是一个非常复杂的字符串293290729382832*!@@#&^%$$)，.m}”和“现在是完全不同的东西”。还有两种选择。

随机性是很难纠正的，仅仅相信“专家已经看过它，所以它是可以的”可能是不够的。专家密码专家(而且很少有人真正精通)是第一个承认他们经常弄错的人。我们信任心脏出血，DigiNotar等。

我认为保罗·汤布林是在谨慎行事。我的2c。