System.Guid.NewGuid()有多随机？（第二部分）

Question

在你将这篇文章标记为重复之前，请先听我说完。其他的问题可能有一个（很可能）不正确的答案。

我不知道.NET如何生成它的GUID，可能只有微软知道，但是很有可能它只是调用了CoCreateGuid()。然而，该函数被文档记录为调用UuidCreate()。创建UUID的算法已经相当好地记录。

长话短说，尽管如此，看起来System.Guid.NewGuid()确实使用版本4 UUID生成算法，因为它生成的所有GUID都符合标准（自己看看，我试过几百万个GUID，它们都匹配）。

换句话说，这些GUID基本上是随机的，除了一些已知的比特位。

这又引出了一个问题 - 这个随机究竟有多随机？就像每个好的程序员知道的那样，伪随机数算法只有其种子（熵）一般随机。那么UuidCreate()的种子是什么？PRNG重新播种的频率是多少？它具有密码学强度吗，还是如果两台计算机不小心同时调用System.Guid.NewGuid()，它们会产生相同的GUID？如果收集了足够多的连续生成的GUID，是否可以猜测PRNG的状态？

添加：为了澄清，我想了解它有多随机，因此 - 我在哪里可以使用它。所以，让我们在这里建立一个粗略的“随机性”尺度：

1. 基础随机性，以当前时间为种子。可用于在纸牌游戏中洗牌，但由于即使不进行尝试也很容易出现碰撞，因此在其他方面使用效果不佳。
2. 更高级的随机性，除了时间外，还使用其他机器特定因素作为种子。可能仅在系统启动时进行一次设定。这可用于在数据库中生成ID，因为重复概率较小。但从安全性角度来看并不好，因为结果可以在付出足够努力后被预测。
3. 密码学随机性，使用设备噪声或其他高级随机源作为种子。每次调用时重新进行设定，或者至少经常重新设定。可用于向不受信任的参与者分发的会话ID等。

我思考是否可以将它们用作DB ID，并且Guid.comb算法实现是否与System.Guid.NewGuid()（如NHibernate所做的）存在缺陷。

- Vilx-

---

请问您的目标是产生伪随机值(a)，还是生成大量GUID并了解碰撞的概率(b)？请说明。 - Greg Hewgill

如果随机性对您很重要，那么我相信您最好使用专门为随机性设计的东西，而不是使用GUID。 - Dirk Vollmar

可能是 https://dev59.com/IXRB5IYBdhLWcg3w6bcE 的重复问题。 - George Stocker

@George。哇！看起来你读得非常仔细，特别是第一句话... - Vilx-

无论被接受的答案是否正确，问题仍然是相同的。是的，我确实阅读了两个问题。 - George Stocker

在底层，Guid.NewGuid() 调用了 Win32Native.CoCreateGuid。 - Steven

Answer 1

答案是：你不应该需要知道这个。正如在相关问题的被接受的答案中所述：

GUID并不能保证随机性，它保证唯一性。

在RFC4122中，关于安全和随机性提出了更强的声明，其中规定了UUID格式：

不要认为UUID难以猜测；不能将其用作安全能力（仅凭持有即可获得访问权限的标识符），例如。一个可预测的随机数源会加剧情况。

其他所有内容都是实现细节（可能会改变）。 Windows 特定内容 通常，人们声称在Windows上的行为已经记录下来，并且因此可以保证GUID是具有密码学安全性的。现在存档的[MS-SECO] Windows Security Overview文档在附录A中提到：

虽然只有少数版本4 GUID需要密码学随机性，但在Windows中构建所有版本4 GUID的随机位都是通过Windows CryptGenRandom加密API或等效API获得的，这是用于生成加密密钥的相同源。

此外，同一文档的2.5.5节明确提到了使用“秘密GUID”值作为nonce或认证器。

但是：这个产品行为文档并不是你可以通常基于的规范（特别是在.NET上下文中）。

