Во многом, продолжение этой темы.

Для многих не секрет, что построить коллизию для полиномиального хеша по модулю, например, 10^9 + 7, не очень сложно.

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

Идея в следующем: парадокс дня рождения позволяет генерировать хеш-коллизию первого хеша простым перебором за O(sqrt(p)), где p — модуль, по которому берется хеш. После этого каждая из полученных строк коллизии первого хеша считается отдельным символом, и при помощи парадокса дня рождения генерируется коллизия для второго хеша (коллизией первого хеша строка-конкатенация коллизий будет автоматически).

Примечание.

Для неизвестного хеша по простому модулю универсальных контртестов, по-видимому, не существует. Это связано с тем, что технически контртест может быть представлен как многочлен, корнем которого является множитель хеша, а количество корней многочлена по простому модулю ограничено его степенью. Универсальный контрпример для 2^64, описанный выше, строил многочлен не очень большой степени, корнями которого являются все нечетные числа.

Вывод: будьте бдительны! Хеши должны быть с рандомизированным множителем/модулем, и модуль должен быть простым, иначе рано или поздно вас поймают!