参加xman夏令营，大佬给我们带来了密码学课程。其中随机数部分感受颇深，记录下几个脚本。
1. 以时间作为种子的随机数
https://www.jarvisoj.com/ 的[xman2019]babyrpd
服务端代码
class Unbuffered(object):
def __init__(self, stream):
self.stream = stream
def write(self, data):
self.stream.write(data)
self.stream.flush()
def __getattr__(self, attr):
return getattr(self.stream, attr)
import sys
sys.stdout = Unbuffered(sys.stdout)
import signal
signal.alarm(600) import random
import time
flag=open("/root/level0/flag","r").read() random.seed(int(time.time()))
def check():
recv=int(raw_input())
if recv==random.randint(0,2**64):
print flag
return True
else:
print "atum tql"
return False while 1:
if check():
break
解决方法：
预测时间种子，进行攻击
#coding=utf-8
import socket
import random
import time while True:
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
host = '47.97.215.88'
port = 20000
random.seed(int(time.time()+2)) #加上延迟所以+2秒
s.connect((host, port))
s.send(str(random.randint(0,2**64))+'\n')
print s.recv(1024)
2. java的Random随机数
https://www.jarvisoj.com/ 的[xman2019]mediumrpd
服务端代码：
class Unbuffered(object):
def __init__(self, stream):
self.stream = stream
def write(self, data):
self.stream.write(data)
self.stream.flush()
def __getattr__(self, attr):
return getattr(self.stream, attr)
import sys
sys.stdout = Unbuffered(sys.stdout)
import signal
signal.alarm(600)
import os
os.chdir("/root/level1") flag=open("flag","r").read() import subprocess
o = subprocess.check_output(["java", "Main"])
tmp=[]
for i in o.split("\n")[0:3]:
tmp.append(int(i.strip())) v1=tmp[0] % 0xffffffff
v2=tmp[1] % 0xffffffff
v3=tmp[2] % 0xffffffff
print v1
print v2
v3_get=int(raw_input())
if v3_get==v3:
print flag
import java.util.Random;
public class Main {
public static void main(String[] args) {
Random random = new Random();
System.out.println(random.nextInt());
System.out.println(random.nextInt());
System.out.println(random.nextInt());
}
}
攻击方法
从题目获取到两个随机数v1,v2，通过已知公式，可以计算出v3
import socket
import random
import time
def liner (seed):
return ((seed*25214903917+11)&0xffffffffffff) while True:
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
host = '47.97.215.88'
port = 20001
s.connect((host, port))
v1=int(s.recv(1024))
v2=int(s.recv(1024))
for i in range(65536):
seed=v1*65536+i
if liner(seed)>>16==v2:
print seed
v3=liner(liner(seed))>>16
s.send(str(v3)+'\n')
print s.recv(1024)
3. python的random
来源是：Mersenne Twister
大佬说php的mt_rand（可以用php_mt_seed攻击）,ruby的rand()，python的random都可以攻击，但我只弄出python的版本
题目为https://www.jarvisoj.com/ 的[xman2019]hardrpd
参考文章：https://ddaa.tw/30c3ctf_2013_number_100_guess.html
https://jazzy.id.au/2010/09/22/cracking_random_number_generators_part_3.html
服务端代码：
class Unbuffered(object):
def __init__(self, stream):
self.stream = stream
def write(self, data):
self.stream.write(data)
self.stream.flush()
def __getattr__(self, attr):
return getattr(self.stream, attr)
import sys
sys.stdout = Unbuffered(sys.stdout)
import os
os.chdir("/root/level2") from random import * while 1:
a=raw_input("#")
target=getrandbits(32)
if a!=str(target):
print target
else:
print open("flag","rb").read()
攻击脚本：（改写至TokyoWestern CTF WriteUp by r3kapig）
#coding=utf-8
import socket
import random
import time def unBitshiftRightXor (value,shift):
i = 0
result = 0
while i * shift < 32:
partMask = right((-1 << (32 - shift)) , (shift * i))
part = value & partMask
value ^= right(part , shift)
result |= part
i+=1
return result
def unBitshiftLeftXor(value, shift, mask):
i = 0;
result = 0;
while i * shift < 32:
partMask = right(-1 , (32 - shift)) << (shift * i)
part = value & partMask
value ^= (part << shift) & mask
result |= part
i += 1
return result def rev(nums):
state=[]
for i in nums:
value = i;
value = unBitshiftRightXor(value, 18)
value = unBitshiftLeftXor(value, 15, 0xefc60000)
value = unBitshiftLeftXor(value, 7, 0x9d2c5680)
state.append(unBitshiftRightXor(value, 11))
return state def sign(iv):
if(iv&0x80000000):
iv = -0x100000000 + iv
return iv def nextState(state):
for i in range(624):
y = (state[i] & 0x80000000) + (state[(i + 1) % 624] & 0x7fffffff)
next = right(y,1);
next ^= state[(i + 397) % 624]
if ((y & 1L) == 1L):
next ^= 0x9908b0df
state[i] = next def nextNumber(state):
currentIndex=0
tmp = state[currentIndex];
tmp ^= right(tmp , 11)
tmp ^= (tmp << 7) & 0x9d2c5680
tmp ^= (tmp << 15) & 0xefc60000
tmp ^= right(tmp , 18)
return tmp def right(n,bit): #python没有>>>运算符，这个函数用作代替
x=n
if n<0 and bit>0:
n=(2147483648*2+n)>>bit
else:
n=n>>bit
return n def crack_prng(outputs_624_list):
state=rev(outputs_624_list)
stateList = state[:]
nextState(state)
r = random.Random()
state = (3, tuple(stateList + [624]), None)
r.setstate(state)
return r
'''
#本地测试代码
n=[random.getrandbits(32) for i in range(625)]
r=crack_prng(n[:-1])
print n[-1],r.getrandbits(32)
'''
n=[]
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
host = '47.97.215.88'
port = 20002
s.connect((host, port))
for i in range(624):
print s.recv(1024),i,
s.send('\n')
n.append(int(s.recv(1024)))
r=crack_prng(n)
s.send(str(r.getrandbits(32))+'\n')
print s.recv(1024),s.recv(1024)
