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

Предположим, у меня есть две строки (или массивы байтов) 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)) и прочего, я имею в виду)


md5 sha1 hash collision digest
person mihi    schedule 15.06.2009    source источник

Ответы (3)


arrow_upward
0
arrow_downward

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

person user122147    schedule 15.06.2009
comment
Итак, знаете ли вы какие-либо ссылки, в которых перечислено несколько хеш-функций? - person mihi; 15.06.2009

arrow_upward
2
arrow_downward

Детали зависят от хэш-функции 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 кратно размеру хэш-блока, но, вероятно, не иначе.

person laalto    schedule 15.06.2009
comment
Я не согласен с этим описанием. Если A и B (разные входные данные) сталкиваются на определенном хэш-вычислении, они делают это, потому что, пройдя через разные «внутренние» состояния, они достигли одного и того же окончательного вычисления (по очень странной случайности, если у нас есть хорошая хеш-функция). - person nik; 15.06.2009
comment
Теперь, если дополнительный вход C снабжен префиксом или суффиксом к двум входам, эти `` внутренние '' состояния, видимые в вычислительной последовательности, должны значительно измениться, чтобы НЕ достичь того же окончательного вычисления для (A, C) и (B, C). Где (X, Y) представляет собой префикс Y или суффикс X. - person nik; 15.06.2009
comment
@nik: Спасибо, я немного пояснил свой ответ. - person laalto; 15.06.2009
comment
@laalto, я думаю, вы много предполагаете о влиянии размера блока на ввод. - person nik; 15.06.2009
comment
Я только что провел несколько тестов MD5, нет размера C ниже 1024 (кроме тривиального 0), где H (C + A) = H (C + B) для всех C (создавал случайные C до тех пор, пока не нашел нечетный, обычно первый ...) Итак, какой размер хеш-блока у MD5? Или я вас неправильно понял? - person mihi; 15.06.2009

arrow_upward
0
arrow_downward

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

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

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

echo "abcd" | md5sum
70fbc1fdada604e61e8d72205089b5eb

echo "0abcd" | md5sum
f5ac8127b3b6b85cdc13f237c6005d80

echo "abcd0" | md5sum
4c8a24d096de5d26c77677860a3c50e3

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

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

person nik    schedule 15.06.2009
comment
Я взял образцы из stackoverflow.com/ questions / 933497 /, которые имеют тот же MD5 (как указано в вопросе), а затем добавили к нему случайные строки. - person mihi; 15.06.2009
comment
Наблюдаемое свойство функции MD5 состоит в том, что если MD5 (A) == MD5 (B), то верно, что MD5 (A + C) == MD5 (B + C) для любого значения C. Значения A и B для проверки этого, но это было продемонстрировано математическим анализом функции MD5. - person defines; 15.06.2009
comment
@dustin: Есть ссылки / упоминания об этом? - person mihi; 15.06.2009
comment
@mihi, хорошо, я получил ваш образец из другого вопроса SO. Хотели бы знать, является ли это академическим интересом, анализом вероятности перебора или просто проверкой шанса случайного столкновения? - person nik; 16.06.2009
comment
Я искал ссылки и опубликую, как только найду хорошую. Я обнаружил, что этот факт упоминается несколько раз, и просмотрел множество официальных документов, чтобы найти хороший источник. Это не «может быть», это свойство функции, которое наблюдалось математически, прежде чем кто-либо смог его продемонстрировать. - person defines; 18.06.2009
comment
Также удалось воспроизвести ваши результаты, используя образец в другом вопросе SO, который я добавил с различными случайными сообщениями и по-прежнему получал конфликтующие хэши. Надеюсь, я найду эту ссылку. - person defines; 19.06.2009
comment
@nik: В основном академический интерес, в основном о некоторых неправильно реализованных HMAC и о том, какое влияние на них окажет аттачмент столкновения. - person mihi; 21.06.2009