伪随机数总结

windows与linux下的随机数生成机制不一样，如果给的是elf文件要求随机序列，需要在linux下编译

C

一般先设置种子srand(seed)，之后调用rand函数；如果没有调用srand函数则默认seed为1

需要注意rand是有内部状态的伪随机数生成器，每调用一次rand，内部状态就会更新一次， 下一次rand会基于更新后的状态继续生成下一个数

动调获取随机序列

2024geek-flower

去除花指令后得到如下结果

尝试提取出前几个随机数0x1b,0x13,0x13,0x41

用c跑随机数发现和调试的不太一样

往后调试发现伪随机数相关的值和明文异或

且加密过程只有一步异或

a=[0x3E, 0x98, 0xEB,
0x26, 0x25,
0x8E, 0x25, 0xE5,
0x86, 0xC8,
0x3F, 0x98, 0xC8,
0xDE, 0x52,
0x44, 0xA0, 0xCB,
0x2B, 0x2A,
0x3C, 0xAA, 0xBE,
0xCB, 0x88,
0x55, 0x9E, 0x6D,
0xD9, 0x94,
0x97, 0x1C, 0x52,
0x31, 0x59,
0xFE, 0x1A, 0x1A,
0xE8, 0xD0,
0x3A, 0x9C, 0x06,
0x5E, 0x25,
0x5A, 0xE4, 0x22,
0xA1, 0xC5]
a1=[0x6D,0xC1,0xA8,0x5D,
0x7C,0xBE,0x50,0xBA,
0xE5,0x88,0x51,0xC7,
0xFB,0xB0,0x18,0x2B,
0xD9,0x94,0x52,0x42,
0x59,0xF5,0xF8,0xA7,
0xE7,0x22,0xAD,0x1F,
0x86,0xF5,0xF9,0x65,
0x26,0x58,0x34,0x9B,
0x45,0x7B,0x86,0xB4,
0x65,0xFD,0x68,0x27,
0x52,0x32,0x81,0x50,0xc4,0xb8]
print(len(a1))
flag=''
for i in range(len(a1)):
    flag+=chr(a[i]^a1[i])
print(flag)

#SYC{Y0u_c@n_3nJoy_yhe_Flow3r_anytime_and_anywhere}

2024CISCN初赛-gdb_debug

伪随机数只取高位

加密逻辑：xor rand->交换下标->xor rand->xor string

按理seed生成的伪随机数会很大，与调试结果不符，这也就是题目要求我们调试的原因

一种思路是输入一个flag，得到密文之后xor得到rand1,rand3和ptr，当然可以一位位提取数据

看汇编去找把rax作为地址的内存，记住开始位置后直接跳出循环，全部提取，这题神奇的点在双击数组进去看不到密文

而需要在调试时看看寄存器的值找内存

#include <stdio.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>

