从 SHA-1 恢复损坏的 128 位密钥
Restore corrupt 128-bit key from SHA-1
免责声明:这是单向作业的一部分
我得到了以下 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 的同时大大减少了猜测的数量。仍然得到一些重复,但仍然没有找到匹配项..
你的代码,如果不是很高效,除了一件事看起来还不错:
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 个翻转位的情况。
免责声明:这是单向作业的一部分
我得到了以下 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 的同时大大减少了猜测的数量。仍然得到一些重复,但仍然没有找到匹配项..
你的代码,如果不是很高效,除了一件事看起来还不错:
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 个翻转位的情况。