хеш-коллизия и добавление данных

Question

Предположим, у меня есть две строки (или байтовые массивы) A и B, которые имеют одинаковый хэш (под хешем я имею в виду такие вещи, как MD5 или SHA1). Если я объединю еще одну строку за ней, будут ли A + C и B + C иметь одинаковый хэш H '? Что происходит с C + A и C + B?

Я тестировал его с MD5 и во всех моих тестах добавление чего-либо в конец делало хеш-код одинаковым, но добавление в начале - нет.

Всегда ли это верно (для всех входов)?

Это правда для всех (хорошо известных) хеш-функций? Если нет, существует ли (общеизвестная) хеш-функция, в которой A + C и B + C не будут сталкиваться (а C + A и C + B тоже не сталкиваются)?

(помимо MD5(x + reverse(x)) и других созданных мной вещей)

Answer 1

Детали зависят от хэш-функции H, но обычно они работают следующим образом:

1. Использовать блок ввода X (скажем, 512 бит)
2. Разбить входные данные на более мелкие части (скажем, 32 бита) и обновить внутреннее состояние хэша на основе входных данных
3. Если есть больше ввода, перейдите к шагу 1
4. В конце выплюнуть внутреннее состояние как хеш-значение H (X)

Таким образом, если A и B сталкиваются, т. Е. H (A) = H (B), хэш будет в том же состоянии после их использования. Дальнейшее обновление состояния с помощью того же ввода C может сделать полученное значение хеша идентичным. Это объясняет, почему H (A + C) иногда является H (B + C). Но это зависит от того, как размеры A и B выровнены по размеру входного блока и как хеш разбивает внутренний входной блок.

C + A и C + B могут быть идентичны, если C кратно размеру блока хеша, но, вероятно, не иначе.

Answer 2

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

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

Я не понимаю, как вы проверили MD5, вот мой тест.

echo "abcd" | md5sum
70fbc1fdada604e61e8d72205089b5eb

echo "0abcd" | md5sum
f5ac8127b3b6b85cdc13f237c6005d80

echo "abcd0" | md5sum
4c8a24d096de5d26c77677860a3c50e3

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

Пожалуйста, предоставьте образцы с результатами ваших испытаний.

Answer 3

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