一道 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 核)

代码及结果

# -*- 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'