Криптографически безопасная аддитивная хеш-функция

Question

Я работаю над системой передачи файлов Fountain Code .В этой системе блоки данных загружаются вместе с функцией xor.Я хочу проверить блоки по мере их поступления.

Мне нужна криптографически безопасная хеш-функция со свойством:

Хеш (A) ^ Хеш (B) == Хеш (A^ B)

существует ли такая вещь?

Примечание: блоки данных должны быть объединены с функцией xor, хэши могут быть объединены с любой функцией, которая вам нравится, если это разумнодешево вычислять.

Answer 1

Если запрашиваемая вами личность в точности равна

Hash(A) ^ Hash(B) == Hash(A ^ B)

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

Что это значит, проще говоря?

Итак, предположим, что ваша карта принимает блоки длиной 6 и возвращает хэши длины 3, и что это некоторые из хешей:

Hash(000001) = 010
Hash(000010) = 111
Hash(000100) = 001
Hash(001000) = 101
Hash(010000) = 110
Hash(100000) = 001

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

Hash(101000) = Hash(100000) ^ Hash(001000) = 001 ^ 101 = 100.

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

Что это означает?

Википедия определяет идеальная криптографическая хеш-функция с четырьмя основными или значимыми свойствами:

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

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

Если вы найдете элемент kernel хеш-функции, то есть, сообщение K такое, что Hash(K) - это все нули, тогда последнее свойство также не срабатывает.Возьми любое сообщение M;тогда M и M^K будут иметь одинаковый хеш, потому что Hash(M^K) = Hash(M)^Hash(K) = Hash(M)^0 = Hash(M).Также легко найти элементы ядра.

Третье свойство немного сложнее, но его также можно нарушить.(Например, предположим, что вы хэшируете юридический контракт. Найдите несколько мест, где можно изменить некоторые случайные запятые или что-то в этом роде. Рассмотрите влияние этих изменений на хеш-функцию, а затем решите систему линейных уравнений.)1050 *

Answer 2

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

Что касается объединения блоков, хэш обычно требует использования сложения в простом поле. Если вы используете фонтанные коды, вам не нужно использовать xor - любая обратимая функция хороша, и это включает в себя дополнение. Описанный выше хэш работает на сложение и умножение в простом поле и надежно защищен.