实际上，上述文档描述的是一个特定产品的实现细节。即使当前的Windows和.NET Framework 4.x实现在Windows上生成真正随机的版本4 UUID值，也不能保证System.Guid.NewGuid在未来或其他.NET平台（例如Mono、Silverlight、CF、.NET Core等）上会这样做。

举个例子，早期版本的.NET Core使用的UUID算法取决于平台，你可能会在BSD上获得一个版本1 UUID。

- Dirk Vollmar

---

你提到RFC文档但错过了第4.4和4.5节有趣的地方。这里指出V4 UUID（Windows 2000及以后版本使用）基于真随机或伪随机数。 - Pauli Østerø

@Pauli - RFC只是说你可以从随机源生成UUID，而不是所有V4 UUID都是真正随机的。如果用于生成V4 UUID的源是伪随机的且可预测的，则仍然存在问题，即随机V4 UUID可能不难猜测。 - bacar

如果没有关于UUID序列随机分布的要求，如何对完全独立实体生成的UUID序列不包含一些共享成员的概率做出任何有意义的陈述？确保在现实情况下避免碰撞可能不需要每个GUID的120多位熵，但是需要一些。 - supercat

@bacar：所谓“成员”，是指任何有助于UUID的数据。问题在于，如果两个独立实体都决定UUID应该由一些固定的位组合以及例如32位真随机数组成，那么如果该制造商的设备从未发出超过几百或几千个UUID，则任何设备的UUID与来自同一制造商的任何其他UUID相撞的概率将很小，但如果多个制造商恰好使用相同的公式，则碰撞的概率可能会变得更糟。 - supercat

@SilverlightFox：实际上恰恰相反。文档并不保证生成值的随机性，因此我们不能声称它产生了“真正随机”的输出。即使输出符合某些明确定义的随机性标准，这也是一种未经文档/RFC支持的实现细节。 - Dirk Vollmar

Answer 2

有些人已经提到了这一点，但我想重复一下，因为似乎存在误解：

随机性和唯一性是两个不同的概念。

随机数据可以是唯一的或冗余的，同样，唯一数据可以使用随机源或确定性源（比如一个全局计数器，每次为创建的GUID锁定并递增）。

GUID被设计用来保证唯一性，而非随机性。如果.NET生成器似乎使用随机输入，那么好吧。但是请不要依赖它作为随机性的来源，无论是用于加密还是其他任何目的（特别是，您期望得到什么分布函数？）。另一方面，您可以相当确定由.NET创建的GUID，即使是大量的，也将是唯一的。

- Konrad Rudolph

---

抱歉，我不同意。如果世界上独立的机器创建GUID，则可以实现最小的碰撞机会，方法是每个机器创建真正随机的GUID（它们足够大，使得碰撞机会变得极小）- 任何偏离完全随机性的行为都将降低熵并增加两台机器在完全相同的起始条件下产生相同GUID的机会。 - Falco

@Falco，只有当UUID的机器特定部分发生碰撞的概率高于相同位长度的真正随机数据的熵时，才是正确的。这是一个重要的警告。实际上，你可能是对的，据我所知，大多数UUID实现都使用纯随机数据（版本4）的规范。但就UUID而言，这是一个实现细节。这就是我的答案所指出的。 - Konrad Rudolph

@KonradRudolph和我都无法想出一种机器依赖的参数，即使在同一系统以及不同系统上大规模创建ID，也比真正的随机性提供更少的冲突。这似乎是不可能的。 - Falco

@Falco ISBN（书籍的国际标准书号）就是其中一个例子（实际上有重复的ISBN，因为制造商很蠢，但可以通过添加附加注释使其唯一，总长度不到GUID的长度）。其他例子包括地址：虚拟地址（IP、URI）和物理地址（邮政地址）。 - Konrad Rudolph

