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

Темы, не касающиеся фреймворка, но относящиеся к программированию в целом.
Аватара пользователя
samdark
Администратор
Сообщения: 9405
Зарегистрирован: 2009.04.02, 13:46
Откуда: Воронеж
Контактная информация:

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

Сообщение samdark »

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

Аватара пользователя
rugabarbo
Сообщения: 1063
Зарегистрирован: 2015.06.21, 16:21
Контактная информация:

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

Сообщение rugabarbo »

Sam Dark писал(а):Ну почему? Если использовать PBKDF2 с не сильно большим количеством итераций, то выбрать пару сотен паролей и сравнить все за несколько секунд вполне реально. Подозреваю, как-то так и реализовано потому что корпоративный сектор. NIST рекомендует PBKDF2, а про bcrypt и blowfish ни слова, хотя объективно для паролей они подходят больше.
Возможно. Я не разбираюсь в криптографических тонкостях, но помнится для PBKDF2 вечная проблема - подобрать оптимальное количество итераций под потребности конкретной системы.

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

R3D3
Сообщения: 352
Зарегистрирован: 2010.04.11, 14:52

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

Сообщение R3D3 »

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

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

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

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

В итоге получаем эффективный быстро работающий алгоритм проверки прошлых паролей, при этом не теряя в безопасности хеша текущего пароля. Как вам идея?
Yii Jabber Conference: yii@conference.jabber.ru

Аватара пользователя
rugabarbo
Сообщения: 1063
Зарегистрирован: 2015.06.21, 16:21
Контактная информация:

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

Сообщение rugabarbo »

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

zelenin
Сообщения: 10596
Зарегистрирован: 2013.04.20, 11:30

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

Сообщение zelenin »

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

Аватара пользователя
rugabarbo
Сообщения: 1063
Зарегистрирован: 2015.06.21, 16:21
Контактная информация:

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

Сообщение rugabarbo »

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

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

R3D3
Сообщения: 352
Зарегистрирован: 2010.04.11, 14:52

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

Сообщение R3D3 »

zelenin писал(а):в чем слабость 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 - там коллизий еще больше.
Yii Jabber Conference: yii@conference.jabber.ru

Аватара пользователя
rugabarbo
Сообщения: 1063
Зарегистрирован: 2015.06.21, 16:21
Контактная информация:

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

Сообщение rugabarbo »

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

zelenin
Сообщения: 10596
Зарегистрирован: 2013.04.20, 11:30

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

Сообщение zelenin »

R3D3 писал(а):

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

Аватара пользователя
girmate
Сообщения: 1534
Зарегистрирован: 2015.10.27, 12:52

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

Сообщение girmate »

R3D3 писал(а):Равномерное распределение символов md5 хеша также означает, что мы очень очень редко будем попадать на более чем одну проверку "подозрительного" пароля в случае, когда пользователем было введено менее чем 256 прошлых паролей.
Где можно почитать, чтобы удостовериться в том, что символы хеша md5 равномерно распределены?
Осторожно! Вы общаетесь с новичком ;)

R3D3
Сообщения: 352
Зарегистрирован: 2010.04.11, 14:52

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

Сообщение R3D3 »

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

Можно написать скрипт который генерирует хеши нескольких миллионов случайных строк и посмотреть, что распределение символов равномерно.
Yii Jabber Conference: yii@conference.jabber.ru

Ответить