NaiveBlue

哈希长度扩展攻击总结

哈希长度扩展攻击(Hash Length Extension Attacks)是一种常见的密码分析方法,在消息验证码(MAC)中应用很广,WEB类题目中也有出现,应队里WEB手要求,第一篇博客就先写这个吧。

应用

在基于 Merkle–Damgård 架构的哈希算法中,如果攻击者掌握了 $Hash(message)$ 的值以及 $message$ 的长度,那么在不知道 $message$ 的情况下,可以获取 $Hash( message\ ||\ padding\ ||\ message’ )$ 的值,其中 $message’$ 为任意值,$padding$ 通过 $message$ 长度计算决定。md5/sha1/sha256 算法可被攻击,sha224 虽然基于Merkle–Damgård架构,但不受影响,sha3 族算法不基于 Merkle–Damgård 架构。

原理

Merkle–Damgård 架构如下图所示。

其中 $IV$ 表示初始向量,$f$ 为压缩函数,$M$ 为明文分块输入,$L$ 为块数,$CV$ 为链接向量。明文每512位为一块,最后的短块依次填充1位1和若干位0(按字节表示为\x80\x00\x00\x00…)直到最后一块中有448位(若短块不小于448位则新加一块,并填充至新块的448位),在剩下的64位中填上有效字节数,最高有效位在前。完整明文块和填充后的短块均为512位,和前一轮的链接向量(首轮则为初始向量)共同作为压缩函数的输入计算出本轮的链接向量。用 $T$ 表示链接向量的拼接操作

  • $Hash(message) = T(CV_L)$。

哈希函数的输出为当前明文填充后的链接变量依次拼接,对于特定的哈希函数(即压缩函数 $f$ 确定),可计算$CV_{i+1} = f(CV_i,\ M_i)$。掌握了 $Hash(message)$ 就等同与掌握了将 $message$ 分组、填充后所得到的最后一轮链接向量,对于任意选取的 $message’$:

  • $Hash(message\ ||\ padding\ ||\ message’) = f(CV_L,\ message’)$
  • $CV_L = T^{-1}(Hash(message))$

用 $Hash(message)$ 值替换 $Hash$ 函数的初始向量得到一个修改过的哈希函数 $Hash’$,那么

  • $f(Hash(message),\ message’) = Hash’(message’)$

前文提到 sha224 不受长度扩展攻击影响,是因为它的链接向量有32字节,而算法输出的哈希值为其中前28字节,链接向量未完全暴露。

实例

mtpox PlaidCTF 2014

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
<?php
require_once("secrets.php");
$auth = false;
if (isset($_COOKIE["auth"])) {
$auth = unserialize($_COOKIE["auth"]);
$hsh = $_COOKIE["hsh"];
if ($hsh !== hash("sha256", $SECRET . strrev($_COOKIE["auth"]))) {
$auth = false;
}
}
else {
$auth = false;
$s = serialize($auth);
setcookie("auth", $s);
setcookie("hsh", hash("sha256", $SECRET . strrev($s)));
}
if ($auth) {
if (isset($_GET['query'])) {
$link = mysql_connect('localhost', $SQL_USER, $SQL_PASSWORD) or die('Could not connect: ' . mysql_error());
mysql_select_db($SQL_DATABASE) or die('Could not select database');
$qstr = mysql_real_escape_string($_GET['query']);
$query = "SELECT amount FROM plaidcoin_wallets WHERE id=$qstr";
$result = mysql_query($query) or die('Query failed: ' . mysql_error());
$line = mysql_fetch_array($result, MYSQL_ASSOC);
foreach ($line as $col_value) {
echo "Wallet " . $_GET['query'] . " contains " . $col_value . " coins.";
}
} else {
echo "<html><head><title>MtPOX Admin Page</title></head><body>Welcome to the admin panel!<br /><br /><form name='input' action='admin.php' method='get'>Wallet ID: <input type='text' name='query'><input type='submit' value='Submit Query'></form></body></html>";
}
}
else echo "Sorry, not authorized.";
?>

这个题是长度扩展攻击的入门题,不过代码中没有暴露私钥 SECRET 的长度,需要通过尝试来确定。

代码逻辑非常直白,如果 cookie 里没有 auth 字段或者哈希验证不通过,服务器就把 false 的序化串 b:0; 放进 cookie 的 auth 字段,把 sha256( SECRET || strrev('b:0;') ) 放进 cookie 的 hsh 字段。如果哈希验证通过,并且 auth 的反序化对象能被判断为真则进入下一步注入。

