Поиск повторяющихся байтовых сигнатур в файле

Discussion in 'Криптография, расшифровка хешей' started by deim_1, 9 Jan 2021.

  1. deim_1

    deim_1 Member

    Joined:
    3 Feb 2016
    Messages:
    63
    Likes Received:
    9
    Reputations:
    0
    Доброго времени суток.

    Необходимо найти повторяющиеся байтовые сигнатуры в hex файле объёмом до 1 Гб.
    при этом изначально не известно какие они будут.
    нужно найти все возможные варианты.
    Самая большая загвоздка для меня в том что эти сигнатуры могут иметь вид
    bytes==0x2c && bytes[i+2]==0x5f && bytes[i+4]==0x65 && bytes[i+6] = 0x89 etc.
    соответственно bytes[i+1], bytes[i+3], bytes[i+5]- могут быть любыми значениями
    минимальная длинна 4 повторяющихся байта(то есть либо 0x2c 0x5f 0x65 0x89, либо 0x2c 0x01 0x5f 0x02 0x65 0x03 0x89)
    Еще добавлю, что не может быть смешанных видов сигнатур. То есть если они повторяются по порядку, то во всем файле. Если повторяются через один байт, то также во всём файле. Если в одном месте имеем определённые байты по порядку, а вдругом эти же байты встетились через один, то это не наш случай.
    Существуют ли инструменты которые позволяют делать подобный анализ данных? Если нет, то подскажите оптимальный алгос для решения этой задачи буду пилить прогу сам.
     
  2. VasiliyP

    VasiliyP Well-Known Member

    Joined:
    30 Aug 2011
    Messages:
    316
    Likes Received:
    600
    Reputations:
    9
    Такой поиск можно реализовать при помощи регулярных выражений. Например, регулярное выражение для первого случая записывается так:
    \x2c.\x5f.\x65.\x89
    А потестировать можно так:
    Code:
    perl -0777 -ne 'printf "%v02x\n", $_ for /\x2c.\x5f.\x65.\x89/gs' file.bin
     
  3. deim_1

    deim_1 Member

    Joined:
    3 Feb 2016
    Messages:
    63
    Likes Received:
    9
    Reputations:
    0
    А если мы не знаем какие повторяющиеся значения будут попадаться. Если сигнатура известна, то проблем нет. Если же не известна, то это мой случай.
    я там значения для примера привёл. фактически же не повторяющиеся байты не известны
     
  4. fandor9

    fandor9 Reservists Of Antichat

    Joined:
    16 Nov 2018
    Messages:
    604
    Likes Received:
    1,018
    Reputations:
    46
    Не совсем понял, вы ищите сигнатуры/патерны которые повторяются во всём файле?
    Т.е. 0x2c 0xXX 0x5f 0xXX 0x65 0xXX 0x89 повторяется до конца файла или же они где-то повторяются, но не везде? И где они начинаются, всегда в одном месте или смещено?
     
  5. deim_1

    deim_1 Member

    Joined:
    3 Feb 2016
    Messages:
    63
    Likes Received:
    9
    Reputations:
    0
    Мне нужно найти повторяющиеся байты в файле. Какие это байты, я заранее не знаю. Они могут повторяться во всём файле от самых первых до последних.
    Смысл такой, в файле хранятся зашифрованные заголовки блоков данных. Их нужно найти. Они разные для каждого файла, но точно имеют одинаковый вид внутри одного файла.
     
  6. fandor9

    fandor9 Reservists Of Antichat

    Joined:
    16 Nov 2018
    Messages:
    604
    Likes Received:
    1,018
    Reputations:
    46
    Ну тогда как идея, если байты повторяются, но вы не знаете какие, то если их заксорить (XOR)
    Code:
    0x2c 0x01 0x5f 0x02 0x65 0x03 0x89
    XOR
    0x2c 0x61 0x5f 0x42 0x65 0x31 0x89
    --------------------------------------------------
    0x00 0x60 0x00 0x40 0x00 0x32 0x00
    то должно выходить каждый второй байт будет 0, а потом уже вытаскивать саму сигнатуру. Сам ХОR должен очень быстро проходить.
    Т.е. алгоритм где-то такой:
    1 задаёте длину сигнатуры в байтах (минимум 4 байта) и максимум скажем 128,
    2 затем по длину всего файла
    3 берёте 2 куска заданной длины и делаете XOR,
    4 сравниваете результат, содержит ли он каждый второй байт 0.
    5 Если да, то это ваш кандидат, записывайте в список. -> вы получаете длину сигнатуры и саму сигнатуру.
    Как-то так
     
  7. VasiliyP

    VasiliyP Well-Known Member

    Joined:
    30 Aug 2011
    Messages:
    316
    Likes Received:
    600
    Reputations:
    9
    Допустим, исходный файл начинается так 00 11 22 33 44 55 66 77 88 99 и мы ищем паттерн XX __ YY __ ZZ __ WW (буквы - неизвестные байты, имеющие значение, подчеркивание - байты значение которых не важно)
    Выписываем все четвёрки байт таким образом
    00 22 44 66
    11 33 55 77
    22 44 66 88
    ...
    После чего сортируем эту таблицу с подсчётом частоты появления каждой четвёрки, в результате видим наиболее часто встречающиеся паттерны (их может быть несколько из-за коллизий). Ну, а далее -
     
  8. deim_1

    deim_1 Member

    Joined:
    3 Feb 2016
    Messages:
    63
    Likes Received:
    9
    Reputations:
    0
    Если честно, то мне было влом сильно ломать мозг и я решил задачу в лоб:
    string file = @"file.......";

    byte[] data = File.ReadAllBytes(file);

    for(int i = 0; i< data.Length-8; i++)
    {

    byte sb1 = data;
    byte sb2 = data[i+ 1];
    byte sb3 = data[i+ 2];
    byte sb4 = data[i + 3];
    byte sb5 = data[i + 4];
    byte sb6 = data[i + 5];
    byte sb7 = data[i + 6];
    byte sb8 = data[i + 7];

    if (sb2==0x02 || sb2 == 0x04 || sb2 == 0x06 || sb2 == 0x08 || (sb1 == sb2 && sb2 == sb3 && sb3 == sb4)) continue; // тут всякие условия чтобы откинуть мусор
    if (sb2 == 0xff || sb2 == 0x00 ) continue;
    if (sb4 == 0xff || sb4 == 0x00 ) continue;
    if (sb6 == 0xff || sb6 == 0x00 ) continue;
    if (sb8 == 0xff || sb8 == 0x00 ) continue;
    if (sb1 != 0x00 || sb3 != 0x00 || sb5!=0x00 || sb7!=0x00) continue;


    for (int j = 0; j < data.Length-8; j++)
    {
    if (data[j] == sb1 && data[j + 1] == sb2 && data[j + 2] == sb3 && data[j + 3] == sb4 && data[j + 4] == sb5 && data[j + 5] == sb6 && data[j + 6] == sb7 && data[j + 7] == sb8 && j != i * 4)
    {

    Debug.WriteLine($"Find 0x{sb1.ToString("X2")},0x{sb2.ToString("X2")},0x{sb3.ToString("X2")},0x{sb4.ToString("X2")},0x{sb5.ToString("X2")},0x{sb6.ToString("X2")},0x{sb7.ToString("X2")},0x{sb8.ToString("X2")} in position {j}");
    }
    }

    Console.WriteLine($"{i} from {data.Length}");
    }

    работает долго. но мои паттерны нашла.
     
  9. DartPhoenix

    DartPhoenix Elder - Старейшина

    Joined:
    15 Sep 2013
    Messages:
    979
    Likes Received:
    7,486
    Reputations:
    23
    В худшем случае тупой перебор.

    Первый байт - 4F. Ищем 4F во всем файле. Находим первое совпадение - берем второй байт. 4F 2C. Не подходит - создаем ветвь для 2С ищем дальше.

    Решение - дерево. Памяти займет хрен знает сколько, решение в лоб - но решается.
     
  10. DartPhoenix

    DartPhoenix Elder - Старейшина

    Joined:
    15 Sep 2013
    Messages:
    979
    Likes Received:
    7,486
    Reputations:
    23
    О_о. Не.... Это.... не :)
     
  11. DartPhoenix

    DartPhoenix Elder - Старейшина

    Joined:
    15 Sep 2013
    Messages:
    979
    Likes Received:
    7,486
    Reputations:
    23
    Мммм. Хрен знает сколько - это как минимум количество байт файла * 2*размер.
     
  12. DartPhoenix

    DartPhoenix Elder - Старейшина

    Joined:
    15 Sep 2013
    Messages:
    979
    Likes Received:
    7,486
    Reputations:
    23
    Хотя даже не обязательно дерево. С деревьями можно делать магию но можно просто для каждого случая создавать отдельного потомка. Работать будет долго - но работать будет. Х/з как быстрее. Надо думать.
     
  13. deim_1

    deim_1 Member

    Joined:
    3 Feb 2016
    Messages:
    63
    Likes Received:
    9
    Reputations:
    0
    ну это лучше чем глазками по hexy бегать подумал я и запил ЭТО.
     
  14. DartPhoenix

    DartPhoenix Elder - Старейшина

    Joined:
    15 Sep 2013
    Messages:
    979
    Likes Received:
    7,486
    Reputations:
    23
    Так тебе надо 8 байт искать конкретно совпадающих ? Тогда напрасный труд ты запилил.
    Если не только - то оно вообще не будет работать...
     
  15. DartPhoenix

    DartPhoenix Elder - Старейшина

    Joined:
    15 Sep 2013
    Messages:
    979
    Likes Received:
    7,486
    Reputations:
    23
    Вместо того чтобы писать

    byte sb1 = data;
    byte sb2 = data[i+ 1];
    byte sb3 = data[i+ 2];
    byte sb4 = data[i + 3];
    byte sb5 = data[i + 4];
    byte sb6 = data[i + 5];
    byte sb7 = data[i + 6];
    byte sb8 = data[i + 7];


    Тебе надо создать соответствующую структуру и делать это одним присваиванием адреса. Если ушь так.
    Работать будет НАМНОГО быстрее.
     
  16. deim_1

    deim_1 Member

    Joined:
    3 Feb 2016
    Messages:
    63
    Likes Received:
    9
    Reputations:
    0
    ну труд не напрасный, вопрос то решен. А так начал с 4-х, потом 6, потом 8 и тут вариантов оказалось всего несколько десятков
     
  17. DartPhoenix

    DartPhoenix Elder - Старейшина

    Joined:
    15 Sep 2013
    Messages:
    979
    Likes Received:
    7,486
    Reputations:
    23
    Ежели вопрос решен - тогда да :)
    Но сам способ... В общем не важно.
     
  18. deim_1

    deim_1 Member

    Joined:
    3 Feb 2016
    Messages:
    63
    Likes Received:
    9
    Reputations:
    0
    согласен.
    идея была чтобы ещё записывалась частота попаданий , offset от начала файла. и ещё на с++ будет быстрее.
     
    CyberTro1n and DartPhoenix like this.
Loading...