int main() {
    char v28[38];
    for (int i = 0; i < 1; i++) {
        int a[16] = {0, 0x10000000, 0x20000000, 0x30000000, 0x40000000, 0x50000000, 0x60000000, 0x70000000, 0x80000000, 0x90000000, 0xa0000000, 0xb0000000, 0xc0000000, 0xd0000000, 0xe0000000, 0xf0000000};
        srand(a[i]);
        int v31[38] = {220, 184, 64, 189, 156, 201, 110, 101, 239, 18, 216, 152, 105, 208, 222, 252, 107, 174, 125, 139, 214, 141, 15, 208, 79, 102, 62, 157, 250, 195, 233, 36, 211, 239, 255, 157, 231, 1};
        int rand1[38]={217, 15, 24, 189, 199, 22, 129, 190, 248, 74, 101, 242, 93, 171, 43, 51, 212, 165, 103, 152, 159, 126, 43, 93, 194, 175, 142, 58, 76, 165, 117, 37, 180, 141, 227, 123, 163, 100};
        int rand3[38]={222, 170, 66, 252, 9, 8, 178, 6, 13, 147, 97, 244, 36, 73, 21, 1, 215, 171, 4, 24, 207, 233, 213, 150, 51, 202, 249, 42, 94, 234, 45, 60, 148, 111, 56, 157, 88, 234};
        char ptr[38]={0x12, 0x0E, 0x1B, 0x1E, 0x11, 0x05, 0x07, 0x01, 0x10, 0x22, 0x06, 0x17, 0x16, 0x08, 0x19, 0x13, 0x04, 0x0F, 0x02, 0x0D, 0x25, 0x0C, 0x03, 0x15, 0x1C, 0x14, 0x0B, 0x1A, 0x18, 0x09, 0x1D, 0x23, 0x1F, 0x20, 0x24, 0x0A, 0x00, 0x21};
        for (int i = 0; i < 38; i++) {
            v31[i] = v31[i] ^ rand3[i];
            //printf("%d ",rand());
            //ptr[i] = i;
        }

        // for (int k = 37; k; --k) {
        // 	int v18 = rand() % 38;
        // 	//printf("%d ",v18);
        // 	int tmp = ptr[k];
        // 	ptr[k] = ptr[v18];
        // 	ptr[v18] = tmp;
        // }
        //printf("\n");
        for (int i = 0; i <38; i++) {
            v28[ptr[i]] = v31[i];
        }
        for (int i = 0; i < 38; i++) {
            v28[i] = v28[i] ^ rand1[i];
        }
        for (int i = 0; i < 38; i++) {
            printf("%c", v28[i]&0xff);
        }
        printf("\n");

    }

    return 0;
}
//flag{�8bace5989660ee38f1fd980a4b4fbcd}

最后一位爆破即可：flag{78bace5989660ee38f1fd980a4b4fbcd}

还有一种方法是直接用时间戳，注意要在linux下运行

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <ctime>
#include <unistd.h>

using namespace std;
typedef long long LL;
typedef long double DD;

int main()
{
    srand(((int)time(0))& 0xF0000000);
    char s2[] = "congratulationstoyoucongratulationstoy";
    unsigned char byte_10A0[] = {
    0xBF, 0xD7, 0x2E, 0xDA, 0xEE, 0xA8, 0x1A, 0x10, 0x83, 0x73, 0xAC, 0xF1, 0x06, 0xBE, 0xAD, 0x88, 
    0x04, 0xD7, 0x12, 0xFE, 0xB5, 0xE2, 0x61, 0xB7, 0x3D, 0x07, 0x4A, 0xE8, 0x96, 0xA2, 0x9D, 0x4D, 
    0xBC, 0x81, 0x8C, 0xE9, 0x88, 0x78, 0x00, 0x00
};
    char rand1[38];
    unsigned int rand2[38],rand3[38];
    int len = strlen(s2);
    cout << "len:" << len << endl;
    for(int i=0;i<len;i++)
        {
            rand1[i] = rand();
            // cout << (unsigned int)(rand1[i]&0xff) << " ";
        }
    for(int i=len-1;i;--i)
        {
            rand2[i] = rand()%(i+1);
            // cout << (unsigned int)(rand2[i]&0xff) << " ";
        }
    for(int i=0;i<len;i++)
        {
            rand3[i] = rand();
        }

    for(int i=0;i<len;i++)
        {
            s2[i] ^= byte_10A0[i];
        }

    for(int i=0;i<len;i++)
        {
            s2[i] ^= rand3[i];
        }

    int str3[39];
    for(int i=0;i<len;i++)
        {
            str3[i] = i;
        }

    for(int i=len-1;i;--i)
        {
            int temp = str3[i];
            str3[i] = str3[rand2[i]];
            str3[rand2[i]] = temp;
        }

    //s2[i]=str2[str3[i]];
    char str2[39] = {0};
    for(int i=0;i<len;i++)
        {
            str2[str3[i]] = s2[i];
        }
    for(int i=0;i<len;i++)
        {
            str2[i] ^= rand1[i];
        }
    cout << str2;

    return 0; //-22 61 13 92
}

