Crypto入门-流密码初探

基础知识

LCG

线性同余生成器，由线性函数生成随机数序列。标准的LCG的生成序列满足下列递推式：

$$
x_{n+1}=(Ax_n+B)\pmod M
$$

其中$A$、$B$、$M$为设定的常数，初始值$x_0$为种子。

攻破Linux Glibc的rand()函数（TYPE_0）

当使用TYPE_0时，采用的是标准LCG，生成公式为：

$$
s_i=(1103515245s_{i-1}+12345)\pmod{2147483648}
$$

直接求逆元得：

$$
s_{i-1}=1857678181(s_i-12345)\pmod{2147483648}
$$

LFSR

线性反馈移位寄存器，由一个移位寄存器和一个反馈函数组成，反馈函数为一个线性函数。进行密钥流生成时，每次从移位寄存器中移出一位作为当前的结果，而移入的位由反馈函数对寄存器中的某些位进行计算来确定。

为使LFSR获得最大周期，即$n$位LFSR获得$2^n-1$的周期，那么选取反馈函数$F$方法：选取$\operatorname{GF}(2)$上的一个$n$次的本原多项时，如当$n=32$时，选取：

$$
x^{32}+x^7+x^5+x^3+x^2+x+1
$$

得到$F$函数为：

$$
F=s_{32}\oplus s_7\oplus s_5\oplus s_3\oplus s_2\oplus s_1
$$

这种周期最大的序列称为“m序列”。

设某LFSR长度为$n$位，当已知长度为$2n$的输出，且方程组有解时，可获得反馈函数。

例如$4$位未知LFSR，输出序列为“10001010”，从左向右输出，因异或等价于模$2$加法，可列出线性方程组：

$$
\begin{cases}
\displaylines{
1a_0+0a_1+0a_2+0a_3=1\pmod 2\\
0a_0+0a_1+0a_2+1a_3=0\pmod 2\\
0a_0+0a_1+1a_2+0a_3=1\pmod 2\\
0a_0+1a_a+0a_2+1a_3=0\pmod 2
}
\end{cases}
$$

解方程组得：

$$
\begin{cases}
\displaylines{
a_0=1\\
a_1=0\\
a_2=1\\
a_3=0
}
\end{cases}
$$

可求得反馈函数为：$F=s_0\oplus s_2$。

攻破Linux Glibc的rand()函数（TYPE_3）

随机数产生方法：状态数组buf中的fptr和rptr指向的数字相加，再除以$2$。在TYPE_3的情况下，buf长度为34，且fptr与rptr分别为当前下标减$31$和减$3$，线性反馈式为：

$$
x_i=\dfrac{s_{i-3}+s_{i-31}}{2}
$$

但因移入状态数组中的数不是产生后的随机数，而是右移$1$位前的数，末位存在$0$和$1$两种情况。当获取$32$组随机数后，向下预测的下一个数会以$25%$的概率存在$1$的误差，且随着预测数增多而增大。

简单Demo：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(){
    int s[256]={0},i=0;
    srand(time(0));
    for(i=0;i<32;i++)
        s[i]=rand()<<1;
    for(i=32;i<64;i++){
        s[i]=s[i-3]+s[i-31];
        int xx=(unsigned int)s[i]>>1;
        int yy=rand();
        printf("predicted %d, actual %d\n",xx,yy);
        if(yy-xx==1){
            s[i-3]++;
            s[i-31]++;
            s[i]+=2;
        };
    };
    return 0;
};

RC4

略。