Хеш-функции — это математические преобразования, которые принимают на вход данные произвольного размера и возвращают фиксированный по длине результат, называемый хешем или дайджестом. Они широко применяются в программировании, базах данных и криптографии.

Существует несколько классов хеш-функций, каждый из которых ориентирован на свои задачи:

1. Простые хеш-функции, такие как контрольные суммы и CRC, предназначены для проверки целостности данных и обнаружения ошибок при передаче. Они работают быстро, но не обеспечивают защиты от намеренного искажения данных.
2. Криптографические хеш-функции разработаны с целью обеспечить безопасность: сделать невозможным восстановление исходных данных по хешу, найти другие данные с таким же хешем или две любые разные записи с совпадающим хешем. Эти свойства называются устойчивостью к нахождению прообраза, второго прообраза и коллизиям соответственно.
3. Специализированные хеш-функции используются для оптимизации задач, таких как быстрый поиск в базах данных или хранение паролей с применением дополнительных методов защиты. Они не всегда криптографически стойкие, но эффективны для своих целей.

   Свойства безопасности

Устойчивость к атакам

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

Размер хеша

Существует обязательный минимальный размер хеш-функции - 256 бит, или 32 байта. При таком большом размере выхода коллизий быть не должно.

В реальной криптографии алгоритмы ориентируются на минимальный уровень безопасности в 128 бит. Злоумышленник, который хочет взломать алгоритма обеспечивающий 128-битную защиту, должен выполнить около $2^{128}$ операций (например, перебор всех возможных входных строк длиной 128 бит потребует $2^{128}$ операций). Самой простой атакой обычно является поиск коллизий в связи с ограниченностью дней рождения.

Парадокс дней рождений и поиск коллизий

Парадокс дней рождений - это известное явление из теории вероятностей. Он говорит о том, что в группе из всего 23 человек вероятность того, что у двух из них совпадет день рождения уже превышает 50%. Это кажется удивительным, потому что дней в году 364, а людей всего 23, но совпадения происходят чаще, чем интуитивно ожидается.

Хеш-функция превращает данные в короткий набор символов — хеш. Поскольку набор возможных хешей ограничен (например, 2^128 вариантов), при большом количестве различных данных с очень высокой вероятностью найдутся два разных входа, которые дадут одинаковый хеш.

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

Важно понимать, что этот парадокс применим именно к поиску любых двух данных с одинаковым хешем (коллизиям) и не облегчает нахождение прообраза или второго прообраза, где задача сложнее и требует гораздо больших вычислительных ресурсов.

Парадокс дней рождений: математическое объяснение

Есть группа из $n$ человек, и необходимо узнать вероятность того, что хотя бы у двух из них совпадёт день рождения. Считаем, что в году $d=365$ дней, и что дни рождения равновероятны и независимы.

• Вероятность того, что у всех nnn человек дни рождения разные, равна: $P(\text{все разные}) = \frac{d}{d} \times \frac{d-1}{d} \times \frac{d-2}{d} \times \cdots \times \frac{d - n + 1}{d} = \prod_{k=0}^{n-1} \left(1 - \frac{k}{d}\right)$

• Тогда вероятность того, что есть хотя бы одна пара с одинаковым днем рождения: $P(совпадение)=1−P(все разные)=1-\prod_{k=0}^{n-1} \left(1 - \frac{k}{d}\right)$

Для $n=23$ эта вероятность уже больше 0.5 — то есть более 50%, что кого-то с днем рождения совпадёт.

Как это связано с поиском коллизий в хеш-функциях

В случае хеш-функций:

• $d$ - количество всех возможных хеш-значений (например, $2^{128}$ для 128-битного хеша).
• $n$ - количество хешей, которые мы вычисляем для разных входных данных.

Парадокс показывает, что вероятность найти хотя бы одну пару с одинаковым хешем (коллизию) становится значительной при количестве вычисленных хешей примерно около $\sqrt{d}$​ (корень из общего числа возможных хешей). Это - следствие вероятностного анализа, аналогичного парадоксу дней рождений.