@KonradRudolph，所有这些都需要一个中央注册表，或者在不同系统之间同步信息，或者依赖于高度有限的参数（邮政位置）。任何数量的系统（包括虚拟机的相同副本）都应该能够在全球范围内生成任意数量的GUID而不发生冲突。你举的例子都无法提供这种功能。- 这意味着我应该能够在同一位置的两个相同但未连接的服务器上创建一百万个GUID。 - Falco

Answer 3

生成随机字节的API如果没有明确说明其能够产生加密强度的随机字节，则不能信任其产生加密强度的随机字节。

如果您需要加密强度的随机字节，则应使用明确说明可以生成这些字节的API。

public Guid CreateCryptographicallyStrongGuid() {
    var rng = new System.Security.Cryptography.RNGCryptoServiceProvider();
    var data = new byte[16];
    rng.GetBytes(data);
    return new Guid(data);
}

这些GUID只是128位的加密随机数，它们没有结构，也不会发生碰撞。

参见本文了解一些数学知识。使用“通用生日公式”，重新排列得到

n = sqrt（-2T * ln（p））

其中n是所选元素的数量，T是总元素数（2^128），p是所有n个所选元素都不同的目标概率。对于p = .99，这给出*n = 2.61532104 * 10 ^ 18*。这意味着我们可以在系统内每秒生成十亿个真正随机的GUID，在十亿秒（32年）内，最终有超过99％的机会使每个GUID在系统内唯一。

- yfeldblum

---

这可能会生成伪随机值，但您失去了生成唯一 GUID 的保证（尽管如果您只生成少量值，则碰撞的可能性很低）。 - Dirk Vollmar

这段代码是否能生成有效的GUID？我看不出你在哪里设置指示GUID类型的位。 - user9876

根据RFC4122（http://tools.ietf.org/html/rfc4122），即使是UUID版本4也应设置版本位和其他2个保留位。 - Dirk Vollmar

小题大做：如果你只想要16个随机字节，或许把它们留作byte[16]会更有价值，而不是把它们放进一个 Guid中。把它称作Guid可能会让理解标准的人产生困惑。 - bacar

@Vilx：将保留位设置不正确是完全错误的。 - Eric Lippert

Answer 4

“随机”的定义与“全局唯一”的定义没有任何关系。

抛两次硬币得到HH、HT、TH、TT都是随机的。HH和HT同样随机。

抛一枚“特殊”的硬币两次，保证只会得到HT或TH，这就是唯一性。

- Robin Day

Answer 5

根据https://msdn.microsoft.com/en-us/library/bb417a2c-7a58-404f-84dd-6b494ecf0d13#id11，自从1999年的Windows 2000起，所有版本4 GUID中的随机比特都是通过Windows CryptGenRandom加密API或等效API获得的，这与生成加密密钥所使用的源相同。因此，我认为它们在密码学上是安全的，至少提供了122位熵。

另请参见https://dev59.com/RFsW5IYBdhLWcg3wHUOb#35384818，Will Dean通过调试步骤验证了CLR正在调用适当的安全操作系统随机生成器。

- Jordan Rieger

---

阅读这篇文章非常有趣。我的担忧是您无法保证实现方式始终如此，并且在框架的不同平台和版本中也不能保持一致。最好坚持使用显式CSPRNG。 - James Westgate

@JamesWestgate 但是我们能保证实现不会改变吗？假设在2030年，.NET 9.5（或其他版本）发布了，它的GUID生成（或Windows的）变得不安全 - 在这种情况下，他们肯定会更新文档以反映新的行为。你永远无法真正保证库/API的未来版本的任何事情，但微软已经将GUID生成的加密安全保持了近20年，这应该是GUID始终如此的强有力的证明。 - Jordan Rieger

Answer 6

它们是随机的，因此可以数学证明很长时间内不应该发生冲突，因此您可以假设它们在全球范围内是唯一的。但是，它们不是密码学强度，因为这需要真正的随机性，在没有专用硬件的计算机上实现并不容易。

