Является ли какая-либо 64-разрядная часть 128-битного хэша как коллизионная, как 64-битный хеш?

Ответ 1

Если у вас были реальные случайные, равномерно распределенные значения, то "нарезка" давала бы точно такие же результаты, как если бы вы начали с меньшего значения с самого начала. Чтобы понять, почему, рассмотрим этот очень простой пример: пусть говорят, что ваш случайный генератор выдает 3 случайных бита, но вам нужен только один случайный бит для работы. Предположим, что выходной сигнал

b1 b2 b3

Возможные значения:

000, 001, 010, 011, 100, 101, 110, 111

и все должно происходить с равной вероятностью 1/8. Теперь, какой бы бит вы не нарезали из этих трех для своей цели - первой, второй или третьей - вероятность наличия "1" всегда будет 1/2, независимо от ее положения - и то же самое верно для "0".

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

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

Криптографические хэш-функции: co-worker # 1 выигрывает

Проблема в реальной жизни заключается в том, что хэш-функции не являются случайными вообще, наоборот, они скучно детерминированы. Но цель проектирования криптографических хеш-функций заключается в следующем: если бы мы не знали их начального состояния, то их вывод был бы неотличим от реальной случайной функции, то есть нет эффективного с точки зрения вычислений разницы между хэш-выходом и реальные случайные значения. Вот почему вы рассмотрели бы хэш уже как некий сломанный, если вы можете найти "различатель", метод для определения хеша из реальных случайных значений с вероятностью более половины. К сожалению, мы не можем действительно доказать эти свойства для существующих криптографических хэшей, но если кто-то их не сломает, мы можем предположить, что эти свойства сохраняются с некоторой уверенностью. Вот пример статьи об отличителе для одного из представлений SHA-3, который иллюстрирует процесс.

Подводя итог, если для данного криптографического хеша не найдено отличительного признака, нарезка отлично прекрасна и не увеличивает вероятность столкновения.

Некриптографические хэш-функции: сотрудник # 2 может выиграть

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

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

И только этот факт означает, что они более или менее отклоняются от случайной функции, и, следовательно, (после того, что мы сказали выше) столкновения, вероятно, более вероятны, чем для случайных функций. Наконец, поскольку столкновения происходят с большей вероятностью для полных 128 бит, это не улучшится с более короткими выводами, в этом случае столкновения будут, вероятно, еще более вероятными.

tl; dr. Вы можете использовать криптографическую хэш-функцию при ее усечении. Но вам лучше с "родной" 64-битной криптографической хэш-функцией по сравнению с усечением некритичного хэша с большим выходом до 64 бит.

Ответ 2

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

Я согласен с сотрудником 1, если хэш имеет хорошие свойства и даже распределение.

Ответ 3

Этот вопрос кажется неполным без упоминания об этом:

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

Это не общий случай, но это пример законной заботы при усечении хэшей.