浅析RSA Padding Attack

前言

近日在复盘一些Crypto的题目，做到了N1CTF的一道rsapadding，进行了一些拓展，于是进行了一些分析记录，有了这篇文章

题目分析

题目已开源在

https://github.com/Nu1LCTF/n1ctf-2018/tree/master/source/crypto/rsapadding

主要代码为

m = '*****************'
n = 21727106551797231400330796721401157037131178503238742210927927256416073956351568958100038047053002307191569558524956627892618119799679572039939819410371609015002302388267502253326720505214690802942662248282638776986759094777991439524946955458393011802700815763494042802326575866088840712980094975335414387283865492939790773300256234946983831571957038601270911425008907130353723909371646714722730577923843205527739734035515152341673364211058969041089741946974118237091455770042750971424415176552479618605177552145594339271192853653120859740022742221562438237923294609436512995857399568803043924319953346241964071252941
e = 3
welcom()
if cmd():
    f = open("/root/crypto/file.py")
    print(f.read())
    return
mm = bytes_to_long(m)
assert pow(mm, e) != pow(mm, e, n)
sys.stdout.write("Please give me a padding: ")
padding = input().strip()
padding = int(sha256(padding.encode()).hexdigest(),16)
c = pow(mm+padding, e, n)
print("Your Ciphertext is: %s"%c)

意思很简单

1.pow(mm, e) != pow(mm, e, n)

2.输入一个值

3.将输入的值sha256，记做padding

4.利用rsa加密m+padding

值得注意的是，e=3，padding可控

那么我们拥有的条件只有

n,e,c,padding

所以这里的攻击肯定是要从可控的padding入手了

初步推导

我们可以随便构造一对已知padding的密文，得到

此时，我们可以设

利用这两个式子，我们可以得到如下线性关系

即方程形式为

其中

即

我们有

我们知道

那么将其带入得到

我们将c1展开得到

我们将这个式子带入得到

于是便一筹莫展

可求证明

上述的推导我们漏了一个非常重要的信息

那么不难发现

同理，我们还可以构造方程

如此一来，我们可以得到

是下列方程组的一个解

那么一定可以有

可以被写成

如此一来，只要

我们由e=3可以得知

只有唯一解，所以k1和k2必互素，所以这里是M2一定是可求的

Related Message Attack

payload

既然推导出了公式，写脚本即可

def getM2(a,b,c1,c2,n):
    a3 = pow(a,3,n)
    b3 = pow(b,3,n)
    first = c1-a3*c2+2*b3
    first = first % n
    second = 3*b*(a3*c2-b3)
    second = second % n
    third = second*gmpy2.invert(first,n)
    third = third % n
    fourth = (third+b)*gmpy2.invert(a,n)
    return fourth % n
m = getM2(a,b,c1,c2,n)-padding2
print libnum.n2s(m)

Coppersmith’s short-pad attack

上述情况是e=3时候，我们可以根据

推导出m

那么当e不是3的时候怎么办呢？

这里稍作拓展，我们可以用Coppersmith’s short-pad attack，即padding过短引起的攻击

脚本如下

https://github.com/ValarDragon/CTF-Crypto/blob/master/RSA/FranklinReiter.sage

后记

根据这一次学习，不难发现在存在padding的情况下，rsa也存在各种风险：

1.若e=3，则可以利用Related Message Attack

2.若e不为3，但padding过短，则可以利用Coppersmith’s short-pad attack