一道 SHA1 暴力破解题

mysterytwisterc3 的一道 LVII 的题
CRACKING SHA1-HASHED PASSWORDS

题目

题中给出了一段泄露的 SHA1 值:
67ae1a64661ac8b4494666f58c4822408dd0a3e4
并给出了管理员输入密码时留下的指纹分布。键盘示意图如下(绿色部分为被按过的键):
键盘指纹
要求还原出密码,并且还原时间不超过 10s(这个是老师另外要求的)

分析

SHA1 作为一种散列函数,是单向不可逆的。通过穷举搜索虽然可以找到明文,但是在空间较大时非常困难。
而密钥空间较小时穷举搜索的效果比较好。如果花费时间较多,可以考虑多线程,多进程,甚至分布式

解法

根据指纹分布,首先确定字符集合:
Q,q,W,w,%,5,8,(,=,0,I,i,*,+,n,N
由于题中没说每个按键是否只按了一次,可以假设一个按键只按了一次。那么就有 len(key)=8

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

则 keyChars 中,每个元组中只出现一个字符,一共有 2^8 种情况,即 256 种,复杂度是 O(2^n)
然后对这 256 个字符串中的字符进行 256 次排列,复杂度是 O(n!)
对于每个排列情况,计算它的 SHA1 后与指定的 SHA1 对比。
如果使用单进程,搜索全部 key 需要 16.7s
多进程则只需要 7.42s (win10,4 核)

小优化

仔细看指纹,其实还是有点线索可以用来优化的。
这个键盘有 2 个 shift 键,左右各被按了一次,所以密码至少有 2 个上字符组成。即
( I = * N % Q W 这些字符最少出现 2 个
这样筛选后,256 种情况可以降为 247 种
再者,按照输入习惯,右边的 shift 键应该与靠右边的按键配合使用,所以
( I = * N 至少出现一个,% Q W 至少出现一个
则 256 种情况可以再降为 217 种情况。此时代码运行时间为 6.5s(win10,4 核)

代码及结果

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
# -*- coding: cp936 -*-
import time
import multiprocessing
import itertools
import hashlib

def Func(C):
return [c for c in itertools.permutations(C, 8) if hashlib.sha1(
''.join(c)).hexdigest() == '67ae1a64661ac8b4494666f58c4822408dd0a3e4']

def Check(s):
return s[:3].count('0')>0 and s[3:].count('0')>0 #( I = * N 至少一个,% Q W 至少一个
#return s.count('0')>1

if __name__ == "__main__":
stime = time.clock()
keyChars = [('Q', 'q'), ('W', 'w'), ('%', '5'), ('(', '8'),('=', '0'), ('I', 'i'), ('*', '+'), ('N', 'n')]
Choose = filter(Check,[str(bin(i))[2:].zfill(8) for i in range(256)]) #列表过滤

pool = multiprocessing.Pool()
for res in [pool.apply_async(
Func, ([keyChars[j][int(i[j])] for j in range(len(i))], )) for i in Choose]:

if res.get() != []:
print 'The key is:', ''.join(res.get()[0])

print 'Timer:', round(time.clock() - stime, 2), 's'

代码及结果

做完之后

题中未给出 key 长度,只能猜测每个键没有重复使用,否则搜索空间很大。
在实现并发爆破的时候,由于 Python 存在 GIL,导致此类 CPU 密集型的代码使用多线程的时候效率没有提升反而会下降。
所以最后使用多进程实现并发,如果是 8 核 CPU,速度会进一步提升。

老爷机 4 进程好慢,差点用 java 写了...


来呀快活呀


一道 SHA1 暴力破解题
https://www.tr0y.wang/2017/10/11/Crypto3/
作者
Tr0y
发布于
2017年10月11日
更新于
2024年6月3日
许可协议