python-rsa签名伪造漏洞(CVE-2016-1494)

作者: 分类: CTF,Python,Security 时间: 2017-05-22 评论: 1条评论

此次也是因为在RCTF里遇到了两道RSA的题目,才因此去研究python-rsa签名伪造漏洞这东西,过程曲折,但是也挺有趣,记录下来和大伙儿分享一下。

此次成果也是站在前人的肩膀上去研究的,参考文章的链接在底下都有,大家可移步过去看看(对于原理的剖析,那几篇文章讲的很好)。

0x00 Python-RSA签名伪造漏洞原理

首先,RSA是非对称加密算法,也就是说RSA存在公私钥,RSA可用于数据加密传输(传输对称加密的密钥),也可以进行数字签名,两者区别在于:

RSA用于加密时:
    公钥加密,私钥解密
RSA用于数字签名时:
    私钥加密,公钥解密

如果还不理解可以花三分钟看这里《数字签名是什么?》

RSA

此图是之前写的文章里的一张关于RSA里涉及到的数的含义,包括E,N,p,qC(Cipher),P(Plaintext)

下面说下RSA签名验签原理,RSA签名使用的方案为PKCS#1 1.5,其基本原理为:

1. 先计算出需要签名的信息的HASH值(可使用MD5、SHA-1、SHA-256、SHA-384、SHA-512),然后再将编码为如下形式:

00 01 FF FF ... FF FF 00 ASN.1 HASH
其中:
    (1) ASN.1包含这段hash值类型的信息,详见源码中HASH_ASN1,具体定义请参考PKCS#1 RSA 算法标准
    (2) FF FF … FF FF 为填充的信息,使得与n的位数相同

2. 将这段编码使用私钥加密(即将其转换为int类型并做此运算)

3. 转换为bytes类型并前缀补零至与n位数相同

4. 签名结束,返回签名信息

RSA签名校验原理:

1. 将这段编码使用公钥解密(即将其转换为int类型并做此运算)

2. 如果解密后数据的前两位为'\x00\x01'则继续下一步,否则抛出校验失败异常

3. 从第三位开始寻找'\x00',即跳过填充的'\xFF'字段。如果没有找到也抛出校验失败异常

4. 判断出签名信息中使用的hash类型(通过ASN.1)

5. 使用判断出的hash算法将原信息求出散列值,并与签名信息中hash(签名信息中hash由上一步得到)进行比较,如果匹配成功则返回True,否则抛出校验失败异常。

下面说下Python-rsa签名伪造漏洞原理

E取得足够小的情况下(E=3),NE就完全没有关联,换句话说就是,E太小,导致P ^ E mod N == P ^ E == C

E

这边已经知道了,那么我们就可以通过求C的立方值,来确定FakeC,也就是我们可以伪造任何的C,这边漏洞发现者给出了一个办法(the pen-and-paper column operation),我们以求立方值后缀为1010101101的数为例:

        9876543210  索引位
s:      0000000001
s^3:    0000000001
target  1010101101  0-1 满足要求,2 不满足要求

s:      0000000101
s^3:    0001111101
target  1010101101  0-3 满足要求,4 不满足要求

s:      0000010101
s^3: ...0000101101  
target  1010101101  0-6 满足要求,7 不满足要求

s:      0010010101
s^3: ...0110101101  
target  1010101101  0-7 满足要求,8 不满足要求

s:      0110010101
s^3: ...0010101101  
target  1010101101  0-8 满足要求,9 不满足要求

s:      1110010101
s^3: ...1010101101  
target  1010101101  全部满足要求

1110010101 ^ 3 = 101101111101011111101010101101
                                       ^^^^^^^^

这样反向计算,就可以构造任意的内容了。

0x01 实践探究过程

这里因为是针对RCTF - RSA Sign,所以我将两边的代码结合,改成了适合此场景的代码,下面来说一下:

def to_bytes(n):
    """ Return a bytes representation of a int """
    return n.to_bytes((n.bit_length() // 8) + 1, byteorder='big')
def to_bytes(n):
    """ Return a bytes representation of a int """
    return n.to_bytes(((n.bit_length()-1) // 8) + 1, byteorder='big')

前面是原作者的代码,和下面的改良后的代码,我们看看算出来是不一样的:

to_bytes.png

此时我们的代码如下:

#!/usr/local/Cellar/pyenv/versions/3.5.0/bin/python3
# -*- coding: utf-8 -*-
# @Function : exp - rctf rsa sign1
# @Author   : iFurySt (hk326459@163.com)
# @Date     : 2017-05-21
# @Link     : http://ifuryst.com/
import hashlib
import rsa
import socket
import binascii
import os
from rsa._compat import b
from gmpy2 import mpz, iroot, powmod, mul, t_mod
from rsa import common, transform, core


def to_bytes(n):
    """ Return a bytes representation of a int """
    return n.to_bytes(((n.bit_length()-1) // 8) + 1, byteorder='big')

def from_bytes(b):
    """ Makes a int from a bytestring """
    return int.from_bytes(b, byteorder='big')

def get_bit(n, b):
    """ Returns the b-th rightmost bit of n """
    return ((1 << b) & n) >> b

def set_bit(n, b, x):
    """ Returns n with the b-th rightmost bit set to x """
    if x == 0: return ~(1 << b) & n
    if x == 1: return (1 << b) | n

def cube_root(n):
    return int(iroot(mpz(n), 3)[0])

def rVerify(message, signature, pub_key):
    blocksize = common.byte_size(pub_key.n)
    encrypted = transform.bytes2int(signature)
    decrypted = core.decrypt_int(encrypted, pub_key.e, pub_key.n)
    clearsig = transform.int2bytes(decrypted, blocksize)
    print("clearsig: \n", clearsig)
    try:
        sep_idx = clearsig.index(b('\x00'), 2)
    except ValueError:
        print ('How ugly your signature looks...More practice,OK?')
        return False

    signature = clearsig[sep_idx+1:]

    # Compare the real hash to the hash in the signature
    print("fin_signature: \n", signature)
    if message != signature:
        print ('wanna cheat me,ah?')
        return False
    return True

def interactRCTF(message,signature):
    target_host = 'rsasign1.2017.teamrois.cn'
    target_port = 3000
    conn = socket.socket(socket.AF_INET,socket.SOCK_STREAM)
    conn.connect((target_host,target_port))

    print(conn.recv(2048))
    conn.sendall(message)
    print(conn.recv(2048))
    conn.sendall(signature)
    print(conn.recv(2048))

def calcSignature(message):
    message = message.encode("ASCII")
    print("message: \n", message)
    message_hash = hashlib.md5(message).digest()
    print("message_hash_raw: \n", message_hash)
    print("message_hash: \n", binascii.hexlify(message_hash))
    ASN1_blob = rsa.pkcs1.HASH_ASN1['MD5']
    suffix = b'\x00' + message
    print("suffix_raw: \n" , suffix)
    print("suffix: \n" , binascii.hexlify(suffix))
    print(suffix[-1]&0x01)
    sig_suffix = 1
    for b in range(len(suffix)*8):
        if get_bit(sig_suffix ** 3, b) != get_bit(from_bytes(suffix), b):
            sig_suffix = set_bit(sig_suffix, b, 1)
    print("sig_suffix: \n", to_bytes(sig_suffix))

    while True:
        prefix = b'\x00\x01' + os.urandom(1024//8 - 2)
        sig_prefix = to_bytes(cube_root(from_bytes(prefix)))[:-len(suffix)] + b'\x00' * len(suffix)
        sig = sig_prefix[:-len(suffix)] + to_bytes(sig_suffix)
        if b'\x00' not in to_bytes(from_bytes(sig) ** 3)[:-len(suffix)]:
            print("sig^3: \n", to_bytes(from_bytes(sig) ** 3))
            break

    with open("./public.pem") as publickfile:
        p=publickfile.read()
        key=rsa.PublicKey.load_pkcs1(p)
    key.e = 3
    print("sig: \n", sig)
    print("sig_hex: \n", binascii.hexlify(sig))

    rVerify(message_hash, sig, key)
    interactRCTF(message, binascii.hexlify(sig))

根据Public.pem,我们可知道公私钥是1024的,所以此处我们选用MD5:

message_hash = hashlib.md5(message).digest()

ASN1_blob = rsa.pkcs1.HASH_ASN1['MD5']

因为针对下面这些参数有解:

n=1024,e=3,md5
n=2048,e=3,md5
n=2048,e=7,md5

n=1024,e=3,sha1
n=2048,e=5,sha1
n=4096,e=7,sha1
n=8192,e=17,sha1
n=8192,e=23,sha1

n=2048,e=3,sha256
n=8192,e=17,sha256

n=2048,e=3,sha384
n=8192,e=13,sha384

n=2048,e=3,sha512
n=8192,e=11,sha512

for循环是计算出一个数,数的立方满足要求的,while循环是确保\x00\x01\x00之间不存在\x00while循环里也相应的把2048改成1024

最后读取public.pem里的公钥调用赛方给的rVerify函数进行验签。

这边因为过程中需要调试,发现问题,故而我在多处地方均输出的当时的关键变量的值。

这边脚本需要在python3下跑,我用了pyenv,故而我直接添加了第一行的#!/usr/local/Cellar/pyenv/versions/3.5.0/bin/python3,再给文件执行权限(chmod +x ./exp.py)就可以直接调用python3

interactRCTF()是为了和远程主机进行交互

Sign1只需要我们传过去signature解开后面那串等于message即可,而Sign2则需要我们传过去的signature解开后的hash,和messagehash是一样的(hash算法根据ASN.1位来识别)。

因此第一题构造

message = 'MoKirinSec'

这边一开始我构造的是iFurySt,被坑惨了,因为待签名信息的二进制最后一位需要为1

这个限制的数学本质是,对于高次同余方程x^r≡a(mod 2^k):

设r、k均为正整数,a为整数,若r、a均为奇数,则x^r≡a(mod 2^k)恰有一解。

Filippo Valsorda所示办法在e比较大时,效率太低,用数学方式求解高次同余方程
更普适,还能对付a为偶数的情形。

因此在

print(suffix[-1]&0x01)

此条件的判断下,即可知道是否符合条件。

Sign1 - exp.py运行结果如下:

Sign1 - Exp.py

Sign2 - exp.py运行结果如下:
Sign1 - Exp.py

完整代码见此:

RCTF - RSA_Sign1 - exp.py

RCTF - RSA_Sign2 - exp.py

这篇文章很多地方参考、引用了下面的文章的内容,在此声明下

参考文章:

[1] BLEICHENBACHER'06 SIGNATURE FORGERY IN PYTHON-RSA

[2] 关于python-rsa签名伪造漏洞(CVE-2016-1494)的讨论

[3] CVE-2016-1494 (python – rsa)漏洞详解

声明:文章基本原创,允许转载,但转载时必须以超链接的形式标明文章原始出处及作者信息。

仅有 1 条评论

  1. Burhan Uddin

    Hey
    A very well-developed post with step by step guidance on python.
    The way you explained each point with necessary details and maintained good balance between theory and practice is really commendable.thank you for posting such a informative article.

    Thanks again

    时间: 2017-08-16 at 07:17 回复

添加新评论