Вскрытие в день рождения против однонаправленных хэш-функций
Существует два способа вскрытия однонаправленных хэш-функций грубой силой. Первый наиболее очевиден: дано значение хэш-функций сообщения, Н(М), врагу хотелось бы суметь создать другой документ, М', такой, что Н(М')=Н(М). Второй способ более тонок: врагу хотелось бы найти два случайных сообщения, М и М', таких, что Н(М')=Н(М). Такой способ называется столкновением и является более простым, чем первый, способом вскрытия.
Парадокс дня рождения является стандартной статистической проблемой. Сколько человек должно собраться в одной комнате, чтобы с вероятностью 1/2 хотя бы у кого-нибудь из них был бы общий с вами день рождения? Ответ - 183. Хорошо, а сколько людей должно собраться, чтобы с вероятностью 1/2 хотя бы у двоих из них был бы общий день рождения? Ответ удивителен - 23. 23 человека, находящихся в комнате, образуют 253 различных пары.
Найти кого-нибудь с тем же днем рождения - аналогия с первым способом вскрытия, найти двух человек с произвольным одинаковым днем рождения - аналогия со вторым способом. Второй способ широко известен как вскрытие в день рождения.
Предположим, что однонаправленная хэш-функция безопасна, и лучшим способом ее вскрытия является вскрытие грубой силой. Результатом функции является число. Поиск сообщения, хэш-значение которого совпадает с заданным, в среднем потребовал бы хэширования 2 m случайных сообщений. А для обнаружения двух сообщений с одинаковым хэш-значением потребуется только 2 т/2 случайных сообщений. Компьютеру, который хэширует миллион сообщений в секунду, потребовалось бы 600000 лет, чтобы найти второе сообщение с тем же 64-битовым хэш-значением. Тот же компьютер сможет найти пару сообщений с общим хэш-значением примерно за час
Это значит, что, если вы опасаетесь вскрытия в день рождения, вы должны выбирать длину хэш-значения в два раза длиннее, чем вам потребовалось бы в противном случае. Например, если вы хотите уменьшить вероятность взлома вашей системы до 1 шанса из 280, используйте 160-битовую однонаправленную хэш-функцию.