CSAW CTF密码学挑战：破解DSA - Trail of Bits博客

Trail of Bits密码学服务团队在最近的CSAW CTF中贡献了两个密码学挑战。今天我们将讨论其中较简单的一个，标题为“灾难性安全装置——祝你好运，‘k？’”。

这个问题涉及数字签名算法（DSA），以及一个看似安全的算法如何通过令人惊讶的实现缺陷变得完全不安全。该挑战依赖于两个漏洞，其中一个曾是PlayStation 3固件黑客攻击的源头，另一个则是无数软件产品中安全漏洞的常见来源。尽管这两个问题已知多年，但大量软件开发人员（甚至安全工程师）仍不熟悉它们。

如果您有兴趣自己解决这个挑战，请在此获取代码并在本地托管。否则，请继续阅读，以便学会在编写或审查的代码中发现这类问题。

需要捕获的旗帜

参与者获得了源代码（main.py）和一个可以联系的活跃HTTP服务器。该服务器设计成大致类似于在线签名服务器。它有一个对发送给它的有效载荷进行签名的端点，以及一个部分实现的登录系统，具有密码重置功能。

枚举的路由集合：

• /public_key：返回DSA公钥的元素（p、q、g、y），作为编码在JSON结构中的整数。
• /sign/：对传递的数据执行SHA1哈希，然后用DSA私钥对生成的哈希进行签名，并在JSON结构中返回两个整数（r、s）。
• /forgotpass：使用random.getrandbits生成用于重置用户密码的URL。
• /resetpass：一个未实现的端点，如果调用则返回500。
• /challenge：返回一个有效的Fernet令牌。
• /capture：当提供对有效Fernet令牌的有效DSA签名时，产生旗帜。

为了捕获旗帜，我们需要恢复DSA私钥，并用它来签名来自/challenge端点的加密有效载荷。然后我们将挑战值和签名都提交给/capture。这允许服务器验证您已恢复私钥。让我们开始吧！

DSA签名，灾难性安全装置在行动

一个完整的DSA密钥由5个值组成：p、q、g、x和y。

p、q、g和y都是公共值。服务器上的/public_key端点提供这些值，并可用于验证给定签名是否有效。私有值x是我们需要的。DSA签名通常按如下方式计算：

首先选择一个k，其中0 < k < q。 计算值r。概念上这是g^k mod p mod q。然而，由于g和k都是大数，直接计算这个值非常慢。幸运的是，模幂运算可以非常快速地完成计算。在Python中，您可以通过内置的pow方法计算：pow(g, k, p) % q。 计算k模q的模乘逆。即，kinv使得(k * kinv) % q = 1。 计算您要签名的消息的哈希。此特定代码使用SHA1，然后将字节字符串转换为大端整数。在Python中这样做：int.from_bytes(hashlib.sha1(data).digest(), 'big')（需要Python 3！）。 最后，使用kinv * (h + r * x) % q计算s。

main.py中的签名器实现方便地拥有此确切代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def sign(ctf_key: DSAPrivateKeyWithSerialization, data: bytes) -> tuple(int, int):
  data = data.encode("ascii")
  pn = ctf_key.private_numbers()
  g = pn.public_numbers.parameter_numbers.g
  q = pn.public_numbers.parameter_numbers.q
  p = pn.public_numbers.parameter_numbers.p
  x = pn.x
  k = random.randrange(2, q)
  kinv = _modinv(k, q)
  r = pow(g, k, p) % q
  h = hashlib.sha1(data).digest()
  h = int.from_bytes(h, "big")
  s = kinv * (h + r * x) % q
  return (r, s)

要确认r和s正确，您还可以执行DSA验证。

计算w，s模q的模逆。 计算u1 = (h * w) % q。 计算u2 = (r * w) % q。 计算v，定义为((g ** u1) * (y ** u2)) % p % q。这将需要通过模幂运算完成！ 此时v应该等于r。

狡猾的数学，破坏我们的安全

我们已经看到了生成和验证DSA签名所涉及的数学，但我们真正想使用的是我们知道的值集来恢复一个未知的值（x，私有标量）。回想这个方程：

s = (kinv * (h + r * x)) % q

DSA签名由两个值组成：r和s。我们还知道h是被签名的值，并且通过签名预言机我们选择该值。最后，我们知道q，因为它是用于验证DSA签名的公钥的一部分。这给我们留下了两个未知数：kinv和x。让我们解x：

