刷题时碰到了一个预测随机数的题目，于是就了解到了 Randcrack，拿来分享一下。

Randcrack 是 Python 的一个伪随机数预测模块，他可以通过分析由 MT19973 算法生成的随机数，来预测之后产生的随机数。

基本使用

rc = RandCrack()

创建一个 RandCrack 对象

rc.submit(num)

传一个 32 位整数，上传 624 个以上就可以预测了

rc.predict_你想预测的函数(函数的参数)

如 rc.predict_getrandbits(32)

一道例题

我们通过一道题目来进一步掌握他的使用方式

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
from Crypto.Cipher import AES
from binascii import b2a_hex
from libnum import s2n
from random import *


def add_to_16(text):
    if len(text.encode('utf-8')) % 16:
        add = 16 - (len(text.encode('utf-8')) % 16)
    else:
        add = 0
    text = text + ('\0' * add)
    return text.encode('utf-8')

def init():
    r1 = getrandbits(64)
    r2 = getrandbits(32)
    m = "{:X}".format(r1).encode('utf-8')
    salt = "{:X}".format(r2).encode('utf-8')
    m += salt
    return add_to_16(m.decode())

def encrypt(m, key, iv):
    mode = AES.MODE_CBC
    cryptos = AES.new(key, mode, iv)
    cipher_text = cryptos.encrypt(m)
    return cipher_text

def chall(key, iv):
    old_m = init()
    c = encrypt(old_m, key, iv)
    return b2a_hex(c)

if __name__=="__main__":
    flag='Stinger{***************************************}'
    f = open("msg.txt", 'w+')
    old_key = b'73E5602B54FE63A5'
    old_iv = b'B435AE462FBAA662'
    for i in range(208):
        old_c = chall(old_key, old_iv)
        f.write("{}\n".format(old_c.decode()))
    salt = "{:X}".format(getrandbits(32)).encode('utf-8')
    m = flag.encode() + salt
    key = "{:X}".format(getrandbits(64)).encode('utf-8')
    iv = "{:X}".format(getrandbits(64)).encode('utf-8')
    c = encrypt(add_to_16(m.decode()), key, iv)
    print("c = %r"%(b2a_hex(c)))

# c = b'9847f103ed4dce08c5ab8cb22288a477df4ae2a96bf10ccecc94ba799e4e072372c401aed54925e2eeff47fe5c56be2c'

整体思路

看上去是道 AES 加密的题目，然而注意到它们都是由getrandbits()函数生成的，这是 random 库的一个随机数生成函数，使用的正是 MT19973 算法，所以只要我们预测出 iv、salt 和 key，这道题基本就做完了

阅读题目，msg.txt 中记录了 208 组 AES 密钥的数据，每组数据由一个 64 位数和一个 32 位数拼接而成，208*3 正好是 624，验证了我们的思路

现在的数据都是十六进制的形式，我们先将他们变回字节的形式：

1
ciphers = [bytes.fromhex(line) for line in open("msg.txt", "r").readlines()]

old_key 和 old_iv 题目直接给出了，于是我们可以直接解密得到明文。解密函数只要对着加密函数照葫芦画瓢就可以了

1
2
3
4
5
def decrypt(c, key, iv):
    mode = AES.MODE_CBC
    cryptos = AES.new(key, mode, iv)
    plain_text = cryptos.decrypt(c)
    return plain_text

解密后去掉补位发现数据又变回了十六进制的形式，长度为 24，取前 16 位为 r1，剩余部分即为 r2

接下来需要按顺序上传，理论上应该先上传 64 位数，再上传 32 位数，但由于 Randcrack 只支持上传 32 位数，需要先将 64 位数分解。64 位随机数的生成本质上是两个 32 位随机数拼接而来，低位先生成，高位后生成。之前我在这里先传高位导致预测错误卡了好久，警钟敲烂。

取位数涉及到位运算的技巧。取低 32 位就用r1 & 0xffffffff，取高 32 位就用r1 >> 32

至此，所有的难关都已攻破，预测完参数后解出 flag 即可，由于 salt 与 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
from Crypto.Cipher import AES
from randcrack import RandCrack

def decrypt(c, key, iv):
    mode = AES.MODE_CBC
    cryptos = AES.new(key, mode, iv)
    plain_text = cryptos.decrypt(c)
    return plain_text


old_key = b"73E5602B54FE63A5"
old_iv = b"B435AE462FBAA662"

ciphers = [bytes.fromhex(line) for line in open("msg.txt", "r").readlines()]

rc = RandCrack()
for c in ciphers:
    plain = decrypt(c, old_key, old_iv).rstrip(b"\x00")
    r1 = int(plain[:16], 16)
    r2 = int(plain[16:], 16)
    rc.submit(r1 & 0xffffffff)
    rc.submit(r1 >> 32)
    rc.submit(r2)

salt = f"{rc.predict_getrandbits(32):X}".encode()
key = f"{rc.predict_getrandbits(64):X}".encode()
iv = f"{rc.predict_getrandbits(64):X}".encode()

c = bytes.fromhex("9847f103ed4dce08c5ab8cb22288a477df4ae2a96bf10ccecc94ba799e4e072372c401aed54925e2eeff47fe5c56be2c")
flag = decrypt(c, key, iv)

print(flag)

# b'Stinger{2301-3092-3291-2994-3911}FF8D434C\x00\x00\x00\x00\x00\x00\x00'

没用的知识增加力