Summary-of-Crypto-in-CTF(PRNG)

LCG - Basis

Theorem

[前置知识]

$S_{n+1}\equiv aS_{n}+b(mod\ m)$，$S_{0}$为对应种子.

在$F_{m}$上（m取大素数），若$gcd(a,m)=1$，则周期$T=ord_{m}(a)$.

所以选取系数时应尽量使得a为模m的原根，以此尽量延长LCG周期，同时也要避免$S_{0}=S_{bad}$.

LCG - Unknown (a, b)

Theorem

$S_{n+1}\equiv aS_{n}+b(mod\ m)$，(a, b)未知，m已知.

则只要给出连续三个生成值$s_{0},s_{1},s_{2}$即可求解（等价于给出两个$F_{m}$上的模方程）

虽然求解上述方程组很容易，但这里介绍一组求模等式方程组的通法.

该方法基于LLL，对构造的格基进行约化.

e.g. 对上述方程组构造如下矩阵：

我们希望格基约化后能得到一个行向量，满足前两个元素为0.

且为了在约化后的矩阵中得到直观的a, b，邻接上一个$\frac{E}{m}$（这里不用单位矩阵E的原因，是因为最好使得包含a(-a),b(-b)的行向量的长度尽可能短，也就是说更大的分母也是允许的）.

在LLL约化后，只要找到满足下列要求的行向量r，即求解成功：

• r[0] = r[1] = 0
• r[-1] = 1(-1)

$\rightarrow m\cdot r[2]=a(-a),m\cdot r[3]=b(-b)$.

exp

A = Matrix([
    [s0  ,s1  ,1/m ,0   ,0   ],
    [1   ,1   ,0   ,1/m ,0   ],
    [-s1 ,-s2 ,0   ,0   ,1   ],
    [m   ,0   ,0   ,0   ,0   ],
    [0   ,m   ,0   ,0   ,0   ]
])
A = A.LLL()
a = None
b = None
for l in A:
    if l[0] == 0 and l[1] == 0:
        if l[-1] == 1:
            a, b = l[2] * m, l[3] * m
        elif l[-1] == -1:
            a, b = -l[2] * m, -l[3] * m
        else:
            continue
if not a or not b:
    raise ValueError("[*] No solves")
a %= m
b %= m

More

构造矩阵进行LLL约化是在解决模等式和CVP等问题时很实用的方法，应熟练掌握.

LCG - Unknown (a, b, m)

Theorem

在乘数，增量和模数均未知时，对任意N，由取得的连续N个数据构成的N个模方程均有N+3个未知元. 因此不能以上述方法求解，因此用下述方法进行Module_crack.

假设我们有一组数据data = $\{k_{i}N\}$(N为大素数，$k_{i}$为$F_{N}$下的随机数)，则reduce(GCD, data)很大概率即为N或N乘上一些很小的因子.（$\because$ 假设len(data)=n，则在$k_{i}$视作完全随机的情况下，reduce(GCD, data)有除N外的素因子p的概率约为$\frac{1}{p^{n}}$，$\therefore$ 在p或n足够大的时候该方法能有效求解N）

引入序列$T_{n}=S_{n+1}-S_{n}$

$T_{n+1}=S_{n+2}-S_{n+1}=a(S_{n+1}-S_{n})=aT_{n}(mod\ m)$

$T_{n+2}=S_{n+3}-S_{n+2}=a(S_{n+2}-S_{n+1})=aT_{n+1}=a^{2}T_{n}(mod\ m)$

$\therefore T_{n}T_{n+2}-T_{n+1}^{2}=0(mod\ m)$

因此只要我们能拿到连续$n(n\geq 6)$组数据，即可对module进行有效攻击. 后续即转为上一个情形的LCG攻击.

exp

# In[1]:
from Crypto.Util.number import *

