200kB файл для поиска 8! (40320 перестановок) в Python или IDA

Question

Я работаю над разборкой прошивки (процессор Siemens C165 - https://www.infineon.com/dgdl/Infineon-C165-DS-v02_00-en%5B8%5D.pdf?fileId=db3a304412b407950112b43a49a66fd7) в IDA.

У меня есть прошивка, поэтому я также могу прочитать ее через Python.

Мне нужно найти строку перестановки

0, 1, 2, 3, 4, 5, 6, 7 (0-7)

Написал эту простую программу:

from itertools import permutations 
l = list(permutations(range(0,8))) 
print(len(l))

with open("firm.ori", 'rb') as f:
    s = f.read()
for i in l:
    hexstr = '\\x'.join('{:02x}'.format(x) for x in i)
    hexstrfinal = "\\0x" + hexstr
    #print hexstrfinal
    if(s.find(b'hexstrfinal')>0):
        print "found"

Тем не менее, он не находит ничего

Я думал, что последовательность будет рядом друг с другом, но, возможно, нет.

Хочется просто быть уверенным, что программа правильная.

Ну, на самом деле 0-7 должно быть клевом, значит ли это, что мне нужно искать, например, как одну комбинацию:

0x01, 0x23, 0x45, 0x67 

Выше это байты.

Может кто-нибудь подтвердить это и посоветовать, как это искать?

Обновление 1:

Пробовал 2-й вариант

from itertools import permutations 
l = list(permutations(range(0,8))) 
print(len(l))

with open("firm.ori", 'rb') as f:
  s = f.read()
for item in l:
  str1 = ''.join(str(e) for e in item)
  n = 2
  out = [str1[i:i+n] for i in range(0, len(str1), n)]

  hexstr = '\\x'.join(e for e in out)
  hexstrfinal  = "\\x" + hexstr 
  #print hexstrfinal
  if(s.find(b'hexstrfinal')>0):
    print "found"

Но тоже нет хитов...

Есть идеи, что я делаю не так?

Answer 1

В вашем коде есть несколько недоразумений и большая неэффективность. Давайте начнем с недоразумений.

поскольку firm.ori открывается в двоичном режиме (rb), результат s = f.read() это bytes объект. Несмотря на то, что методы похожи на строку, это не строка! Содержит байты, а не символы. Когда вы отображаете это, \x... выходы не указывают на то, что bytes объект, содержащий обратную косую черту ASCII и xes. Вместо этого каждый \x... является escape-последовательностью, используемой для представления шестнадцатеричного значения данного байта, которое не соответствует печатному символу ASCII.

Внутри вашего цикла вы имеете дело исключительно со строками: hexstr = '\\x'.join('{:02x}'.format(x) for x in i) берет вашу перестановку и форматирует ее, чтобы выглядеть как строковое представление bytes объект. Надеюсь, вы поняли из предыдущего параграфа, почему это не сработает.

s.find(b'hexstrfinal') ищет буквенный массив ASCII b'hexstrfinal'не для переменной с именем hexstrfinal, Последний не будет работать, конечно, потому что hexstrfinal имеет тип strне bytes, Если бы вы должны были преобразовать его в bytes используя простой hexstrfinal.encode('ascii'), вы получите b'\\x...', что совсем не то, что вы хотите. Правильный путь будет

s.find(hexstrfinal.encode('ascii').decode('unicode-escape').encode('latin1'))

Надеюсь, вы поймете, почему излишне неэффективно преобразовывать строку три раза, чтобы получить bytes ты хочешь. Каждый раз, когда вы начинаете использовать строки в качестве опоры для манипулирования числами, самое время оценить ваш подход. Это начинает наше обсуждение неэффективности в вашем коде.

В настоящее время вы пытаетесь перебрать все возможные перестановки 0-7 вместо того, чтобы искать перестановки, которые на самом деле есть. Учитывая, что размер файла составляет всего 200 КБ, было бы неразумно ожидать, что в нем появятся все или даже большинство перестановок. Кроме того, вы ищете во всем файле для каждой возможной перестановки. Для размера файла N а также K перестановки, ваш код работает в O(N * K) время, в то время как это можно сделать за один проход через файл, или O(N), При наличии соответствующих структур данных даже цикл, написанный на простом Python, скорее всего будет работать быстрее, чем оптимизированная версия текущего кода.

Стратегия проста. Итерация по s, Если текущий персонаж и следующие семь составляют правильную перестановку, начните вечеринку. В противном случае продолжайте искать:

N = 8
allowed = set(range(N))
for index, b in enumerate(s):
    if b in allowed and set(s[index:index + N]) == allowed:
        print(f'Found sequence {s[index:index + N]} at offset {index}')

Здесь возможен целый ряд возможных оптимизаций, и вы могли бы сделать все это более эффективно с помощью numpy или scipy.

Вещи также станут более сложными, если вы разрешите повторения в последовательности. В этом случае вам придется отсортировать последовательности:

allowed = sorted(...)
N = len(allowed)
for index, b in enumerate(s):
    if b in allowed and sorted(s[index:index + N]) == allowed:
        print(f'Found sequence {s[index:index + N]} at offset {index}')

Если вы собираетесь искать кусочки, все становится еще сложнее. Я бы бросил чек полностью b in allowedи просто напишите пользовательскую проверку, которая может применяться на каждом полушаге:

N = 8

def build_set(items):
    output = set()
    for b in items:
        output.add(b & 0xF)
        output.add((b >> 4) & 0xF)
    return output

def matches(seq):
    if len(seq) == N // 2:
        return build_set(seq) == allowed
    elif len(seq) == N // 2 + 1:
        check = build_set(seq[1:-1])
        check.add(seq[0] & 0xF)
        check.add((seq[-1] >> 4) & 0xF)
        return check == allowed
    else:
        return False

allowed = set(range())
for index, b in enumerate(s):
    if matches(s[index:index + N // 2]):
        print(f'Found sequence {s[index:index + N // 2]} at offset {index}.0')
     if matches(s[index:index + N // 2 + 1]):
        print(f'Found sequence {s[index:index + N // 2 + 1]]} at offset {index}.5')

Вот, build_set просто разбивает грызть в набор. matches проверяет либо массив из 8 полубайтов, выровненный по байту (4 элемента), либо массив из 8 полубайтов, смещенный на половину байта (5 элементов). Оба случая сообщаются независимо.

Answer 2

Не понятно, что вы пытаетесь найти, но...

Каждая перестановка (0,1,2,3,4,5,6,7) будет кортеж из семи предметов, подобный этому

t = (7, 6, 4, 1, 3, 5, 0, 2)

Вы можете сделать строки из двух элементов, как это

>>> a = [''.join(map(str,thing)) for thing in zip(t,t[1:])]
>>> a
['76', '64', '41', '13', '35', '50', '02']

Затем сделайте целые числа из строк и передайте его bytes

>>> b = bytes(map(int,a))
>>> b
b'L@)\r#2\x02'

Тогда ищи его

>>> b in s
????

Если это не находит это, это не там.

---

Вот десятибайтовый объект (похожий на ваш файл)

>>> b = b'\xcbl\x7f|_k\x00\x9f\xa2\xcc'

Просто так получилось:

>>> bytes([203, 108, 127, 124, 95, 107, 0, 159, 162, 204])

Поиск 3-символьных (или 3-целых) последовательностей

>>> bytes([127,94,107]) in b
False
>>> bytes([127,95,107]) in b
False
>>> bytes([124,95,107]) in b
True
>>>

---

Когда я использую двоичные файлы, я действительно думаю, что целые числа, а не символы.