ROCA攻击——CVE-2017-15361

2023-09-06

未分类

2.9k 词

2023WMCTF的badprime官方wp提到了这个漏洞CVE-2017-15361。

badprime

源码：

from Crypto.Util.number import *
from secret import flag
 
M = 0x7cda79f57f60a9b65478052f383ad7dadb714b4f4ac069997c7ff23d34d075fca08fdf20f95fbc5f0a981d65c3a3ee7ff74d769da52e948d6b0270dd736ef61fa99a54f80fb22091b055885dc22b9f17562778dfb2aeac87f51de339f71731d207c0af3244d35129feba028a48402247f4ba1d2b6d0755baff6
 
def getMyprime(BIT):
    while True:
        p = int(pow(65537, getRandomRange(M>>1, M), M)) + getRandomInteger(BIT-int(M).bit_length()) * M
        if isPrime(p):
            return p
 
p = getMyprime(1024)
q = getPrime(1024)
n = p * q
m = bytes_to_long(flag)
 
print("Try to crack the bad RSA")
print("Public key:", n)
print("The flag(encrypted):", pow(m, 65537, n))
print("Well well, I will give you the hint if you please me ^_^")
leak = int(input("Gift window:"))
if M % leak == 0:
    print("This is the gift for you: ", p % leak)
else:
    print("I don't like this gift!")

题解：

这题传M然后copper，很简单。但是官wp提到了个cve，想来看看怎么个事。

exp:

from sage.all import *
from Crypto.Util.number import long_to_bytes

M = 0x7cda79f57f60a9b65478052f383ad7dadb714b4f4ac069997c7ff23d34d075fca08fdf20f95fbc5f0a981d65c3a3ee7ff74d769da52e948d6b0270dd736ef61fa99a54f80fb22091b055885dc22b9f17562778dfb2aeac87f51de339f71731d207c0af3244d35129feba028a48402247f4ba1d2b6d0755baff6
gift = 10024313384012746250694208538949686447032355241059569161518116640903009793798604684812989972951794463837898271416656747821246172846318000100642976088351263390343566563706839156952569571295913267481277331199225506966486951661539619597002534258121910069983897789675728728232822162150931695346789
N = 4527815560823898629090647633115302565837083515415976989690995912533144402828153290938790009126615705345926094457204119165604978427936576957465024752372112088234196073103717618632250550457634287834840701441955152299257503315744314335307821065466785930677769272236861589143544968634247690966457155973029019492515848925422374199922226662095089357969581197472453406092735214388947778181441370905665865989787799516773111366231899212901002557397391641026737581811832827350154376098191096933368295719329855350653664823378217291487968979523352051265095565946743081123073185487467693023515416676113819101085553626421514061953

maxlen = 1024 -len(bin(M)[2:])
PR.<x> = PolynomialRing(Zmod(N))
f = gift + M*x
root = f.monic().small_roots(X=2**maxlen, beta=0.42)[0]

print(root)
p = int(f(x=root))
q = N // p
assert p*q == N

c = 671423126344208979817020905319387107659521538401974581808466400658740425949121176339811220873187770177211049553654784310187701419630988633907039522390923642257247011797390197264431099444628550241370342966809803434077602089915863876682573081967204200944311396918398626099269491924960069539014293172012589912456689762187833047695244229784895185860115454875875027756981261009120804422582439068086000037380136289751308973297117752176034134418622366871665313790352235666401502989780634803665475527926954123107148643985437557292021664410162756392459081674875458282375811451846338551390975585916239510041697895364036127409
d = inverse_mod(65537, (p-1)*(q-1))
print(long_to_bytes(int(pow(c, d, N))))

ROCA攻击:

以下内容主要参考Analysis of the ROCA vulnerability | BitsDeep

在 RSALib 的情况下，质数具有特殊的形式：p=k⋅M+(65537^a^modM)。其中，参数 k 和 a 未知，M 是一个素数阶乘（前 n 个连续素数的乘积）。

