2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Вероятность коллизии хэш-функции
Сообщение31.08.2019, 13:40 


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

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

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

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

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

 Профиль  
                  
 
 Re: Вероятность коллизии хэш-функции
Сообщение31.08.2019, 13:47 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Вероятность коллизии хэш-функции
Сообщение31.08.2019, 14:09 


27/08/16
9426
files2 в сообщении #1413028 писал(а):
Почему считается, что вероятность коллизии хэш-функций зависит только от размера хэш-суммы, т.е. от размера выхода хэш-функции и не зависит от размера входа?
Если энтропия входа меньше длины хэш-функции, то зависит. Вход должен быть достаточно длинным и хэш-функция хорошей.

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

 Профиль  
                  
 
 Re: Вероятность коллизии хэш-функции
Сообщение31.08.2019, 15:05 


05/09/16
11469
files2 в сообщении #1413028 писал(а):
Почему вероятность обнаружения коллизии для случаев, описанных в экспериментах 1 и 2, будет одинакова?

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

 Профиль  
                  
 
 Re: Вероятность коллизии хэш-функции
Сообщение31.08.2019, 15:49 


27/08/16
9426
wrest в сообщении #1413035 писал(а):
Для хеша в один бит, вероятность коллизии будет 0,5 независимо от длины входа...
Если возможен только один вход, то вероятость коллизии будет 1 вне зависимости от длины хэша.

 Профиль  
                  
 
 Re: Вероятность коллизии хэш-функции
Сообщение31.08.2019, 16:19 


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

 Профиль  
                  
 
 Re: Вероятность коллизии хэш-функции
Сообщение01.09.2019, 12:15 


31/08/19
2
wrest в сообщении #1413035 писал(а):
Под коллизией понимается совпадение хешей для разных исходных данных или что-то другое?
Да

ozheredov в сообщении #1413046 писал(а):
Вероятность коллизии определяется на прямом произведении множеств возможных входов?
Множество возможных входных значений (входов) одно.

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

 Профиль  
                  
 
 Re: Вероятность коллизии хэш-функции
Сообщение01.09.2019, 13:21 


10/03/16
3871
Aeroport
files2 в сообщении #1413137 писал(а):
Множество возможных входных значений (входов) одно.


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

 Профиль  
                  
 
 Re: Вероятность коллизии хэш-функции
Сообщение27.09.2019, 03:29 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Вероятность коллизии хэш-функции
Сообщение27.09.2019, 07:58 


07/08/14
4231
Snegovik в сообщении #1417678 писал(а):
Т.е. если выход хеш функции 128 бит, то вероятность коллизии должна быть не меньше, чем 2 в степени 64.
Как это "не меньше"? Вероятность - частота (доля, ...) "нужных" событий в множестве "нужных и ненужных", как она может быть не меньше (не больше)?

 Профиль  
                  
 
 Re: Вероятность коллизии хэш-функции
Сообщение27.09.2019, 16:53 


27/08/16
9426
upgrade в сообщении #1417682 писал(а):
Как это "не меньше"?
Если входное распределение неравномерное и/или хэш функция плохая, т. е. не выполняются те условия, которые я написал выше, то вероятность коллизии может оказаться больше написанной величины. Например, если на вход подаётся с вероятностью 1 всегда одна и та же последовательность, то вероятность коллизии для любой хэш-функции, тоже, будет единица.

 Профиль  
                  
 
 Re: Вероятность коллизии хэш-функции
Сообщение27.09.2019, 20:58 


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

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

 Профиль  
                  
 
 Re: Вероятность коллизии хэш-функции
Сообщение28.09.2019, 01:48 
Аватара пользователя


30/04/19
235
upgrade в сообщении #1417682 писал(а):
Как это "не меньше"?

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

-- 28.09.2019, 04:51 --

realeugene в сообщении #1417803 писал(а):
в зависимости от того, принадлежат ли эти входы к одному классу.

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

 Профиль  
                  
 
 Re: Вероятность коллизии хэш-функции
Сообщение28.09.2019, 13:59 


27/08/16
9426
Snegovik в сообщении #1417862 писал(а):
Что значит к одному классу? Блок входной информации это ведь просто набор определенных данных, любых.
К одному классу эквивалентности входных последовательностей, имеющих равные хэши.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group