# In[2]:
class LCG:
    def __init__(self):
        m = getPrime(256)
        a = getRandomRange(2, m)
        b = getRandomRange(2, m)
        seed = getRandomRange(2, m)
        self._key = {'a':a, 'b':b, 'm':m}
        self._state = seed
        
    def next(self):
        self._state = (self._key['a'] * self._state + self._key['b']) % self._key['m']
        return self._state
    
    def export_key(self):
        return self._key
    
# In[3]:
data = []
for i in range(6):
    data.append(prng.next())
from functools import reduce
delta = [d1 - d0 for (d0, d1) in zip(data, data[1:])]
m_mul = [d0 * d2 - d1 * d1 for (d0, d1, d2) in zip(delta, delta[1:], delta[2:])]
m = reduce(GCD, m_mul)
factors = factor(m)
if len(factors) > 1:
    for (prime, degree) in factors:
        if size(prime) == 256:
            m = prime
            break
        m //= (prime**degree)
print(m)

# Jump to Unknown (a, b) case

Link

https://tailcall.net/blog/cracking-randomness-lcgs/

LCG - Truncated (Given a, b, m)

Theorem

Truncated LCG可以表示如下:

$x_{i}=2^{\beta\cdot size(m)}y_{i}+z_{i}$，$\beta$为discarded bits的比例因子，使用的随机数流仅为$y_{i}s$，在给出部分连续$y_{i}$和(a, b, m)的情况下，我们能有效恢复出$z_{i}$，从而预测接下来的随机数流.

首先讨论一类求解模等式组的问题，可以表示为

$$\sum^{k}_{j=1}a_{ij}x_{j}=c_{i}(mod\ M),i\in\{1,...,k\}$$

如果此时我们对系数矩阵A进行格基约化，即AL=LLL(A)，则

$$\sum^{k}_{j=1}a'_{ij}x_{j}=c'_{i}(mod\ M)\\ C'=A.solve\_left(AL)\cdot C$$

因为AL为约简基，所以也同时有效减小$k_{i}(Mk_{i}+c_{i}=\sum^{k}_{j=1}a_{ij}x_{j})$.（约化后可视作$k\rightarrow k_{min}$）

令$delta_X=[x_{1}-x_{0},x_{2}-x_{1},…,x_{n}-x_{n-1}]^{T}$

$delta_Y=[2^{\beta\cdot size(m)}(y_{1}-y_{0}),2^{\beta\cdot size(m)}(y_{2}-y_{1}),…,2^{\beta\cdot size(m)}(y_{n}-y_{n-1})]^{T}$

$delta_Z=[z_{1}-z_{0},z_{2}-z_{1},…,z_{n}-z_{n-1}]$

$\because x_{i+1}-x_{i}=a^{i}(x_{1}-x_{0})\quad(mod\ m)$

$\therefore$ 构造矩阵A如下

$$\left[ \begin{matrix} m & 0 & 0 & ... & 0\\ a & -1 & 0 & ... & 0\\ a^{2} & 0 & -1 & ... & 0\\ ... & ... & ... & ... & ...\\ a^{n} & 0 & 0 & ... & -1 \end{matrix} \right]$$

$A\cdot delta_X=0(mod\ m),AL=LLL(A)$

$AL\cdot delta_X=0(mod\ m),AL\cdot delta_X=m\cdot [k_{0},…,k_{n-1}]^{T}$

$AL\cdot(delta_Y+delta_Z)=m\cdot [k_{0},…,k_{n-1}]^{T}$

则此时满足：$k\rightarrow k_{min}$，因为delta_Z未知，我们只能利用delta_Y进行估值，可以做个粗略估计

AL中每个元大小近似取作$det(AL)^{\frac{1}{n}}=m^{\frac{1}{n}}$，而$size(delta_Z[i])\leq\beta\cdot size(m)$，因此

$nm^{\frac{1}{n}}2^{\beta\cdot size(m)}<m\Rightarrow$ 在m足够大时，n可忽略不计（一般取10即可），即$\beta<\frac{n-1}{n}$

