Коллизии хеш функций? Ассимитричное шифрование решает! Надеюсь вы помните, я обещал в прошлой статье "Хранение паролей пользователей" предложить вариант того как можно гарантированно избавится от коллизий. На самом деле, избавится от коллизий в хеш функциях невозможно по одной простой причине: полученная хеш-сумма должна иметь фиксированную длину. Т.е. если логически подумать то перебрав 2n комбинаций (где n - длина хеша в битах), мы стопроцентно найдем коллизию. Ну а если вы слышали про парадокс дней рождения, то для вас будет очевидным что достаточно будет перебрать "всего лишь" 2n/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 байт. Пусть конечно эта вероятность фактически стремится к нулю, но она есть! Стопроцентная защита от коллизий есть! Читайте под катом. Решение проблемы Вообщем что же делать? В данной статье я хочу попробывать предложить отказаться от хеш функций в пользу функций шифрования. Как вы поняли из заголовка, я предлагаю использовать ассиметричное шифрование. Почему именно ассиметричное? Вспомним классическую (симметричную) систему шифрования. В ней данные шифруются и расшифровываются одним и тем же ключом. Теперь представте практическую реализацию хранения паролей с помощью симметричной системы. Помимо хранения паролей нам нужно будет хранить и ключ, но при этом если вдруг злоумышленник завладеет этим ключом, то вся безопасность системы рушится на корню, так как злоумышленник сможет без особого труда расшифровать все пароли. То есть нам нужна такая функция которая позволила бы только зашифровывать данные без возможности их обратно расшифровывать, а по факту - нужен аналог хеш функции только без фиксированной длины. Теперь вернемся к ассиметричной. Ее прицнип заключается в том что данные зашифровываются одним ключем (публичный ключ) а расшифровываются уже другим (приватный ключ). Вообщем как то так: А теперь представте. Мы при генерации ключей удаляем приватный ключ, и храним только публичный. Расшифровать зашифрованные данные мы уже не сможем, злоумышленник тоже (даже если и завладеет публичным ключем), фактически получаем хеш функцию с переменной выходной длиной. На практике это будет выглядеть так: мы один раз генерируем ключи, приватный ключ удаляем, а публичный сохраняем где нибудь в конфиге, каждый пароль (не забываем про соль) шифруем с помощью хранимого публичного ключа и полученную строку (по сути - уже хеш) храним в БД: При проверке авторизации, введенный пароль также шифруем хранимым публичным ключем и сравниваем со строкой в БД. Если строки идеинтичны то пользователь ввел верный пароль. Собственно все =) На самом деле очень простая идея. Только проблема скорее всего будет в реализации на практике. Стоит ли защита от мизерной вероятности коллизии вашего пароля такого геммороя с ассиметричным шифрованием? Итог К сожалению такая система имеет огромное колличество минусов. И самый главный из них - это переменная длина зашифрованного пароля. Да и в реализации эта система довольно сложна. Не знаю будет ли кто нибудь ее применять, но как говорится неразрешимых проблем не бывает - проблему с коллизиями в классической системе хранения паролей мы решили =) Дата: 14.06.2012 02:43 Автор: Intellect http://intsystem.org/723/hash-collision-vs-asymmetric-encryption/