2022-08-08   10 m   1.5 k0 visits

RSA parity oracle例题复现

最近在比赛中碰到了RSA parity oracle攻击的题目，当时对这个攻击没有什么印象，赛后看wp复现了一遍，这里稍微总结一下。

[CTFshow七夕杯] 优势在我

题目源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from Crypto.Util.number import *
import hashlib
import sys
from private import d

def pr(x, end="\n"):
    sys.stdout.write(str(x)+end)
    sys.stdout.flush()

BANNER = """
...
"""

N = 18546721845979927569500143751660105533561486316231224465080625317376238264944740878457193385226698959802719372533690834284860737851929107163579187879895388120942312652954549671398264315985738386063687826049340153475764762320419809887400141782272319772175613926330746384510813184415900331770119033044622690940477810277396517358312757248120240055407842257982535105406966617903737782220404404644459553334905091694987679788339901767262741660223359618116200505397580036748964773373441655648565481823043475551779287949673519191553190302422175246969165641890331993628578551062334369824625164536808726394693221961254696074691
e = 65537
p = 24074624372939710957902553829568388349796810585932597965247721110129830468800036256026076982213498961372616008101708874099574700088150475222639563817914865052788850184089778132465415340980378135746900061263517304153485433985299953682148733981366808528082636204740025363446729188464380931250501761664305346381138286856186476986484913576109916879190154878781616175599052154216615394032414499234529973797040464698872321982946683153298157064531262284470661150270186224788419122959403896437988552792877168892664837002108590144855389176310488655364026719942320436915792611600545729690463037233338070404315644982404557646573
g = 2

with open("flag.txt", "rb") as f:
    flag = f.read()
flag = bytes_to_long(flag)
assert flag < N

def strange_tales(x):
    msg1 = b"Never gonna make you cry" + x
    msg2 = b"Never gonna say goodbye" + x
    return bytes_to_long(hashlib.sha512(msg1).digest() + hashlib.sha512(msg2).digest())

def full_of_foolish_talk(x):
    k = getRandomRange(0, p - 1)
    r = pow(g, k, p)
    e = strange_tales(str(r).encode() + b"Never gonna tell a lie and hurt you")
    s = (k - x * e) % (p - 1)
    return r, s

pr(BANNER)
pr(f"We're no strangers to love: {pow(flag, e, N)}")
pr("You know the rules and SO DO I")
while True:
    pr("> ", end="")
    c = int(input())
    m = pow(c, d, N)
    r, s = full_of_foolish_talk(m)
    pr(f"Never gonna give you up: {r}")
    pr(f"Never gonna let you down: {s}")

乍一看r和s，以为是一道DSA，其实半毛钱关系没有。题目中能对任意密文解密，并输出解密后明文m对应的r和s，其中有动态随机数k参与运算，我们很难构造r，s和m之间的关系来反推出m，正向分解N来破解RSA也不可能。

这里就是本题关键所在了，我们需要通过r和s来分析得到对应m的奇偶性，然后运用RSA parity oracle的思想来求出m。首先简单说一下RSA parity oracle攻击的思路。这一攻击的前提是需要能够进行任意密文的解密，并能得到解密明文的奇偶性，即对于任意c，能够知道的奇偶性，这样即可恢复所求明文。具体分析如下：

对于所求明文m，我们可以构造c来求出的奇偶性。然后由于2m为偶数，N为奇数，且有,若为奇数，则说明,即有;反之则有.这样我们就可以得到m的一个二分取值区间。然后我们继续迭代这样的构造，最终二分区间缩小为一个值时，该值即为最终的明文m。对于RSA而言，即是构造 继续说回此题，我们的目的即是通过r和s找出m的奇偶性。首先根据可以看到，p-1是偶数，那么s和k-x*e的奇偶性一致。这里k满足,k的奇偶性可以由r关于p的勒让德符号求出（因为k为偶数时，r必定是一个二次剩余），因此可以算出x*e的奇偶性。如果此时e也为奇数，那么也就可以得到x的奇偶性了。由于e是r的哈希，我们可以多次尝试，得到一个我们想要的奇数e，以算出当前m的奇偶性，进而用RSA parity oracle逐步二分得到flag。

