Как стать автором
Обновить

Восстановление повреждённых файлов на основе CRC32

Уровень сложностиПростой
Время на прочтение8 мин
Количество просмотров7K

Нашел я недавно в закромах старый оптический диск (CD). Открыл его в проводнике и не могу зайти ни в одну папку. Протёр диск. Попробовал снова - та же оказия. Царапины на диске конечно есть, но не много и не сильные. Решил воспользоваться специальным софтом BadCopy. Половина мелких файлов восстановилась, половина нет. Большие файлы восстановились не полностью. В итоге в двух повреждённых архивах (повреждено 2% и 10%) я обнаружил один и тот же файл. При попытке его извлечь вылезала ошибка CRC. Но если в WinRAR при извлечении установить галочку "Keep broken files" (Не удалять файлы, извлечённые с ошибками), то извлекается как есть. Так как мой файл был дорог мне как воспоминание и был небольшим - всего 640 КБ, я решил заморочиться. Там же в WinRAR, кстати, можно узнать оригинальный размер файла и его CRC32.

Итак, у нас есть две повреждённые версии файла, его длина и даже его CRC32, нужно восстановить оригинал. Что может быть проще?

Спойлер: у меня на конкретно этом файле не получилось, но я определил какие должны быть условия, чтобы задача была решена, с какой вероятностью и немного о самом хэше. Оказывается, всё наоборот - это невероятно сложно.

Для начала нам потребуется допущение, что если бит в двух версиях одинаковый и находится на одном и том же месте, то в оригинале на этом же месте точно такой же бит. Вообще-то это не всегда верно: для файла уже в 3 байта с повреждением в 5% в обоих версиях вероятность что повреждённый бит окажется на одном и том же месте - те же 5%, вероятность того, что биты окажутся одинаковыми 50%. Таким образом, при столь малом размере наше допущение неверно уже в 2,5%. Это недопустимо, однако иначе на эти версии вообще нельзя полагаться, а значит придётся перебирать все возможные комбинации. Но это мы тоже сделать не можем - для файла уже в 6 байт нас придётся перебрать 256^6 комбинаций, а это больше 2,8*10^14, и не просто перебрать, а вычислить для каждого хэш и сравнить с требуемым. Так что, похоже, допущение остаётся с нами, но нельзя ли его сделать строже? Можно, если учитывать одинаковые участки не по биту, а например по байту (или по несколько байт - но чем жёстче условия - тем дольше нам придётся ждать). Ок, что дальше? Перебрать просто все варианты для повреждённых участков? Нет, потому как если повреждено более 6 байт, мы опять-таки не сможем этого сделать (см. выше). Поэтому нам нужна какая-то оптимизация.

Я придумал три способа восстановления, которые оптимизируют скорость процесса, но уменьшают и без того не 100% вероятность успеха:

1. Побайтовый перебор, но перебираем не все 256 вариантов для каждого байта, а только от до b, где а = v1 AND v2, b = v1 OR v2, где v1 и v2 - это соответствующие значения этого байта в версиях. Таким образом, если в одной версии там символ в кодировке Windows-1251 "Б", а в другой - "Ю", то мы будем перебирать не 256 вариантов, а только 32 варианта от "А" до "Я" ("Ё" идёт лесом).

2. Малый побайтовый перебор - тут мы вместо 256 вариантов для каждого повреждённого байта перебираем всегда только 2 - из первой версии или из второй

3. Поинтервальный перебор - то же, что 2., но перебор идёт не каждого байта, а для всего повреждённого интервала байтов. Например, если в 100-байтном файле повреждены байты с 70-го по 75-ый, 83-91, 96-100, то нам для всего процесса восстановления потребуется перебрать всего 8 вариантов - по 2 для каждого из трёх интервалов.

А теперь статистика по этим методам для файлов до 1МБ (получена эмпирически и плохо экстраполирована):

  • Вероятность успеха.

Максимум на что можно рассчитывать при первом способе - 70% вероятность успеха.

Второй способ даёт успех в два раза реже.

Третий способ даёт успех ещё в два раза реже.

Однако, зато "слабые" способы намного быстрее:

*с описанными в 1. оптимизациямиграфик не совсем точный
*с описанными в 1. оптимизациями
график не совсем точный

В среднем - больше 95 лет.

Тут получилось более точно передать пик при больших размерах файла, поэтому среднее время вышло немного больше - 98 лет, зато точнее (по идее у первого графика должен быть тоже такой же пик - чем больше повреждений - тем больше вариантов - тем дольше). Но всё-таки этот способ гораздо быстрее - это мы увидим далее.

В среднем два года.

*Выше и нижеуказанные значения времени были получены на одном ядре процессора 1.8ГГц

