Атака «дней рождения».
Этот тип атаки основан на том факте, что одинаковые значения, называемые также коллизиями (collisions), появляются намного быстрее, чем можно было ожидать. В системе финансовых транзакций, в которой для обеспечения безопасности, применяется новый 64-битовый ключ аутентификации. (Для простоты предполагается, что шифрование не используется.) Существует 264 возможных значения ключа (это больше, чем 18·1018, т.е. 18 миллиардов миллиардов). Отследив около 232 транзакций, злоумышленник может предположить, что две из них используют один и тот же ключ. Предположим, что сообщение-заголовок, передаваемый в ходе каждой транзакции, всегда одинаково. Если две транзакции используют один и тот же ключ аутентификации, тогда значения MAC первых сообщений этих транзакций будут совпадать, что легко отследит злоумышленник. Зная, что обе транзакции используют один и тот же ключ аутентификации, он сможет вставлять сообщения из более старой транзакции в более новую транзакцию во время выполнения последней. Поскольку ложные сообщения успешно пройдут аутентификацию, они будут приняты, что является очевидным взломом системы финансовых транзакций.
В общем случае, если элемент может принимать N различных значений, ожидать первой коллизии можно после случайного выбора приблизительно элементов. В большинстве случаев мы будем говорят об n-битовых значениях. Поскольку n-битовый элемент может иметь 2n возможных значения, необходимо извлечь = 2n/2 элементов множества, чтобы надеяться на возникновение коллизии. Назовем это оценкой 2n/2 или оценкой парадокса задачи о днях рождения (birthday bound).