在进行哈希长度扩展攻击前，首先要清楚哈希的原理。

hash 原理（以 sha1 为例）

哈希算法的具体算法其实是非常复杂的，但在这个攻击中只需要理解补位的过程，具体的哈希算法概括为“复杂的计算”。

首先，进行补位。hash 函数将需要被 hash 的字符串的字节长度整除 64，取得余数。如果余数不等于 56，就先对字符串进行长度填充，填充时第一个字节为 0x80 ，其他字节均用 0x00 填充。填充至余数为 56 后，增加 8 个字节的长度描述符，该长度为原字符串的 bit 长度。

补位以后，字符串可以以 64 位一组进行分组。字符串被分成几组就会进行多少次“复杂的计算”。每次进行“复杂的计算”都会生成一组新的 registers 值供下一次“复杂的计算”来调用。第一次“复杂的计算”会调用初始值。最后一个分组生成的 registers 值就是最后的 hash 值。

举个例子

有这样的字符串：key=123456789abcdef，字节长度为 19。

hash_ext_1

对 64 取余不等于 56，所以要进行补位。填充时第一个字节为 0x80，其他字节均为 0x00。填充至 56 位。

hash_ext_2

增加 8 个字节的长度描述符。原字符串共有 19 字节，即 152 bit，即 0x98。注意 sha1 为大端位序。不同 hash 算法存储位序可能不同，例如 md5 为小端位序。

hash_ext_3

现在该分组已经有 64 字节，并且只有一个分组，所以只要进行一次“复杂的计算”，根据该 64 个字节的数据和 registers 初始值生成新的 registers 值，那么该新的 registers 值就是该字符串的 sha1 值。多个分组原理类似。

哈希长度扩展攻击

假如服务器上随机生成一个不可预测的 salt 值，但是知道 hash(salt+filename)，该 filename 也可知。那么我们可以根据已知的 hash 值计算出自己构造的 hash(salt+filename+other)。

假设服务器随机生成的 salt 值为 xFQ2K7W5cn23dKE，长度为 15，filename 为 document.pdf。将 xFQ2K7W5cn23dKE&document.pdf 经过 sha1 计算后值为：740a6f25cad72ec21b46afe4b0f70f6df7180926。

hash_ext_4

我们可以根据 hash 原理自行填充，填充时第一个字节为 0x80，其他字节均为 0x00，填充至 56 位。然后增加 8 个字节的长度描述符，原字符串共有 28 字节，即 224 bit，即 0xE0。将第一个分组填充完毕后，就可以自己计算自己构造的数据的 hash 值了。

hash_ext_5

虽然并不知道 salt，但是我们知道 hash(salt+filename)，以及 salt 的长度，不知道的话需要爆破其长度。经过这样填充后，两次第一个分组的数据完全相同，则第一轮经过“复杂的计算”后 registers 值就完全相同，这个值就是之前得到的 hash 值。然后可以通过第一轮的 registers 值按照哈希算法计算出第二轮的 registers 值。这个值就是最终的 hash。多个分组原理类似。

hash_extender

我们可以利用 hash_extender 工具帮助我们计算扩展后的哈希值。

用法很简单：

-d 原字符串
-a 拓展的字符串
-l 盐的长度
-f 加密方式
-s 带盐加密的 hash 值
--out-data-format 输出格式
--quiet 仅输出必要的值

工具网址：
https://github.com/iagox86/hash_extender

例子

2018百越杯：买手机

题目

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
import random
import string
import signal
import sys
import os
import time
from hashlib import sha256
from urlparse import parse_qsl

os.chdir(os.path.dirname(os.path.abspath(__file__)))
signkey = ''.join([random.choice(string.letters+string.digits) for _ in xrange(random.randint(8,32))])
items = [
    ('iPhone X', 7399),
    ('iPhone 8', 4599),
    ('P20 Pro', 5488),
    ('P20', 3788),
    ('Honor 10', 2399),
    ('Mi 8', 2999),
    ('Find X', 4999),
    ('Nex', 4498),
    ('Mate10 Pro', 4899),
    ('Flag', 99999)
]

money = random.randint(3000, 30000)

def list_items():
    for i,item in enumerate(items):
        print '%2d - %-30s$%d' % (i, item[0], item[1])

def order():
    n = input_int('Product ID: ')
    if n < 0 or n >= len(items):
        print 'Invalid ID!'
        return
    payment = 'product=%s&price=%d&timestamp=%d' % (items[n][0], items[n][1], time.time()*1000000)
    sign = sha256(signkey+payment).hexdigest()
    payment += '&sign=%s' % sign
    print 'Your order:\n%s\n' % payment

