CSAW CTF加密挑战：破解DSA签名

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

挑战背景

该问题涉及数字签名算法(DSA)，展示了看似安全的算法如何通过实现缺陷变得完全不安全。挑战利用了两种漏洞：

1. PlayStation 3固件破解的根源漏洞
2. 无数软件产品中常见的安全漏洞来源

尽管这两个问题已存在多年，但许多软件开发人员(甚至安全工程师)仍不熟悉它们。

挑战架构

参与者获得源代码(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：提交有效DSA签名和Fernet令牌后返回flag

DSA签名机制剖析

完整的DSA密钥包含5个值：p,q,g,x,y。其中x是私钥值，签名过程如下：

1. 选择随机数k(0 < k < q)
2. 计算r = (g^k mod p) mod q
3. 计算k的模逆kinv：(k * kinv) % q = 1
4. 计算消息哈希h = int.from_bytes(hashlib.sha1(data).digest(), ‘big’)
5. 计算s = kinv * (h + r * x) % q

签名验证过程则通过计算v = ((g^u1) * (y^u2)) % p % q，应与r值相等。

漏洞利用链

核心漏洞在于随机数k的生成使用了非加密安全的Mersenne Twister(MT)算法。通过以下步骤可恢复私钥x：

1. 从/forgotpass端点收集624个64位随机数(转换为MT内部状态)
2. 克隆MT状态预测未来输出
3. 获取任意消息的签名(r,s)
4. 使用预测的k值解方程：x = (rinv * ((s * k) - h)) % q
5. 验证pow(g,x,p) == y确认私钥正确性

完整攻击流程

1. 调用/forgotpass构建MT状态克隆
2. 调用/sign获取(r,s)签名
3. 使用预测的k值计算私钥x
4. 调用/challenge获取Fernet令牌
5. 使用私钥签名后提交/capture获取flag

安全启示

在实际系统中：

1. 避免使用非加密安全RNG(如MT)进行密码学操作
2. 考虑采用确定性nonce生成(RFC 6979)
3. 优先选择更健壮的签名算法(如ed25519/RFC 8032)

本次CTF中44支队伍有28支成功破解，证明这类"密码重置与签名nonce共享RNG"的隐蔽关联可能导致灾难性安全后果。