Вероятность коллизии хэш-функции

[files2]

Здравствуйте, уважаемые участники форума.

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

Давайте рассмотрим предельно упрощенный пример.
Пусть, например, есть хэш-функция h, дающая 3-х разрядный выход (8 возможных значений).
Эксперимент 1: размер входных данных 4 разряда (16 возможных значений), каждые 16/8 = 2 входных значений имеют одинаковый хэш.
Эксперимент 2: размер входных данных 16 разрядов (65536 возможных значений), каждые 65536/8 = 8192 входных значений имеют одинаковый хэш.

Почему вероятность обнаружения коллизии для случаев, описанных в экспериментах 1 и 2, будет одинакова? В первом эксперименте 8 классов эквивалентности по 2 значения в каждом, во втором эксперименте тоже 8 классов эквивалентности, но уже по 8192 значения в каждом. И это количество значений в каждом из классов не влияет на вероятность обнаружения коллизии?

Спасибо за ответы.

[Pphantom]

Попробуйте просто вручную посчитать вероятность для обоих случаев.

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

[realeugene]

files2 в сообщении #1413028 писал(а):

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

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

Ваш упрощённый пример хорош для самостоятельного подсчёта вероятности коллизии. Как подсчитать для него вероятность коллизии? Добавьте условия равновероятности и независимости входов и равного распределения классов эквивалентности по множеству входов.

[wrest]

files2 в сообщении #1413028 писал(а):

Почему вероятность обнаружения коллизии для случаев, описанных в экспериментах 1 и 2, будет одинакова?

Под коллизией понимается совпадение хешей для разных исходных данных или что-то другое?
Для хеша в один бит, вероятность коллизии будет 0,5 независимо от длины входа...

[realeugene]

wrest в сообщении #1413035 писал(а):

Для хеша в один бит, вероятность коллизии будет 0,5 независимо от длины входа...

Если возможен только один вход, то вероятость коллизии будет 1 вне зависимости от длины хэша.

[ozheredov]

Вероятность коллизии определяется на прямом произведении множеств возможных входов? То есть отношение числа всех пар, для которых хэши совпадают, к числу вообще всех возможных пар?

[files2]

wrest в сообщении #1413035 писал(а):

Под коллизией понимается совпадение хешей для разных исходных данных или что-то другое?

Да

ozheredov в сообщении #1413046 писал(а):

Вероятность коллизии определяется на прямом произведении множеств возможных входов?

Множество возможных входных значений (входов) одно.

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

[ozheredov]

files2 в сообщении #1413137 писал(а):

Множество возможных входных значений (входов) одно.

Я и имел в виду произведение множества на самое себя

[Snegovik]

files2 в сообщении #1413137 писал(а):

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

Вероятность коллизии хорошей хеш-функции равна, если не ошибаюсь, двойке в степени равной размру "битности" функции деленной на 2. Т.е. если выход хеш функции 128 бит, то вероятность коллизии должна быть не меньше, чем 2 в степени 64.

[upgrade]

Snegovik в сообщении #1417678 писал(а):

Т.е. если выход хеш функции 128 бит, то вероятность коллизии должна быть не меньше, чем 2 в степени 64.

Как это "не меньше"? Вероятность - частота (доля, ...) "нужных" событий в множестве "нужных и ненужных", как она может быть не меньше (не больше)?

[realeugene]

upgrade в сообщении #1417682 писал(а):

Как это "не меньше"?

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

[realeugene]

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

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

[Snegovik]

upgrade в сообщении #1417682 писал(а):

Как это "не меньше"?

Сорри, поторопился и ерунду конечно написал. Имел в виду криптостойкость. Т.е. для нахождения коллизии нужно выполнить не менее $2^{n/2}$ операций.

-- 28.09.2019, 04:51 --

realeugene в сообщении #1417803 писал(а):

в зависимости от того, принадлежат ли эти входы к одному классу.

Что значит к одному классу? Блок входной информации это ведь просто набор определенных данных, любых.

[realeugene]

Snegovik в сообщении #1417862 писал(а):

Что значит к одному классу? Блок входной информации это ведь просто набор определенных данных, любых.

К одному классу эквивалентности входных последовательностей, имеющих равные хэши.