Понятно, что эти огромные цифры мало общего имеют с реальностью - вряд ли кто-то будет ждать 2 года, чтобы восстановить файл меньше мегабайта (разве что там написано почему смысл жизни = 42), а если речь идёт о более 90 лет (две жизни), то вообще может лучше не начинать процесс, а просто подождать когда компьютеры станут быстрее?

Кстати - это интересный вопрос. Согласно закону Мура, количество ядер на вычислительном элементе удваивается каждые 2 года. А так как нашу программу можно полностью распараллелить, то считаем, что каждые 2 года ждать нужно в 2 раза меньше, но нужно сначала подождать эти 2 года. Так что же лучше - начать как можно раньше или как можно дольше ждать?

Если наша задача решается за 100 лет, то самое оптимальное - подождать 10 лет и через 3 года и 1,5 месяца - она решится. То есть потребуется не меньше чем 13 лет! Если для Вас это неприемлемо - то Вам не повезло родиться слишком рано. Конечно, если у Вас нет сохранения промежуточного состояния программы или сети ботов, делающих всю работу за Вас.

Однако, как я уже оговаривался ранее, такие цифры у меня получились, задействуя всего лишь 1 ядро процессора. А если задействовать 8? Уже будет меньше 13 лет! А если вычисления производить на видеокарте? Смотря на какой, но порядок для современных средне-бюджетных видеокарт будет всего около 2 месяцев! Как это, спросите Вы? Дело в том, что ядер на видеокарте больше в 100 раз, чем в процессоре, а их частота меньше всего в 1,5 раза. Поэтому, если нужно что-то посчитать последовательно - быстрее будет на процессоре, а если множество вычислений (более 8-16 потоков) не зависят друг от друга (например, если цвет каждого пикселя напрямую не зависит от цвета других, обучение нейросети на одном примере можно производить отдельно от другого, вычисление множества хэшей как в нашем случае или в криптовалюте и т.п.), то лучше использовать видеокарту или несколько.

Итого: около месяца потребуется, чтобы восстановить файл 1МБ с менее, чем 35% вероятностью успеха на среднем ПК в 2024 году. Всё равно неутешительно.

Но и это ещё не всё. Вы можете сказать: "Подожди, а зачем нам ждать полного перебора - вдруг правильный ответ ждёт нас уже на втором проценте?" Совершенно верно, поэтому я исследовал и это:

Я ждал максимум сутки (1 ядро CPU), поэтому максимальное значение здесь равно 86400 секунд (что равно примерно 3 минутам для среднего GPU) и записывал результат самого быстрого способа, который всё же дал верный результат (а это 69% успеха при условии, что Вы перепробуете все три способа) - на практике это время может быть намного больше, тем более, что если с первого раза Вы не угадали самый быстрый способ, который не подведёт, но даже так видно, что есть области где пусть не всегда, но требуемый оригинальный файл достигается за гораздо меньшее время.

Таким образом, получается, что наиболее благоприятные условия (до ~ 12 часов на одном ядре или ~ 2 минут на видеокарте - если Вы думаете, что 2 минуты - это мало, то вспомните, что это для размеров меньше 1 МБ - стоит добавить десяток повреждённых интервалов - и вот уже вновь 12 часов), чтобы получить верный результат будут следующими:

график получен эмпирически и не отражает точного/среднего положения дел, но даёт адекватное представление о нём
график получен эмпирически и не отражает точного/среднего положения дел, но даёт адекватное представление о нём

То есть, повреждения желательно должны быть меньше 40% либо размер файла до ~ 50 байт.

Объединяя это с предыдущими графиками получаем:

Это рекомендация по выбору самого успешного способа.

Если у Вас имеется только 24 часа на одном процессоре или 3 минуты на одной видеокарте, то:

Правый нижний угол ведёт себя вроде бы немного странно - это потому что при таком повреждении наше изначальное не всегда верное допущение перестаёт иметь значение. Аналогично в левом нижнем углу допущение начинает играть значительную роль. Почему только в нижних? Потому что при таком отпущенном времени на поиски до верха мы просто не доберёмся.

Выкладываю здесь свою программу: ссылка на яндекс диск

Извлеките из двух повреждённых архивов один и тот же файл (с галочкой Keep broken files в WinRar) в папку с программой как 1 и 2 (без расширения), введите длину файла и CRC32 из архиватора

Но и это ещё не всё! Если Вы сейчас попробуете восстановить так какой-нибудь файл (рядом с программой есть примеры, на которых можно поиграться, дайте знать если у Вас получится восстановить D82C64A7 как работающий exe), то Вы получите результат гораздо быстрее:

В среднем за 5,5 часов (используя мою программу, которая задействует всего одно ядро), но, скорее всего, он будет не тот, что Вам нужен.