文章提供了一个表格：

key size	n	M
512-960	39	P~39#~
992-1952	71	P~71#~
1984-3936	126	P~126#~
3968-4096	225	P~225#~

这种生成方法存在问题，以512位N，g=65537举例（下面都是）。

此时M=P~39#~约219bit，p为256bit，可见k约37bit。

而对于a，求满足g^k^=1 mod M的最小非0正整数k，可知a约在62bit

文中提供了sage代码：

g = 65537
k = Zmod(M)(g).multiplicative_order()
print(log(k, 2).n())
#61.0899035000874

即相对于256bit素数的2^256^种可能性，该方法生成的p只有2^99^种

然后文中提到了一些在研究中发现的特殊性质，略过。

随后文中提到了两种检测一个密钥是否易受 ROCA 攻击：

第一种方法基于前文提到的特殊性质——N 被限制在模小素数的小余数集合

第二种更好的方法基于求解log~65537~N mod M以及前文提到的一个性质N=65537^a^ mod M。

因为M是个光滑数，所以 Pohlig-Hellman算法可以快速求解。
以下是文中提供的相关检测代码,实现了给定一个n，自动生成对应的M并求解log~65537~N mod M

```python
def isVuln(n):

params = getParameterSizes(n.bit_length())
if params is not None:
    M = params[0]
    try:
        a = Zmod(M)(n).log(65537)
        print(f"Vulnerable Key ! Found a={a}")
        return True
    except ValueError:
        print("Key not vulnerable to ROCA :(")
        return False

test a vulnerable key

isVuln(genWeakKey(512))

Now test a normal key

from Crypto.Util.number import getPrime
notvuln = int(getPrime(300)*getPrime(300))

isVuln(notvuln)




#### **攻击原理：**

感觉这一部分有点乱，大概是解释了coppersmith，然后实现了给定a的情况下求解k，但用的是比较复杂（指参数较多）的coppersmith_howgrave_univariate函数，而不是small_roots。

直接看优化部分吧，有提到优化部分会缩小a的可能范围。

##### **优化1：**

缩小搜索范围。 （后文：一个不大的优化）

文中有提到两个性质，这里用到其中一个：模数 *N* 与其素因子具有相同的形式，即*N*=*k*~3~⋅*M*+(65537^a^mod*M*);其中a≡a1+a2 mod |G|,G是由 65537(模M) 生成的Z~m~的子群，a1、a2是素因子生成时的指数值。

> 原本a~1~（a~2~）的搜索范围是 [0, a] ，但根据a≡a~1~+a~2~ mod |G|，我们可以缩小为[a/2,（a+∣*G*∣）/2]。因为 a~1~=a~2~=a/2 是可以产生 a 的最小组合，而a~1~=*a*~2~=(*a*+∣*G*∣ )/2是最大的组合。

|G|是乘法阶，应该就是个数，这个''||''符号不知道干什么的；同余式看成a+k|G|=a~1~+a~2~，然后结合实际的一些隐性条件，大概就出来了上面的结论。

> 对于其他所有组合，只有 *a*~1~ 或 *a*~2~ 中的一个会在这个区间内，但是只要我们在正确的情况下猜测了*a*~1~ 或*a*~2~，就不会有问题。

这里的其他组合大概是a~1~≠a~2~吧，意思大概是不管什么情况，总有个崽种落在缩小后的区间里，能找到a~1~或a~2~，也就能求出p或q，然后成功分解N。

但是和后面说的又有些矛盾，在案例中，没落在范围中的a1被求出来了，范围中的a2却没求出来q，为了同时求出，修改参数beta为0.1。但既然有p了,验证一下直接q=N//p就行了吧，这样反倒和上一段的求出a~1~或a~2~即可分解N比较符合。



###### coppersmith_howgrave_univariate：

```python
def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
    """
    Taken from https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/coppersmith.sage
    Removed unnecessary stuff
    """
    dd = pol.degree()
    nn = dd * mm + tt
    
    if not 0 < beta <= 1:
        raise ValueError("beta should belongs in (0, 1]")

    if not pol.is_monic():
        raise ArithmeticError("Polynomial must be monic.")

    # change ring of pol and x
    polZ = pol.change_ring(ZZ)
    x = polZ.parent().gen()

    # compute polynomials
    gg = []
    for ii in range(mm):
        for jj in range(dd):
            gg.append((x * XX)**jj * modulus**(mm - ii) * polZ(x * XX)**ii)
    for ii in range(tt):
        gg.append((x * XX)**ii * polZ(x * XX)**mm)
    
    # construct lattice B
    BB = Matrix(ZZ, nn)

    for ii in range(nn):
        for jj in range(ii+1):
            BB[ii, jj] = gg[ii][jj]
            
    # LLL
    BB = BB.LLL()

    # transform shortest vector in polynomial    
    new_pol = 0
    for ii in range(nn):
        new_pol += x**ii * BB[0, ii] / XX**ii

    # factor polynomial
    potential_roots = new_pol.roots()

    # test roots
    roots = []
    for root in potential_roots:
        if root[0].is_integer():
            result = polZ(ZZ(root[0]))
            if gcd(modulus, result) >= modulus^beta:
                roots.append(ZZ(root[0]))
                
    return roots

