Нашел я недавно в закромах старый оптический диск (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 вариантов для каждого байта, а только от a до 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.8 ГГц
Понятно, что эти огромные цифры мало общего имеют с реальностью - врят ли кто-то будет ждать 2 года, чтобы восстановить файл меньше мегабайта (разве что там написано почему смысл жизни = 42, шучу, это потому что это ASCII-код джокера), а если речь идёт о более 90 лет (две жизни), то вообще может лучше просто подождать когда компьютеры станут быстрее?
Кстати - это интересный вопрос. Согласно закону Мура, количество ядер на вычислительном элементе удваивается каждые 2 года. А так как нашу программу можно полностью распараллелить (просто в начале заранее определить для какого ядра какая область перебора), то считаем, что каждые 2 года ждать нужно в 2 раза меньше, но нужно сначала подождать эти 2 года. Так что же лучше - начать как можно раньше или как можно дольше подождать?
Однако, как я уже оговаривался ранее, такие цифры у меня получились, задействуя всего лишь 1 ядро процессора. А если задействовать 8? Уже будет меньше 13 лет! А если вычисления производить на видеокарте? Смотря на какой, но порядок для современных бюджетных видеокарт среднего класса будет всего около 2 месяцев! Как это, спросите Вы? Дело в том, что ядер на видеокарте больше в 100 раз, чем в процессоре, а их частота меньше всего в 1,5 раза. Поэтому, если нужно что-то посчитать последовательно - быстрее будет на процессоре, а если множество вычислений (более 8-16 потоков) не зависят друг от друга (например, если цвет каждого пикселя напрямую не зависит от цвета других, обучение нейросети на одном примере можно производить отдельно от другого, вычисление множества хэшей как в нашем случае или в криптовалюте и т.п.), то лучше использовать видеокарту или несколько.
Итого: не меньше 2 месяцев потребуется, чтобы восстановить файл 1МБ с менее, чем 35% вероятностью успеха на среднем ПК в 2022 году. Всё равно неутешительно.
Но и это ещё не всё. Вы можете сказать: "Подожди, а зачем нам ждать полного перебора - вдруг правильный ответ ждёт нас уже на втором проценте?" Соврешенно верно, поэтому я исследовал и это:
Таким образом, получается, что наиболее благоприятные условия (до ~ 12 часов на одном ядре или ~ 9 минут на видеокарте - если Вы думаете, что 9 минут - это мало, то вспомните, что это для размеров меньше 1 МБ - стоит добавить парочку повреждённых байт или десяток повреждённых интервалов - и вот уже вновь 12 часов), чтобы получить верный результат будут следующими:
Объединяя это с предыдущими графиками получаем:
Если у Вас имеется только 24 часа на одном процессоре или 18 минут на одной видеокарте, то
Выкладываю здесь свою программу https://disk.yandex.ru/d/6EyRQlGQ6K8gRg
Но это ещё не всё! Если Вы сейчас попробуете восстановить так какой-нибудь файл (рядом с программой есть примеры, на которых можно поиграться, дайте знать если у Вас получится восстановить D82C64A7 как работающий exe), то Вы получите результат гораздо быстрее:
, но, скорее всего, он будет не тот, что Вам нужен.
Проблема в том, что так как CRC32 имеет длину в 4 байта, то на каждые 256^4 (4 миллиарда) комбинаций в среднем будет приходиться одна, подходящая под один любой CRC32. Поэтому сложность не только в том, чтобы найти вариант, подходящий под длину и хэш, но и выявить нужный из всего множества таких. А это множество может быть очень большим:
Так, например:
Таким образом, если у Вас на сайте есть достаточное органичение на минимальную длину пароля, имеет смысл хранить и проверять не только его хэш, но и длину. Тогда подобрать или найти подходящий в радужной таблице будет в разы сложнее.
Но и это ещё не всё: Дело в том, что как заметил @Sap_ru, считывание с CD происходит по блокам в 2 КБ. Поэтому я также добавил несколько новых способов:
4. Малый поблоковый перебор - аналогичен малому побайтовому, но работает не с отдельными байтами, а с целыми блоками по 2 КБ, вследствие чего намного быстрее:
5. Интервальный поблоковый - аналогично. Перебирает очень мало вариантов и выполняется практически на любом файле до 1 МБ почти мгновенно.
Таким образом, вот рекомендации когда их использовать:
Обратите внимание, что процент поврежденных блоков и поврежденных байтов - это разные вещи:
Увеличим:
Однако, как выяснилось в моём случае - даже некоторые совпадающие блоки - это просто нули, которых не должно быть в сигнатуре файла, то есть в моём случае допущение оказалось не верным. Скорее всего, это касется всех архивов без информации восстановления. Однако, если у Вас другой случай или Вам нужно просто подобрать особенную коллизию (напаример, чтобы Windows не выдавал ошибку в самом начале из-за несовпадения CRC32 типа "Невозможно запустить это приложение на Вашем ПК") - пробуйте.
Поэтому я добавил ещё один способ, которому не нужно это допущение, однако он всё-таки опирается на имеющиеся версии:
6. Случайный - все повреждённые байты каждый раз принимают случайное значение, неповреждённые байты с 75% вероятностью - значение из версий, с 25% - случайное. Теоретически, так можно получить искомую коллизию при любых изначальных условиях, но за время в среднем гораздо большее 100 лет. Но может повезти :)
И всё-таки, скажите мне, если у Вас получится запустить D82C64A7 в примерах по ссылке (Может случайно или ещё как-то).
По вышеприведённой ссылке есть также исходники программы на VB6. Пробуйте перевести её на видеокарту, изобретите другой способ перебора (например, с какой-то вероятностью в каких-то байтах верить изначальному допущению, а с какой-то не верить повреждённым версиям), расширяйте её на большее количество повреждённых версий, ставьте проверку на требуемую структуру файла, оптимизируйте - непаханное поле!
Но и это ещё не всё. Пишите комментарии - что понравилось/что нет, подписывайтесь, а если хотите поддержать такие околонаучные статьи и упоротые расчёты - можете сделать это здесь.
Подробнее здесь