C#随机数生成器漏洞分析与利用

利用随机数生成器需要数学知识吗？感谢C#的Random类，情况并非如此！我遇到了一个HTTP 2.0 Web服务，该服务使用(new Random()).Next(min, max)输出的自定义编码来生成密码重置令牌。

这导致了严重的账户接管漏洞。利用此漏洞不需要编写脚本、数学计算或使用库，只需在Burp中进行几次点击。虽然我有源代码，但我会展示在黑盒或漏洞赏金式参与中发现和利用此漏洞的方法。

漏洞详情

我无法分享客户端代码，但大致如下：

1
2
3


var num = new Random().Next(min, max);
var token = make_password_reset_token(num);
save_reset_token_to_db(user, token);

这代表了典型的密码重置流程。令牌使用Random()创建，并且没有设置种子。该令牌被编码为字母数字令牌，通过电子邮件发送给用户，用户可以使用其电子邮件和令牌登录。

这可能是可被轻易利用的。

C# PRNG工作原理

文档链接到了以下参考实现。这不是真正的实现，但足够好。不要在这里深入细节，Random(int Seed)仅为了上下文显示。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


public Random()
  : this(Environment.TickCount) {
}

public Random(int Seed) {
  int ii;
  int mj, mk;

  //初始化种子数组
  int subtraction = (Seed == Int32.MinValue) ? Int32.MaxValue : Math.Abs(Seed);
  mj = MSEED - subtraction;
  SeedArray[55]=mj;
  mk=1;
  for (int i=1; i<55; i++) {
    ii = (21*i)%55;
    SeedArray[ii]=mk;
    mk = mj - mk;
    if (mk<0) mk+=MBIG;
    mj=SeedArray[ii];
  }
  for (int k=1; k<5; k++) {
    for (int i=1; i<56; i++) {
      SeedArray[i] -= SeedArray[1+(i+30)%55];
      if (SeedArray[i]<0) SeedArray[i]+=MBIG;
    }
  }
  inext=0;
  inextp = 21;
  Seed = 1;
}

整个系统依赖于32位种子。这通过一些复杂的数学构建了内部状态(SeedArray[55])。如果Random在没有参数的情况下初始化，则使用Environment.TickCount作为种子。PRNG的所有输出都由其种子决定。在这种情况下，它就是TickCount - 本质上只是时间。

利用方法

文档说得最好：

“在.NET Framework中，默认种子值来自系统时钟，其分辨率有限。因此，通过调用无参数构造函数在短时间内创建的不同Random对象具有相同的默认种子值，因此会产生相同的随机数集。”

如果我们在相同的1毫秒窗口内提交两个请求，我们会得到相同的种子，相同的种子产生相同的输出，相同的重置令牌会发送到两个电子邮件地址。当然，一个电子邮件地址是我们拥有的，另一个属于管理员。

我们如何使用单数据包攻击来命中1毫秒窗口？它真的有效吗？

黑盒方法

在验证漏洞之前，您不希望向管理员发送垃圾重置电子邮件。因此，在您控制的网站上创建两个账户。虽然您可以使用一个账户进行攻击，但这容易产生误报。

使用Burp的Repeater组执行单数据包攻击来重置两个账户。检查您的电子邮件中是否有重复的令牌。如果失败，请继续测试其他内容，直到锁定窗口结束。然后再次点击发送，很可能您不需要担心保持会话令牌活动。

注意：Burp在Repeater的右下角显示往返时间。

密切关注该数字。每个请求都有自己的时间。对我来说，大约需要10个请求才能获得重复令牌。这仅在往返时间差为1毫秒或更少时发生。

在发起实际攻击时，检查您的令牌是否与受害者账户匹配的唯一方法是登录。登录请求往往受到速率限制和保护。因此，首先使用测试账户进行验证。使用它来获得有效的时间差窗口。然后，在发起实际攻击时，仅当时间差在您的测试范围内时才尝试登录。

总结

这种攻击并非完全新颖。我在CTF中见过类似的攻击。这是关于时间的一个很好的教训。我们通过等待或不等待来控制时间。如果秘密令牌只是编码的时间，您可以通过复制时间来复制它们。

如果您深入研究.NET运行时，您可能会说服自己这种攻击不会奏效。Random有多个实现，我的客户端应该使用的实现不是按时间播种的。

弱PRNG漏洞的修复方法总是检查文档。在这种情况下，您必须点击"Remarks"部分中的"Supplemental API remarks for Random.“才能获得安全信息，其中说明：

“要生成加密安全的随机数，例如适合创建随机密码的数字，请使用System.Security.Cryptography.RandomNumberGenerator类中的静态方法之一。”

