Парадокс дней рождения: почему коллизии хешей находить проще, чем кажется
• В посте про хэш-функции я вскользь упоминал коллизии. Сегодня разберём, почему их поиск связан с парадоксом дней рождения.
• Представьте группу из 23 человек, вероятность, что у двух из них совпадёт день рождения примерно 50%. Это кажется неожиданным, потому что мы сравниваем не дни рождения всех с одним конкретным человеком, а каждую возможную пару. Для 23 человек это уже 253 пары.
• С хэш-функциями похожая ситуация. Хэш любой длины данных имеет фиксированный размер, например, 256-битный хэш может принимать 2^256 разных значений, но при поиске коллизии мы ищем любые два разных сообщения с одинаковым результатом и сравниваем множество возможных пар.
• Поэтому для идеальной хэш-функции с результатом длиной
n бит найти коллизию можно примерно за 2^(n/2) вычислений, а не за 2^n. Для SHA-256 это порядка 2^128 попыток, стойкость SHA-256 к коллизиям оценивается в 128 бит.• Коллизия — это не то же самое, что подобрать сообщение к заданному хэшу. В первом случае ищут любые два сообщения с одинаковым результатом, во втором сообщение для конкретного заранее известного хэша, это разные задачи с разной сложностью.
• Поиск коллизий важен для систем, которые полагаются на уникальность хэша, например, цифровых подписей и проверки целостности файлов. Но сам факт существования коллизий не означает, что любую современную хэш-функцию можно взломать.
• Вот почему длина хэша и стойкость к коллизиям не одно и то же. Удачи!
• Поддержать автора монеткой: @v_meshke