破解Phobos UUID

与其他语言相反，D'；对UUID的当前标准实现不是加密安全的，不应用于生成密钥。这得到了RFC的支持，RFC不鼓励人们使用UUID来获取机密。

当然，很多人、项目和框架都使用它们来生成诸如会话cookie、密码重置令牌等内容，因为它看起来应该可以工作，而且几乎可以在任何其他语言中使用。

合理地说，人们会问，好吧，理论上这是不好的，但在实践中有多难。我在本文中展示了在收集了156个UUID之后，可以猜测出最多8 192个请求将生成的下一个UUID：与最初的2²²⁸可能性相比，这确实是一个非常实用的攻击。

这应该被视为行动的号召：Phobos必须提供SecureRandom数字生成器。它是一个太基本和重要的组件，不能以标准的方式提供它。

如果您的项目使用随机UUID()，请确保它的值不是假定为机密的。否则，更改从密码安全随机性构建的令牌。

前段时间，我与一家图书馆的维护人员进行了一次愉快的交谈，讨论了随机数生成及其与安全性的关系。它提醒了我，这个主题并不明显，我决定看看D的现状，因为那已经成为我最近几年开源搜索的主题了。

特别值得一提的是，我知道D'；的标准库Phobos目前没有提出任何标准方法来获得加密安全的随机数。没有太多的项目使用默认且不安全的Uniform()来生成诸如会话令牌之类的记录。不过，我决定看看UUID，因为它们通常是出于安全目的。果然，许多我不会列出的项目使用了不安全的UUID。

问题是，虽然他们不应该这样做，但我不能因为他们认为这是正确的而责怪他们。在大多数语言中，UUID是从安全随机性中生成的，并且是生成安全秘密的一种合理方式。但D并非如此，这意味着这些项目很容易受到攻击。

在这篇文章中，我们将了解如何从以前的UUID中预测未来的UUID。这当然是件小事，但也不是那么难。这里是我们的路线图：

这将是一个相当长的技术性帖子，但无论如何，它肯定会很有趣！

在进一步讨论之前，我们需要弄清楚我们所说的密码安全随机性是什么意思，以及它与规则随机性有何不同。

正态随机性通常只由一个假设来定义：没有或低偏差。这意味着，如果您要生成大量数字，则您看到的每个特定输出的次数应该是均匀匹配的。这一特性足以满足大多数应用，从随机狗名生成器到蒙特卡罗模拟。

(正确的定义比这个稍强一些，但这在我们的文章上下文中就足够了。)。

如果有偏差，那么我有关于生成哪些数字的信息，而不必收集一个数字。我认为我不需要解释预测未来数字对于生成会话令牌等秘密的系统来说是一个问题。最后一项可能会令人惊讶，但请考虑一下这一点：如果可以从当前的输出中恢复过去的输出，并且您使用随机数字作为密码重置令牌(例如)，那么我可以要求重置另一个用户的密码，然后请求重置我的密码，并确定前一个条目是什么，从而泄露该用户的密码重置令牌。

如果密码安全的伪随机数生成器(CSPRNG)更安全，为什么它们不能用于所有的东西呢？因为强制执行这些条件也会使它们比传统的PRNG慢得多，而且许多应用程序不需要这些保证。

MT19937不是一个密码安全的伪随机数生成器，不能作为一个生成器使用。这不是选择正确的种子或经常重新播种的问题(实际上，经常重新播种对我们是有好处的，正如我们最后会看到的那样)。它有一些偏见(诚然不是很多)，但最重要的是，它既有可能预测未来，也有可能从几个输出中恢复过去。

通用唯一标识符(UUID)是RFC 4122中定义的一类标识符。顾名思义，他们的目标是提供一种生成ID的方法，即使在不能在一起通信的系统中，这些ID也保证是不同的。你可能见过它们，它们看起来是这样的：0d3120f8-f209-43f2-949d-e70dcf228403。

有不同类型的UUID，但最常见的是类型4：随机UUID。这些在RFC的第4.4节中描述如下：

位12至15必须设置为UUID版本号：在本例中为4(0100)。

在实践中，图书馆通常选择4个32位随机数，将它们连接起来，然后将第6位、第7位和第12位改为15位。这意味着关于这些随机数的一些信息在这个过程中会丢失，我们得不到干净的PRNG输出。

请注意，RFC不要求使用加密安全的随机数，但如果使用正常随机性，它会警告不要对敏感值使用UUID。

