SHA1 哈希口令破解与候选空间控制

这篇文章复现 MysteryTwister C3 的题目 Cracking SHA1-Hashed Passwords。

题目给出的 SHA1 哈希值是：

67ae1a64661ac8b4494666f58c4822408dd0a3e4

我们的目标是找到一个 password，使得：

SHA1(password) = 67ae1a64661ac8b4494666f58c4822408dd0a3e4

这里先说清楚：这不是“反解 SHA1”。SHA1 是哈希函数，没有解密算法。实际做法是根据题目线索构造候选口令，然后逐个计算 SHA1 比对。

1. SHA1 口令破解的本质

Python 中计算 SHA1 很简单：

import hashlib

password = "test"
digest = hashlib.sha1(password.encode("utf-8")).hexdigest()
print(digest)

输出：

a94a8fe5ccb19ba61c4c0873d391e987982fbbd3

哈希函数有几个特点：

同一输入总是得到同一输出
输入稍微变化，输出会完全不同
输出长度固定
无法从摘要直接解密回原文

所以破解哈希口令一般是这个流程：

候选口令 -> 计算 SHA1 -> 和目标摘要比较

如果候选空间太大，就会非常慢；如果候选空间控制得好，就可以很快找到答案。

2. 为什么不能盲目暴力

假设完全不知道线索，只枚举 8 位大小写字母、数字和常见符号，候选数量会非常大。

例如只考虑 62 个字符、长度 8：

62^8 = 218,340,105,584,896

这还没有算更多符号。这样的规模不是写两层循环就能轻松跑完的。

所以这道题的核心不是电脑有多快，而是题目给了什么线索，以及如何把线索转成候选空间。

3. 题目线索：键盘指纹与 German keyboard layout

MTC3 题目 PDF 里给了一个重要提示：登录终端键盘上有明显指纹，并且提醒使用 German keyboard layout。

这意味着：

用户输入口令时只按过少数几个物理按键
同一个物理按键可能对应 Shift / 非 Shift 两种字符
符号位置要按德语键盘理解，不能按美式键盘想当然
题目没有告诉字符顺序，所以需要枚举排列

我把可疑键位整理为：

key_positions = [
    ("Q", "q"),
    ("W", "w"),
    ("%", "5"),
    ("8", "("),
    ("=", "0"),
    ("I", "i"),
    ("*", "+"),
    ("n", "N"),
]

每个元组代表同一个物理键可能产生的字符。

4. 候选空间大小

这里有 8 个键位，每个键位有 2 个可能字符，所以先有：

2^8 = 256

题目没有告诉顺序，所以每组选择还要全排列：

8! = 40320

总候选数量上界是：

2^8 * 8! = 10,321,920

这个数量就可控多了。它比盲目枚举所有 8 位可见字符小很多，而且每个候选都有题目线索支撑。

5. Python 实现

核心函数：

import hashlib
import itertools


def crack_sha1_from_keyboard_hash(target_hash: str) -> str:
    key_positions = [
        ("Q", "q"),
        ("W", "w"),
        ("%", "5"),
        ("8", "("),
        ("=", "0"),
        ("I", "i"),
        ("*", "+"),
        ("n", "N"),
    ]

    for choices in itertools.product(*key_positions):
        for chars in itertools.permutations(choices):
            password = "".join(chars)
            if hashlib.sha1(password.encode("utf-8")).hexdigest() == target_hash:
                return password

    raise ValueError("password not found in keyboard candidate space")

第一层：

itertools.product(*key_positions)

负责从每个键位中选一个字符。例如 ("Q", "q") 中选 Q 或 q。

第二层：

itertools.permutations(choices)

负责枚举这 8 个字符的所有顺序。

每次拼出口令后计算：

hashlib.sha1(password.encode("utf-8")).hexdigest()

如果等于目标哈希，就返回。

6. 真实运行结果

运行脚本：

python work\experiment_01_cryptopals_xor\07_crack_mtc3_sha1_password.py

真实 VSCode 截图：

输出结果：

Target SHA1: 67ae1a64661ac8b4494666f58c4822408dd0a3e4
Recovered password: (Q=win*5
Recomputed SHA1   : 67ae1a64661ac8b4494666f58c4822408dd0a3e4
Verification      : PASS

所以恢复出的口令是：

(Q=win*5

重新计算 SHA1 后与题目目标完全一致。

7. 和实验一一起做回归测试

这道题也被放进了实验一的单元测试里，防止后续改代码时破坏结果。

def test_mtc3_sha1_hash_matches_recovered_password(self):
    password = experiment1.crack_sha1_from_keyboard_hash(
        "67ae1a64661ac8b4494666f58c4822408dd0a3e4"
    )
    self.assertEqual(
        hashlib.sha1(password.encode("utf-8")).hexdigest(),
        "67ae1a64661ac8b4494666f58c4822408dd0a3e4",
    )

测试截图：

8. 常见错误

8.1 把 SHA1 当成可逆加密

SHA1 没有密钥，也没有解密。所谓破解，是找到一个输入，其 SHA1 摘要等于目标值。

8.2 不利用题目线索

直接枚举所有 8 位可见字符会非常大。题目给出的键盘指纹和 German keyboard layout 是关键条件。

8.3 忽略 Shift 字符

同一个物理按键可能对应普通字符和 Shift 字符。例如题目中的 %/5、8/(、*/+。

8.4 忽略键盘布局

German keyboard layout 会影响符号键的对应关系。符号不是按自己常用键盘随便猜。

8.5 找到字符串后不复验

最终必须重新计算 SHA1，并确认和目标值完全一致。看起来像口令不代表正确。

9. 防御角度的启发

这道题从防御角度看也很有意义：

不要使用短口令
不要使用裸 SHA1 存储口令
登录设备要注意键盘指纹等物理痕迹
系统应限制在线尝试次数
口令存储应使用带盐慢哈希，例如 Argon2id、scrypt、bcrypt、PBKDF2

尤其是裸 SHA1。SHA1 计算太快，如果数据库泄露，攻击者可以离线高速枚举候选口令。

10. 小结

本题完整流程：

读取目标 SHA1
分析 PDF 中键盘指纹
按 German keyboard layout 建立候选键位
枚举 Shift/非 Shift 选择
枚举字符顺序
逐个计算 SHA1
命中后重新计算验证

这道题最重要的不是写出多少行代码，而是把真实线索转成合理候选空间。候选空间控制好了，哈希破解才会从盲目爆破变成可复现实验。

参考资料

• MysteryTwister C3: Cracking SHA1-Hashed Passwords
• NIST FIPS 180-4, Secure Hash Standard
• Python hashlib 文档: https://docs.python.org/3/library/hashlib.html
• OWASP Password Storage Cheat Sheet