一维拼图?

一般逐 bit/byte 处理信息。一般来说

伪随机数生成器 (PRNG)

用来生成接近于绝对随机数序列的数字序列的算法,电子计算机本身只能产生伪随机序列。

一般来说,PRNG 会依赖于一个初始值 seed 来生成对应的伪随机数序列。只要 seed 确定了,PRNG 所生成的随机数就是完全确定的,因此其生成的随机数序列并不是真正随机的,且序列具有周期性。

随机性的严格性

类别 随机性 不可预测性 不可重现性
弱伪随机数
强伪随机数
真随机数

一般来说,密码学中使用的随机数是第二种。

随机序列:不能可靠重复产生、概率服从均匀分布(产生每个比特概率为1/2,任意两个比特统计上相互独立)。给定两个串判断是否随机,只能通过产生其的方法去判断。

分类

目前通用的伪随机数生成器主要有

问题

通常来说,伪随机数生成器可能会有以下问题:

密码学安全伪随机数生成器 (CSPRNG)

一般而言,CSPRNG 的要求可以分为两类:

反馈移位寄存器 (FSR)

一般的,一个 n 级反馈移位寄存器如下图所示:

fsr

一般来说,反馈移位寄存器都会定义在某个有限域上,从而避免数字太大和太小的问题。

线性反馈移位寄存器 (LFSR)

LFSR 的反馈函数一般如下:$a_{i+n}=\sum\limits_{j=1}^{n}c_ja_{i+n-j}$

对于一个 n 级的 LFSR 来讲,其最大周期为2^n-1

多数情况下,考察方式可以概括为:给出反馈函数输出序列,要求我们反推出初始状态。另外大多数情况下,初始状态的长度我们也是已知的。

例题

flag = "flag{xxxxxxxxxxxxxxxx}"
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==14

def lfsr(R,mask):
    output = (R << 1) & 0xffffffff
    i=(R&mask)&0xffffffff
    lastbit=0
    while i!=0:
        lastbit^=(i&1)
        i=i>>1
    output^=lastbit
    return (output,lastbit)

R=int(flag[5:-1],16)
mask = 0b10100100000010000000100010010100

f=open("key","w")
for i in range(100):
    tmp=0
    for j in range(8):
        (R,out)=lfsr(R,mask)
        tmp=(tmp << 1)^out
    f.write(chr(tmp))
f.close()

可以推出每一次的 out,也即 lastbit of (R&mask),mask已知,则可表达为:

$lastbit = R_3\oplus R_5 \oplus R_8\oplus R_{12} \oplus R_{20} \oplus R_{27} \oplus R_{30} \oplus R_{32}$

则知道前 31 个 lastbit 后,现在的 R 由 原R_1 与 lastbit_(1~31) 组成,又知道 lastbit_32,则可推出 原R_1。由此反推,可推出 原R。

import binascii
mask = 0b10100100000010000000100010010100
key = 0x20fdeef8
flag = 0
mul = 1
NBITS = 32
for i in range(NBITS):
    aim = key & 1
    key >>= 1
    i = (key & mask) & 0xffffffff
    lastbit = 0
    while i != 0:
        lastbit ^= (i & 1)
        i = i >> 1
    key |= (aim ^ lastbit) << (NBITS - 1)
    flag += (aim ^ lastbit) * mul
    mul <<= 1
    print(flag)
print('flag{' + hex(flag)[2:] + '}')

相关攻击

若有 NLFSR,其输出函数 Combine() 的结果 S_i 和其中某一个参数 X_i 的相关系数 $P_i \ge 0.6$(列真值表相等的比率),那么我们一般可以认为,X 对应的 LFSR_i 是能够被还原出的。

既然单个 X_i 与 S_i 的相关系数一定是 P_i(与 X 的产生方式完全无关),那么对整个序列而言,相关系数也应趋于 P_i。也就是说,对于既定的 S 序列(依托于正确的 X 序列) 和 正确的 X 序列,相关系数为 P_i。既然我们知道 S 和 X 的产生方式,那枚举 key 就完事。(已知 mask 求 key)

