Automne's Shadow.

RSA LSB Oracle攻击原理分析

pwntools rsa lsb oracle
2020/02/16 Share

Crypto

这是RSA加解密系统里的一种攻击模式，适用于可以选择密文攻击和泄露最低有效位的场景。

RSA的加解密公式：

c=me%nc = m^e\%n

m=cd%nm = c^d\%n

d=inverse(e,phi)d = inverse(e,phi)

phi=(p−1)∗(q−1)phi = (p-1)*(q-1)

n=p∗qn = p*q

首先看2019年的BambooFox CTF里的这道oracle题

server.py

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
#!/usr/bin/env python3
from Crypto.Util.number import *

with open('flag', 'rb') as f:
    flag = int.from_bytes(f.read(), 'big')

def genkeys():
    e = 65537
    while True:
        p, q = getPrime(512), getPrime(512)
        n, phi = p * q, (p - 1) * (q - 1)
        if GCD(e, phi) == 1:
            d = inverse(e, phi)
            return n, e, d

def menu():
    print('1) Info')
    print('2) Decrypt')
    print('3) Exit')

def main():
    n, e, d = genkeys()

    while True:
        menu()
        option = input('> ')
        if option == '1':
            c = pow(flag, e, n)
            print(f'c = {c}')
            print(f'n = {n}')
        elif option == '2':
            c = int(input('c = '))
            m = pow(c, d, n)
            print(f'm = {m % 3}')
        else:
            return

main()

代码容易阅读，RSA的加密系统打印出密文c和模数n，解密系统只打印出明文m模3之后的内容m%3，泄露了LSB的值。一般的 RSA LSB Oracle攻击都是返回m%2后的值，根据返回值的奇偶性，利用二分法计算。

mod 2场景

攻击原理是利用二分算法将RSA明文的范围逼近到足够狭窄的空间，从而确定出明文。

记明文为m，模数为n，加密指数为e，密文为c，那么就有c = m^e % n，可以构造出c’ = (2^e * c ) % n = (2 * m)^e % n，因为m的2倍可能大于n，所以解密得到的明文m’ = 2 * m % n，又因为服务端通过 m % 2 的形式泄露最低有效位，即LSB，m % 2 的最低有效位为0和1，因为模数n为质数，2 * m为偶数，如果LSB是0，说明2 * m % n是偶数，2 * m没有超过n，即0<m<n/2；反之n/2<m<n。这样可以通过二分法确定出m的范围，然后再构造c’’ = (4^e * c ) % n = (4 * m)^e % n，解密后的明文m’’ = 4 * m % n，于是可以进一步判断m和n/4的关系，以此类推。

直接看案例，下面的服务端代码对上面的代码稍作修改，即输出m % 2

server_mod2.py

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
#!/usr/bin/env python3
from Crypto.Util.number import *

with open('flag', 'rb') as f:
    flag = int.from_bytes(f.read(), 'big')

def genkeys():
    e = 65537
    while True:
        p, q = getPrime(512), getPrime(512)
        n, phi = p * q, (p - 1) * (q - 1)
        if GCD(e, phi) == 1:
            d = inverse(e, phi)
            return n, e, d

def menu():
    print('1) Info')
    print('2) Decrypt')
    print('3) Exit')

def main():
    n, e, d = genkeys()

    while True:
        menu()
        option = input('> ')
        if option == '1':
            c = pow(flag, e, n)
            print(f'c = {c}')
            print(f'n = {n}')
        elif option == '2':
            c = int(input('c = '))
            m = pow(c, d, n)
            print(f'm = {m % 2}')
        else:
            return

main()

本地使用socat监听服务

1
socat -T60 tcp-listen:1337,reuseaddr,fork EXEC:"python3 -u server_mod2.py"

直接看利用代码

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
#encoding=utf-8

from pwn import *
from binascii import a2b_hex
import decimal
from Crypto.Util.number import *


def lsbOracle(c):
	r.recv()
	r.sendline("2")
	r.recvuntil("c = ")
	r.sendline(str(c))
	m = r.recvline().strip()[3:]
	print("m: "+m)
	m = int(m)
	return m

