python - 从SHA-1恢复损坏的128位 key

免责声明：这是uni作业的一部分

我得到了以下AES-128-CBC密钥，并告知密钥中最多3位已更改/损坏。

d9124e6bbc124029572d42937573bab4

提供了原始密钥的SHA-1哈希值；

439090331bd3fad8dc398a417264efe28dba1b60

而且我必须通过尝试最多3位翻转的所有组合来找到原始密钥。

据推测，这在349633个猜测中是可能的，但是我不知道该数字来自何处；我本来以为它将接近128 * 127 * 126，这将超过2M组合，这是我的第一个问题所在。
其次，我在下面创建了一个Python脚本，其中包含一个三重嵌套循环（我知道，远非最佳代码...）来迭代所有2M可能性，但是，在一小时后完成后，它没有找到我真正匹配的任何匹配项不明白

希望有人能为我指明正确的方向，欢呼

#!/usr/bin/python2

import sys
import commands

global binary

def inverseBit(index):
    global binary
    if binary[index] == "0":
        return "1"
    return "0"

if __name__ == '__main__':
    if len(sys.argv) != 3:
        print "Usage: bitflip.py <hex> <sha-1>"
        sys.exit()

    global binary
    binary = ""

    sha = str(sys.argv[2])
    binary = str(bin(int(sys.argv[1], 16)))
    binary = binary[2:]
    print binary

    b2 = binary
    tries = 0
    file = open("shas", "w")

    for x in range(-2, 128):
        for y in range(-1,128):
            for z in range(0,128):
                if x >= 0:
                    b2 = b2[:x] + inverseBit(x) + b2[x+1:]
                if y >= 0:
                    b2 = b2[:y] + inverseBit(y) + b2[y+1:]
                b2 = b2[:z] + inverseBit(z) + b2[z+1:]
                #print b2
                hexOut = hex(int(b2,2))
                command = "echo -n \"" + hexOut + "\" | openssl sha1"
                cmdOut = str(commands.getstatusoutput(command))
                cmdOut = cmdOut[cmdOut.index('=')+2:]
                cmdOut = cmdOut[:cmdOut.index('\'')]
                file.write(str(hexOut) + " | " + str(cmdOut) + "\n")
                if len(cmdOut) != 40:
                    print cmdOut
                if cmdOut == sha:
                    print "Found bit reversals in " + str(tries) + " tries. Corrected key:"
                    print hexOut
                    sys.exit()
                b2 = binary
                tries = tries + 1
                if tries % 10000 == 0:
                    print tries

编辑：
更改为

for x in range(-2, 128):
            for y in range(x+1,128):
                for z in range(y+1,128):

在仍覆盖整个空间的同时（我认为吗？）大大减少了猜测的数量。虽然仍然有一些重复，但仍然找不到运气。

最佳答案

您的代码虽然效率不高，但除了以下几点外，看起来还不错：

hexOut = hex(int(b2,2))

作为hex的输出

>>> hex(int('01110110000101',2))
'0x1d85'

以'Ox'开头，不应该是键的一部分。因此，删除这两个字符应该没问题。

有关可以尝试使用的键的数量，您可以：


1，没有任何翻转
翻转1位的128
128 * 127/2 = 8128，翻转了2位（选择第一个的128种方法，选择第二个的127种方法，每对将出现两次）
128 * 127 * 126/6 = 341376，翻转了3位（每个三元组出现6次）。这是一次取3的128位组合的数量。


因此，总数为1 + 128 + 8128 + 341376 = 349633。

您的代码对它们每个进行了多次测试。您可以通过这样循环（3位）来避免无用的重复：

for x in range (0, 128):
    for y in range(x+1, 128):
        for z in range(y+1, 128):
            .....

您可以采用以下方法调整从-2开始的技巧：

for x in range (-2, 128):
    for y in range(x+1, 128):
        for z in range(y+1, 128):
            .... same code you used ...

您还可以使用itertools.combinations生成组合：

from itertools import combinations
for x, y, z in combinations(range(128), 3):  # for 3 bits
    ......

但是在这种情况下，您需要做更多的工作来处理0、1、2和3翻转位的情况。