Надеюсь вы помните, я обещал в прошлой статье «Хранение паролей пользователей» предложить вариант того как можно гарантированно избавится от коллизий.

На самом деле, избавится от коллизий в хеш функциях невозможно по одной простой причине: полученная хеш-сумма должна иметь фиксированную длину. Т.е. если логически подумать то перебрав 2ⁿ комбинаций (где n — длина хеша в битах), мы стопроцентно найдем коллизию. Ну а если вы слышали про парадокс дней рождения, то для вас будет очевидным что достаточно будет перебрать «всего лишь» 2^n/2 чтобы с достаточной вероятностью найти коллизию.

Конечно эти числа для хешей длинной более чем 100бит будут огромны. Например для md5 длинной 128 бит, полный перебор это всего лишь ~30 000 000 000 000 000 000 000 000 000 000 комбинаций, учитывая парадокс дней рождения надо будет перебрать совсем чуть-чуть, где-то ~18 000 000 000 000 000 000 комбинаций. На моем ноуте это «всего лишь» около 500 тысяч лет беспрерывного перебора.

Вродебы вот решение — используйте хеш функции с большой длинной выходной хеш-суммы. Но, как я говорил раньше, никто ни застрахован от того что ваш хеш от вашего пароля длинной минимум в 30 символов, не будет иметь коллизию длиной всего лишь в 1 байт. Пусть конечно эта вероятность фактически стремится к нулю, но она есть!

Стопроцентная защита от коллизий есть! Читайте под катом.
Читать далее →