- Lucero

---

真的，但我认为设备噪声是一个相当好的熵源。 - Vilx-

嗯......存在着具有加密强度的随机数生成器。它们可以完全通过软件实现。（虽然硬件支持可以使编写和证明安全性变得更容易）。在Windows PC上，CryptGenRandom()是常用的一个。 - user9876

尽管直到Windows Vista之前，它存在已知问题，并且该算法未公开，只是考虑了一个非常长的特定信息列表，以使其尽可能随机，但这并不意味着在虚拟实验室环境中无法进行重放攻击（这并不意味着在实际使用中不安全）。http://en.wikipedia.org/wiki/CryptGenRandom - Lucero

如果数学上可以证明碰撞不应该发生，那么根据定义它根本就不是随机的！这就好比说只有当所有数字都出现一次后才能算轮盘才是随机的。 - Robin Day

Answer 7

GUID被设计为在您的规模上排名第2，即“可以用于在数据库中生成ID，因为重复不太可能发生”。

至于安全性，问题不是“它对安全性不好，因为结果可以通过足够的努力预测”。问题是没有人给您提供文档化的安全保证。

实际上，根据这个评论和这个评论，GUID生成已经采用了基于密码学安全的RNG（CryptGenRandom）。但这似乎是一个未经记录的实现细节。（我还没有验证过这一点-这是互联网上的随机评论，请谨慎对待）。

（*其中“unlikely”意味着“在宇宙末日之前，任何人找到重复的GUID的机会都比你个人赢得彩票的机会要小。”当然，除了实现错误。）

- user9876

---

实际上，根据这个评论和这个评论，GUID生成是基于加密安全的随机数生成器实现的，这完全不可能。这混淆了唯一性（防止意外重复）和随机性（防止预测）。找到重复的GUID和寻找重复的GUID之间存在区别。 - Mark Sowul

Answer 8

关于您的问题“使用GUID作为行标识符”的重点：

GUID适用于面向复制的数据库，或在将它们添加到数据库之前提前生成行。如果您不需要GUID来解决特定问题，请尝试坚持增量编号。 GUID会使调试和测试有点复杂。

您提到的文章中的COMB方法似乎非常棒。我从未意识到，谢谢！（附注：该文章的打印友好版本读起来更好）

因此，如果您不需要提前生成GUID，则可以让数据库为您处理GUID生成。只有当您开始一次性添加成千上万条记录时，您才会注意到速度差异，但您不应该这样做，这就是批量导入的用途。

还请参阅Jeff on ID's vs GUID's。

create table #temp ([id] uniqueidentifier primary key default(newid()), [name] varchar(20))
insert into #temp (name) values ('apple')
insert into #temp (name) values ('orange')
insert into #temp (name) values ('banana')
select * from #temp
drop table #temp

id                                   name
------------------------------------ --------------------
911B0CBD-4EED-4EB0-8488-1B2CDD915C02 banana
56CF3A80-A2DE-4949-9C9B-5F890824EA9C orange
5990B9FD-143D-41B0-89D1-957B2C57AB94 apple

- invert

---

在我的情况下，需要使用GUID的原因比较复杂。首先，我正在使用NHIbernate ORM，其次，我想在我的应用程序中创建对象，然后让用户决定是否保存它们（例如，用户按下“确定”或“取消”）。如果我使用IDENTITY，NHibernate将需要立即插入记录以获取ID（这正是我不想要的）。GUID允许我创建ID而不触及数据库，并且COMB可以解决性能问题。但是，如果由于实现细节而生成重复的GUID，则可能会失败，这些细节原作者并不知道。 - Vilx-

Answer 9

我在某处读到，赢得彩票的机会相当于2个4字节“GUID”发生冲突。标准的16字节GUID则提供了更少的冲突机会。

- cjk