solve函数：

def solve(M, n, a, m, t, beta):
    base = int(65537)
    # the known part of p: 65537^a * M^-1 (mod N)
    known = int(pow(base, a, M) * inverse_mod(M, n))
    # Create the polynomial f(x)
    F = PolynomialRing(Zmod(n), implementation='NTL', names=('x',))
    (x,) = F._first_ngens(1)
    pol = x + known
    # Upper bound for the small root x0
    XX = floor(2 * n^0.5 / M)
    # Find a small root (x0 = k) using Coppersmith's algorithm
    roots = coppersmith_howgrave_univariate(pol, n, beta, m, t, XX)
    # There will be no roots for an incorrect guess of a.
    for k in roots:
        # reconstruct p from the recovered k
        p = int(k*M + pow(base, a, M))
        if n%p == 0:
            return p, n//p

提供的案例：

# Gen 2 week primes
# I'm not generating the key directly because I need to know the primes
# in order to calculate the right value for a
M, k_s, a_s = getParameterSizes(512)
#p = genWeakPrime(M, k_s, a_s)
#q = genWeakPrime(M, k_s, a_s)

#Those values were generated using the lines above
#I just kept the ones that produced the desired behaviour
p = 121581495375123779193452413925265932089610720448703103558690293198717539850471
q = 116416434871278081772053124243609476193526753637462138632814719321940358203829
n = p*q
print(f"n: {n}")
print(f"p: {p}")
print(f"q: {q}")

print(f"p > q: {p > q}")

a3 = Zmod(M)(n).log(65537)
order = Zmod(M)(65537).multiplicative_order()
inf = a3//2
sup = (a3+order)//2
print(f"interval : [{inf}, {sup}]")

# attempt to find p
# Compute the right values for a and k
a1 = int(Zmod(M)(p).log(65537))
print(f"a1: {a1}. In interval: {inf <= a1 <= sup}")
k = (p - int(pow(65537, a1, M))) // M
# Assert correctness of the values
assert(k*M + pow(65537, a1, M) == p)
# solve using the parameters from the paper
factors = solve(M, n, a1, 5, 6, 0.5)
print(f"Known p: {factors}")

# attempt to find q
# Compute the right values for a and k
a2 = int(Zmod(M)(q).log(65537))
print(f"a2: {a2}. In interval: {inf <= a2 <= sup}")
k = (q - int(pow(65537, a2, M))) // M
# Assert correctness of the values
assert(k*M + pow(65537, a2, M) == q)
# solve using the parameters from the paper
factors = solve(M, n, a2, 5, 6, 0.5)
print(f"Known q: {factors}")

优化后的案例：