在上述条件满足时，可视作$AL\cdot delta_Z<|m|$（但只是大致估计）

因此$k_{i}=round((AL\cdot delta_Y)_{i}/m)$，求得$k_{i}$后，$delta_Z=AL.solve_right(mk-AL\cdot delta_Y)$，delta_X获知，即可推出种子破解整个truncated LCG.

exp

# In[4]:
prng = LCG(128)
data = []
for i in range(20):
    data.append(prng.next())
leak_data = []
for i in range(20):
    leak_data.append(data[i] - data[i] % 2^48)
print(prng.export_key())

# In[29]:
def lcg(seed, a, b, m):
    x = seed % m
    while True:
        x = (a * x + b) % m
        yield x

# In[51]:
a = 94105412428421315937226606524092193902
b = 272271222013811783094314393442542793059
m = 335812331024081385414724338959789210621
A = Matrix(ZZ, 10, 10)
A[0, 0] = m
for i in range(1, 10):
    A[i, 0] = a^i
    A[i, i] = -1
AL = A.LLL()
delta_Y = vector([leak_data[i + 1] - leak_data[i] for i in range(10)])
W1 = AL * delta_Y
W2 = vector([round(RR(w) / m) * m - w for w in W1])
delta_Z = AL.solve_right(W2)
delta_X = delta_Y + delta_Z
x0 = (inverse(a - 1, m) * (delta_X[0] - b)) % m
rand_iter = lcg(x0, a, b, m)
for i in range(20):
    x = next(rand_iter)
print(x)

More

https://www.math.cmu.edu/~af1p/Texfiles/RECONTRUNC.pdf

java的nextInt即适用该种LCG攻击模式，但网上多选择穷举（因为discard bits才只有$2^{16}$，暴力更省事-.-）

MT - Predict/Backtrace

Theorem

Mersenne Twister也是一种流行的PRNG算法，在python的random.getrandbits和php的mt_rand中均有使用

MT算法有624个32bits长的state，新一轮更新state的算法如下

int[] state;
// Iterate through the state
for (i = 0; i < 624; i++) {
  // y is the first bit of the current number,
  // and the last 31 bits of the next number
  int y = (state[i] & 0x80000000) + (state[(i + 1) % 624] & 0x7fffffff);
  // first bitshift y by 1 to the right
  int next = y >>> 1;
  // xor it with the 397th next number
  next ^= state[(i + 397) % 624];
  // if y is odd, xor with magic number
  if ((y & 1L) == 1L) {
    next ^= 0x9908b0df;
  }
  // now we have the result
  state[i] = next;
}

从每个state生成等长(32bits)的随机数的算法如下

currentIndex++;
int tmp = state[currentIndex];
tmp ^= (tmp >>> 11);
tmp ^= (tmp << 7) & 0x9d2c5680;
tmp ^= (tmp << 15) & 0xefc60000;
tmp ^= (tmp >>> 18);
return tmp;

要破解MT算法，先决条件是要leak至少624个连续随机数(32bits)，或是说至少连续624*32bits二进制流

• Step 1(从随机数恢复state)

  具体实现函数unBitshiftRightXor和unBitshiftLeftXor在exp中已给出，具体原理较容易推出，不在此赘述

• Step 2(预测/回溯)

  预测即正常生成新的state即可

  回溯state则从state[623]开始（因为new_state[623]和(old_state[623],new_state[0],new_state[396])有关，且唯一未知的即为old_state[623]），回溯得到old_state[623]后，同理向前推即可

exp

from typing import List
from binascii import unhexlify

rand_buffer = ''
states = []

def read_data() -> List[int]:
    with open('random', 'r') as f:
        data = [int(line.rstrip('\n')) for line in f]
    assert(len(data) >= 624)
    return data
    '''
    data = [random.getrandbits(32) for i in range(624)]
    return data
    '''

