Проблема с курицей / яйцом: хеш файла (включая хеш) внутри файла! Возможный?

Question

Дело в том, что у меня есть файл, в котором есть место для метаданных. Я хочу хранить хэш для проверки целостности в нем. Проблема заключается в том, что после сохранения хэша файл и хэш вместе с ним изменяются.

Я прекрасно понимаю, что по определению это невозможно при использовании односторонних криптографических методов хеширования, таких как md5 / sha.

Мне также известно о возможности контейнеров, которые хранят данные проверки отдельно от контента, как это делают zip & co.

Мне также известна возможность отдельно вычислять хеш и отправлять его вместе с файлом или добавлять его в конце или куда-то, где клиент, вычисляя хеш, игнорирует его.

Это не то, что я хочу.

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

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

Я действительно не очень разбираюсь в математике, но разве не может быть какой-то действительно продвинутой экспоненциальной модели по модулю полинома циклической обратной ссылки, которая делает это возможным?

А если нет, то какие (если есть) доказательства против этого?

Причина, по которой я нуждаюсь в этом, состоит в том, что я хочу (в конечном итоге) хранить хэш вместе с файлами MP4. Его сложные, но другие решения нелегко реализовать, так как файл идет по плохо спроектированному производственному конвейеру ...

Answer 1

Можно сделать это с помощью CRC, в некотором роде.В прошлом я занимал 4 байта в файле в качестве заполнителя для CRC32, заполняя их нулями.Затем я вычисляю CRC файла.

Затем можно заполнить байты-заполнители, чтобы сделать CRC файла произвольной фиксированной константой, путем вычисления чисел в поле Галуа многочлена CRC.

(Более подробная информациявозможно, но не прямо сейчас. В основном вам нужно вычислить (CRC_desired - CRC_initial) * 2 ^{-8 * byte_offset} в поле Галуа, где byte_offset - это число байтов между байтами заполнителя и концомфайл.)

---

Примечание: согласно комментариям @ KeithS, это решение не должно предотвращать преднамеренное вмешательство.Мы использовали его в одном проекте в качестве средства для привязки метаданных во встроенной системе к исполняемому файлу, используемому для его программирования - сама встроенная система не имеет прямого знания о файле (ах), использованном для ее программирования, и поэтому не может вычислитьCRC или сам хэш - для обнаружения случайного несоответствия между встроенной системой и файлом, используемым для ее программирования.(В более поздних системах я только что использовал UUID.)

Answer 2

Конечно, это возможно множеством способов. Однако не может предотвратить преднамеренное вмешательство.

Например, пусть

hash(X) = sum of all 32-bit (non-overlapping) blocks of X modulo 65521. 

Пусть

Z = X followed by the 32-bit unsigned integer (hash(X) * 65521)

Тогда

hash(Z) == hash(X) == last 32-bits of Z

Идея здесь заключается в том, что любое 32-разрядное целое число, равное 0 по модулю 65521, не будет влиять на хэш X. Тогда, поскольку 65521 <2 ^ 16, хэш имеет диапазон меньше 2 ^ 16, и по крайней мере 2 ^ 16 значений меньше, чем 2 ^ 32, соответствуют 0 по модулю 65521. И поэтому мы можем закодировать хеш в 32-битное целое число, которое не повлияет на хеш. На самом деле вы можете использовать любое число меньше 2 ^ 16, просто получается, что 65521 является наибольшим таким простым числом. </p>

Answer 3

Я помню старую программу DOS, которая смогла встроить в текстовый файл значение CRC этого файла.Однако это возможно только при использовании простых хеш-функций.
Хотя теоретически вы можете создать такой файл для любого вида хеш-функции (при условии достаточного времени или правильного алгоритма), атакующий сможет использовать точно такой же подход.Более того, у него был бы выбор: использовать именно ваш подход для получения такого файла или просто избавиться от чека.

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

РЕДАКТИРОВАТЬ: вы можете рассмотреть возможность хеширования некоторых промежуточных результатов (таких как RAW-декодированный вывод или что-то специфическое для вашего кодека).Таким образом, декодер все равно получит его, но для другой программы его будет сложнее вычислить.

Answer 4

Нет, не возможно. Либо у вас есть отдельный файл для хэшей ala md5sum, либо встроенный хэш предназначен только для части файла «data».

Answer 5

способ менеджер пакетов nix делает это, вычисляя хеш, вы притворяетесь, что содержимое хеша в файле имеет фиксированное значение, например 20 x, а не хешзатем вы записываете хэш над этими 20 x, и когда вы проверяете хэш, вы читаете его и снова игнорируете, делая вид, что хеш был просто фиксированным значением 20 x при хешировании

они делают это, потому что пути, по которым установлен пакет, зависят от хеша всего пакета, поэтому, поскольку хеш имеет фиксированную длину, они устанавливают его как некоторое фиксированное значение, а затем заменяют его реальным хешем и при проверке игнорируют значениеони разместили и притворились, что это фиксированное значение

, но если вы не используете такой метод, то это невозможно

Answer 6

Это зависит от вашего определения "хэш".Как вы утверждаете, очевидно, что с любым псевдослучайным хешем это было бы невозможно (в разумные сроки).

Не менее очевидно, что существуют, конечно, тривиальные «хеши», где вы можете сделать это.Например, для данных с нечетным числом битов установлено значение от 1 до 00, а для четного числа от 1 до 11.Хеш не изменяет нечетность / четность 1 бита, поэтому файлы хешируются одинаково, когда их хэш включен.