Восстановить поврежденный 128-битный ключ из SHA-1 - PullRequest
Новая
       9

Восстановить поврежденный 128-битный ключ из SHA-1

0 голосов
/ 16 октября 2018

Отказ от ответственности: это раздел из универсального задания

Мне дали следующий ключ 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):

резко сокращаетколичество догадок пока (думаю?) еще охватывает все пространство.Все еще получаю дубликаты и все же не везет найти совпадение ..

1 Ответ

0 голосов
/ 16 октября 2018

Ваш код, если он не очень эффективен, выглядит хорошо, за исключением одной вещи: 

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 раз).Это количество комбинаций по 128 битов, взятых по 3 за раз.

Таким образом, всего получается 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.combination : 

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

, но вам потребуется немного больше работы для управления делами с 0, 1, 2 и 3 перевернутыми битами вэто дело.

...