个人比赛的时候就用了这种，但是rand2的生成循环写反了，以及rand1和rand3的位置没考虑

#include <stdio.h>
#include <string.h>
#include <time.h>
#include<stdlib.h>
#include<stdint.h>
int main() {
    char v28[38];
    for(int i=0;i<1;i++){
        //int a[16]={0,0x10000000,0x20000000,0x30000000,0x40000000,0x50000000,0x60000000,0x70000000,0x80000000,0x90000000,0xa0000000,0xb0000000,0xc0000000,0xd0000000,0xe0000000,0xf0000000};
        srand(((int)time(0))&0xf0000000);
        unsigned char v31[38]={220, 184, 64, 189, 156, 201, 110, 101, 239, 18, 216, 152, 105, 208, 222, 252, 107, 174, 125, 139, 214, 141, 15, 208, 79, 102, 62, 157, 250, 195, 233, 36, 211, 239, 255, 157, 231, 1};
        char s[50]="congratulationstoyoucongratulationstoy";
        int ptr[38];
        unsigned int rand1[38];
        unsigned int rand2[38];
        unsigned int rand3[38];
        for(int i =0;i<38;i++){
            rand1[i]=rand();
            //printf("%d ",rand1[i]);
        }
        printf("\n\n");
        for(int i=0;i<37;i++){
            rand2[i]=rand();
            //printf("%d ",rand2[i]);
        }
        printf("\n\n");
        for(int i =0;i<38;i++){
            rand3[i]=rand();
            //printf("%d ",rand3[i]);
        }
        for(int i=0;i<38;i++){
            v31[i]=v31[i]^rand3[i];
            printf("%d ",rand3[i]);
            ptr[i]=i;
        }

        for(int k=37,j=0;k>=0;k--,j++){
            uint32_t t=rand2[j]%(k+1);
            printf("%d ",t);
            char tmp=ptr[k];
            ptr[k]=ptr[t];
            ptr[t]=tmp;
        }

        for(int i=0;i<38;i++){
            v28[ptr[i]]=v31[i];
        }
        for(int i=0;i<38;i++){
            v28[i]=v28[i]^rand1[i];
        }
        //for(int i=0;i<38;i++){
        // printf("%c",v28[i]&0x7f);
        //}
        printf("%s",v28);
        printf("\n");
    }

    return 0;
}

爆破seed

2023春秋杯冬季赛-upx

📎upx2023_0.zip

原来upx小写改大写然后脱壳

双击v7按几次d就发现只是顺序变了

找到修改时间往前爆

#include <stdio.h>
#include <stdlib.h>

int main() {
    int seed, i, key;
    for (seed = 1685762995; seed > 0; seed--) {
        srand(seed);
        int right = 1;
        for (i = 0; i <= 32; i++) {
            key = rand() % 255;
            switch (i) {
                case 0:
                    if (key != ('f' ^ 0x09)) { //102^9=111(0x6F)
                        right = 0;
                    }
                    break;
                case 1:
                    if (key != ('{' ^ 0x63)) { //123^99=24(0x18)
                        right = 0;
                    }
                    break;

                case 11:
                    if (key != ('l' ^ 0xC6)) { //108^198=170(0xAA)
                        right = 0;
                    }
                    break;
                case 12:
                    if (key != ('g' ^ 0x65)) { //103^101=2(0x02)
                        right = 0;
                    }
                    break;
                case 32:
                    if (key != ('a' ^ 0xFA)) { //97^250=155(0x9B)
                        right = 0;
                    }
                    break;
                default:
                    break;
            }
            if (right == 0) {
                break;
            }
        }
        if (right == 1) {
            printf("%u\n", seed);
            break;
        }
    }
    int data[] = { 0x09, 0x63, 0xD9,
                  0xF6, 0x58,
                  0xDD, 0x3F, 0x4C,
                  0x0F, 0x0B,
                  0x98, 0xC6, 0x65,
                  0x21, 0x41,
                  0xED, 0xC4, 0x0B,
                  0x3A, 0x7B,
                  0xE5, 0x75, 0x5D,
                  0xA9, 0x31,
                  0x41, 0xD7, 0x52,
                  0x6C, 0x0A,
                  0xFA, 0xFD, 0xFA,
                  0x84, 0xDB,
                  0x89, 0xCD, 0x7E,
                  0x27, 0x85,
                  0x13, 0x08
                  };
    srand(seed);
    for (int i = 0; i < 42; i++)
        printf("%c", ((rand() % 255) ^ data[i]) & 0xff);
}
//1682145110
//f{52bgb-281lg00ff-46f7-ca009c8e}a381-b7191

