Коллизии хеш функций? Ассиметричное шифрование решает!

13 комментариев

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

На самом деле, избавится от коллизий в хеш функциях невозможно по одной простой причине: полученная хеш-сумма должна иметь фиксированную длину. Т.е. если логически подумать то перебрав 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 байт. Пусть конечно эта вероятность фактически стремится к нулю, но она есть!

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

Решение проблемы

Вообщем что же делать? В данной статье я хочу попробывать предложить отказаться от хеш функций в пользу функций шифрования. Как вы поняли из заголовка, я предлагаю использовать ассиметричное шифрование. Почему именно ассиметричное?

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

Теперь вернемся к ассиметричной. Ее прицнип заключается в том что данные зашифровываются одним ключем (публичный ключ) а расшифровываются уже другим (приватный ключ). Вообщем как то так:

Подробнее смотрите в этом моем посте: Ассиметричное шифрование. Как это работает?

А теперь представьте. Мы при генерации ключей удаляем приватный ключ, и храним только публичный. Расшифровать зашифрованные данные мы уже не сможем, злоумышленник тоже (даже если и завладеет публичным ключем), фактически получаем хеш функцию с переменной выходной длиной. На практике это будет выглядеть так: мы один раз генерируем ключи, приватный ключ удаляем, а публичный сохраняем где нибудь в конфиге, каждый пароль (не забываем про соль) шифруем с помощью хранимого публичного ключа и полученную строку (по сути — уже хеш) храним в БД:

При проверке авторизации, введенный пароль также шифруем хранимым публичным ключем и сравниваем со строкой в БД. Если строки идеинтичны то пользователь ввел верный пароль.

Собственно все =) На самом деле очень простая идея. Только проблема скорее всего будет в реализации на практике. Стоит ли защита от мизерной вероятности коллизии вашего пароля такого геммороя с ассиметричным шифрованием?

Итог