Проблема в том, что так как CRC32 имеет длину в 4 байта, то на каждые 256^4 (4 миллиарда) комбинаций в среднем будет приходиться одна, подходящая под один любой CRC32. Поэтому сложность не только в том, чтобы найти вариант, подходящий под длину и хэш, но и выявить нужный из всего множества таких. А это множество может быть очень большим:

учитывайте, что все бросающиеся в глаза странности графиков получились из малого количества проанализированных примеров (~10 штук)
учитывайте, что все бросающиеся в глаза странности графиков получились из малого количества проанализированных примеров (~10 штук)

В среднем 22 подходящих варианта под любой CRC и размер.

Так, например:

некоторые 17 вариантов для db7d2bac и размера в 54 байта (малый побайтовый перебор)
некоторые 17 вариантов для db7d2bac и размера в 54 байта (малый побайтовый перебор)
начальные 17 вариантов и оригинал для CRC32 = 9b225956 и размера в 11 байт (побайтовый перебор). Обратите внимание на 3-й символ - первые два не меняются, и практически для каждого байта находится несколько вариантов.
начальные 17 вариантов и оригинал для CRC32 = 9b225956 и размера в 11 байт (побайтовый перебор). Обратите внимание на 3-й символ - первые два не меняются, и практически для каждого байта находится несколько вариантов.

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

По вышеприведённой ссылке есть также исходники программы на VB6. Пробуйте перевести её на видеокарту, изобретите другой способ перебора (например, с какой-то вероятностью в каких-то байтах верить изначальному допущению, а с какой-то не верить повреждённым версиям), расширяйте её на большее количество повреждённых версий, учитывайте CRC вышестоящих каталогов в архиве, ставьте проверку на требуемую структуру файла, оптимизируйте, может как-то можно не перебирать, а вычислять варианты? - непаханное поле!

Но и это ещё не всё. Пишите комментарии - что понравилось/что нет, подписывайтесь, если хотите ещё почитать такие околонаучные статьи и упоротые расчёты)

UPD: Скормил извлечённый .text из повреждённого exe и из такой же сигнатуры неповреждённого файла в https://www.jpeg-repair.org/ru/vg-jpeg-repair/ - показал изображения, что были внутри. Есть у кого аналог бесплатный или ещё что-то что может восстанавливать другие типы информации?

UPD2: Дело в том, что как заметил @Sap_ru считывание с CD происходит блоками в 2 КБ. Поэтому я также добавил несколько новых способов:

4. Малый поблоковый перебор - аналогичен малому побайтовому, но работает не с отдельными байтами, а с целыми блоками по 2 КБ, вследствие чего намного быстрее:

В среднем 13 лет вместо 98
В среднем 13 лет вместо 98

В среднем в лучшем случае 24% успеха
В среднем в лучшем случае 24% успеха

5. Интервальный поблоковый - аналогично. Перебирает очень мало вариантов и выполняется практически на любом файле до 1 МБ почти мгновенно.

В среднем в лучшем случае 15% успеха.
В среднем в лучшем случае 15% успеха.

Таким образом, вот рекомендации когда их использовать:

Обратите внимание, что процент поврежденных блоков и поврежденных байтов - это разные вещи:

Увеличим:

Однако, как выяснилось в моём случае - даже некоторые совпадающие блоки - это просто нули, которых не должно быть в сигнатуре файла, то есть в моём случае допущение оказалось не верным. Скорее всего, это касается всех архивов, считанных с диска без уцелевшей информации восстановления об этих блоков на нём. Однако, если у Вас другой случай или Вам нужно просто подобрать особенную коллизию (например, чтобы Windows не выдавал ошибку в самом начале из-за несовпадения CRC32 типа "Невозможно запустить это приложение на Вашем ПК") - пробуйте.

Поэтому я добавил ещё один способ, которому не нужно это допущение, однако он всё-таки опирается на имеющиеся версии:

6. Случайный - все повреждённые байты каждый раз принимают случайное значение, неповреждённые байты с 75% вероятностью - значение из версий, с 25% - случайное. Теоретически, так можно получить искомую коллизию при любых изначальных условиях, но за время в среднем гораздо большее 100 лет (если никто так и не перепишет на GPU). Но может повезти :)

И всё-таки, скажите мне, если у Вас получится запустить D82C64A7 в примерах по ссылке (Может случайно или ещё как-то).

Также добавил автоматические рекомендации по выбору способа поиска коллизий в программу

Теги:
Хабы:
Всего голосов 12: ↑10 и ↓2+11
Комментарии79

Публикации

Истории

Ближайшие события

11 – 13 февраля
Epic Telegram Conference
Онлайн
27 марта
Deckhouse Conf 2025
Москва
25 – 26 апреля
IT-конференция Merge Tatarstan 2025
Казань