因为相关系数 P_i 偏离 0.5 较大,那么若有足够长的 NLFSR 流,输出就越满足相关系数,基本上不太可能有多解。

快速相关攻击

学习自 深入分析CTF中的LFSR类题目(二)

待补充

知道 2n 序列,怎么日出抽头序列和初始序列呢?

  1. lfsr

    例如构造如上 n*n 的矩阵和 1*n 的抽头序列,然后带入 2n 序列 求解。

    拿到抽头序列后,用对单个 lfsr 的方法去还原初始序列。

  2. B-M 算法

B-M algorithm

见 Post - Algorithm 那一篇。

线性同余生成器(LCG)

\[N_{i+1}\equiv AN_i+B\ (mod\ M)\]

LCG 根据以上递归公式生成,其中 A, B, M 是设定常数。

LCG 的周期最大为 M,但大部分情况都会少于 M。要使 LCG 达到最大周期,应符合以下条件:

详见 https://zeroyu.xyz/2018/11/02/Cracking-LCG/,写的不错。(其中介绍了四种攻击情况)

例题

MT19937 (梅森旋转算法)

之所以叫做是梅森旋转算法,是因为它的最大循环节是 2 ^ 19937 - 1,也即梅森素数。

used in rand() in Ruby, random module in Python and mt_rand() in PHP.

如果知道某一轮 twist 中任意的 state[i], state[i + 1],那么可以得到 state[(i + 397) % 624]。

若知道任意的连续 624 个 state,那无敌了。

Mersenne Twister 最常见的实现方式使用 624 个 32 bits 的初始状态。这些整数按顺序分发 (分发前对每个初始数进行转换),分发完后对该状态应用某种算法以获取下一组 624 个整数。

但这样的伪随机数生成器是有问题的,详见用2个随机值破解PHP的MT_RAND函数

以及可以通过得到连续的 624 个输出,还原出原来的 624 个 states,再根据原算法推算出接下来每个 state 下一次的 value,从而算出接下来的输出。

参考:坏猴子的MT19937详解30C3CTF2013 Guess

这里介绍一下如何由已知 state 推导出原来的 state(以 Python 3 为例):

乱数生成过程如下,不再多说:

tmp = state
tmp ^= (tmp >> 11)
tmp ^= (tmp << 7) & 0x9d2c5680
tmp ^= (tmp << 15) & 0xefc60000
tmp ^= (tmp >> 18)
return tmp

由 old_state 生成 new_state 的过程如下:

y = (state[i] & 0x80000000) + (state[(i + 1) % 624] & 0x7fffffff);
nx = y >> 1
if (y & 1) == 1:
  nx ^= 0x9908b0df
nx ^= state[(i + 397) % 624]
new_state[i] = nx

不难发现 MSB of (nx ^ state[(i + 397) % 624]) 和 LSB of y 保持一致。

所以若已知 new_state[i], old_state[(i + 397) % 624],我们就能推导出 MSB of old_state[i] and old_state[i] without MSB。

如此一来就可以先利用 new_state[i], old_state[(i + 397) % 624] 推出 MSB of old_state[i],再利用 new_state[i - 1], old_state[(i - 1 + 397) % 624] 推出剩余部分。

Tips:state[0] 之所以能推出来,是因为 seed 在产生 state 之前已进行了一轮转换。

显然,__init__ 可逆;而不管是生成乱数的过程 extract_number 还是每 624 组为一轮的 twist,都是线性的,故可以将生成随机数的过程看作是位与位之间的线性变换(单个位的影响)。也即,我们可以将其看作 $GF(2^n)$ 上,$X·T=Y$ 的矩阵运算。其中 $X$ 与 $Y$ 为 1xn 的向量,$T$ 则为 nxn 的矩阵。(同组之中,n 应当为 32 的倍数;不同组之间应为 624 * 32 的倍数)