def revealFlag(c,n):
	k = n.bit_length() #二进制长度数，这里是1024
	decimal.getcontext().prec = k #设定小数点精度
	low = decimal.Decimal(0)
	high = decimal.Decimal(n)
	for i in range(k):
		plaintext = (low + high) / 2
		state = lsbOracle(c)
		if not state:  # state = 0
			high = plaintext #0<high<n/2
		else:
			low = plaintext
		c = (c * pow(2,e,n)) % n
		print i,state,int(high-low)
	return int(high)
	

if __name__ == '__main__':
	r = remote("127.0.0.1",1337)
	e = 65537
	r.recv()
	r.sendline("1")
	c = r.recvline().strip()[3:]
	print("c: "+c)
	c = int(c)
	n = r.recvline().strip()[3:]
	print("n: "+n)
	n = int(n)
	res = revealFlag((c * pow(2,e,n)) % n, n)
	#res = 1624569960321307593137113337496607296102769342145048575242
	print res
	res_hex = hex(res)
	#print res_hex
	print a2b_hex(res_hex[2:]) #一种方式打印flag
	print long_to_bytes(res) #另一种方式打印flag

简单说明一下，lsbOracle©函数用于选择密文攻击，发送构造的密文得到的m % 2的值，表现为0或1；revealFlag(c,n)函数则是执行二分法的函数，默认传入的(c * pow(2,e,n)) % n，实际就是构造的pow(2m,e,n) % n通过二分法确定出明文m和n/2的关系；然后在循环里再赋值c = (c * pow(2,e,n)) % n，从而进一步得到明文m和n/4的关系，最后一直趋近于真实的明文。

运行后，即可得到flag

automne

mod 3和mod xx场景

上面提到的这种二分法，依我看只适用于明文m % 2的场景，通过返回的LSB奇偶性来逼近结果。

对其他数取余的场景需要进一步分析适用的攻击模式。

automne

开始发送原始密文c，服务端返回了原始明文m%3的值

将明文m表示成3的多项式：

m=an∗3n+an−1∗3n−1+...+a1∗3+a0m = a_n*3^n + a_{n-1}*3^{n-1} + ... + a_1*3 + a_0

于是 LSB记为p，有

p=m%3=a0p = m \% 3 = a_0

a0的值知道了

接下来开始构造(pow(3,-e)*c) % n这样的密文，发送到服务端，得到的明文m’也就是pow(3,-1)m

原理如下图：

(3−e∗c)%n=3−e∗(me%n)=(3−1∗m)e%n(3^{-e}*c)\%n = 3^{-e}*(m^e\%n) = (3^{-1}*m)^e\%n

于是p的值

p=(3−1∗m)%3p = (3^{-1}*m)\%3

3−1∗m=an∗3n−1+an−1∗3n−2+...+a1+a0∗3−13^{-1}*m = a_n*3^{n-1}+a_{n-1}*3^{n-2}+...+a_1+a_0*3^{-1}

于是有

p=[a1+(a0∗3−1%n)]%3p = [a_1 +(a_0*3^{-1}\%n)] \%3

a1=p−(a0∗3−1%n)]%3a_1 = p - (a_0*3^{-1}\%n)] \%3

a1的值知道了

然后再发送(pow(3,-2e)*c) % n这样的密文，得到明文m’'也就是pow(3,-2)m

a2的值知道了

…

这样就可以得到所有多项式的参数，最终拼接起来就是明文m的值。

利用代码

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
#encoding=utf-8

from pwn import *
import decimal
from Crypto.Util.number import *
from Crypto.PublicKey import RSA


def lsbOracle(c):
	r.recv()
	r.sendline("2")
	r.recvuntil("c = ")
	r.sendline(str(c))
	m = r.recvline().strip()[3:]
	print("m: "+m)
	m = int(m)
	return m

