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

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

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

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

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

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

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

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

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

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

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

Ответ 1

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

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

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

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

Ответ 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, как оказалось, самое большое такое простое число.

Ответ 3

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

Ответ 4

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

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

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

Ответ 5

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

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

Ответ 6

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

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

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