def unBitshiftLeftXor(value, shift, mask):
    i = 0
    res = 0
    while i * shift < 32:
        partMask = (0xffffffff >> (32 - shift)) << (shift * i)
        part = value & partMask
        value ^= (part << shift) & mask
        res |= part
        i += 1
    return res

def unBitshiftRightXor(value, shift, mask):
    i = 0
    res = 0
    while i * shift < 32:
        partMask = ((0xffffffff << (32 - shift)) & 0xffffffff) >> (shift * i)
        part = value & partMask
        value ^= (part >> shift) & mask
        res |= part
        i += 1
    return res

def crack_states(data: List[int]) -> List[int]:
    states = []
    for i in range(624):
        value = data[i]
        value = unBitshiftRightXor(value, 18, 0xffffffff)
        value = unBitshiftLeftXor(value, 15, 0xefc60000)
        value = unBitshiftLeftXor(value, 7, 0x9d2c5680)
        value = unBitshiftRightXor(value, 11, 0xffffffff)
        states.append(value)
    return states

def predict_randbits(bit_length):
    assert(bit_length % 4 == 0)
    global states
    global rand_buffer
    if len(rand_buffer) >= (bit_length // 4):
        res = rand_buffer[:bit_length // 4]
        rand_buffer = rand_buffer[bit_length // 4:]
        return res
    else:
        for i in range(624):
            y = (states[i] & 0x80000000) + (states[(i + 1) % 624] & 0x7fffffff)
            res = y >> 1
            res ^= states[(i + 397) % 624]
            if y & 1 == 1:
                res ^= 0x9908b0df
            states[i] = res
        for i in range(624):
            value = states[i]
            value ^= (value >> 11)
            value ^= (value << 7) & 0x9d2c5680
            value ^= (value << 15) & 0xefc60000
            value ^= (value >> 18)
            rand_buffer += hex(value)[2:].rjust(8, '0')
        res = rand_buffer[:bit_length // 4]
        rand_buffer = rand_buffer[bit_length // 4:]
        return res

def backtrace_randbits(bit_length):
    assert(bit_length % 4 == 0)
    global states
    for i in range(623, -1, -1):
        res = 0
        tmp = states[i]
        tmp ^= states[(i + 397) % 624]
        if (tmp & 0x80000000) == 0x80000000:
            tmp ^= 0x9908b0df
        res = (tmp << 1) & 0x80000000    #the first bit of the res
        # the remaining 31 bits of the res
        tmp = states[(i - 1 + 624) % 624]
        tmp ^= states[(i + 396) % 624]
        if (tmp & 0x80000000) == 0x80000000:
            tmp ^= 0x9908b0df
            res |= 1
        res |= (tmp << 1) & 0x7fffffff
        states[i] = res
    value = ''
    for state in states[-(bit_length // 32 + 1):]:
        state ^= (state >> 11)
        state ^= (state << 7) & 0x9d2c5680
        state ^= (state << 15) & 0xefc60000
        state ^= (state >> 18)
        value += hex(state)[2:].rjust(8, '0')
    return value[-bit_length // 4:]

def main():
    global states
    data = read_data()
    # predict
    states = crack_states(data[-624:])
    print(int(predict_randbits(32), 16))
    # backtrace
    '''
    states = crack_states(data[:624])
    print(backtrace_randbits(32 * 4))
    '''

if __name__ == '__main__':
    main()

More

或者python2下直接调用randcrack

from randcrack import RandCrack

Rand = RandCrack()
with open('random', 'r') as f:
    data = [int(line.rstrip('\n')) for line in f]
assert(len(data) >= 624)
for i in range(624):
    Rand.submit(data[i])
for i in range(624, len(data)):
    Rand.predict_randrange(0, 0xffffffff)
print Rand.predict_randrange(0, 0xffffffff)

视时间补充