再通过python索引把位置换回来

example='flag{1234567890zxcvbnmlkjhgfdsaqwertyuiop}'
result='f{48xnjdwyplg13579zcbmkhfsqetuo}a260vlgari'
crypto = "f{52bgb-281lg00ff-46f7-ca009c8e}a381-b7191"

for i in example:
    print(crypto[result.index(i)], end="")

#flag{0305f8f2-14b6-fg7l-bcgf-0a0299c881e1}

2024山东省省赛决赛rand

参考链接：https://mp.weixin.qq.com/s/3PZK2O2PftCqr2mS7vn5wA

Python

python中random库使用的是MT19937算法(梅森旋转算法)，利用算法可以求出后随机数，前未知随机数，种子等，详见博客：https://lazzzaro.github.io/2020/11/07/crypto-%E6%B5%81%E5%AF%86%E7%A0%81/

1.利用seed初始化624个状态

2.对状态进行旋转

3.根据状态提取伪随机数

def _int32(x):
    return int(0xFFFFFFFF & x)

class MT19937:
    # 根据seed初始化624的state
    def __init__(self, seed):
        self.mt = [0] * 624
        self.mt[0] = seed
        self.mti = 0
        for i in range(1, 624):
            self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)

    # 提取伪随机数
    def extract_number(self):
        if self.mti == 0:
            self.twist()
        y = self.mt[self.mti]
        y = y ^ y >> 11
        y = y ^ y << 7 & 2636928640
        y = y ^ y << 15 & 4022730752
        y = y ^ y >> 18
        self.mti = (self.mti + 1) % 624
        return _int32(y)

    # 对状态进行旋转
    def twist(self):
        for i in range(0, 624):
            y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
            self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]

            if y % 2 != 0:
                self.mt[i] = self.mt[i] ^ 0x9908b0df

有默认种子，由当前时间和操作系统提供的熵源例如urandom综合生成

import random
import time

print(int(time.time()))
print('随机数1：',random.random())
print(int(time.time()))
random.seed(int(time.time()))
print('随机数2：',random.random())
random.seed(0)
print('随机数3：',random.random())

# 1732158156
# 随机数1： 0.4747416427572331
# 1732158156
# 随机数2： 0.2260060177159785
# 随机数3： 0.8444218515250481

2021GKCTF-Random

如果能获取前624个32位的随机数，就能预测出后面全部32位的随机数

import random
from hashlib import md5
 
def get_mask():
    file = open("random.txt","w")
    for i in range(104):
        file.write(str(random.getrandbits(32))+"\n")
        file.write(str(random.getrandbits(64))+"\n")
        file.write(str(random.getrandbits(96))+"\n")
    file.close()
get_mask()
flag = md5(str(random.getrandbits(32)).encode()).hexdigest()
print(flag)

random的随机数以32位为一个单位，所以如果要产生一个64位的随机数，则等价于一次产生两个32位随机数

本题中已知的随机数有104*(1+2+3)=624个，刚好满足能够预测的条件，需要预测出下一个