因此，C#应使用RandomNumberGenerator而不是Random。

奖励：破解C#的旧随机算法

前面涉及一些数学计算。这不算太糟，但我想警告您。这是利用此发现的"困难"方法。我编写了一个可以预测Random::Next输出的库。它还可以反转它，回到种子。或者您可以从第七个输出中找到第一个输出。这些都不需要暴力破解，只需要一个模方程。代码可以在这里找到。

我本打算这是一个有趣的周末数学项目。当我发现由于整数下溢导致的冲突时，事情变得混乱了。

播种只是数学

让我们看看种子算法，但尝试概括您所看到的内容。SeedArray[55]显然是PRNG的内部状态。这是用"数学"构建的。如果您仔细观察，几乎每次分配SeedArray[i]时，都是通过减法进行的。紧接着，您总是看到一个检查，减法结果是否为负数？如果是，则添加MBIG。换句话说，所有的减法都是以MBIG为模完成的。

MBIG值是Int32.MaxValue，即0x7fffffff，即2^31 - 1。这是一个梅森素数。在素数上进行模运算会产生数学人员所谓的伽罗瓦域。

所以，假设SeedArray[i]是某个aSeed + b mod MBIG。它在循环中通过减去某个其他cSeed + d mod MBIG而改变。我们不需要那个循环 - 代数说明只需(a+c)Seed + (b+d) Mod MBIG。通过循环进行代数运算，您可以得到SeedArray的每个元素，形式为aSeed + b mod MBIG。

每次采样PRNG时，都会调用Random::InternalSample。这只是另一个减法。结果既被返回，又被用于设置SeedArray的某个元素。这又是一些方程。它仍然在伽罗瓦域中，仍然只是代数，您可以反转所有这些方程。给定Random::Next的一个输出，我们可以反转相应的方程并获得原始种子。

但是，我们还可以做更多！

csharp_rand.py库

我制作的库从这些方程构建SeedArray。它将输出这些方程的形式。让我们得到表示任何种子的Random的第一个输出的方程：

1
2
3
4
5


>>> from csharp_rand import csharp_rand
>>> cs = csharp_rand()
>>> first = cs.sample_equation(0)
>>> print(first)
rand = seed * 1121899819 + 1559595546 mod 2147483647

这表示任何种子的Random的第一个输出。使用.resolve(42)获取new Random(42).Next()的输出。

1
2


>>> first.resolve(42)
1434747710

或者反转并解析1434747710以找出什么种子将在Random的第一个输出中产生1434747710。

1
2


>>> first.invert().resolve(1434747710)
42

Random中的整数下溢

刚完成我的库，我兴奋地把它展示给第一个愿意听我说话的人。当然，它失败了。肯定有错误，当然我责怪原始实现。但由于账户接管错误不在乎我的感受，我修复了代码…大部分…

简而言之，原始实现有一个整数下溢，对于某些种子值会使数学方程出错。只有某些SeedArray元素受到影响。例如，以下显示Random的第一个输出不需要任何调整，但第13个输出需要。

1
2
3
4


>>> print(cs.sample_equation(0))
rand = seed * 1121899819 + 1559595546 mod 2147483647
>>> print(cs.sample_equation(12))
rand = seed * 1476289907 + 1358625013 mod 2147483647 underflow adjustment: -2

因此，第13个输出将是seed * 1476289907 + 1358625013，除非种子导致下溢，那么它将偏离-2。代码本身尝试决定是否发生溢出。这在您反转事物之前工作得很好。考虑一下，什么种子值将在Random::Next的第13个输出中产生908112456？

1
2


>>> cs.sample_equation(12).invert().resolve2(908112456)
(619861032, 161844078)

两个种子，619861032和161844078，都将在第13个输出中产生908112456。种子619861032以正确的方式实现，来自未调整的方程。种子619861032从下溢到达那里。这种"冲突"意味着恰好有2个种子产生相同的输出。这意味着908112456在第13个输出中出现的可能性是第一次的两倍。这也意味着没有种子会在Random的第13个输出中产生908112458。快速的暴力破解产生了其他80K+类似的"冲突”。

奖励结论

有时聪明的方法是愚蠢的。一开始是一个有趣的数学项目，最终感觉像是被千刀万剐。最好版本匹配和语言匹配您的利用并快速使其运行。如果花费很长时间，在它仍在运行时开始优化。但在优化之前，测试！测试一切！否则您将运行暴力破解数小时而一无所获。为什么？也许Random(Environment.TickCount)不是Random()，因为显式播种会导致不同的算法！

呃…我要去审计更多的端点…