if __name__ == '__main__':
	r = remote("127.0.0.1",1337)
	e = 65537
	r.recv()
	r.sendline("1")
	c = r.recvline().strip()[3:]
	print("c: "+c)
	c = int(c)
	n = r.recvline().strip()[3:]
	print("n: "+n)
	n = int(n)
	a = 0
	plaintext = 0
	i = 0
	f = 0
	while True:
	#for i in range(0,400):
		inv = inverse(3,n) # pow(3,-1)
		c1 = (c * pow(inv,e*i,n)) % n
		p = lsbOracle(c1)
		print p
		aa = (p - (a*inv) % n) % 3
		print aa
		print "****" + str(i)
		if aa == 0:
			f += 1
			if f == 20:
				break
		else:
			f = 0
		a = a*inv + aa
		plaintext = 3**i*aa + plaintext
		print long_to_bytes(plaintext)
		i += 1
		'''content = long_to_bytes(plaintext)
		if "BAMBOOFOX" in content:
			break''' 
	print long_to_bytes(plaintext)

代码和上面的原理描述是一致的，需要解释一下的是下面这段代码

1
2
3
4
5
6
if aa == 0:
			f += 1
			if f == 20:
				break
		else:
			f = 0

这是用来判断所有参数是不是都计算完成了，使用f这样的累加器，如果多项式的参数在连续20次(或者少点)循环里都是0的话，可以认为计算完成，可以break了。

automne

这种方法是通用的，如果服务端只打印出m%1337的值，同样可以使用上面的方法修改对应的代码从而计算出明文。

参考链接

[https://github.com/kuruwa2/ctf-writeups/tree/master/BambooFox CTF/oracle](https://github.com/kuruwa2/ctf-writeups/tree/master/BambooFox CTF/oracle)

https://blog.bi0s.in/2019/09/29/Crypto/PubKey-Enc/InCTFi19-waRSAw/

https://xz.aliyun.com/t/2446#toc-22

题外话

Hexo默认对markdown的公式是不支持的，参考https://blog.chaos.run/dreams/hexo-enable-math-support/可以让Hexo博客支持公式模块，我的主题是archer，同样适用。

  1. 卸载默认的渲染引擎，安装新的

    1
    2
    npm un hexo-renderer-marked --save
    npm i hexo-renderer-markdown-it-plus --save

  2. 修改文章模板

    修改/scaffolds/post.md 文件，在 — 前添加一行 math: false 。故如果某篇文章想启用数学公式支持，需将 false 改为 true 。

  3. 修改主题布局模板

    编辑 Hexo/themes/archer/layout/_partial/base-head.ejs ，在前加入如下代码

    1
    <link href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css" rel="stylesheet" type="text/css">

  4. 编辑配置文件

    在站点配置文件 _config.yml 中加入如下配置：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    markdown_it_plus:
      highlight: true
      html: true
      xhtmlOut: true
      breaks: true
      langPrefix:
      linkify: true
      typographer:
      quotes: “”‘’
      pre_class: highlight

原文作者: Automne

原文链接: https://ce-automne.github.io/2020/02/16/RSA-LSB-Oracle攻击原理分析/

发表日期: February 16th 2020, 2:53:00 pm

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. mod 2场景
  2. 2. mod 3和mod xx场景
  3. 3. 参考链接
  4. 4. 题外话
Total : 62
2021
2020
2019
2018
2017
lfsr z3 python reverse fat git broadcastreceiver sha-1 cbc sqli sqlite golang race condition luks hashcat photorec MAC sso oauth 2.0 padding oracle csp xss abe vdex ransomware frida ndk pwntools hashpumpy sourceleakhacker ecb socat fastjson JdbcRowsetImpl idea servlet volatility inet_aton boneh durfee lcg rabin egcd cipolla's algorithm spi snakeyaml ScriptEngineManager malware codereflect mysql yara plugin deserialization log4j rsa binary javascript prototype pollution nodejs shiro ysoserial primefac rsatool ssl AES tshark gmpy2 RsaCtfTool Hex flask ssti ecc Modular operation WebGoat8 order by tomcat nim game .iso gpg outguess sage google cloud sdk zsteg base58 fermat multi-primes prng rmi jndi Paillier Cryptosystem rsa lsb oracle SQL Injection ping delay xor CAS 单点登录 渗透测试 weblogic xxe reflect 010 editor gcd
Crypto Android Web Forensics Misc