randcrack

from hashlib import md5
from randcrack import RandCrack

with open(r'random.txt', 'r') as f:
    l = f.readlines()
l = [int(i.strip()) for i in l]
t = []
for i in range(len(l)):
    if i % 3 == 0:
        t.append(l[i])  # 32位长度直接存入
    elif i % 3 == 1:
        t.append(l[i] & (2 ** 32 - 1))  # 64位长度先存入低32位
        t.append(l[i] >> 32)  # 再存入高32位
    else:
        t.append(l[i] & (2 ** 32 - 1))
        t.append(l[i] & (2 ** 64 - 1) >> 32)
        t.append(l[i] >> 64)
rc = RandCrack()
for i in t:
    rc.submit(i)  # 把每个数据都丢进预测器里
flag = rc.predict_getrandbits(32)  # 预测的下一个32位
print(md5(str(flag).encode()).hexdigest())

列举全部state的状态

from random import Random

def invert_right(m,l,val=''):
    length = 32
    mx = 0xffffffff
    if val == '':
        val = mx
    i,res = 0,0
    while i*l<length:
        mask = (mx<<(length-l)&mx)>>i*l
        tmp = m & mask
        m = m^tmp>>l&val
        res += tmp
        i += 1
    return res

def invert_left(m,l,val):
    length = 32
    mx = 0xffffffff
    i,res = 0,0
    while i*l < length:
        mask = (mx>>(length-l)&mx)<<i*l
        tmp = m & mask
        m ^= tmp<<l&val
        res |= tmp
        i += 1
    return res

def invert_temper(m):
    m = invert_right(m,18)
    m = invert_left(m,15,4022730752)
    m = invert_left(m,7,2636928640)
    m = invert_right(m,11)
    return m

def clone_mt(record):
    state = [invert_temper(i) for i in record]
    gen = Random()
    gen.setstate((3,tuple(state+[0]),None))
    return gen


f = open("random.txt",'r').readlines()
prng = []
j=0
for i in f:
    i = i.strip('\n')
    print(int(i).bit_length())
    if(j%3==0):
        prng.append(int(i))
    elif(j%3==1):#将生成两次随机数的两个随机数分离出来
        prng.append(int(i)& (2 ** 32 - 1))
        prng.append(int(i)>> 32)
    else:#将生成三次随机数的三个随机数分离出来
        prng.append(int(i)& (2 ** 32 - 1))
        prng.append(int(i)& (2 ** 64 - 1) >> 32)
        prng.append(int(i)>>64)
    j+=1

g = clone_mt(prng[:624])
for i in range(624):
    g.getrandbits(32)#产生前624个随机数，让state状态到生成flag前

key = g.getrandbits(32)
print(key)
from hashlib import md5
flag = md5(str(key).encode()).hexdigest()
print(flag)
#14c71fec812b754b2061a35a4f6d8421

2023HITCTF邀请赛-random

数据：📎output.zip

import random

with open('output.bin', 'wb') as f:
    f.write(random.randbytes(2500))

print('HITCTF2023{%s}' % random.randbytes(16).hex())

题目已知产生了2500个byte，一个byte是8位，也就是说4个byte组成一个32位随机数，2500/4=625>624，满足预测条件

import random
from mt19937predictor import MT19937Predictor

#读取数据，并4个一组组成一个32位随机数(little是重点)
c = open('output.bin', 'rb').read()
c = [c[x:x+4] for x in range(0, len(c), 4)]
c = [int.from_bytes(x, 'little') for x in c]

predictor = MT19937Predictor()
for x in c[:624]:
	predictor.setrandbits(x, 32) #只需要624组数据就行
assert predictor.getrandbits(32) == c[-1]
print('HITCTF2023{%s}' % predictor.randbytes(16).hex())
# HITCTF2023{d6712c20657ce5e02118f8592b7da71f}