К сожалению такая система имеет огромное колличество минусов. И самый главный из них — это переменная длина зашифрованного пароля. Да и в реализации эта система довольно сложна. Не знаю будет ли кто нибудь ее применять, но как говорится неразрешимых проблем не бывает — проблему с коллизиями в классической системе хранения паролей мы решили =)

  1. mr.The

    Интересная идея. Да и перебор такого пароля должен, по идее, занять больше времени(хотя, зависимо от алгоритма).

    А в чём проблема реализации? В итоге все всё-равно сведётся к виду

    Да и переменная длинна не такая уж и проблема если сам пароль ограничен например 30 символами, то у нас уже не будет шифрованных данных в over9000 символов, так что можно будет нормально использовать что-то вроде varchar(500). (500 — сферическое в вакууме число, зависит от того на сколько увеличиваются данные после шифрования.)

    1. Дмитрий Амиров Автор

      Проблема в том что практически ни в одном из скриптовых языков типа php, perl, asp и прочих, нет встроенных функций ассиметричного шифрования. Прийдется подключать дополнительные библиотеки, городить кучу кода для сведения всего к виду:

      Да и насчет переменной дилины. Возникает проблема с размером БД и скоростью работы. К примеру есть очень огромная разница между хранить хеш md5 в виде CHAR(16) (именно 16, так как 32 байта он занимает в hex представлении) или хранить VARCHAR(500). Да, на простеньких сайтах с маленькой БД это роли не сыграет, но на крупных проектах это может тупо загнуть сервак.
      Ну а вообще, я согласен, в целом идея неплоха.

      1. mr.The

        Прийдется подключать дополнительные библиотеки, городить кучу кода для сведения всего к виду:

        Я погуглил с сразу нашел кучку готовых модулей, где всё примерно к такому виду и сводится. Так что тут проблемы как бы и нет.

        Ну а про крупные проекты я не уверен, что переменный размер поля будет так уж сильно мешать. Разве что, если будут миллионы записей, но тут уже и подход к архитектуре другой должен быть.

        1. Дмитрий Амиров Автор

          Хм. Может быть вы таки и правы =)
          Но согласитесь, есть разница, использовать обычную функцию md5() или подключать библиотеки, писать обертку под них и тд и тп. Может быть это не так весомо, но так или иначе это минус.
          Ну а насчет переменной длины, я скорее имел ввиду проблему того что зашифрованный пароль может быть довольно длинной строкой. И грозит это увеличением общего объема БД.
          Нет, вы не подумайте, мне нравится эта моя идея с ассиметричным шифрованием. Я всего лишь пытаюсь заранее предупредить о всех возможных недостатках этой системы =)

  2. Дядя

    А теперь представьте. Мы при генерации ключей удаляем приватный ключ, и храним только публичный. Расшифровать зашифрованные данные мы уже не сможем, злоумышленник тоже (даже если и завладеет публичным ключем).

    А злоумышленник, возьмет, да и воспользуется МЕТОДОМ БЕСКЛЮЧЕВОГО ЧТЕНИЯ.

    1. Дмитрий Амиров Автор

      Гм, вы о чем? Данный термин описывает всего лишь класс атак на шифры. И если уж, извините, выбранный вами алгоритм подвержен данной атаке — то вы сами себе виноваты.
      Естественно при разработке данного алгоритма «хеширования» нужно выбрать наиболее стойкий шифр.

  3. Лео

    А если пользователь потерял пароль и хочет его восстановить? Ключа для расшифровки его пароля из БД нет. Как поступить в данной ситуации?

    1. Дмитрий Амиров Автор

      Происходит то же самое по аналогии с хешами, ему просто генерируется новый пароль. Старый естественно восстановить невозможно.

      1. xmoonlight

        Ну, здесь я не соглашусь, что удобнее сразу генерировать пользователю новый пароль!
        Это будет неудобно для пользователя, если он привык к своему паролю и ему придётся выполнять две итерации: генерацию и смену на свой в профиле.

        Лучше сгенерировать линк с токеном на 1 час для ВВОДА НОВОГО ПАРОЛЯ самим пользователем и отправить его по почте (или PIN по SMS).
        Как альтернатива: можно предоставить выбор после перехода по ссылке смены пароля: «ввести свой» или «сгенерировать случайный».

        Конечно, не стоит допускать ввода последних N-вариантов или их производных: цифры, буквы, пунктуацию — эти символьные группы хранить отдельными хешами, чтобы можно было бы проверять по таблице предыдущих ПАРОЛЕСОДЕРЖАЩИХ хешей, которые хранят все символьные группы и общие парольные хеши (итого: 4 поля).

  4. Apologiz

    При проверке авторизации, введенный пароль также шифруем хранимым публичным ключем и сравниваем со строкой в БД. Если строки идентичны то пользователь ввел верный пароль.

    Не совсем укладывается в голове. А как сверить пароль пользовательский и хранимый в базе, не имея приватного ключа?
    То есть, если мы зашифровали пароль с закрытым ключём и удалили его, то при сравнении паролей не имея закрытого ключа (так как мы его удалили), пароли просто не совпадут.

    1. Дмитрий Амиров Автор

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

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

  5. Дмитрий

    «Шифруем не приватным а публичным ключом»
    Так это тот-же самый хеш. Только хеш*2. Суть не меняется … есть ключ по нему делается какая-то контрольная сумма, она и сравнивается.
    Вся ваша схема сводится лишь к тому… что изменяется пользовательский пароль перед тем как сделать хеш… это как переставить буквы в пароле перед получением хеша, только перестановка чуть посложнее. Как была проблема одинаковых хешей так и остается.
    Вопрос лишь в том, что быстрее перебрать — пароли или хеши…зависит от длины.

    1. Дмитрий Амиров Автор

      К сожалению, вы не уловили суть статьи совсем.

      Проблема хеш функций — в их алгоритме «свертки» до строки фиксированной длины. Суть в том что из за этого могут возникать коллизии. Так например, вы используете какой то супер длинный пароль длиной в 50 символов. Существует вероятность того что хеш такого пароля будет равен хешу какого нибудь например пяти символьного пароля. Т.е. злоумышленник сможет авторизоваться в систему используя коллизию, а не искать полный оригинальный пароль.

      Использование ассиметричного шифрования в данном случае — это не контрольная сумма в прямом ее понимании. Это зашифрованный пароль (далее «шифрохеш»), который можно расшифровать только приватным ключом, который мы целенаправленно «потеряли». Т.е. обратно пароль из такого импровизированного «шифрохеша» уже не получить.

      Что это дает? У такого «шифрохеша» не бывает коллизий априори. Не могут два разных текста (в нашем случае пароля), зашифрованные одним и тем же ключом одним и тем же алгоритмом, давать одинаковые шифротексты. Появляется другая проблема — выходной «шифрохеш» получается произвольной длины, это нужно учитывать при их хранении в БД. И еще некоторые нюансы.

Добавить комментарий

Прочли запись? Понравилась? Не стесняйтесь, оставьте, пожалуйста, свой комментарий. Мне очень интересно, что вы думаете об этом. Кстати в комментарии вы можете задать мне любой вопрос. Я обязательно отвечу.

Вы можете оставить коментарий анонимно, для этого можно не указывать Имя и email. Все комментарии проходят модерацию, поэтому ваш комментарий появится не сразу.