解题脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import random
from pwn import *
from Crypto.Util.number import *
import gmpy2
import hashlib

sh = remote('pwn.challenge.ctf.show',28027)
context.log_level='debug'
l64 = lambda      :u64(sh.recvuntil("\x7f")[-6:].ljust(8,"\x00"))
l32 = lambda      :u32(sh.recvuntil("\xf7")[-4:].ljust(4,"\x00"))
sla = lambda a,b  :sh.sendlineafter(str(a),str(b))
sa  = lambda a,b  :sh.sendafter(str(a),str(b))
lg  = lambda name,data : sh.success(name + ": 0x%x" % data)
se  = lambda payload: sh.send(payload)
rl  = lambda      : sh.recvline()
rv  = lambda n    : sh.recv(n)
sl  = lambda payload: sh.sendline(payload)
ru  = lambda a     :sh.recvuntil(str(a))
rud  = lambda a     :sh.recvuntil(str(a),drop=True)

N = 18546721845979927569500143751660105533561486316231224465080625317376238264944740878457193385226698959802719372533690834284860737851929107163579187879895388120942312652954549671398264315985738386063687826049340153475764762320419809887400141782272319772175613926330746384510813184415900331770119033044622690940477810277396517358312757248120240055407842257982535105406966617903737782220404404644459553334905091694987679788339901767262741660223359618116200505397580036748964773373441655648565481823043475551779287949673519191553190302422175246969165641890331993628578551062334369824625164536808726394693221961254696074691
E = 65537
p = 24074624372939710957902553829568388349796810585932597965247721110129830468800036256026076982213498961372616008101708874099574700088150475222639563817914865052788850184089778132465415340980378135746900061263517304153485433985299953682148733981366808528082636204740025363446729188464380931250501761664305346381138286856186476986484913576109916879190154878781616175599052154216615394032414499234529973797040464698872321982946683153298157064531262284470661150270186224788419122959403896437988552792877168892664837002108590144855389176310488655364026719942320436915792611600545729690463037233338070404315644982404557646573
g = 2

def interact(c):
	sla('> ',str(c))
	ru('Never gonna give you up: ')
	r=int(rl())
	ru('Never gonna let you down: ')
	s=int(rl())
	return r,s

def H(r):
	x=str(r).encode() + b"Never gonna tell a lie and hurt you"
	msg1 = b"Never gonna make you cry" + x
	msg2 = b"Never gonna say goodbye" + x
	return bytes_to_long(hashlib.sha512(msg1).digest() + hashlib.sha512(msg2).digest())

def get_parity(r,s):
	e=H(r)
	if e%2:
		sp=s%2
		kp=1 if gmpy2.legendre(r,p)==-1 else 0
		xp=sp^kp
		return xp
	else:
		return None

ru("We're no strangers to love: ")
encflag=int(rl())
lb,ub,c=[0,N,pow(2,E,N)*encflag%N]
cnt=0
while True:
	r,s=interact(c)
	parity=get_parity(r,s)
	if parity is None:
		continue
	if parity==1:
		lb=(lb+ub)//2
	else:
		ub=(lb+ub)//2
	c=pow(2,E,N)*c%N
	cnt+=1
	if lb==ub:
		print(cnt)
		print(long_to_bytes(lb))
		exit(0)
p.interactive()

这里直接用gmpy里的legendre，sage里的legendre_symbol跑起来有点慢。

总结一下RSA parity oracle攻击的条件就是：需要能够任意密文的解密，并能得到明文的奇偶性。满足这一条件就可以考虑采用这种思想了。

在corctf貌似看到了该手法的变种，等赛后有了wp再来复现一波~

补充复现：

[corCTF 2022] generous

题目源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#!/usr/local/bin/python
from Crypto.Util.number import getPrime, inverse, bytes_to_long
from random import randrange

with open("flag.txt", "rb") as f:
	flag = f.read().strip()

