被动型RSA签名错误攻击的分析

引言

RSA签名错误攻击（Fault attacks）是一种在CRT-RSA签名发生错误时，通过错误的签名恢复签名私钥的攻击。

以往的RSA签名错误攻击都是主动型的攻击，即需要攻击者主动干扰签名的过程，往签名中注入错误，需要攻击者有很强的攻击能力。但最近Ryan、He、Sullivan和Heninger提出了一种被动型的RSA签名错误攻击[1]，他们在网络上以窃听者的身份收集了52亿条SSH记录，并对其中的4900个错误签名使用Coppersmit的算法[2]进行攻击，成功恢复了这些签名的签名私钥。

今天这篇文章将介绍Ryan他们这种攻击的原理、成功条件和防御方法。

前置知识

在说原理前，首先来补习一点密码学的相关知识。

RSA签名

和RSA的加密算法类似，首先需要生成两个大素数和，然后计算模数，然后选择与互素的公钥，最后计算私钥

在教科书中，令是需要签名的消息，则RSA的签名即是

但这种教科书的方法会存在很多漏洞，所以实际使用的时候会在签名前给消息进行填充（Padding），使签名变为

CRT-RSA签名

为了加快签名速度，会使用到CRT-RSA的签名方式。

其中的CRT是指中国剩余定理（Chinese Remainder Theorem），令

则使用CRT的算法可以找到

在CRT-RSA签名中，首先通过计算

然后使用CRT计算最终的签名

PKCS#1 v1.5的填充方法

填充方法有很多种，其中Ryan的文章中分析的是目前主流的PKCS#1 v1.5标准[3]的填充算法。

这种填充方法的具体填充方式可见标准的8.1节，大概意思是填充为

EB = 00 || BT || PS || 00 || D

其中EB是填充后的结果，BT是填充块类型（Block Type），PS是填充字符串（Padding String），00字节用于分割和标识，D是被填充的数据（Data）。

PS的内容由BT确定，其中：

• 当BT = 00时，PS全为00字节（这个类型需要D的首字节非00）。
• 当BT = 01时，PS全为FF字节。
• 当BT = 02时，PS全为伪随机的非00字节。

对于签名算法（RFC2313中的private- key operation），一般只使用00或01类型，实际应用中更多是使用01类型，即Ryan的文章中分析的类型。

在RSA签名中，令是需要签名的消息，则数据D为消息的哈希值。

所以最终文章分析的填充算法形如

pad(m) = 00 || 01 || FF ... FF || 00 || H(m)

单元Coppersmith算法

Coppersmith算法是一种用于解小未知模数方程的方法，单元（Univariate）指所解的方程只有一个未知数。

Coppersmith算法的过程和证明十分复杂，从结论上看是：如果一元多项式的度为（Degree，即最高项的次数），若方程

的一个小根满足

则使用单元Coppersmith算法可解出这个根，其中是误差值。

对于RSA的模数，若和同规模，且多项式的度为时，若方程

的一个小根满足

则使用单元Coppersmith算法可在不知道的情况下解出这个根，其中是误差值。这种方法常见于RSA的已知高位攻击，详细可参考文献[4]的19.4.2节。

Ryan的攻击原理

使用GCD分解模数

Ryan他们主要实施的是RSA签名的错误攻击，其中的错误是指，在CRT-RSA的签名过程中，其中一个模数的运算发生了错误，导致产生了错误的签名，不妨令在模的运算时产生错误，即

假设签名的消息已知，填充方式可重复，则可以通过求最大公约数分解得到。首先通过展开

的模操作，可得存在使得

然后代入

可得

于是可得和互素，即

由于和互素，所以

最后通过求最大公约数可得

使用Coppersmith算法求消息哈希

通过RSA签名的参数和窃听信道上的SSH通信，Ryan他们可以知道、和，如果要实现上述攻击，还需要知道，但显然通过被动攻击是不能窃听到消息的。

所以接下来需要通过已知的信息恢复，这里假设使用的填充方法是PKCS#1 v1.5的01类型填充，其他填充方法分析类似。

PKCS#1 v1.5的01类型填充方法为：

pad(m) = 00 || 01 || FF ... FF || 00 || H(m)

如果把其中的H(m)切割出来，令为已知的高位填充

00 || 01 || FF ... FF || 00 || 00 ... 00

令为H(m)，则可以在数学上表示为

其中和模数同等规模，的规模由所使用的哈希算法所决定。

把以上填充代入到错误的RSA签名中，即得

其中是已知量，所以以上是一个关于未知数的、度为的模方程，所以根据Coppersmith算法，若

则可恢复，然后计算出，最后使用GCD分解模数。

如果忽略系数和误差，可以大概认为哈希的比特长度为模数比特长度的1/4时即可分解RSA签名的模数，进而恢复签名私钥。

结果

以下是Ryan他们在各种参数下的实验结果

实验结果基本符合理论分析的预期，只不过在时，由于理论值存在误差，会导致攻击失败，这时可通过枚举部分未知值解决这个问题，只是这种枚举会消耗大量的时间，可见在RSA-1024, SHA256和RSA-2048, SHA512参数下的实验结果。