2020 pwnhub公开赛 CoinFlip2

import random
count = 0
while True:
    print("Progress: %s/50" % count)
    coin = random.getrandbits(1)
    if int(input("Your guess: ")) == coin:
        print("Correct!")
        count += 1
        if count == 50:
            print(open("flag").read())
            exit()
    else:
        print("Wrong!")
        count = 0

以上代码对每个 32bits 输出截取其 MSB。如果我们能够拿到这样的 32 * 624 个输出,并得到其线性变换所对应的满秩矩阵 T,那么我们就能还原出 32 * 624bits 输入。

由于我们想要预测接下来的状态,故我们最好能够得到连续的 624 个 states。所以在 states to outputs 为线性变换的前提下(无论 state 实际上是什么,只要输入输出的位置保持不变,变换矩阵 T 都是固定的),我们可以进行黑盒测试:即设置 X = [1, 0, 0, 0, …, 0, 0] 得到 Y,此时 Y 就是 T 的第 1 行;由此类推,重复 32 * 624 次得到整个 T;然后根据远端的 Y 还原出 states。

但由坏猴子测试,发现这样得到的 T 并不是满秩的,求解出来的 states[0] 总是不正确的,但我们可以由 state[1 ~ 623] 还原出 state[0],进而达成目标。

Xorshift

似乎有简单的操作方法,但👴懒得写了

关于 y = x ^ x >>/<< a & MASK 的攻击方法:

对于每一次操作,都必定有 BIT(y, i) = BIT(x, i) for which i = hibits(a)/lobits(a)。故可以通过每次得到 a bits 部分的相邻 a bits 来还原出整个 x。

def getbits(x, st, size):
    return (x >> st) & ((1 << size) - 1)

def re_lxorshift(y, shift, mask = 0xffffffff, xbits = 32):
    # get x s.t. y = x ^ ((x << shift) & mask)
    for i in range(shift, xbits, shift):
        y ^= (getbits(y, i - shift, shift) & getbits(mask, i, shift)) << i
    return y & ((1 << xbits) - 1)

def re_rxorshift(y, shift, mask = 0xffffffff, xbits = 32):
    # get x s.t. y = x ^ ((x >> shift) & mask)
    y <<= shift
    mask <<= shift
    xbits += shift
    for i in range(xbits - 2 * shift, -1, -shift):
        y ^= (getbits(y, i + shift, shift) & getbits(mask, i, shift)) << i
    xbits -= shift
    y >>= shift
    return y & ((1 << xbits) - 1)

类多项式乘法

def calc(m,p):
    res = 0
    lens = len(hex(p)[2:])
    for i in bin(m)[2:]:
        res*=2
        res^=m if i=='1' else 0
        res^=p if len(hex(res)[2:]) == lens else 0
    return res

若把以上这段代码看作 GF<2> 下的多项式乘法,p 为(多项式)模数,那么这段代码描述的就是在模域 p 下,多项式 m 在 GF<2> 上进行平方的计算。

这样的加密,如果给出 calc(m, p) 要求 m, 那么相当于求一个平方根。最粗暴的方法是用给出的 calc(m, p) 继续进行平方,在一个周期后必定能找到其平方根。

不过我仍对其的多解性和优雅程度保持怀疑态度。

RC4

简介

RC4 是一种密钥长度可变的加密算法。加、解密使用相同密钥,逐字节加密。突出优点是容易实现。现在已被列为不安全的加密算法。

加密流程

KSA

  1. for i in range(256):
        S[i] = i
        T[i] = Key[i % keylen]
    
  2. j = 0
    for i in range(256):
        j = (j + S[i] + T[i]) % 256
        swap(S[i], S[j])
    

PRGA

res = []
i = j = 0
for c in plain:
    i = (i + 1) % 256
    j = (j + S[i]) % 256
    swap(S[i], S[j])
    t = (S[i] + S[j]) % 256
    res.append(chr(ord(c)^S[t]))