s = (kinv * (h + r * x)) % q s * k = (h + r * x) % q (s * k) % q = (h + r * x) % q
注意：(s * k)将始终小于q，因此添加% q只是为了清晰。 ((s * k) - h) % q = (r * x) % q (rinv * ((s * k) - h)) % q = x

rinv的计算方式与kinv（模乘逆）类似。

从最终方程可以看出，如果我们能确定任何给定签名元组（r, s）使用的k，那么我们就可以恢复私有标量。但k是通过random.randrange生成的，因此不可预测。

RNG和全局状态，哦我的！

随机数生成很难。Python的random模块使用Mersenne Twister（MT）的全局单例实例来提供快速且统计上随机的RNG。然而，MT绝对不是密码学安全的伪随机数生成器（CSPRNG）。Python的文档和MT的文档都记录了此属性，但记录危险API结果不足以防止误用。在MT的情况下，观察624个32位输出足以重建RNG的内部状态并预测所有未来输出。尽管MT的周期为2^19937 − 1。如果用户能够通过另一个端点查看MT RNG的输出，那么他们可以使用这些输出来预测random.randrange的输出。进入/forgotpass，此挑战的Chekhov之枪。

/forgotpass实现如下：

1
2
3
4
5
6
7
8

@app.route("/forgotpass")
def returnrand() -> str:
  # Generate a random value for the reset URL so it isn't guessable
  random_value = binascii.hexlify(struct.pack(">Q",
  random.getrandbits(64)))
  return "https://innitech.local/resetpass/{}".format(
    random_value.decode("ascii")
  )

因此，每次调用该端点将获得一个大端形式打包的随机64位整数。但是我们如何将其变成工作的MT实例？

玩扭扭乐

我们现在知道如何从MT实例获取数据块，但是我们如何处理这些数据并使用它来预测未来输出？首先我们需要我们自己的MT实现：

 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

class ClonedMersenneTwister:
    length = 624

    def __init__(self, state):
        self.state = state[:]
        self.index = 0

    def next(self):
        if self.index == 0:
            self.generate_numbers()

        y = self.state[self.index]
        y = y ^ (y >> 11)
        y = y ^ (y << 7) & 2636928640
        y = y ^ (y << 15) & 4022730752
        y = y ^ (y >> 18)

        self.index = (self.index + 1) % self.length
        return y

    def generate_numbers(self):
        for i in range(self.length):
            y = ((self.state[i] & 0x80000000) +
                 ((self.state[(i + 1) % self.length]) & 0x7fffffff))
            self.state[i] = self.state[(i + 397) % self.length] ^ (y >> 1)
            if y % 2:
                self.state[i] ^= 2567483615

从next中的代码可以看出，内部状态应用了一系列位移、AND和OR操作，MT算法称之为“调温”。要恢复原始状态，我们需要反转这些操作。

你是钥匙大师吗？

我们拥有所有部分。让我们把它们放在一起。

首先，我们需要调用/forgotpass来获取RNG的内部状态并构建本地克隆。我们需要拆分URL末尾的重置代码，并将其转换为内部状态的两个值，因为它是64位数据，而我们正在克隆32位MT实例。

一旦完成，我们将使用一些要签名的数据调用/sign，并取回r、s。任何数据都可以。然后我们可以使用r、s、p、q、g以及从克隆的RNG获得的值（这是我们预测服务器将使用的k）来解x。

为了确认我们计算的x正确，我们可以计算pow(g, x, p)，结果将等于y。

最后，我们将调用/challenge以获取Fernet令牌，使用私钥对其进行签名（使用SHA256作为哈希），并将令牌和签名提交到/capture端点以捕获旗帜！

总结

在36小时的CSAW决赛中，44支队伍中有28支能够捕获此旗帜。对于一个利用密码重置令牌生成和DSA签名随机数生成之间意外关系的挑战来说，这是一个相当不错的成功率。加上像DSA这样的算法的脆弱性，这个看似温和的问题实际上导致了灾难性和不可恢复的安全漏洞，大多数参与团队都能够解决它。

在现实世界中，您可能正在构建或审计处理此类敏感数据的系统，请记住，应仔细调查使用非CSPRNG源获取随机性的情况。如果高性能或序列可重现性不是硬性要求，那么CSPRNG是更好的选择。如果您没有遗留约束，那么您的系统应避免具有此类故障模式的签名算法。确定性随机数生成（RFC 6979）可以显著降低风险，但在可行的情况下，更强大的签名算法（如ed25519（RFC 8032））是更好的选择。