def gen_keypair():
	p, q = getPrime(512), getPrime(512)
	n = (p**2) * q
	while True:
		g = randrange(2, n)
		if pow(g, p-1, p**2) != 1:
			break
	h = pow(g, n, n)
	return (n, g, h), (g, p, q)

def encrypt(pubkey, m):
	n, g, h = pubkey
	r = randrange(1, n)
	c = pow(g, m, n) * pow(h, r, n) % n
	return c

def decrypt(privkey, c):
	g, p, q = privkey
	a = (pow(c, p-1, p**2) - 1) // p
	b = (pow(g, p-1, p**2) - 1) // p
	m = a * inverse(b, p) % p
	return m

def oracle(privkey, c):
	m = decrypt(privkey, c)
	return m % 2

pub, priv = gen_keypair()
n, g, h = pub
print(f"Public Key:\n{n = }\n{g = }\n{h = }")
print(f"Encrypted Flag: {encrypt(pub, bytes_to_long(flag))}")
while True:
	inp = int(input("Enter ciphertext> "))
	print(f"Oracle result: {oracle(priv, inp)}")

这题仍然是有一个明显的parity oracle，只不过加密系统不再是RSA。注意到这里公钥加密是模n的，而私钥解密出的m则是模p的。由于p是未知的，因此我们无法像之前一样设置上下界来准确地二分求出m。但是，此题我们可以换一个思路，利用parity oracle去求p。原理同前一题类似：

我们知道p是小于的，因此我们可以构造，然后利用parity oracle得到的奇偶性，若为奇数，则说明m大于p；否则，m小于p。接着，我们继续二分缩小p的范围，最终能够求出p。

求出p之后就能算出私钥，然后直接解密即可。

解题脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
from random import randrange
from pwn import *
from Crypto.Util.number import *
import gmpy2
import hashlib

sh = remote('be.ax',31244)
#context.log_level='debug'
l64 = lambda      :u64(sh.recvuntil("\x7f")[-6:].ljust(8,"\x00"))
l32 = lambda      :u32(sh.recvuntil("\xf7")[-4:].ljust(4,"\x00"))
sla = lambda a,b  :sh.sendlineafter(str(a),str(b))
sa  = lambda a,b  :sh.sendafter(str(a),str(b))
lg  = lambda name,data : sh.success(name + ": 0x%x" % data)
se  = lambda payload: sh.send(payload)
rl  = lambda      : sh.recvline()
rv  = lambda n    : sh.recv(n)
sl  = lambda payload: sh.sendline(payload)
ru  = lambda a     :sh.recvuntil(str(a))
rud  = lambda a     :sh.recvuntil(str(a),drop=True)

def get_parity(c):
	sla('ciphertext> ',str(c))
	ru('Oracle result: ')
	parity=int(rl())
	return parity

def encrypt(pubkey, m):
	n, g, h = pubkey
	r = randrange(1, n)
	c = pow(g, m, n) * pow(h, r, n) % n
	return c

def decrypt(privkey, c):
	g, p, q = privkey
	a = (pow(c, p-1, p**2) - 1) // p
	b = (pow(g, p-1, p**2) - 1) // p
	m = a * inverse(b, p) % p
	return m

ru('n = ')
n=int(rl().strip())
ru('g = ')
g=int(rl().strip())
ru('h = ')
h=int(rl().strip())
ru("Encrypted Flag: ")
encflag=int(rl())
lb,ub=[0,2**512]
cnt=0
while True:
	tmpm=(lb+ub)//2
	c=encrypt((n,g,h),tmpm)
	parity=get_parity(c)
	if parity==1:
		ub=tmpm
	else:
		lb=tmpm
	cnt+=1
	print(lb,ub)
	if ub-lb<=1:
		print(cnt)
		p=lb
		assert isPrime(p)
		q=n//(p**2)
		flag=decrypt((g,p,q),encflag)
		print(long_to_bytes(flag))
		exit(0)
p.interactive()

RSA parity oracle例题复现

https://litao6666.github.io/202208/1880d078.html

Author

zealot

Posted on

2022-08-08

Updated on

2022-08-27

Licensed under

Catalogue

×