Вероятность столкновения с хэшем

Извините, если это дублирующийся вопрос; большинство из тех, что я нашел, находятся над моей головой, поэтому я, возможно, пропустил ответ.

Для данного хэша, скажем, MD5 (128 бит), какова вероятность коллизии хэшей с 10 ^ 12 из них?

Моя математика не очень хороша, я придумал это уравнение (я думаю, что оно правильное), но понятия не имею, как его решить:

Collision_Chance = 1 - (1 - (1/2 ^ 128) ) ^ (10 ^ 12)

Я предполагаю, что это где-то около 10 ^ -26, это звучит правильно?

Спасибо

Редактировать: я думаю, что моя оценка очень неверна. См. Парадокс дня рождения.


hash-collision
person CL22    schedule 11.01.2014    source источник
comment
Парадокс дня рождения — это термин Google. И шанс примерно SQRT(n) , в вашем случае 128 бит --›› 64 бита. А 10^12 меньше 64 бит.   -  person wildplasser    schedule 11.01.2014
comment
@wildplasser «Шанс в SQRT(n)» — что это значит? Вероятность должна быть числом от 0 до 1. sqrt(n) — это количество значений, при которых вероятность столкновения равна 1/2.   -  person Christopher Creutzig    schedule 11.01.2014
comment
Небрежная формулировка. Если у вас есть пространство ключей из 128 бит, и вы выбираете его случайным образом, вероятность столкновения (в кумулятивной выборке) превышает предел 0,5, когда в вашем наборе около 2 ^ 64 элементов. Ваша ссылка на википедию имеет правильную формулировку (и формулы)   -  person wildplasser    schedule 11.01.2014

Ответы (2)


arrow_upward
2
arrow_downward

Что говорит ваша формула о наличии 2 ^ 128 + 1 значений? Я считаю, что это не говорит о том, что вероятность столкновения равна 1, поэтому это не может быть правильным. на самом деле я знаю, что это не так - правильная формула довольно большая и громоздкая, но есть хорошие приближения с использованием экспоненты дроби. SO не печатает формулы, поэтому я не буду пытаться записывать формулы здесь.

Лучшее ключевое слово для поиска, вероятно, «нападение на день рождения».

person Christopher Creutzig    schedule 11.01.2014
comment
What does your formula say for having 2^128 + 1 values? Я не думаю, что это так?! Если кто-то может объяснить, как прийти к правильной вероятности приведенного выше примера, приближения или чего-то еще, это было бы здорово. - person CL22; 11.01.2014
comment
Я имел в виду следующее: предположим, что у вас есть 2 ^ 128 + 1 хэш-значение. Что ваша формула говорит о вероятности столкновения? (Должно быть 1.) (И мой ответ содержит ссылку, указывающую на правильную формулу приближения.) - person Christopher Creutzig; 11.01.2014
comment
Спасибо. Формула приближения была именно тем, что я хотел. - person CL22; 11.01.2014

arrow_upward
0
arrow_downward

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

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

person oɔɯǝɹ    schedule 11.01.2014
comment
-1 Это просто неправильно. Многие хеш-функции предназначены для того, чтобы сделать коллизии маловероятными, и хеш-функции с такими свойствами имеют множество замечательных применений. См. en.wikipedia.org/wiki/Cryptographic_hash_function для определений и примеров. - person ; 11.01.2014
comment
@delnan unlikely здесь ключевое слово. Хеш-функция всегда является либо буквальной копией элемента (и, следовательно, уникальной), либо операцией, которая в конечном итоге упрощает данные (и, следовательно, своего рода сжатие с потерями). Нет никаких гарантий и намерений сделать сгенерированные хэши уникальными. - person oɔɯǝɹ; 11.01.2014
comment
Вы, кажется, ссылаетесь на принцип сортировки. Этот принцип верен, но это не означает, что нельзя проектировать систему, которая будет давать сбои перед лицом коллизий хэшей (о чем вы, по-видимому, говорите). Это противоречило бы современной практике криптографии и некоторым другим областям, которые полагаются на коллизии хэшей (для определенных хорошо выбранных хэш-функций), которые менее вероятны, чем, например, космический луч, переворачивающий результат сравнения. Фактически, эти системы часто не имеют или логически не могут иметь полное исходное значение для сравнения. - person ; 11.01.2014
comment
Как алгоритм может быть правильным, если известно, что он дает сбои на определенных входных данных (особенно если вы не контролируете входные данные?) - person oɔɯǝɹ; 11.01.2014
comment
Вы можете обсудить это с криптографами всего мира, но я бы сказал, что на данный момент я представил достаточно доказательств, подтверждающих, что ваш ответ неверен ;-) - person ; 11.01.2014
comment
Какая часть моего ответа «неправильная»? Я только пытаюсь предположить, что исходный вопрос может подразумевать неправильное понимание или применение хэш-кодов. Я не привносил в обсуждение криптографию и практические компромиссы... - person oɔɯǝɹ; 11.01.2014
comment
Я хочу сказать, что ваше утверждение о том, что коллизии хэшей являются потенциальной проблемой, означает, что вы используете их неправильно (что, давайте будем честными, здесь почти весь ответ), не является устойчивым. Это противоречит чрезвычайно широко распространенному использованию хеш-функций для целей, которые могут быть нарушены коллизиями, но прекрасно работают, несмотря на теоретическую возможность коллизий. - person ; 11.01.2014
comment
Ах хорошо. Это совершенно другой вид рассуждений, которые вы используете сейчас. Я вижу вашу точку зрения. Я только пытаюсь сказать, что при использовании хэш-кодов вам нужно иметь дело с тем фактом, что они могут и будут конфликтовать на практике, насколько маловероятно это может быть в теории. Иначе зачем бы хэш-таблица использовала сегменты? Существует достаточно примеров неправильного использования хэш-кодов, от которых я хочу предостеречь... - person oɔɯǝɹ; 11.01.2014
comment
Потому что все, что делает коллизии достаточно маловероятными, не может быть применено к хеш-таблицам: это несовместимо с ограничениями пространства и производительности таких структур данных. Хеш-функции слабее (как правило, не криптографически стойкие), домен хеш-функции на десятки порядков меньше и так далее. В хеш-таблицах коллизии вероятны (практически гарантированы) и должны обрабатываться — здесь теория и практика также сходятся. Вы правы в том, что не каждое использование хеш-функций может игнорировать коллизии, но общее утверждение просто вводит в заблуждение. - person ; 11.01.2014
comment
Раньше мы думали, что SHA1 также криптостойкий, но посмотрите, к чему это нас привело... :-) - person oɔɯǝɹ; 11.01.2014