CSAW CTF Crypto Challenge: Breaking DSA

Trail of Bits密码学服务团队为最近的CSAW CTF贡献了两道密码学挑战。今天我们将解析其中较简单的一道，题目名为"灾难性安全设备——祝你好运，‘k？"。

这道题目涉及数字签名算法(DSA)，展示了表面安全的算法如何通过实现细节变得完全不安全。该挑战利用了两种漏洞，其中一个是PlayStation 3固件破解的根源，另一个则是无数软件产品中常见的安全漏洞来源。

获取旗帜

参赛者获得了源代码(main.py)和一个可交互的HTTP服务器。该服务器模拟在线签名服务，包含以下端点：

/public_key：返回DSA公钥元素(p,q,g,y)的JSON编码整数
/sign/：对数据进行SHA1哈希后使用DSA私钥签名，返回两个整数(r,s)
/forgotpass：使用random.getrandbits生成密码重置URL
/resetpass：未实现的端点，调用返回500
/challenge：返回有效的Fernet令牌
/capture：当提供有效的Fernet令牌的DSA签名时，返回旗帜

DSA签名机制剖析

完整的DSA密钥包含5个值：p,q,g,x和y。其中x是私钥值，我们需要恢复它。DSA签名的计算过程如下：

选择随机数k(0 < k < q)
计算r = (g^k mod p) mod q
计算k的模逆kinv：(k * kinv) % q = 1
计算消息的SHA1哈希h
计算s = (kinv * (h + r * x)) % q

服务器中的签名实现如下：

 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)

数学漏洞利用

从签名方程s = (kinv * (h + r * x)) % q出发，我们可以解出私钥x：

1

x = (rinv * ((s * k) - h)) % q

关键在于预测随机数k的值。服务器使用Python的random模块(基于梅森旋转算法)生成k，这不是密码学安全的随机数生成器。

随机数生成器攻击

通过调用/forgotpass端点，我们可以获取梅森旋转算法的输出：

1
2
3
4


@app.route("/forgotpass")
def returnrand() -> str:
    random_value = binascii.hexlify(struct.pack(">Q", random.getrandbits(64)))
    return "https://innitech.local/resetpass/{}".format(random_value.decode("ascii"))

我们实现了梅森旋转算法的克隆版本，可以预测未来的随机数输出：

 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


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

完整攻击流程

通过多次调用/forgotpass重建RNG内部状态
调用/sign获取签名(r,s)
使用克隆的RNG预测k值
解方程恢复私钥x
验证x的正确性：pow(g,x,p)应当等于y
获取挑战令牌并签名，提交到/capture获取旗帜

总结

在36小时的CSAW决赛中，44支队伍中有28支成功获取了旗帜。这个挑战展示了密码重置令牌生成与DSA签名随机数生成之间的意外关联，加上DSA算法的脆弱性，导致了灾难性的安全漏洞。

在实际系统中，应避免使用非密码学安全的随机数生成器。如果不需要高性能或序列可重现性，应优先选择CSPRNG。此外，可以考虑使用更健壮的签名算法如ed25519(RFC 8032)，或采用确定性随机数生成(RFC 6979)来降低风险。

破解CSAW CTF加密挑战：DSA签名漏洞分析

本文详细分析了CSAW CTF中一道涉及DSA签名算法的密码学挑战，揭示了由于随机数生成器不安全导致的私钥泄露漏洞，并提供了完整的漏洞利用方法。