RSA专题——泄露与攻击

密码学 9个月前 admin
219 0 0
根据信息论之父 Shannon (香农) 的理论,密码体制的安全应当只取决于密钥的安全,而不取决于对密码算法的保密。因此现在大多数的密码算法都是公开的。不过算法可以公开,加密过程中的中间数据可不能公开。但是或多或少,我们在实际操作中总是会在不经意间中导致信息的泄露。接下来我们将讨论在获得各种泄露信息的场景下如何对其进行利用,对 RSA 公钥加密系统进行攻击,获取解密私钥,获取原明文信息等。

泄露

之前我们提到过,为了提高 RSA 解密的效率,我们可以选择比较小的私钥,但同时我们也发现私钥太小会带来一定的安全隐患。那么还有没有什么方法可以在保证安全的前提下,提高效率呢?我们回顾 RSA 的解密公式: ,其中  是两个大素数。那么我们不难得到这样两条同余式

此时由于是在模数  下在进行计算,那么处理的数据都会小于 ,数据小了,那么相应的计算速度则会得到提升。那么此时读者可能会有疑惑,在做加密前我们是要求 ,因此我们在正常解密后得到的  与 原来的  是相等的。但此时,这里的两条解密式子经过计算后得到的得到的分别是 ,我们并不能保证  或者 ,因此此时得到的 “明文” 并不一定会是我们想要的“明文“,很可能还是一串乱码。那么我们该如何恢复明文呢?答案就是对  运用中国剩余定理进行组合,我们就能够得到  了,从而也就恢复了明文。
还有一个问题,如果  是根据  计算而来的话,其也肯定会比  大,那么我们在进行计算的时候该怎么处理它呢?这里根据费马小定理,我们可以得出,,因此我们定义了两个新的变量,分别是 
可以预见,由于中国剩余定理的存在,我们也是可以通过  组合计算得到 ,也就是私钥,因此, 的泄露与私钥  的泄露是等价的。
下面我们给出完整的利用   对明文  进行恢复及相应公式的推导。

由 
 
得  
设  
则  
由费马小定理,
所以  
同理  
然后我们就有同余式方程组: 
 
