从 SHA-1 恢复损坏的 128 位密钥

Question

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

我得到了以下 AES-128-CBC 密钥，并被告知密钥中最多 3 位 changed/corrupt。

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 循环更改为

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

在（我认为？）仍然覆盖整个 space 的同时大大减少了猜测的数量。仍然得到一些重复，但仍然没有找到匹配项..

Answer 1

你的代码，如果不是很高效，除了一件事看起来还不错：

hexOut = hex(int(b2,2))

作为hex

的输出

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

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

对于可能尝试的键数，您有：

1 位没有翻转
128 位翻转 1
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 个翻转位的情况。

从 SHA-1 恢复损坏的 128 位密钥

Restore corrupt 128-bit key from SHA-1

python

encryption

aes

sha