# attempt to find p
# Compute the right values for a and k
a1 = int(Zmod(M)(p).log(65537))
print(f"a1: {a1}. In interval: {inf <= a1 <= sup}")
k = (p - int(pow(65537, a1, M))) // M
# Assert correctness of the values
assert(k*M + pow(65537, a1, M) == p)
# solve using a smaller beta
factors = solve(M, n, a1, 5, 6, 0.1)
print(f"Known p: {factors}")

# attempt to find q
# Compute the right values for a and k
a2 = int(Zmod(M)(q).log(65537))
print(f"a2: {a2}. In interval: {inf <= a2 <= sup}")
k = (q - int(pow(65537, a2, M))) // M
# Assert correctness of the values
assert(k*M + pow(65537, a2, M) == q)
# solve using a smaller beta
factors = solve(M, n, a2, 5, 6, 0.1)
print(f"Known q: {factors}")

优化2：

调整M的值。（主要的优化）

类比已知p高位的coppersmith，此处M的大小类似于p已知位数的数量。

前面提到的此处利用coppersmith求解的条件是log~2~(M) > log~2~(N)/4，实际中的M要比这个需求的值大不少，为减少搜索空间，寻找一个更小的M‘，以满足：（这里好像没有证明更小的M和减少搜索空间的关系~~也可能是我学的太少了一眼看不出来~~）

N的因子与先前相同的形式（M’必须是M的除数）；
可以使用CHG（log~2~(M) > log~2~(N)/4）；
攻击的运行时间是最小的（尝试次数和每次尝试的时间应产生最小的时间）。

对于512位密钥，M中有39个因子，因此有2^39^个M的除数，无法全部测试。

但可以寻找由65537生成的群G’的阶|G’|（应该是对应M’）。事实上，|G’|是|G|的除数，而|G|本身是M的除数，因此其搜索空间较小：

def primorial(n):
    M = 1
    p = 1
    for i in range(n):
        p = next_prime(p)
        M *= p
    return int(M)
M = primorial(39)
print(M)
print(number_of_divisors(M))
order = Zmod(M)(65537).multiplicative_order()
print(order,M%order)
print(number_of_divisors(order))
"""
962947420735983927056946215901134429196419130606213075415963491270
549755813888  =2**39
2454106387091158800 1538361133389550470
76800
"""

意思大概是M‘可能值（549755813888）太多，直接测试很困难;而M‘对应的|G’|也是M对应的|G|的因子，又因为|G|的因子的可能值（76800）比较小，所以就比较好爆破。（因为一个|G‘|对应多个M’）

然后|G|是M除数这边好像不是很对，上面代码注释里有结果，不是0。不懂内~~

总之，遍历全部|G|因子，用以下函数寻找|G‘|对应的最大M’

def recover_M_prime_from_order(M, order):
    M_prime = M
    for p, e in factor(M):
        ordP = Zmod(p)(65537).multiplicative_order()
        if order % ordP != 0:
            M_prime /= p
    return int(M_prime)

M所有素因子对应的阶若不为|G|的因子则剔除，这里似乎还是没有解释完原理。

对M‘的寻找：

import pickle

M = primorial(39)

order = Zmod(M)(65537).multiplicative_order()
di = divisors(order)#order的全部正整数因子
print(f"Number of divisor of the order of M: {len(di)}")

# 使用pickle保存结果，以便在更改代码时无需重新计算
try:
    M_ps = pickle.load(open("save.txt", "rb"))
except FileNotFoundError:
    # 计算足够大的所有M_p
    M_ps = []
    treshold = log(n, 2)/4
    f = factor(M)
    for ordp in di:
        M_p = recover_M_prime_from_order(M, ordp)#这个函数的实现似乎没有
        if log(M_p, 2) >= treshold:
            M_ps.append(M_p)
    M_ps.sort()
    pickle.dump(M_ps, open("save.txt", "wb"))

print(f"Number of possible M': {len(M_ps)}")
"""
Number of divisor of the order of M: 76800
Number of possible M': 13004
"""