最后使用中国剩余定理恢复  就好了(

python代码:
from Crypto.Util.number import *

def decrypt(c,dp,dq,p,q):
    mp = pow(c,dp,p)
    mq = pow(c,dq,q)

    # CRT
    a = inverse(p,q)
    b = inverse(q,p)
    m = (mp*p*a + mq*q*b) % (p*q)
    return m

泄露

在上面的攻击中,我们使用  可以计算得到 ,使用  可以计算得到 ,随后利用中国剩余定理对  进行组合才能给够恢复 。那么如果我们无法同时获得  呢?如果仅有一个  我们是否能够顺利恢复  呢?
答案是可以,不过既然少使用了一个参数,相应的我们就需要付出一些”额外代价“,并且也需要满足一些额外的条件。”额外代价“就是我们需要进行一定的爆破计算,而爆破的范围则由公钥  决定,因此额外条件就是这个公钥  不能够太大,不能够超出我们可以遍历的范围。下面我们给出完整的公式推理过程

已知:公钥  以及 
求解:
已知条件:
    
由上式可以得到  
即  ①
又  ②
①带入②得到: 
即 
整理一下  
因为 
所以 
我们设 
的范围为  
那么我们可以遍历  种可能就可以求出 

有了  后其实就意味着我们成功分解了 ,从而也就能够顺利的解密密文,获取明文了。
下面给出利用  分解  获取  的 python 代码实现。
def rsa_nedp(n,e,dp):
    for i in range(1,e):
        if (dp*e-1) % i == 0:
            tmp = (((dp*e-1)//i) + 1)
            if n % tmp == 0:
                p = tmp
                q = n // p
                return p,q

RSA LSB Oracle Attack

上面的两种情况读者可能会觉得泄露的信息也太多了,这都相当于把私钥都给出来了,那么如果只泄露很少的信息呢?
:怎么个少呢?
:一比特行不行?
:也不是不行!
如果存在这么一台Oracle,它使用 RSA 公钥加密系统,并且我们可以访问以获取其使用 RSA 的公钥,然后它提供一个解密服务:就是用户可以对其发送密文,它会使用自己的 RSA 私钥对明文进行解密,随后返回解密结果的最后一个比特。那么我们该如何利用这样一台 Oracle 对一条由其公钥加密的密文进行解密呢?在一次 RSA 加解密中,我们设明文为 ,模数为 ,加密指数为 ,密文为 。那么我们可以构造出 , 那么由 Oracle 解密后就会得到明文  。由 Oracle 我们还能够知道  的最低位是 1 还是 0。 由于  是奇数,而  肯定是偶数,所以如果最低为是 0,说明  是偶数,比  小,于是我们得到 ,反之则。然后以此类推,我们可以再构造 ,以更进一步的获取  和  之间的大小关系。每一次交互  的取值范围都会被压缩一半,因此  次交互后  就能够被确定,从而达到了解密  的目的。

注:类似 2 % 3 = 2 是偶数,而 4 % 3 = 1 由于 ,取模后奇偶性会发生翻转而变为奇数。以此类推,构造密文  使其解密后为 ,判断 的奇偶性可以知道  和 (或 ) 的大小关系。于是我们就有了一个二分算法,可以在对数时间内将  的范围逼近到一个足够狭窄的空间。

下面给出python代码的实现
def oracle(c):
    '''
    c: ciphertext
    rev: last bit of plaintext
    '''

    
    sh.recvuntil(">")
    sh.sendline(str(c))
    rev = sh.recvuntil("n")[:-1]
    return int(rev)

def lsb_oracle_attck(c,n,t):
    L=0
    H=n
    for i in range(1024):
        c = (t*c) % n
        if oracle(c) == 0:
            H = (L+H) // 2
        else:
            L = (L+H) // 2
    return long_to_bytes(L)

lsb_oracle_attck(c, n, pow(2,e,n))
上面的脚本很好理解,就是一个经典的二分法,但是由于整除的关系在最后一个字节会出现一点误差,下面则是一个没有误差的版本:
def lsb_oracle_attack(encrypted_flag, n, e):

    flag_count = n_count = 1
    flag_lower_bound = 0
    flag_upper_bound = n
    ciphertext = encrypted_flag
    mult = 1
    while flag_upper_bound > flag_lower_bound + 1:
        ciphertext = (ciphertext * pow(2, e, n)) % n
        flag_count *= 2
        n_count = n_count * 2 - 1
        print("bit = %d" % mult)
        mult += 1
        data=oracle(str(ciphertext))
        if(data==1):
            flag_upper_bound = n * n_count // flag_count
        else:
            flag_lower_bound = n * n_count // flag_count
            n_count += 1
    return flag_upper_bound

Bleichenbacher’s attack(Chosen Ciphertext Attacks)

如果读者仍觉得上面这样一个 Oracle 的存在不太现实,那么接下来我们就介绍一个现实中真实存在的攻击(读者可以搜索 Return Of Bleichenbacher’s Oracle Threat 了解详情)。由 Bleichenbacher 发现的一个针对 RSA-PKCSv1.5 填充方案的攻击,该攻击能够恢复任意由 RSA 加密的,使用 PKCSv1.5 填充方案的密文。

PKCSv1.5 填充方案

由于篇幅的原因,我们直接给出填充规则,设  为原始数据, 为填充数据(其中不存在 x00), 为填充数据,那么就有

随后, 会经过 RSA 加密为密文  然后进行消息的传递。

攻击方案

该攻击的实现场景是当用户将密文  传递给服务器后,服务器会使用私钥对  进行解密得到 ,然后判断  是否符合 PKCS 1.5 的填充规则(PKCS conforming),如果不符合,则返回报错,如果符合,则进行进一步得解填充(unpadding)获取原始消息  以进行接下来得运算。
那么 Bleichenbacher 就是仅根据服务器是否返回填充报错这么一个信息,从而对密文进行了成功的解密。(在现实应用中原始信息  一般是通讯双方的会话密钥,如果能够解密密文,即意味着通讯双方之间所有的加密通话都将被解密)
Bleichenbacher’s 攻击手法分为以下几个阶段:
  1. 第一阶段 Blinding
    给到一个整数 ,随机选取整数 ,通过 oracle 去确认,当  满足 PKCS conforming的时候,我们设定

  2. 第二阶段 Searching for PKCS conforming message

    a. Starting the search. 如果 ,我们开始寻找最小的  使得  是 PKCS conforming

    b. Searching with more than one interval left. 如果,并且  中的区间数量大于 1,那么继续寻找最小的  使得  是 PKCS conforming

    c. Searching with one interval left. 如果  只包含一个区间(即 ),那么从小开始选取 ,其中

    直到  是 PKCS conforming
  3. 第三阶段 Narrowing the set of solutions 当找到  后,我们开始计算新的 :

  1. 第四阶段 computing the solution. 如果  只包含一个长度为 1 的区间(即 ,那么我们就有 ,否则 ,继续回到第二阶段。

注:

  1. 在第一阶段中,因为 c 解密后本身就是 PKCS conforming 所以可以跳过这个阶段,然后设置 $s_0 = 1$。

2. 在 2.a 中,我们从 $s_1 = lceil n / 3B rceil$ 开始寻找,因为不可能存在小于该值的 $s_1$ 满足 $m_0s_1$ 符合 PKCS conforming。可以简单计算一下,要使 $m_0s_1$ 满足 PKCS conforming,其中 $s_1 ne 1$,必须要被 n 取余过,也就是 $m_0 s_1 gt n$,因为 $m0 in [2B,3B]$,所以 $s_1 gt frac{n}{m_0} ge frac{n}{3B}$

3. 在 2.c 中 $r_i$ 的选取是因为我们想让新的区间大小为原来一半,($r_i$ 为原来两倍的时候,$s_i$ 也会为原来两倍左右,而间隔大约为 $B/s_i$)类似于二分法

4. 在第三阶段中,区间边界的选取是在取一个交集,我们根据 $s_i$ 算出来的区间为 $left [ left lceil frac{2B+rn}{s_i} right rceil,left lfloor frac{3B-1+rn}{s_i}) right rfloor right ]$,因为

对于下面  的选取,是需要保证新区间和原来的区间有交集,即新区间的上界要大于原来区间的下界,新区间的下届要小于原来区间的上界

  1. 如果在第三阶段中有多个满足条件的 r 值,则  中就会产生多个没有交集的区间,但只有其中一个区间是包含  的,此时进入2.b,另外的无效区间,会在增大  的过程中,由于选取不到合适的 r 值(即 )而被丢弃。那些无效区间中的值  是和  选取了同样,但是在不同  值下也满足 PKCS conforming,可以说是碰巧,所以解决这种碰巧的方式就是继续增加 ,取这些碰巧区间的交集,他们迟早会是一个空集。当没有碰巧区间的时候,我们就可以进行加速,将剩下的区间进行二分。可以理解为在剩下区间中选一个大小为原来一半的区间,然后查验里面是不是包含 ,显然这样的概率相对来说是很高的,所以到后面的阶段我们选取的  使得  是 PKCS conforming 的可能性也很大。
下面给出 python 代码实现
def Bleichenbachers_attack(e,n,c0,s1):
    print("step 1")
    e = e
    n = n
    c = c0
    k = 64
    B = 2**(8*(k-2))
    Mi = set([(2 * B, 3 * B - 1)])
    si = 1
    count = 1
    while True:
        print("step 2")
        si_1 = si     
        Mi_1 = Mi
        if count == 1:
            print("step 2.a")
            si = s1
            while True:
                ans = inter(si)
                if ans:
                    print(si)
                    break     
                si+=1

        elif len(Mi_1)>1:
            print("step 2.b")
            si = si_1 + 1  
            while True:
                ans = inter(si)
                if  ans:
                    break
                si += 1   
        else:
            print("step 2.c")
            a = list(Mi_1)[0][0]
            b = list(Mi_1)[0][1]
            ri = ((b * si_1 - 2 * B) // n) * 2
            FLAG = True
            while FLAG:
                si = (2 * B + ri * n) // b
                si_max = (3 * B + ri * n) // a
                while si <= si_max:
                    ans = inter(si)
                    if ans:
                        FLAG = False
                        break    
                    si += 1  
                ri+=1
        Mi = set()
        print("step 3")
        for a,b in Mi_1:
            r = (a * si - 3 * B + 1)// n
            r += 1 if ((a * si - 3 * B + 1) % n > 0else 0
            r_max = (b * si - 2 * B) // n 
            while r <= r_max:
                MIN = (2*B+r*n)//si
                MIN += 1 if  (2*B+r*n) % si > 0 else 0
                MIN = max(a,MIN)
                MAX = ((((3*B)-1)+(r*n))//si)
                MAX = min(b,MAX)
                Mi.add((MIN,MAX))
                r+=1
        print(Mi)
        if len(Mi)==1
            print("step 4")
            a = list(Mi)[0][0]
            b = list(Mi)[0][1]
            print('a-b:',a-b)
            if a == b:
                global TIMES
                print(TIMES)
                message = long_to_bytes(a)
                print(message)
                return message
        count += 1
PS:该漏洞的存在是由于服务端对不同类型的错误(包括填充方案是否正确,协议版本号是否正确,原始信息长度是否正确等)有不同的回复,因此修复方案则是服务端对所有错误都进行一致的回复,让攻击者无法判断真实的错误类型。

小结

在这一篇中,我们简单介绍了两种在使用 RSA 公钥加密系统时一些参数泄露导致的攻击。除去参数泄露,在加密过程中一些信息数据的泄露也很有可能导致加密数据的恢复,因此即使使用了安全的加密算法,也不一定就意味着数据的百分百安全。

原文始发于微信公众号(山石网科安全技术研究院):RSA专题——泄露与攻击

版权声明:admin 发表于 2023年5月30日 上午11:41。
转载请注明:RSA专题——泄露与攻击 | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...