Comments 79
на каждые 256^4 (4 миллиарда) комбинаций в среднем будет приходиться одна, подходящая под один любой CRC3 А это множество может быть очень большим: В среднем 22 штуки.
Мне казалось что даже в идеальном случае кол-во коллизий = 2^((N-4)*8), где N-кол-во восстанавливаемых байтов, т.е. для 5 байтов уже 256 коллизий в идеальном случае.
Правильно, но это теоретические расчёты, а у меня там эмпирически полученные варианты, найденные всего лишь за сутки
Но в том то и дело, что бесперспективность данной затеи всё это можно было теоретически легко и быстро посчитать. И мне показалось ваши эмпирические результаты как - то сильно расходятся с теорией - собственно об этом мой изначальный комментарий.
Вы понимаете разницу между всеми найденными и найденными лишь за сутки?
Я понимаю что 32 байта - это уже приватный ключ от биткоина, например, и там надо найти любую одну коллизию. А у вас надо найти одну-единственную верную коллизию и как-то (никак) отсеять остальные. И структура файлов особо не поможет, т.к. если много информации можно восстановить из ниоткуда - значит это очень избыточный формат файла.
Естественно избыточный - у нас две повреждённые версии (а это уже два размера файла), хэш и знание структуры файла - конкретно на этом файле я знаю не только его расширение, но и компилятор, и что оно должно делать и как выглядеть - в теории последнего уже достаточно чтобы я заново сделал это приложение, но мне влом)
Учитывая три разных способа?
И, выложив исходники, мне интересно сможет ли кто приблизиться к практическому результату, грамотно отсеяв из множества вариантов не подходящие под структуру и какое минимальное кол-во времени для этого потребуется?
Только не восстановить, а подобрать коллизию. К восстановлению это как правило не имеет никакого отношения.
Вы про что-то конкретное или про статью в целом?
Про саму идею что-то восстанавливать по хешу.
Ну в теории вы конечно правы. Но на практике, если у нас есть силный хэш, и CRC32, и применив восстановление одного бита по CRC32 мы видим что сильный хэш совпал. То для практических применений я думаю это можно назвать восстановлением. Потому что вероятность того что испортился не один бит, а столько и так чтобы сильный хэш совпал - ну сами понимаете какая.
Другое дело, что по CRC32 можно восстановить только 1, ну максимум несколько бит и то при условии что мы имеем способ проверить что получился правильный файл, например по сильному хэшу.
У вас слишком много условий стало появляться. Чисто математически легкий хеш + криптографический хеш дают возможность перебирать варианты быстрее. А просто два разных хеша уменьшают вероятность одновременной коллизии. И это все не имеет никакого отношения к восстановлению файлов на основе CRC32.
Это не условия стали появляться, просто я описывал реальный случай восстановления "сбойного" бита в видеофайлах по CRC32. К данной статье имеет отношение только в смысле заголовка: Восстановление повреждённых файлов на основе CRC32.
Даже с теоретической точки зрения, вероятность того что в файле поменялся только один бит, а не кучка да еще и так что совпал сильный хэш сильно разная. А с практической только ее и можно учитывать.
Видеофайлы не критичны к потере не то что бит, а даже целых кусков файла. Их форматы умные люди делали. Видели разваливающуюся картинку при проигрывании или зеленую заливку? Вот это оно, кусок битый. Бит вы глазами не заметите.
Теория говорит нам что задача восстановления решается другими способами, а не через хеш от всего файла. И наоборот что задача восстановления данных через хеш от файла не решается.
Я до сих пор не понимаю почему 1 бит-то? Мы получаем кучу вариантов, но CRC32 просто уменьшает эту кучу в 4 миллиарда раз, разве не так?
Вы видели график вероятности успеха? Если файл до 100 байт, то вполне неплохие шансы
Microsoft на оригинальных образах винды раньше всегда делала чтоб crc32 был FFFFFFFF, как сейчас не знаю
Интересная статья, спасибо, такой вопрос к знатокам, квантовый компьютер может восстановить файлы по такому алгоритму?
Ни квантовый ни даже компьютер с бесконечным быстродействием не сможет, если нет больше другой инфы кроме этих CRC32.
В общем случае они просто нагенерят почти бесконечное количество мусорных файлов у которых CRC32 совпадает с оригиналом плюс совпадает часть файла с обеими оригиналами.
Ну вообще-то есть ещё такая информация как минимиум как расширение файла, а предпологаемой или достоверно известной может быть намного больше - например использовавшийся компилятор для exe. Я её здесь не учитывал, но зная структуру файла можно отсеять большинство мусора.
увы не "большинство мусора" а меньшинство, так же как и CRC32 добавление валидаторов по структуре файла лишь несущественно сократит количество вариантов. Ведь валидных вариантов останется гораздо больше чем невалидных разве нет?
(Если конечно речь идет не о повреждении всего лишь небольшого участка из нескольких байтов в исходном файле.)
то есть по вашему exe файл из рандомных байтов запустится виндой без ошибки типа: "Невозможно запустить это приложение на Вашем ПК" или "Файл содержит потенциально нежелательную программу" ?
В PE заголовке содержится CRC, по которому винда и определяет целостность. Так что такой файл скорее всего выдаст заглушку MS DOS.
Я и написал про валидатор exe, но это не отменяет того факта что множество "валидных" вариантов будет несравненно больше множества отсеянного этими CRC32 + валидатором хоть что ты там не проверяй
А если будет хеш файла? например SHA256, то квантовый компютер сможет востановить файл?
Даже чисто теоретически SHA256 может помочь восстановить не более 256 битых битов. Но нужен еще способ определить который из примерно 2^(N-256) файлов, где N - длинна файла в битах - правильный.
Crc32 - тоже хеш, хоть и в 8 раз меньший
SHA256 конечно уменьшит количество вариантов на (256-32)=224 двоичных порядка, что по прежнему дает огромнейшее количество валидных вариантов (коллизий), которые тоже можно отсеивать проверкой структуры файла, что все также несущественно уменьшит количество вариантов.
Так что точный ответ на ваш вопрос - нет, не сможет. При условии что количество поврежденных битов сильно превышает 256, а я напомню что файл 640кб и речь идет о потерянных десятках процентов насколько я понял.
VB6, о, моя молодость. Как гляну на иконку окна, так сразу... (роняет скупую слезу)
Но это мы тоже сделать не можем — для файла уже в 6 байт нас придётся перебрать 256^6 комбинаций, а это больше 2,8*10^14, и не просто перебрать, а вычислить для каждого хэш и сравнить с требуемым.
Если ты не бог, то не стоит действовать по алгоритму бога. Практически у каждого типа файлов есть внутренняя структура, налагающая ограничения и сужающая диапазон допустимых значений. Даже у plain text. От этого и стоит плясать.
Так как мой файл был дорог мне как воспоминание
Если правда дорог, то стоит поискать другие приводы, и пробовать прочитать на них, есть достаточно большой шанс что на другом приводе прочитается.
А можно подробнее, интересно как другой привод прочитает, если проблема в диске? Другие диски привод нормально читает?
Там слишком много параметров. Например, у меня в начале 00х было 3 привода для CD: Acer 52x, Asus 52x и резак Asus 48x16x52. Так вот, хуже всех считывал резак. Он отлично считал новые CD (без следов деградации алюминия) и хорошие CD-R/CD-RW. Acer 52x считывал все диски, что мог считывать резак + некоторое количество дисков, которые резак уже не брал. Причём, большинство - просто с грубыми повреждениями поверхности (видимо, его оптическая система более быстрая и ей относительно сильные царапины не страшны). А вот Asus 52x мог считать такие диски, которые не читали два предыдущие. Причём, даже CD-R и CD-RW. Последние вообще в некоторых приводах считывались через раз, у меня были такие RWхи, которые не читались прямо после записи и для их восстановления приходилось периодически делать полное медленное стирание.
Так что да, смена привода вполне может повысить шансы на удачное чтения диска. И важны тут все параметры: скорость чтения (чем она выше, тем быстрее механика и на малой скорости будет легче реагировать на царапки), сама оптическая система (чем качественнее и чище линза тем проще ему считывать с повреждениями на самой подложке). И прочее, вроде прошивки или мозгов.
Помню, были ещё приводы Creative, которые с пультом шли. Они читали хуже всего, почему-то.
Помню, были ещё приводы Creative, которые с пультом шли. Они читали хуже всего, почему-то.
Мой первый привод был LG x48 и вот он был рекордсмен по плохому чтению, причём всего от штамповок до CD-R, RW я бы сказал он ненавидел. Пару раз приходилось брать у друга какой то очень старый x8 привод, который ооочень медленно но при этом спокойно читал всё, что не мог прочитать мой LG.
При этом был правда ещё веселый диск с UT как полагается русская+англиканская версия. И вот англиканскую версию во всем моем городе мог прочитать только TEAK.
TEAK
TEAC. Они да, были звери (их профессионалы юзали), просто из попсы Asus CD-ROM (и только он) был наиболее всеядный, имел честное UDMA33 (даже под DOS драйвер был) + отлично управлялся программой CD Slow. Acer у меня пару дисков внутри рванул, ещё какой-то мутный привод был в конторе (вероятно LG или Lite ON), который тоже взорвал диск, раскрутив его на максимум.
Для CRC32 можно вычислить четыре последовательных байта изменяющие её на произвольную другую. Без всякого перебора. Поэтому много там не навосстанавливаешь. Четыре подряд битых байта на файл и всё.
А, вот, при битовом потоке можно, теоретически, без перебора узнать номер искаженного бита аж в 8 килобайтном блоке.
Так надо найти не один любой подходящий, а все и отсеять из них те, что не подходят под структуру
А, вот, при битовом потоке можно, теоретически, без перебора узнать номер искаженного бита аж в 8 килобайтном блоке.
Если битый бит один, то по CRC32 его надежно можно найти в 4Гб.
Да, ошибся :) Про CRC16 подумал. Кстати, на сколько я помню, на практике там далеко не 4Гб, из-за того, что полином позволяет исправлять и детектировать ещё и какое-то количество множественных ошибок.
полином позволяет исправлять и детектировать ещё и какое-то количество множественных ошибок.
Нет. Вы наверно путаете с другими кодами. CRC32 обладает следующими свойствами:
Каждому значению CRC32 соответсвует ровно один файл вида (2^32)-1 бит нулей и один бит 1. Т.е. грубо говоря в CRC32 "зашифровано" положение одного установленного бита в 4Гб.
Для любых двух файлов верно то, что XOR CRC32 этих файлов равер CRC32 файла полученного побайтным XOR-ом этих двух файлов.
Т.е. если у нас неправильный один бит, то сделав XOR корректного CRC32 и текущего CRC32 мы получим "положение" битого бита.
А если у нас 2 битых бита, то мы получим XOR этих двух положений. А для любого 32-х битного числа есть ровно 2^32 вариантов как его получить XOR-ом из двух других чисел. Т.е. по сути никакой дополнительный информации нет. Точней для короткого файла можно большую часть пар выкинуть, но все равно придется перебрать все 2^32 варианта. Для трех бит все еще хуже...
А если есть две повреждённые версии этого файла, но +- в совокупности (комбинации) байтов первой и второй версии есть верный ответ?
Каждому значению CRC32 соответсвует ровно один файл вида (2^32)-1 бит нулей и один бит 1. Т.е. грубо говоря в CRC32 "зашифровано" положение одного установленного бита в 4Гб.
Можно обоснование этого факта? По каким ключевым словам гуглить?
Специально про CRC32 я ничего не нашел, но на вики есть вот такое предложение: If r is the degree of the primitive generator polynomial, then the maximal total block length is 2^r-1, and the associated code is able to detect any single-bit or double-bit errors. И есть ссылочка на более подробную статью: "Section 22.4 Cyclic Redundancy and Other Checksums".
Соответсвенно, чтобы иметь возможность обнаружить ошибку в любом месте файла полином выбрали именно простым. Я обнаружил эту особенность экспериментальным путем, когда занимался восстановлением "попорченных" видео файлов.
Вы в курсе, что кроме хеша и длины файла, у меня есть ещё и две повреждённые версии этого файла, которые наполовину побайтно совпадают? Вполне возможно, что все нужные байты есть в этих версиях на своих местах, только некоторые в первой, а некоторые для второй. Может кто-нибудь из опенсорса переписать это для видеокарты, чтобы проверить?
А какие байты не совпадают между файлами и какое распределение этих байтов?
Данные на диске хранятся блоками и все повреждения локализованы в блоках. Блоки будут размером по 2КБ, помнится. Можете попробовать поперебирать не байты, а блоки между файлами - вдруг CRC сойдётся.
И главное. Там на CD два вагона информации для коррекции ошибок. Из которых сам привод использует только небольшую часть:
Первый уровень: коррекция/синхронизация на физическом уровне. Её привод всегда использует. И получает на выходе блоки по 2336 байт данных, где только 2048 байт полезных данных, а всё остальное - информация для восстановления.
Второй уровень - CRC32 этих двухкилобайтных блоков. Если она не сходится, то привод просто перечитывает блок, пока не сойдётся. Если за указанное количество попыток чуда не случилось, то привод сообщает, что блок плохой.
Но! Есть ещё и третий уровень - коды Рида-Соломона. И это аж прядка 256 байт на информации для восстановления на каждый 2048-байтный блок данных! И не это не просто CRC, это уже код для восстановления множественных блочных ошибок. На сколько я знаю, на практике сия информация приводами не используются или практически не используется, по причине сложности реализации и крайней длительности процесса восстановления. Но у некоторых приводов есть режим чтения с восстановлением ошибок и они медленно и мучительно читают битые сектора реально восстанавливая информацию. Но, опять же, на сколько я знаю, даже они не используют 100% возможностей восстановления из-за ограниченности вычислительных ресурсов привода. Вплоть до того, что на хорошем приводе, в случае царапин рекомендуется тонким чёрным маркером их закрашивать, и путь он восстанавливает 100% потерянных данных по кодам коррекции. Тем более, что повреждения носителя, как правило, точечные или радиальные, а дорожки на диске поперечные.
Для DVD/BL всё ещё намного круче. Там на хорошем приводе можно восстановить ОЧЕНЬ много потерь.
Но никто не запрещает прочитать сырые данные с привода и максимально использовать всю информацию для восстановления данных. Были даже утилиты, которые это программно делали, но давно это было, и знание, похоже, утеряно.
Я так понимаю, что вы даже CRC32 двухкилобатных блоков не используете, хотя уже только это сильно упростило бы задачу.
А ещё можно руками много раз читать блок, сравнивать отличия и выбирать в финальный результат значения байт, которые прочитались чаще всего, в надежде, что это верные значения. Либо маркировать такие нестабильные байт, чтобы потом проще было по кодам коррекции восстанавливать.
Это всё, как я сейчас помню и могу, конечно, ошибаться.
Могу вам написать прогу для восстановления, гораздо более быструю за определенную плату. Пишите в телегу @vasyusha_artemov95
Вообще, если там архив именно "заархивированный", а не просто "сложенный в один файл" (store method). То нет абсолютно никакого смысла "фиксить" разархивированный файл, т.к. с того бита который был поврежден в архиве дальше будет идти полный мусор до конца файла, а не один или несколько байт.
А насчет CRC32 - он может надежно восстановить ровно 1 бит на файлах меньше 4Гб. Лично когда-то занимался таким на видефайлах для которых были известны более "сильные" хэши.
Вообще по моему опыту, XOR "правильного CRC32" и "битого CRC32" можно рассматривать как "зашифрованную" позицию измененного бита. Точнее сказать это будет CRC32 файла состоящего из всех нулей с одним битом (битым) в единичке.
Если таких битов 2 и более эти позиции тоже складываются по XOR. Таким образом можно попробовать восстановить 2 бита для более менее коротких файлов, т.к. там для каждого бита его пара может "улетать" за пределы файла и понятно будет что это неверная пара, но и верных пар может быть очень много и чем длинней файл - тем больше. 3 и более бит - уже по сути нереально, кроме ну очень коротких файлов.
Восстановление повреждённых файлов на основе CRC32