Вычисление коллизий хэшей со 160 битами

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

Спасибо за помощь :)


cryptography hash collision hash-function hash-collision
person Bernd Eber    schedule 27.04.2018    source источник
comment
Очень много. Каждый компьютер на земле работает на полную мощность вплоть до тепловой смерти вселенского типа масштаба.   -  person mypetlion    schedule 28.04.2018
comment
@mypetlion Или два конкретных, для SHA-1: P   -  person Maarten Bodewes    schedule 28.04.2018
comment
Я голосую за то, чтобы закрыть этот вопрос как не относящийся к теме, потому что он не связан с программированием или разработкой программ.   -  person Maarten Bodewes    schedule 30.04.2018

Ответы (2)


arrow_upward
1
arrow_downward

Эмпирическое правило заключается в том, что вероятность столкновения составляет 50 % после того, как выпадет sqrt(n) число. Число немного больше, чем это, но квадратный корень является хорошим ориентиром. Таким образом, в вашем случае у вас есть 50% вероятность столкновения после 2 ^ 80 попыток.

Другое эмпирическое правило заключается в том, что после 4*sqrt(n) ваша вероятность получить дубликат почти не вызывает сомнений.

Согласно https://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem, вы можете вычислить количество, n значений, которые вам нужно нарисовать, чтобы получить вероятность p дубликата:

n = sqrt(2 * d * ln(1/(1-p)))

Где ln — натуральный логарифм, а p — вероятность от 0 до 1,0.

Итак, в вашем случае:

n = sqrt(2 * 2^160 * ln(1/.25))
n = sqrt(2^161 * 1.38629)

Что-то меньше, чем 2 ^ 81.

person Jim Mischel    schedule 28.04.2018

arrow_upward
0
arrow_downward

Где-то в диапазоне 2 septillion. Это 2 000 000 000 000 000 000 000 000 сообщений. Вот уравнение.

chance of collision = 1 - e^(-n^2 / (2 * d))

Где n — количество сообщений, d — количество возможностей. Итак, если d равно 2^160, то n будет рядом с 2^80.7.

person mypetlion    schedule 27.04.2018
comment
т.е. около половины размера вывода хэша из-за парадокса дня рождения. Обратите внимание, что требования к памяти для хранения хэшей для их сравнения друг с другом будут в том же порядке, и, насколько я знаю, в мире недостаточно памяти, чтобы сделать это. Эти хэши были созданы, чтобы избежать коллизий. Однако SHA-1 не справляется с этим, google sha-1 разбился. - person Maarten Bodewes; 28.04.2018
comment
@MaartenBodewes Не половина размера вывода, а квадратный корень из размера вывода. - person Jim Mischel; 01.05.2018