1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
LCG 的优缺点
--------
LCG 目前是分流行，得益于其在数学表达实现上十分优雅、非常容易理解并且容易设计实现、计算速度可以非常快。但是它也存在一些缺点，比如它在加密安全性方面十分弱。接下来将从以下几种情况对其进行攻击。
### 攻击 LCG
**对于 A、B、M 以及 N0 已知的情况** 假设我们观察到有一个 LCG 系统产生了以下三组连续的值，并且我们知道内部的参数如下:```
# 三组连续的值
s0 = 2300417199649672133
s1 = 2071270403368304644
s2 = 5907618127072939765
# 内部的参数
m = 672257317069504227 # the "multiplier"
c = 7382843889490547368 # the "increment"
n = 9223372036854775783 # the "modulus"
```在已知了这些参数之后我们可以很快的推算出未来的数值或者之前的某个数值，所以还是存在安全问题的。```
In [1]: m = 672257317069504227
In [2]: c = 7382843889490547368
In [3]: n = 9223372036854775783
In [4]: s0 = 2300417199649672133
In [5]: s1 = (s0*m + c) % n
In [6]: s2 = (s1*m + c) % n
In [7]: s3 = (s2*m + c) % n
In [8]: s4 = (s3*m + c) % n
In [9]: s1
Out[9]: 2071270403368304644L
In [10]: s2
Out[10]: 5907618127072939765L
In [11]: s3
Out[11]: 5457707446309988294L
```**增量未知** 我们不清楚增量，但是我们知道以下信息:```
m = 81853448938945944
c = # unknown
n = 9223372036854775783
# 初值和第一个计算值
s0 = 4501678582054734753
s1 = 4371244338968431602
```我们稍稍改写下公式就可以将目标 c 计算出来```
s1 = s0*m + c (mod n)
c = s1 - s0*m (mod n)
```此种类型 Python 攻击代码如下所示:```
def crack_unknown_increment(states, modulus, multiplier):
increment = (states[1] - states[0]*multiplier) % modulus
return modulus, multiplier, increment
print crack_unknown_increment([4501678582054734753, 4371244338968431602], 9223372036854775783, 81853448938945944)
```**增量和乘数都未知** 我们虽然不知道增量和乘数但是我们知道以下数值```
m = # unknown
c = # unknown
n = 9223372036854775783
# LCG 生成的初值和后面生成的两个值
s0 = 6473702802409947663
s1 = 6562621845583276653
s2 = 4483807506768649573
```解决办法很简单，想想怎么解线性方程组就好了```
s_1 = s0*m + c (mod n)
s_2 = s1*m + c (mod n)
s_2 - s_1 = s1*m - s0*m (mod n)
s_2 - s_1 = m*(s1 - s0) (mod n)
m = (s_2 - s_1)/(s_1 - s_0) (mod n)
```此种类型 Python 攻击代码如下所示:```
def crack_unknown_multiplier(states, modulus):
multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
return crack_unknown_increment(states, modulus, multiplier)
print crack_unknown_multiplier([6473702802409947663, 6562621845583276653, 4483807506768649573], 9223372036854775783)
```这个算法中应用到了求模，所以我们就需要逆推。```
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)
def modinv(b, n):
g, x, _ = egcd(b, n)
if g == 1:
return x % n
```**增量，乘数和模数均未知** 现在内部状态基本是都不知道了，但是我们知道初值和随后 LCG 产生的连续的几个值。```
m = # unknown
c = # unknown
n = # unknown
s0 = 2818206783446335158
s1 = 3026581076925130250
s2 = 136214319011561377
s3 = 359019108775045580
s4 = 2386075359657550866
s5 = 1705259547463444505
s6 = 2102452637059633432
```这次用线性方程式不好解决的了，因为对于每一个方程，我们是不知道前一个模数，因此我们将形成的每个方程都会引入新的未知量：```
s1 = s0*m + c (mod n)
s2 = s1*m + c (mod n)
s3 = s2*m + c (mod n)
s1 - (s0*m + c) = k_1 * n
s2 - (s1*m + c) = k_2 * n
s3 - (s2*m + c) = k_3 * n
```这就相当于六个未知数和三个方程。所以线性方程组是不可能行得通的了，但是数论里面有一条很有用:如果有几个随机数分别乘以 n，那么这几个数的欧几里德算法(gcd)就很可能等于 n。```
In [944]: n = 123456789
In [945]: reduce(gcd, [randint(1, 1000000)*n, randint(1, 1000000)*n, randint(1, 1000000)*n])
Out[945]: 123456789
```某些取模运算是会等于 0 的```
X = 0 (mod n)
```然后，根据定义，这相当于：```
X = k*n
```所以这种 X != 0 但是 X = 0 (mod n)的情况就很有趣。我们只需要取几个这样的值进行 gcd 运算，我们就可以解出 n 的值。这种是在模数未知的情况下十分常用的方法。 我们在此引入一个序列 – T(n) = S(n+1) - S(n):```
t0 = s1 - s0
t1 = s2 - s1 = (s1*m + c) - (s0*m + c) = m*(s1 - s0) = m*t0 (mod n)
t2 = s3 - s2 = (s2*m + c) - (s1*m + c) = m*(s2 - s1) = m*t1 (mod n)
t3 = s4 - s3 = (s3*m + c) - (s2*m + c) = m*(s3 - s2) = m*t2 (mod n)
```之后我们就可以得到我们想要的效果了:```
t2*t0 - t1*t1 = (m*m*t0 * t0) - (m*t0 * m*t0) = 0 (mod n)
```然后我们就可以生成几个这样模是 0 的值，进而利用我们上文讲述的技巧，此种类型 Python 攻击代码如下所示:```
def crack_unknown_modulus(states):
diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
modulus = abs(reduce(gcd, zeroes))
return crack_unknown_multiplier(states, modulus)
print crack_unknown_modulus([2818206783446335158, 3026581076925130250,
136214319011561377, 359019108775045580, 2386075359657550866, 1705259547463444505])
|
