Crypto趣题-随机数

该文章主要记录一些随机数相关的趣题

WeakRandom

题目来源：强网拟态 2022

题目：

#!/usr/bin/env python
import os, random, hashlib, string
from signal import alarm
from secret import flag

class WeakRandom:
    def __init__(self,seed,n,s):
        self.x = seed
        self.n = n
        self.s = s

    def next(self):
        x = int((self.x ** 2) // (10 ** (self.s // 2))) % self.n
        self.x = x
        high = (int(hashlib.sha256(str(x).encode()).hexdigest(),16) >> 16) & (2 ** 16 - 1)
        low = x & (2 ** 16 - 1)
        result = high << 16 | low
        return result

def proof_of_work():
    random.seed(os.urandom(8))
    proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
    digest = hashlib.sha256(proof.encode()).hexdigest()
    print("sha256(XXXX+%s) == %s" % (proof[4:],digest))
    print("Give me XXXX:")
    x = input()
    if len(x) != 4 or hashlib.sha256((x + proof[4:]).encode()).hexdigest() != digest: 
        return False
    return True
   
def main():
    alarm(60)
    if not proof_of_work():
        return
    alarm(100)
    print("Welcome to the predict game!")
    n = 10000000000
    s = 4
    seed = os.urandom(4)
    seed = int.from_bytes(seed,byteorder = "big")
    r = WeakRandom(seed,n,s)
    count = 0
    for i in range(100):
        try:
            x = r.next()
            guess = int(input("Please your guess : "))
            if guess == x:
                print("Success!")
                count += 1
            else:
                print(f"Fail! The number is {x}")
            if count >= 20:
                print(f"You win! The flag is : {flag}")
        except:
            print("Error!")

if __name__ == "__main__":
    main()

题目内容如下：

• 通过proof后，开始限时100s
• 随机生成4字节作为seed，并初始化一个WeakRandom()对象r
• 有一百次机会进行随机数猜测，猜错的话，靶机会返回本次的正确值，并生成下一个随机数
• 一百次中猜对20次就能得到flag

那么分析一下这个WeakRandom()如何产生随机数的：

class WeakRandom:
    def __init__(self,seed,n,s):
        self.x = seed
        self.n = n
        self.s = s

    def next(self):
        x = int((self.x ** 2) // (10 ** (self.s // 2))) % self.n
        self.x = x
        high = (int(hashlib.sha256(str(x).encode()).hexdigest(),16) >> 16) & (2 ** 16 - 1)
        low = x & (2 ** 16 - 1)
        result = high << 16 | low
        return result

可以看到，每次调用next，实现的是以下步骤：

• 计算

  $$x = int(\frac{x^2}{100}) \quad (mod\;n)$$

• 取x的sha256值，并右移16位后取低十六位，作为result高位

• 取x的低十六位作为result低位

• 返回result

而每次随机数迭代其实也就是与x有关，所以我们如果能获得某一次的x，就能获得这一次之后的所有result，就能准确预测随机数了。

而由题目知道，每一次的x都会模n，也就是说x其实是一个小于n的数，而由每一次返回的result又可以知道x的低16位，那么x的未知部分其实就只有约 n/(2^16) ，可以计算出这个数的数量级为2^18，在可以爆破的范围内。而爆破的依据就是当次返回result的高位，具体来说就是：

• 先随便给靶机传一个错误的result，得到第一次的正确result
• 得到的result的低16位也即为x的低16位
• 爆破x的高18位，爆破方式为：将需爆破的x高位与已知的x低位拼接为完整x，然后用next中high的计算方法计算出对应的high，若计算出的high与实际result高16位相等，则本次x即为可能的解

而实际上每一次x可能会有多组解，不过一般也就3、4个，从中随便选一个往后计算随机数就行，如果不对就重新连接靶机再重复上述流程即可。

exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import *
from hashlib import sha256

def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = r.recvuntil(b"sha256(XXXX+")
	temp = r.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						r.sendline(temp1.encode())
						return

def next(x):
    x = int((x ** 2) // (10 ** (s // 2))) % n
    high = (int(hashlib.sha256(str(x).encode()).hexdigest(),16) >> 16) & (2 ** 16 - 1)
    low = x & (2 ** 16 - 1)
    result = high << 16 | low
    return (x,result)


while(1):
    r = remote("node5.anna.nssctf.cn", 28469)
    proof_of_work()

    #guess
    #part1 get_first_result
    r.recvuntil(b"guess : ")
    r.sendline(b"1")
    r.recvuntil(b"number is ")
    result = int(r.recvline().strip().decode())
    x = result
    n = 10000000000
    s = 4
    hash = x >> 16
    for i in range(n // (2**16)):
        temp = i*(2**16) + (x & (2**16-1))
        high = (int(sha256(str(temp).encode()).hexdigest(),16) >> 16) & (2 ** 16 - 1)
        if(high == hash):
            x = temp

    #part2 get_subsequent_result
    right = 1
    for i in range(20):
        x,result = next(x)
        r.sendline(str(result).encode())
        temp = r.recvline()
        if(b"Success!" not in temp):
            right = 0
    if(right == 1):
        print(r.recvline())
        exit()	
    else:
        r.close()


#NSSCTF{b41d8883-e328-48a2-8909-7454d57eee62}

而实际上调试过程中可以发现一个非预期解法，测试时，可以发现靶机有时会返回两个很特殊的数字：

670760960
3587999844

这两个数字特殊在哪里呢？一旦某次计算出的结果result是这两个值，那么根据next的计算过程，之后的result一定也会是这两个值。也就是说我们只要反复重连靶机，不断提交这两个数的其中一个，也是有机会拿到flag的，并且从测试过程来看这个机会并不小。