Нашел я недавно в закромах старый оптический диск (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 для каждого из трёх интервалов.
А теперь статистика по этим методам (получена эмпирически и плохо экстраполирована):
Вероятность успеха
Максимум на что можно рассчитывать при первом способе - 70% вероятность успеха.
Второй способ даёт успех
в два раза реже
Третий способ даёт успех ещё в два раза реже
Однако, зато "слабые" способы намного быстрее:
*с описанными в 1. оптимизацией. В среднем - больше 95 лет.
Тут получилось более точно передать пик при больших размерах файла, поэтому среднее время вышло немного больше - 98 лет, зато точнее (по идее у первого графика должен быть тоже такой же пик - чем больше повреждений - тем больше вариантов - тем дольше). Но всё-таки этот способ гораздо быстрее - это мы увидим далее.
В среднем два года.
*Выше и нижеуказанные значения времени были получены на одном процессоре 1.8 ГГц
Понятно, что эти огромные цифры мало общего имеют с реальностью - врят ли кто-то будет ждать 2 года, чтобы восстановить файл меньше мегабайта (разве что там написано почему смысл жизни = 42, шучу, это потому что это ASCII-код джокера), а если речь идёт о более 90 лет (две жизни), то вообще может лучше просто подождать когда компьютеры станут быстрее?
Кстати - это интересный вопрос. Согласно закону Мура, количество ядер на вычислительном элементе удваивается каждые 2 года. А так как нашу программу можно полностью распараллелить (просто в начале заранее определить для какого ядра какая область перебора), то считаем, что каждые 2 года ждать нужно в 2 раза меньше, но нужно сначала подождать эти 2 года. Так что же лучше - начать как можно раньше или как можно дольше подождать?
Если наша задача решается за 100 лет, то самое оптимальное - подождать 10 лет и через 3 года и 1,5 месяца - она решится. То есть потребуется не меньше чем 13 лет! Если для Вас это неприемлемо - то Вам не повезло родиться слишком рано. Конечно, если у Вас нет сохранения промежуточного состояния программы или сети ботов, делающих всю работу за Вас.
Однако, как я уже оговаривался ранее, такие цифры у меня получились, задействуя всего лишь 1 ядро процессора. А если задействовать 8? Уже будет меньше 13 лет! А если вычисления производить на видеокарте? Смотря на какой, но порядок для современных бюджетных видеокарт среднего класса будет всего около 2 месяцев! Как это, спросите Вы? Дело в том, что ядер на видеокарте больше в 100 раз, чем в процессоре, а их частота меньше всего в 1,5 раза. Поэтому, если нужно что-то посчитать последовательно - быстрее будет на процессоре, а если множество вычислений (более 8-16 потоков) не зависят друг от друга (например, если цвет каждого пикселя напрямую не зависит от цвета других, обучение нейросети на одном примере можно производить отдельно от другого, вычисление множества хэшей как в нашем случае или в криптовалюте и т.п.), то лучше использовать видеокарту или несколько.
Итого: не меньше 2 месяцев потребуется, чтобы восстановить файл 1МБ с менее, чем 35% вероятностью успеха на среднем ПК в 2022 году. Всё равно неутешительно.
Но и это ещё не всё. Вы можете сказать: "Подожди, а зачем нам ждать полного перебора - вдруг правильный ответ ждёт нас уже на втором проценте?" Соврешенно верно, поэтому я исследовал и это:
Я ждал максимум сутки, поэтому максимальное значение здесь равно 86400 секунд и записывал результат самого быстрого способа, который всё же дал верный результат (а это 69% успеха при условии, что Вы перепробуете все три способа) - на практике это время может быть намного больше, тем более, что если с первого раза Вы не угадали самый быстрый способ, который не подведёт, но даже так видно, что есть области где пусть не всегда, но требуемый оригинальный файл достигается за гораздо меньшее время.
Таким образом, получается, что наиболее благоприятные условия (до ~ 12 часов на одном ядре или ~ 9 минут на видеокарте - если Вы думаете, что 9 минут - это мало, то вспомните, что это для размеров меньше 1 МБ - стоит добавить парочку повреждённых байт или десяток повреждённых интервалов - и вот уже вновь 12 часов), чтобы получить верный результат будут следующими:
То есть, повреждения желательно должны быть меньше 40% либо размер файла 50 байт.
Объединяя это с предыдущими графиками получаем:
Это рекомендация по выбору самого успешного способа.
Если у Вас имеется только 24 часа на одном процессоре или 18 минут на одной видеокарте, то
Правый нижний угол ведёт себя немного странно - это потому что при таком повреждении наше изначальное не всегда верное допущение перестаёт иметь значение. Аналогично в левом нижнем углу допущение начинает играть значительную роль. Почему только в нижних? Потому что при таком отпущенном времени на поиски до верха мы просто не доберёмся.
Выкладываю здесь свою программу https://disk.yandex.ru/d/6EyRQlGQ6K8gRg
Извлеките из двух повреждённых архивов один и тот же файл (с галочкой Keep broken files в WinRar) в папку с программой как 1 и 2 (без расширения), введите длину файла и CRC32 из архиватора
Но это ещё не всё! Если Вы сейчас попробуете восстановить так какой-нибудь файл (рядом с программой есть примеры, на которых можно поиграться, дайте знать если у Вас получится восстановить D82C64A7 как работающий exe), то Вы получите результат гораздо быстрее:
В среднем за 5,5 часов*
, но, скорее всего, он будет не тот, что Вам нужен.
Проблема в том, что так как CRC32 имеет длину в 4 байта, то на каждые 256^4 (4 миллиарда) комбинаций в среднем будет приходиться одна, подходящая под один любой CRC32. Поэтому сложность не только в том, чтобы найти вариант, подходящий под длину и хэш, но и выявить нужный из всего множества таких. А это множество может быть очень большим:
В среднем 22 штуки.
Так, например:
некоторые 17 вариантов для db7d2bac и размера в 54 байта (малый побайтовый перебор)
начальные 17 вариантов и оригинал для CRC32 = 9b225956 и размера в 11 байт (побайтовый перебор). Обратите внимание на 3-й символ - первые два не меняются, и практически для каждого байта находится несколько вариантов.
Таким образом, если у Вас на сайте есть достаточное органичение на минимальную длину пароля, имеет смысл хранить и проверять не только его хэш, но и длину. Тогда подобрать или найти подходящий в радужной таблице будет в разы сложнее.
По вышеприведённой ссылке есть также исходники программы на VB6. Пробуйте перевести её на видеокарту, изобретите другой способ перебора (например, с какой-то вероятностью в каких-то байтах верить изначальному допущению, а с какой-то не верить повреждённым версиям), расширяйте её на большее количество повреждённых версий, ставьте проверку на требуемую структуру файла, оптимизируйте - непаханное поле!
Но и это ещё не всё. Пишите комментарии - что понравилось/что нет, подписывайтесь, а если хотите поддержать такие околонаучные статьи и упоротые расчёты - можете сделать это здесь.