我们也使用SageMath对这种攻击进行了模拟，参考代码如下，供有兴趣的读者进行继续研究：

#!/usr/bin/env sage
import libnum
import hashlib
import logging

def pad(m, N):
  pl = N.nbits() // 8
  return b'x00x01' + b'xff' * (pl - 3 - len(m)) + b'x00' + m

def inject_fault(m):
  mb = m.bits()
  ipos = randint(0, len(mb)-1)
  mb[ipos] = 1 - mb[ipos]
  res = Integer(''.join([str(x) for x in mb[::-1]]), 2)
  return res

def keygen(pbits):
  p = random_prime(2^pbits, lbound=2^(pbits-1), proof=False)
  q = random_prime(2^pbits, lbound=2^(pbits-1), proof=False)
  logging.debug(' p = %d' % p)
  logging.debug(' q = %d' % q)
  N = p * q
  phi = (p - 1) * (q - 1)
  e = 65537
  d = e.inverse_mod(phi)
  pk = N, e
  sk = p, q, d
  return pk, sk

def CRT_RSA_sign(sk, msg, H, fault=True):
  logging.debug(' fault = %s' % fault)
  p, q, d = sk
  pm = Integer(libnum.s2n(pad(H(msg).digest(), p*q)))
  sp = Integer(pow(pm, d, p))
  if fault:
    sq = Integer(pow(inject_fault(pm), d, q))
  else:
    sq = Integer(pow(pm, d, q))
  s = crt([sp, sq], [p, q])
  return s

def attack(pk, s, hbytes):
  N, e = pk
  PR.<h> = PolynomialRing(Zmod(N))
  a = Integer(libnum.s2n(pad(b'x00' * hbytes, N)))
  f = (pow(s, e, N) - a) - h
  f = f.monic()
  roots = f.small_roots(X=2^(hbytes*8), beta=0.48)
  logging.debug(' roots = %s' % roots)
  if roots: 
    h = Integer(roots[0])
    pm = h + a
    p = gcd(N, Integer(pow(s, e, N)) - pm)
    logging.debug(' p in atk = %s' % p)
    if N % p == 0:
      q = N // p
      return p, q
  return None

def test(pbits, H):
  logging.debug(' pbits = %s' % pbits)
  logging.debug(' H     = %s' % H)
  pk, sk = keygen(pbits)
  msg = b'Euphoric Phantasmagoria!'
  s = CRT_RSA_sign(sk, msg, H)
  hbytes = len(H(msg).digest())
  atk = attack(pk, s, hbytes)
  if atk == None:
    return False
  p, q = atk
  if p in (sk[0], sk[1]):
    return True
  return False
   
if __name__ == '__main__':
  #logging.basicConfig(level=logging.DEBUG)
  H = hashlib.sha256
  for pbits in (2048, 1024, 768, 513, 512, 256):
    res = test(pbits, H)
    print('RSA-%d + SHA256: %s' % (pbits*2, res))

漏洞条件、影响及修复建议

以上模拟代码通过主动注入的方式让签名产生出错，在真实世界这种错误出现的概率极低，我们在本地设备上进行实验，重复生成了百万次签名，也并未发现有出现这种错误，Ryan他们的实验通过窃听不同设备的52亿个签名，也只找到4900个错误签名。不过虽然这种漏洞出现的概率很低，也应该对其进行修复，避免造成严重影响。

经以上分析可以总结出漏洞产生的条件：使用了CRT-RSA签名算法，使用了类PKCS#1 v1.5的填充方法且哈希的比特长度小于模数比特长度的1/4。漏洞可导致签名私钥被泄露，私钥被用于身份伪造，或结合其他漏洞对设备发起中间人攻击。

在和Ryan他们交流以及参考了他们的文章后，我们总结出以下的修复方案：

1. 签名后对签名进行验证：这是Ryan他们强调的最简单而且最有效的修复方案，以上漏洞产生的最主要原因是签名错误，所以只需在每次签名后对其进行检验，保证签名不出错，即可避免漏洞产生。
2. 调用如OpenSSL的第三方库进行签名：原因是OpenSSL中的签名方法默认对签名结果进行验证，原理和修复方案1类似。
3. 填充消息时使用比特长度尽量长的哈希算法：即让哈希的比特长度大于模数比特长度的1/4，使Coppersmith方法攻击失败。
4. 升级到TLSv1.3：由于TLSv1.3会对密钥交换后的握手信息加密，所以会使得窃听者获取不到签名信息，不过这种修复方案仅对支持TLS的协议有用。

参考

1. Ryan K, He K, Sullivan G A, et al. Passive SSH Key Compromise via Lattices[J]. Cryptology ePrint Archive https://eprint.iacr.org/2023/1711, 2023.
2. Coppersmith D. Finding a small root of a univariate modular equation[C]. International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 1996: 155-165.
3. Kaliski B. PKCS# 1: RSA encryption version 1.5[R]. https://www.rfc-editor.org/rfc/rfc2313.html. 1998.
4. Galbraith S D. Mathematics of public key cryptography[M]. Cambridge University Press, 2012.

原文始发于微信公众号（山石网科安全技术研究院）：被动型RSA签名错误攻击的分析