def pay():
    global money
    print 'Your order:'
    sys.stdout.flush()
    payment = raw_input().strip()
    sp = payment.rfind('&sign=')
    if sp == -1:
        print 'Invalid Order!'
        return
    sign = payment[sp+6:]
    try:
        sign = sign.decode('hex')
    except TypeError:
        print 'Invalid Order!'
        return

    payment = payment[:sp]
    signchk = sha256(signkey+payment).digest()
    if signchk != sign:
        print 'Invalid Order!'
        return

    for k,v in parse_qsl(payment):
        if k == 'product':
            product = v
        elif k == 'price':
            try:
                price = int(v)
            except ValueError:
                print 'Invalid Order!'
                return

    if money < price:
        print 'Go away you poor bastard!'
        return

    money -= price
    print 'Your current money: $%d' % money
    print 'You have bought %s' % product
    if product == 'Flag':
        print 'Well Done! Here is your flag: %s' % open('flag.txt').read().strip()

def input_int(prompt):
    sys.stdout.write(prompt)
    sys.stdout.flush()
    try:
        n = int(raw_input())
        return n
    except:
        return 0

def menu():
    print "CPU Shop"
    while True:
        print "Money: $%d" % money
        print "1. List Items"
        print "2. Order"
        print "3. Pay"
        print "4. Exit"
        sys.stdout.flush()
        choice = input_int("Command: ")
        {
            1: list_items,
            2: order,
            3: pay,
            4: exit,
        }.get(choice, lambda *args:1)()
        sys.stdout.flush()

if __name__ == "__main__":
    signal.alarm(60)
    menu()

分析

初始金钱只有 3000-30000，肯定买不起 flag。
可以看到服务器会生成一个 8-31 字节的 signkey。
在 order 阶段，生成的 payment 是 product+price+timestamp 的字符串，sign 是将 signkey 和 payment 字符串相加计算 sha256。再把 sign 加到 payment 后面，输出最终的 payment。
重点在 pay 阶段，手动输入 payment，从右向左找 sign 的值，计算 sign 之前的字符串的 sha256，判断是否等于 sign，然后根据 payment 中的 product 和 price 购买相应的物品，钱够就购买成功。
没有逻辑方面的漏洞，但我们可以进行哈希长度拓展攻击。
在 order 阶段得到含有 salt 的 hash 值，在 pay 阶段构造 &price=1，加到末尾，然后用工具计算出新字符串的 hash 值，替换原来的 sign 值。之后的程序由于设计有误 price 的值就会更新为 1，然后就可以成功购买 flag。
但由于我们不知道 signkey 的长度，需要从 8-31 逐次尝试。

代码

由于该题服务器已经关闭，所以我对源码的 order 和 pay 函数进行了修改采用本地测试。
真正比赛时要用 pwntools 连接服务器。

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
def order():
    global s_1
    n = input_int('Product ID: ')
    if n < 0 or n >= len(items):
        print 'Invalid ID!'
        return
    payment = 'product=%s&price=%d&timestamp=%d' % (items[n][0], items[n][1], time.time()*1000000)
    sign = sha256(signkey+payment).hexdigest()
    payment += '&sign=%s' % sign
    s_1 = 'Your order:\n%s\n' % payment

def pay(IN):
    global money
    print 'Your order:'
    sys.stdout.flush()
    payment = IN
    sp = payment.rfind('&sign=')
    if sp == -1:
        print 'Invalid Order!'
        return
    sign = payment[sp+6:]
    try:
        sign = sign.decode('hex')
    except TypeError:
        print 'Invalid Order!'
        return

    payment = payment[:sp]
    signchk = sha256(signkey+payment).digest()
    if signchk != sign:
        print 'Invalid Order!'
        return

    for k,v in parse_qsl(payment):
        if k == 'product':
            product = v
        elif k == 'price':
            try:
                price = int(v)
            except ValueError:
                print 'Invalid Order!'
                return

    if money < price:
        print 'Go away you poor bastard!'
        return

    money -= price
    print 'Your current money: $%d' % money
    print 'You have bought %s' % product
    if product == 'Flag':
        print 'Well Done! Here is your flag: %s' % open('flag.txt').read().strip()

if __name__ == "__main__":
    s_1 = ''
    order()
    s_1, s_2 = s_1[12:63], s_1[69:-1] 
    for i in range(8, 32):
        print 'sign_len =', i
        find_hash = './hash_extender -d \'' + s_1 + '\' -s ' + s_2 + ' -f sha256 -a \'&price=1\' -l ' + str(i) + ' --out-data-format=hex --quiet'
        data = os.popen(find_hash).readline()
        new_hash = data[:64]
        padding = data[64:]
        attack = padding.decode('hex') + '&sign=' + new_hash
        pay(attack)

如何防御

解决这种攻击的办法是使用 HMAC 算法，这种算法进行了双重摘要：
MAC = hash(salt + hash(salt + message))
这样就可以避免用户可控 message 了。

参考文章

https://www.freebuf.com/articles/web/69264.html
https://blog.csdn.net/qq_35078631/article/details/70941204