Хранение истории паролей.

[samdark]

Ну почему? Если использовать PBKDF2 с не сильно большим количеством итераций, то выбрать пару сотен паролей и сравнить все за несколько секунд вполне реально. Подозреваю, как-то так и реализовано потому что корпоративный сектор. NIST рекомендует PBKDF2, а про bcrypt и blowfish ни слова, хотя объективно для паролей они подходят больше.

[rugabarbo]

Ну почему? Если использовать PBKDF2 с не сильно большим количеством итераций, то выбрать пару сотен паролей и сравнить все за несколько секунд вполне реально. Подозреваю, как-то так и реализовано потому что корпоративный сектор. NIST рекомендует PBKDF2, а про bcrypt и blowfish ни слова, хотя объективно для паролей они подходят больше.

Возможно. Я не разбираюсь в криптографических тонкостях, но помнится для PBKDF2 вечная проблема - подобрать оптимальное количество итераций под потребности конкретной системы.

На самом деле в Microsoft хорошие инженеры работают и вряд ли использовали md5, мне видится, что у них больше проблем на менеджерском и продуктовом уровне, а не на техническом. Я лишь по привычке пошутил про них (:

[R3D3]

Предлагаю чисто техническое решение проблемы (оно не претендует на криптографическую идеальность, но по-моему что-то в этом есть):

Вместе со стандартным yii-хешем 5 последних паролей храним также первые 2 (или 3) начальных символа от md5 каждого пароля. С одной стороны, если база будет украдена, то восстановить оригинальные пароли по таким частицам хешей невозможно.

С другой стороны, при вводе нового пароля, мы можем очень быстро выявить среди прошлых паролей "подозрительные", 2 символа md5 хеша которых совпадает с только что введенным новым. Для таких паролей уже производим полноценную тяжелую проверку по yii-хешу, и если он полностью совпадает, то выводим пользователю ошибку.

В чем профит? Пространство поиска по двухсимвольному хешу составляет 16*16 = 256 комбинаций, таким образом, при проверке попадание в "подозрительные" пароли весьма маловероятно (можно с натяжкой сказать что вероятность составляет 1/256). Равномерное распределение символов md5 хеша также означает, что мы очень очень редко будем попадать на более чем одну проверку "подозрительного" пароля в случае, когда пользователем было введено менее чем 256 прошлых паролей.

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

[rugabarbo]

Интересная идея. Получается быстрая грубая проверка с возможностью применить более медленную точную проверку в случае необходимости.

[zelenin]

в чем слабость md5? в малой стойкости к перебору и радужные таблицы.
какова вероятность, что e10 - первые 3 символа от e10adc3949ba59abbe56e057f20f883e (123456)? большая.

[rugabarbo]

Можно ведь потюнинговать:
* брать не 3 символа, а половину md5
* брать вообще полный md5 от некой части пароля (первых 4 символов)
* и т.д.

Мне кажется, можно добиться приемлемой вероятности, не сильно снижая безопасность.

[R3D3]

в чем слабость md5? в малой стойкости к перебору и радужные таблицы.
какова вероятность, что e10 - первые 3 символа от e10adc3949ba59abbe56e057f20f883e (123456)? большая.

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

Если перебирать все числа от 1 до 123456, то мы встретим 34 числа, первые 3 символа от хеша которых равны 'e10':

Код: Выделить всё

3652
5078
5976
8817
11041
19838
20896
24135
24912
24984
27819
33286
47053
52521
53484
56249
57034
70818
72290
80596
85014
87433
89935
94563
95504
104189
105263
107342
114525
115693
118962
119605
120514
120868

Получается, что искать коллизии от двухсимвольного хеша бессмысленно, т.к. их находится слишком много.

* брать не 3 символа, а половину md5
* брать вообще полный md5 от некой части пароля (первых 4 символов)

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

[rugabarbo]

Открывает злоумышленник украденную БД, а там какие-то части md5 вместо хэшей. Он будет так глубоко шокирован, что сразу же удалит всё к чертям без попыток взлома

[zelenin]

Получается, что искать коллизии от двухсимвольного хеша бессмысленно, т.к. их находится слишком много.

коллизии исктаь не надо. если md5 начинается с e10, то вероятность того, что это 123456 очень велика. Мы просто берем словарь частых паролей, берем первые 3 символа md5 от них и ищем их в базе.
Коллизии вообще не имеет смысла искать, т.к. мы не можем восстановить полный md5. Мы можем только с большой долей вероятности предположить, что пароль является часто употребляемым. В течении пары минут проверяем все явные пароли, а дальше решаем что делать с оставишимися.
Я к тому, что обрезанный md5 в десятки раз упрощает работу.

[girmate]

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

Где можно почитать, чтобы удостовериться в том, что символы хеша md5 равномерно распределены?

[R3D3]

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

Где можно почитать, чтобы удостовериться в том, что символы хеша md5 равномерно распределены?

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