sha256每块64字节,最后一块的最后8字节表明长度,若 SECRET 长度为 x ,那么填充内容为'\x80' + '\x00'\*(51-x) + hex(x+4)(这里的hex长度8字节,高位用\x00填充,auth 长度为4字节,\x80 占1字节,所以 \x00 字节共51-x个),在下一块的内容是能被反序化后能被判断为真的字符串的翻转,比如 ‘;1:b’ 。所以 auth 的内容为'b:1;' + strrev( '\x80' + '\x00'*(51-x) + hex(x+4) ) + 'b:0;' + SECRET,根据之前得到的 hsh 值,枚举 x 计算长度扩展后的哈希值。

xor挑战 三个白帽

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
<?php
include("config.php");
header("Content-type: text/html; charset=utf-8");
function authcode($string, $operation = 'DECODE', $key = '', $expiry = 0) {
$ckey_length = 8;
$key = md5($key ? $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 = hash('sha256', $keya.md5($keya.$keyc));
$string = $operation == 'DECODE' ? base64_decode(substr($string, $ckey_length)) : sprintf('%010d', $expiry ? $expiry + time() : 0).md5($keyb.$string).$string;
$string_length = strlen($string);
$result = '';
for ($i=0; $i<$string_length; $i++){
$result .= $string[$i] ^ $cryptkey[$i % 64];
}
if($operation == 'DECODE') {
if((substr($result, 0, 10) == 0 || substr($result, 0, 10) - time() > 0) && substr($result, 10, 32) == md5($keyb.substr($result, 42))) {
return substr($result, 42);
} else {
return '';
}
} else {
return $keyc.str_replace('=', '', base64_encode($result));
}
}
if (isset($_GET['showSource'])){
show_source(__FILE__);
die;
}
session_start();
if ($_COOKIE['auth']){
list($user, $password) = explode("\t", authcode($_COOKIE['auth'], 'DECODE', $secret_key));
if ($user !='' && $password != ''){
$sql = "select uid, username, password from users where username='$user'";
$result = mysql_query($sql);
if ($result){
$row = @mysql_fetch_array($result);
if ($row['password']===md5($password)){
$_SESSION['uid'] = $row['uid'];
echo "<div style=\"text-align:left\"><h4>Welcome ".$row['username'].". My lord!</h4></div><br/>";
}
}
}
}
if (!$_SESSION['uid']) {
echo "<div style=\"text-align:left\"><h4>Decrypt me!: ".authcode(base64_encode($msg), 'ENCODE', $secret_key)."</h4></div><br/>";
}else{
echo $msg;
}
?>
<!--<a href="/?showSource">view source</a>-->

读懂代码之后难度不算大,主要的难点并不在与长度扩展攻击,而是破解异或加密。

明文在经过 authcode 函数加密后,形式如下:

  • cipher = keyc || base64( cryptkey xor result )
  • result = "0000000000" || md5( keyb || plain ) || plain

其中 keyc 可视为一个随机公钥,明文进行加密时系统会随机选定并作为密文的前8字节给出, keyb 是私钥, cryptkey 是 keyc 和另一私钥 keya 哈希计算的结果,也可视为私钥。

打开这个php首先看到 msg 的密文,可以从中恢复出 t = cryptkey xor result 这一步的值, cryptkey 有64位,对 result 进行循环异或,注意到 result 的前10位是 0,11-42位是 md5 值,也就是字符 0-f ,后面的全部是可打印字符。那么 cryptkey 的前10位可以直接解出,11-42位各有16种可能,后面各位各有64种可能,最后一位是等号的可能性非常大,由于是循环加密,并且 msg 是有意义的字符串,将 cryptkey 各位上的可能字符集求交集就能将它推出。

求出 cryptkey 后,就得到了 md5( keyb || msg ) 和 msg ,然后构造一个 $_COOKIE['auth'] 的密文进行注入,后面的步骤就比较简单了。由于 cryptkey 是用 keyc 和 keya 计算得到,不能构造,而 keya 在加解密中一直不变,所以构造的密文中的 keyc 仍然使用 msg 密文中的 keyc 。以 msg 为前缀构造注入语句 plain ,其中包含 '\t' 字符可被分为 username 和 password 两部分,利用长度扩展攻击计算 md5( keyb || plain ) ,再依次计算 result 和 cipher ,放到 cookie 里,完成。

salt 强网杯 2015

2015年强网杯的salt是我做的第一个长度扩展,当时还不知道这种攻击方法,还好经过虾米酱提醒,学习了一个新姿势。

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
import random, string, re, urlparse
from hashlib import sha1
import SocketServer,threading,os
try:
from flag import FLAG
except:
FLAG = 'flag{test-flag}'
urlre = re.compile('^/login\?username=.+&password=.+$')
passwordre = re.compile('^[-_a-z0-9]{6,20}$', re.I)
def ask(s, msg = ''):
if msg:
s.send(msg)
try:
return s.recv(10).lower()[0] in ('y', '\n')
except:
return False
class threadedserver(SocketServer.ThreadingMixIn, SocketServer.TCPServer):
pass
class incoming(SocketServer.BaseRequestHandler):
def handle(self):
cur_thread = threading.current_thread()
self.request.settimeout(120)
self.request.send('Here is a login system using sha1(salt + password) to protect your safety.\nHow many password/hash pair do you need to crack the salt?\n')
salt = ''.join([random.choice(string.printable[:62]) for x in range(16)])
seen = set()
while True:
if not ask(self.request, msg = "Register Account?[Y/n] "):
break
self.request.send("Your username: ")
username = self.request.recv(1024).strip()
if not username or username == 'admin':
self.request.send('invalid username')
return
self.request.send("Your password: ")
password = self.request.recv(1024).strip()
if not password:
self.request.send('invalid password')
return
url = '/login?username=' + username + '&password=' + password
if url in seen:
self.request.send('duplicate password\n')
return
seen.add(url)
sr = sha1(salt + url)
srx = [x for x in sr.hexdigest()]
rans = set()
while len(rans) < 7:
rans.add(random.randint(0, len(srx)-1))
for i in rans:
srx[i] = 'x'
self.request.send('%s\n' % ''.join(srx))
r = random.randint(0, 1)
correct = False
if r == 0:
self.request.send('Question1: Tell me the salt: ')
if self.request.recv(1024) == salt:
correct = True
elif r == 1:
self.request.send('Question2: Now try to cheat the login system.\nSend login url: ')
url = self.request.recv(1024)
if not url: return
self.request.send('Signature: ')
sig = self.request.recv(1024).strip()
if not sig: return
urlparsed = urlparse.urlparse(url)
account = dict((k, v) for k, v in urlparse.parse_qsl(urlparsed.query))
self.request.send(str(len(url)) + '\n' + sha1(salt + url).hexdigest() + '\n' + sig + '\n')
if urlre.match(url) and account.get('username') == 'admin' and passwordre.match(account.get('password', '')) \
and len(account) == 2 and urlparsed.path == '/login' and sig == sha1(salt + url).hexdigest():
correct = True
if correct:
self.request.send('Congratulations, flag is %s\n' % FLAG)
else:
self.request.send('Incorrect answer, bye\n')
SocketServer.TCPServer.allow_reuse_address = True
server = threadedserver(("0.0.0.0", 4444), incoming)
server.timeout = 120
server_thread = threading.Thread(target=server.serve_forever)
server_thread.daemon = False
server_thread.start()

简单解释题意:

  • 可以注册多个账号,用户名不能是 admin
  • 服务器每次将检查通过的用户名密码拼接成一个url:/login?username=x&password=y
  • 服务器将16字节密钥 salt 与 url 拼接后用 sha1 进行签名,以十六进制形式发给用户,Signature = sha1( salt || url ).hexdigest() ,随机隐去其中7位
  • 用户选择一种方式进行hack:
    • 提交 salt
    • 提交一对匹配的 url 和签名,从 url 中提取的 username 是 admin

这个题salt肯定是算不出来的,整体思路是通过长度扩展攻击算出被隐去部分内容的签名值。有用的签名值需要满足两点: username 是 admin ,并且可以用来进行长度扩展。

对于url的限制有两点:

  • 正则满则^/login\?username=.+&password=.+$
  • 通过 urlparse 进行解析所得到的字典长度为2, username 为 admin

在注册的时候 username 写admin&username=admin或其它类似的方法就能绕过这个验证,获得一个有用的签名,下一步就是进行长度扩展攻击来确定签名中被隐去的字符。

在服务器上注册两次,服务器生成的 url 分别为 url1 和 url2 ,并使 url1 是 url2 的前缀,若知道sig1 = sha1( salt || url1 ),就可以用长度扩展攻击得到sig2 = sha1( salt || url2 )的值。所以枚举sig1中的未知字符进行扩展,经计算所得与sig2比对,比对成功则得到了两个有用的签名值。

这个方法复杂度为$16 ^ 7 * O(sha1)$,当时我是拿到两个签名之后调用一个修改的C代码来算,如果用python不知道能不能在120秒内算出来。


禁止商业转载,转载请注明作者及原链接