UUID随机UUID(RNG)(参考RNG随机生成)IF(isInputRange！RNG&；&；is Integral！(ElementType！Rng)){import std.Random：isUniformRNG；static assert(isUniformRNG！RNG，"；随机生成必须是统一的RNG"；)；别名E=ElementEncodingType！Rng；枚举size_t elemSize=E。Sizeof；静态断言(elemSize<；=16)；静态断言(16%elemSize==0)；uuid u；foreach(ref E e；u.。As ArrayOf！E()){e=随机生成。前面；随机生成。PopFront()；}//设置变量//必须是0b10xxxxxx u。DATA[8]&；=0b10111111；u.。DATA[8]|=0b10000000；//设置版本//必须是0b0100xxxx u。DATA[6]&；=0b01001111；u。DATA[6]|=0b01000000；返回u；}。

它使用std.Random：MT19937的默认随机数生成器生成4个32位uint值。如果PRNG状态太小，它将退回到XorShit192(这里的代码)。

因此，MT19937广为人知，使用频繁，而且不安全。过去肯定有人写过破解它的文章吧？

的确，有很多文章，但最有趣的肯定是这篇由Ambionics撰写的文章，它做了一些不同的事情。

我们在这些文章中看到的基本策略是通过收集624个值来恢复Mersenne Twister的内部624字节状态。从那里可以预测任何未来的价值。当然，对于我们更大的项目来说，这不是立即的选择，因为由于UUID的构建方式，UUID中缺少了一些内容，但它是一个重要的基石。

仿生学策略也非常有趣：它们表明，由于每个输出值仅取决于两个状态值，因此只需两个输出即可恢复先前的值。从那里，他们通过颠倒其过程来重建完整的种子。好东西。我们不会使用它，但绝对值得一读。

最后，所有的Mersenne Twister都有点不同，所以我们需要为Phobos量身定做方法，但我们将使用两个值来预测下一个。

MT19337'；的内部状态是由624个32位整数组成的数组。该数组是在初始化时设定种子的，但我们在本文中不会讨论种子设定。出于所有意图和目的，我们从一个由624个随机整数组成的数组开始。

一旦播种，就有两种机制在发挥作用。一个在将其置乱后输出一个数字(在图中为蓝色)，而另一个通过组合状态数组的三个元素来更新下一个条目：索引、下一个和共轭(命名困难)。此过程在图中显示为橙色。

提供的实际值大多特定于Phobos'；实现，但让我们注意一下最重要的值：

有一件事在这个图表中并不明显，那就是NEXT和INDEX是如何组合在一起产生y的。y由索引的最高有效位和NEXT中除最高有效位之外的所有位组成。

每次输出一个新数字时，这两个过程都会向左前进一步，以相反的顺序遍历状态数组。在n次迭代之后，它循环回到数组的末尾。

您可以在此处阅读Phobos的实现，但请注意，为了提高缓存性能，蓝色和橙色进程都是交织的。

MT19937完全由其内部状态定义。如果我们可以识别它的所有624个组件，那么我们只需用这些值设置我们自己的MT19937 PRNG的状态，它就会输出相同的数字。现在，给定一个输出，如果我们能够反转加扰(蓝色过程)，那么我们直接获得相应的状态值。如果我们能够做一次，我们就可以连续输出624次，并且有一个完整的内部状态。关键部分在于，在该场景中，我们永远不需要担心更新(橙色)过程。

Uint置乱(Uint Z){不可变b=0x9d2c5680；不可变c=0xefc60000；z^=z>；>；11；z^=(z<；<；7)&；b；z^=(z<；<；15)&；c；z^=(z>；>；18)；返回z；}。

向左和向右滑动东西..。让我们以相反的方式滑动(考虑到重叠部分)。

Uint解扰(Uint Z){不变b=0x9d2c5680；不变c=0xefc60000；z^=(z>；>；18)；z^=(z<；<；15)&；c；z=undoLShitXorMask(z，7，b)；//扭曲z^=z>；>；11；z^=z>；&。}uint undoLshitXorMask(uint v，uint Shift，uint掩码){uint bitts(uint v，uint start，uint size){return(v&>；&>start)&；((1<；<；size)-1)；}foreach(i；iota(Shift，32，Shift))v^=(Bits(v，i-Shift，Shift)&；Bits(MASK，I，SHIFT))<。<；i；return v；}unittest{uint z=0x12345678；assert(z==解扰(scurble(Z)；}。

就这样，第一个障碍已经过去了。很简单。要预测所有未来的数字，我们只需收集624个连续的数字，对它们进行解读，然后用它们来播种我们自己的MersenneTwisterEngine。但这不是我们的目标，所以让我们继续前进。

这是朝着我们的目标迈出的中间一步。我们看到，如果我们获得624个连续输出，我们就有能力破解MT19937，但是当我们获得UUID时，我们就不会有那样的奢侈了。请记住，每个UUID由4个输出(128位)组成，其中6位缺失。如果我们试图强制每4个输出丢失这6位，我们将不得不强制936位，这远远超出了可能的范围。

但是，请记住，更新值仅使用3个基值，因此如果我们知道正确的3个状态值，则可以预测下一个状态。

这一部分实际上并不难，因为我们只需要遵循算法通常做的事情。我们只需要解开/重新加密我们的原始产值。

Uint forectNumber(uint index，uint next，uint conj){不可变n=624；不可变m=397；不可变a=0x9908b0df；uint lowerMask=(cast(Uint)1u<；<；31)-1；//除msb uint upperMask=(~lowerMask)&；uint之外的所有位。最大；//最高有效位uint q=解扰(Index)&；upperMask；uint p=解扰(下一个)&；lowerMask；uint y=q|p；auto x=y>；>；1；if(y&；1)x^=a；x^=解扰(Conj)；返回加扰(X)；}unittest{import std.Random；auto prng=Mt19937(不可预测。Uint[]rawOutput=prng。取(n*2)。数组；uint index=4；uint target=index+n；auto prediction=predictNumber(rawOutput[index]，//index rawOutput[index+1]，//next rawOutput[index+397])；//共轭Assert(rawOutput[target]==预测)；}。

好的，所以我们只能读取3个值，这样我们就可以预测下一个值，624个输出。现在，让我们转到挑战的核心：当我们由于UUID的格式化方式而开始删除位时，我们还能有效地做到这一点吗？

当然，UUID的主要问题来自于某些信息丢失的事实。我们无能为力地召唤这些缺失的部分，但如果缺失的足够少，我们可以列举出所有的可能性。这将为我们提供一个候选UUID列表，以尝试攻击易受攻击的系统。

每个UUID由4个整数组成，因此我们需要分别处理这4个部分。它们呈现不同的情况，所以让我们给每个UUID部分起自己的名字。

现在让我们假设我们有一个UUID。INDEX是一个P0，我们想要预测该索引处的下一个值(624个输出中也是如此)。我们的下一个自然是P1，我们的共轭比索引多397位。因为397%4=1，我们的共轭也是P1。因为在每个P1中缺少4位，所以总共有8个未知位来预测未来整数。

在下一个和共轭中都缺少2个比特。由于我们不知道前一部分的正确值，我们也不知道它最重要的部分，所以我们需要强制它。应该可以为每个先前计算过的候选人找到它，但是我们没有在这上面花费任何时间。

幸运的是，即使两位在P2中被覆盖，其最高有效位保持不变，因此我们有计算其未来值所需的一切。这里一点都不缺。

最后，我们的总数是13个丢失的位，我们必须在4个整数内强制执行这些位。一旦我们确定了哪些位需要强制执行，这就是一项简单的任务。这将提供8192名候选人的名单。

调试提示：我实际上有点被这里的字符顺序搞糊涂了，有一段时间我找不到我丢失的部分在哪里。在这种情况下，请记住，即使某些位被覆盖，您仍然可以确保它们没有更改，并且UUID仍然有效：冲突。这意味着，通过在调整值时运行统计测试，您可以根据冲突发生的次数来测量您有多少位。事实证明，这在这种情况下非常非常有用。当然，将数据可视化为位也是一个好主意。

最后，这里是允许我们从UUID输出列表预测UUID的代码。

自动预测Uuid(uuid[]uuidLst，size_t uuidIndex){uint[]data=uuidLst。地图！UuidToUints。Join；size_t index=uuidIndex*8；uint[]part0；foreach(mask1；0..16){uint c=data[index+397]；c&；=~(15<；<；32-12)；c|=mask1<；<；32-12；foreach(mask2；0..16){uint n=data[index+1]；n&；=~(15<；&。32-12)；n|=mask2<；<；32-12；part0~=forectNumber(data[index]，n，c)；}}uint[]part1；foreach(mask1；0..4){uint n=data[index+1+1]；n&；=~(3<；<；6)；n|=mask1<；<；6；foreach(mask2；0..4){uint c=data[index+1+397]；c&；=~(3<；<；6)；c|=mask2<；<；6；uint i=data[index+1]；part1~=recrectNumber(i，n，c)；i^=1<；<；31；part1~=recrectNumber(i，n，c)；}}uint part2=forectNumber(data[index+2]，data[index+2+1]，data[index+2+397])；uint part3=recrectNumber(data[index+3]，data[index+3+1]，data[index+3+397])；uuid[]Candients；foreach(p0；part0){foreach(p1；part1){ubyte[16]Candidate；Candidate[0.。4]=nativeToLittleEndian(P0)；候选[4.。8]=nativeToLittleEndian(P1)；候选[8.。12]=nativeToLittleEndian(第2部分)；候选[12.。16]=nativeToLittleEndian(Part3)；Candidate[8]&；=0b10111111；Candidate[8]|=0b10000000；Candidate[6]&；=0b01001111；Candidate[6]|=0b01000000；Candidate~=uuid(Candidate)；}}返回候选人；}。

我考虑过在一个真实的项目上展示这一点，找到一个足够容易的，但这对那个项目是有害的。我不希望引起人们对任何特定项目的注意，也不希望引起恶意行为者的注意。然而，我确实在实践中测试了该攻击，如下所示：

登录/注销156次，以构建连续的UUID列表(如果网站繁忙但实际上在高峰时段之外，则很难实现连续性)。

您现在可以构建一个包含8192个候选UUID的列表，并且知道生成的nextsession令牌将是该列表的一部分

试试看所有的候选人，其中一个会奏效。8000个请求可以在几秒钟内完成，所以这绝对是一个实际的攻击。

类似的策略可以应用于符号链接攻击中的文件名、密码设置令牌(这是最好的策略，因为您可以要求重置另一个帐户，无需等待)，以及被认为不可猜测的API端点等。

必须使用密码随机性生成秘密。在Windows上，这意味着CryptGenRandom；在Linux上，意味着getRandom()或/dev/urandom；在Unix/dev/Random上，意味着CryptGenRandom。有一些库可以正确地实现跨平台包装，比如libNa(有关D绑定，请参阅Na)。

作为一个项目经理，你应该考虑引入这样的依赖关系，因为没有什么可以替代好的CSPRNG，而且没有任何CSPRNG可以在不依赖系统的情况下被正确播种。

然而，解决这个特殊问题的最好方法是让Phobos直接向系统CSPRNG提供此接口。人们选择阻力最小的道路，这是我们必须面对的事实。目前，人们很难使用安全的随机性，而不是直接使用std.arithon.form()，通常是临时的。如果std.uuid要更改(应该更改)，它必须依赖于系统CSPRNG，而不是其他东西。

我知道有些人不愿意在标准库中引入任何与密码学相关的东西，但这里我们不是在谈论实现算法。在这种情况下，不采取行动显然比提供标准解决方案造成更大的损害。特别是在webera，获得密码随机性是必须的。

现在的CPU一般都嵌入CSPRNG，不是吗？为什么不使用它而不是处理特定于操作系统的资源呢？

有几个原因。例如，系统可以访问更多熵，并使用CPU作为熵源(如果可用)，因此可以保证系统CSPRNG至少与CPU一样好，而且往往更好。

此外，甚至在最近也有CPU缺陷的案例，这甚至没有考虑到它是封闭源代码的事实，这对安全性从来都不是一件好事。

但主要原因更简单：如果CPU不提供CSPRNG怎么办？并不是所有的CPU都提供CSPRNG，远非如此，那么你应该怎么做呢？在一种我们知道会导致问题的方法上默默地倒退？这将给人一种安全的假象，甚至比目前所做的更有害。

尽管如此，必须处理特定于平台的代码仍然是一件痛苦的事情。难道我不能不依赖系统而只编写我自己的CSPRNG吗？

没有人应该滚动他们自己的密码并期望它在生产中可用。但是让我们假设您正确地编写了这个困难而关键的组件：您如何为它提供熵？

唯一合理的来源是从系统的CSPRNG中提取，所以您仍然不会比直接使用它更好，您只是添加了另一层错误。

您可能会尝试在其他地方收集熵，但与系统相比，您对它的访问权限必然较少，而且任何这样的收集都会涉及特定于平台的代码。那里。

.