How to become an author
Search
Write a publication
Pull to refresh

Comments 88

Я вот только не очень понимаю как потом с хешем с динамической солью работать. Соль чтоли отдельно придется хранить для каждого пароля?
Total votes 2: ↑2 and ↓0+2
Да, в таблице теперь будет храниться не только логин/хеш пароля, но и значение динамической соли, сгенерированной, например, при регистрации пользователя. Сейчас добавлю этот момент в пост.
Total votes 1: ↑1 and ↓0+1
если утекает база целиком, то какая разница динамическая соль у тебя или статическая?
Total votes 7: ↑2 and ↓5-3
Хотя в случае тупого брутфорса видимо поможет
Total votes 1: ↑1 and ↓0+1
База утекла, только как теперь пароли подобрать то? В случае использования SHA, подобрать пароли для, хотя бы десятка пользователей, уже будет проблематично.
Total votes 4: ↑3 and ↓1+2
Для каждого юзера брутфорсить надо по новому. Если у двух юзеров одинаковый пароль то со статической солью будет и одинаковый хэш, с динамической — разный. Если использовать в качестве динамического ключа не случайную строку, а хэш других уникальных полей (id, login, e-mail, ...) или даже их напрямую, то можно не хранить отдельно, главное не забывать при изменении «ключа» перегенерировать хэш.
Total votes 8: ↑8 and ↓0+8
А, вот теперь понятно, спасибо :)
И про другие поля сразу не додумался, интересно
Total votes 1: ↑1 and ↓0+1
Например, можно использовать в качестве динамической соли — кусок от sha1 (айди пользователя ):
$id — id пользователя в базе
$password — его пароль
Тогда, cолью будет $salt=sha1($id), а хэшем пароля — sha1($password. substr($salt,0,6)).

Тогда, утащив базу, злоумышленник получит только базу соленых хэшей без самих солей. А соли высчитываться будут в скриптах. Правда, это будет дополнительная нагрузка, но не об этом разговор.
Total votes 3: ↑2 and ↓1+1
Пару раз встречал подобный подход. Всегда удивляло это: substr($salt,0,6). Поясните, пожалуйста, почему не просто $salt? Зачем её ещё обрезать? Дабы уменьшить коллизии? А разве оных будет много при пароле до 20+ символов?
Total votes 5: ↑5 and ↓0+5
Можно определить соль фиксированной длины, и в базе, в поле пароля хранить склейку "<хэш пароля>+<соль>. Ну или склеивать еще более хитрым алгоритмом.
Но это все имеет смысл только если утекла одна только база и неизвестен алгоритм склейки.
Как вариант кстати — использовать бинарную реализацию алгоритма генерации значения поля пароля для базы (например, своим расширением для PHP).
This comment wasn’t rated yet0
>Но это все имеет смысл только если утекла одна только база и неизвестен алгоритм склейки.

Известный алгоритм не избавит от необзодимости подбирать каждый хэш.

This comment wasn’t rated yet0
Если база не утекла, то можно и в открытом виде держать.
This comment wasn’t rated yet0
эм… немного не понял, ну будет у вас в таблице еще одно боле с солью (обычное нехешированое поле) и в чем тогда выигрыш? т.е. слив базу злоумышленник получает связки пароль + соль для пароля, остается только разгадать алгоритм как соль участвует в получении пароля + сам пароль, разве не так?
Total votes 5: ↑1 and ↓4-3
Если соль статическая (одинаковая для всех юзеров), то у всех паролей qwerty в базе будет хэш bdadb0330124cda0e8499c9cd118f7bd, подобрав пароль для одного пользователя мы получим пароли остальных с таким же хэшем. А будет соль у каждого своя — нужно будет подбирать у каждого.
Total votes 1: ↑1 and ↓0+1
Еще раз.

1. Нет соли — используем уже готовые радужные таблицы.
2. Есть одна на всех соль — генерируем одну радужную таблицу и «ломаем» по ней всех пользователей.
3. Есть отдельная соль для каждого пользователя — отдельно брутфорсим каждого пользователя.
Total votes 11: ↑11 and ↓0+11
и что дальше? вы радужную таблицу сами будете генерировать? хм, сомневаюсь. пункт 1 ясен всем, пункт 3 — единственное преимущество это только выигрыш времени в брутфорсе каждого отдельно взятого пользователя, т.е. фактически как я и описал выше все сводится к: узнать алгоритм применения соли + сам пароль, так? поэтому как-то совсем не выигрышно, ну будет 2 польз. с разной солью, но одинаковыми паролями и что? зная алгоритм как соль применяется в пароле тут они абсолютно ничем не защищены.
Total votes 7: ↑0 and ↓7-7
Вы в курсе что такое хеш-функция? Зная хеш вы не можете эффективно узнать входное значение, в идеале вы можете сделать это не быстрее чем тупым перебором, это так называемая односторонняя функция, краеугольный камень современной криптографии.
Так что вы знаете алгоритм и соль, но это вам никак не поможет избежать перебора для нахождения пароля. Так что в случае 2 вам достаточно подобрать пароль у одного пользователя и вы автоматически узнаете пароли у всех пользователей использовавших этот пароль. В случае же 3 вам придётся брутфорсить для каждого пользователя отдельно, посему скорость узнавания паролей катастрофически снижается.
Total votes 2: ↑2 and ↓0+2
Вы опять отвечаете на то что понятно любому, я рассматриваю ситуацию для разных пользователей у которых разные пароли. поэтому случай 3 странный совсем, хранить соль рядом с паролем. соль лучше вычислять динамически взависимости от каких либо данных, а не хранить рядом в поле, а то смысл 3его пункта тогда совсем теряется, т.к. зная соль и алгоритм можно тупо перебирать по таблицам так же как и всегда.
Total votes 7: ↑1 and ↓6-5
Для полностью скомпрометированной системы (слиты дамп БД и исходники) ваше «динамически вычисляемая» соль не будет ничем отличаться от соли хранимой рядом с результирующим хешем. Тем не менее, да, как дополнительный ступень усложнения жизни злоумышленника это имеет право на жизнь, примерно это я и описывал в идеальной на мой взгляд схеме.

зная соль и алгоритм можно тупо перебирать по таблицам так же как и всегда.

Для вас радужные таблицы это что-ли какая-то магия? Почитайте хотя-бы вот этот раздел на вики. Я посмотрю как вы будете составлять таблицу для строк у которых длина больше 20 символов в которые входит длинное случайное сочетание символов и особенно мне интересно откуда вы достанете столько памяти.
Total votes 2: ↑2 and ↓0+2
В чём нет смысла? Процитирую вас:
>поэтому как-то совсем не выигрышно, ну будет 2 польз. с разной солью, но одинаковыми паролями и что? зная алгоритм как соль применяется в пароле тут они абсолютно ничем не защищены.
В среднем пользователи будут защищены лучше, т.к. что бы взломать эти два пароля злоумышленнику придётся брутфорсить в два раза дольше, а значит стоимость взлома одного пароля станет больше, что равнозначно лучшей защищённости паролей в данной схеме.
Упреждая уже приевшуюся риторику: когда говорят о схемах защиты и соления подразумевается что защищается вся база целиком, а не какой-то отдельный пользователь. Для защиты одного пользователя соли мало спасают, в т.ч. и ваши «динамически генерируемые», единственный путь здесь это использовать медленные хеш-функции.

В любом случае, будьте подробны обозначить свою позицию поподробней, иначе мне уже совершенно непонятно что вас не удовлетворяет в обсуждаемых схемах и к чему у вас есть претензии.
This comment wasn’t rated yet0
Я ссылку вашу прочитал, решение хорошее да. Я ниже описал, что рассматриваю ситуацию когда нужно взломать 1го конкретного пользователя, тогда особо хранение соли рядом с паролем не поможет, я считаю что соль должна динамически генерироваться. ладно тут и так слишком много моих комментов, мне ваша позиция ясна :)
Total votes 3: ↑0 and ↓3-3
«Мыши плакали, кололись, но продолжали грызть кактус»
>> т.к. зная соль и алгоритм
чтобы узнать алгоритм, нужно глянуть исходники (да, есть вариант самому его подобрать, но мы его опустим). Раз есть исходники, точно также можно посмотреть как «динамически» генерируется ваша соль. Собственно профит сомнительный, кроме как лишняя нагрузка, чтобы каждый раз ее вычеслять
This comment wasn’t rated yet0
Ваше мнение очень интересно :)
Total votes 4: ↑0 and ↓4-4
и что дальше? вы радужную таблицу сами будете генерировать? хм, сомневаюсь
Почему сомневаетесь? На моем скромном ноутбуке, скриптом на PHP у меня генерируется примерно 1,7 млн. MD5-хэшей в секунду. Так что сгенерировать радужные таблицы по словарю или перебором коротких паролей с любой солью — задача не такая уж и невыполнимая.

все сводится к: узнать алгоритм применения соли + сам пароль, так?
Нет, не так. По-умолчанию всегда считаем, что алгоритм известен.

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

Т.е. если у нас одна соль на всех, и хакер может генерировать радужную таблицу для словаря и недлинных алфавитно-цифровых паролей за 7 дней, то именно 7 дней у него уйдет на взлом всех пользователей. Если же соль для каждого пользователя разная, то 7 дней (ну чуть меньше) у хакера уйдет на взлом одного пользователя! А если пользователей 1000, то на из взлом потребуется уже 7000 дней, т.е. почти 20 лет!

А если еще и использовать действительно медленный алгоритм для получения хэша пароля, чтобы в секунду хакер мог генерировать не миллионы значений, а сотни или даже десятки, то и одного пользователя таким образом взломать будет за приемлемое время невозможно.
Total votes 3: ↑3 and ↓0+3
>>На моем скромном ноутбуке, скриптом на PHP у меня генерируется примерно 1,7 млн. MD5-хэшей в секунду
>>Т.е. если у нас одна соль на всех, и хакер может генерировать радужную таблицу для словаря и недлинных алфавитно-цифровых паролей за 7 дней
что-то как то слабо кореллирует одно с другим. я спрашиваю не про всех пользователей а про одного конктретного, пусть хакере интересует 1 конкретный польз. а не все, выигрыш в хранении в поле БД динамической соли в данном случае сомнителен. Щас опять заминусуют специалисты криптозащиты из школы :D
Total votes 2: ↑1 and ↓10
Пример про 7 дней у меня чисто гипотетический, с реальным временем ничего общего не имеет и ни на какие конкретные функции не ориентирован.

Если хакера интересует один конкретный пользователь, то, естественно, выигрыша нет. И если в системе предполагается лишь один пользователь, то соль можно хранить хоть в конфиге, хоть в самом коде (хотя это и не гибко).

Ну а если у вас в системе предполагается много пользователей, то хоть тут-то Вы видите преимущества разной соли для каждого пользователя?
Total votes 2: ↑2 and ↓0+2
Естественно, я спорил про ситуацию когда нужено получить пароль конкретного пользователя, а тут сразу «специ криптозащиты» заминусовали, ппц. Редко когда хакеру нужно получить пароли именно _всех_ пользователей, почти всегда интересует кто-либо конкретный скорее всего.
Total votes 4: ↑0 and ↓4-4
Скорее наоборот. Хакеров в большинстве случаев будут интересовать все пользователи, вернее, как можно больше пользователей. Зачем? Потому что есть большая вероятность того, что пароли, украденные с какого-либо сайта, подойдут к email-ам, указанным пользователя на том же сайте. А это спам, это связанные аккаунты в социальных сетях, в которых, опять же, спам.

А вот ситуацию, при которой с сайта крадут базу данных, чтобы найти пароль какого-то одного пользователя, мне как-то сложно представить — цель не оправдывает средства.
Total votes 6: ↑6 and ↓0+6

можно еще чуть-чуть приподнять сложность дополнив последний вариант до
4. дополнительная глобальная соль всасывается сервом из внешнего репозитория секретов

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

This comment wasn’t rated yet0
А нельзя использовать в качестве соли уже существующие данные? Например, логин
This comment wasn’t rated yet0
Можно, используют. Но лучше всего случайные числа. Так даже удобнее, хранятся с хешем одной строкой.
This comment wasn’t rated yet0
Чаще используется «засаливание» не самого пароля, а хэша от него:

password = md5(md5(password) + salt)
Total votes 1: ↑1 and ↓0+1
С точки зрения брутфорса нет разницы как засаливать. Также, насколько я помню, брать хеш из хеша — плохо, добавляет коллизий.
Total votes 6: ↑5 and ↓1+4
Ну вероятность коллизии будет одинаковая, сколько вложенных хэшей не делай. А вот если злоумышленнику известна соль — то со вложенным md5, по-моему, сложнее — надо 2 раза перебирать хэши — сначала чтобы вычислить md5(password) + salt, затем сам password.
Total votes 2: ↑0 and ↓2-2
Это почему она будет одинаковая? При каждом применении функции хэширования множество значений неувеличивается. Остаётся прежним оно только тогда, когда коллизий нет вообще. Коллизии md5(<some_hash>) не изучены, поэтому считать, что их нет было бы странно. В результате чем больше применяем, тем меньше множество значений и тем больше вероятность коллизии.
Total votes 1: ↑1 and ↓0+1
А с чего вы взяли что чем больше мы применяем, тем меньше множество значений?
Total votes 1: ↑0 and ↓1-1
Оно не больше по очевидным причинам. А так как вопрос «остаётся ли оно таким же (т.е. нет коллизий при применении функции ко всем возможным хэшам» открыт и неизучен, было бы странно надеяться на то, что их нет. Тут пишут.

С другой стороны, я действительно не понимаю, как это может помочь при взломе и подборе.
This comment wasn’t rated yet0
Не забывайте, что там не md5(), а md5( + salt), причем salt — динамическое значение.
Total votes 1: ↑1 and ↓0+1
А вот про это забыл, извиняюсь. Может стать сильно лучше.
This comment wasn’t rated yet0
Не будет она одинаковая в общем случае. Может быть несколько паролей, которые дадут одинаковый внутренний хэш, и может быть несколько сочетаний этого хэша с солью, которые дадут одинаковый итоговый хэш.
Total votes 1: ↑1 and ↓0+1
Скорее всего это историческое прошлое конкретных продуктов. Конкретный пример: в MediaWiki используется два вида хэшей: «:A:md5(password)» и «:B:salt-md5(salt-md5(password))». Первый вариант — исторический, когда ещё радужные таблицы не были в обиходе. Потом до разработчики сообразили, что нужна соль, но что делать сайтам, где уже зарегистрированы тысячи пользователей, а в базе данных только хэши? Пришлось хэшировать хэши.

А брутфорсить такие хэши (и то только такие) умеет John the Ripper community-enhanced version.
This comment wasn’t rated yet0
> но что делать сайтам, где уже зарегистрированы тысячи пользователей, а в базе данных только хэши

Взять эти _хэши_ да просолить. То есть вообще никаких проблем…
This comment wasn’t rated yet0
Так же, как вариант, чтобы отдельно не хранить соль:
sha1($login.":".$password);
Total votes 1: ↑1 and ↓0+1
Или номер ID пользователя — юзернейм иногда может меняться, тогда хеш нужно будет генерировать заново, а ID обычно постоянен.
This comment wasn’t rated yet0
ID плохо для атак по словарю, по-моему.
This comment wasn’t rated yet0
А стоит ли использовать sha1? На php.net — не рекомендуют, также, как md5.
Total votes 2: ↑1 and ↓10
> Вот здесь и кроется минус статической соли: злоумышленник сможет сгенерировать свою таблицу хешей со статической солью

Минус не в этом. Минус в том, что хеши для разных пользователей будут совпадать если у них одинаковый пароль. Ломать их становится проще, так как пароль явно словарный.

SHA* не подходят для хеширования паролей. Автор заметки плохо осведомлен. Годные алгоритмы — это PBKDF2, bcrypt и scrypt.
Total votes 4: ↑3 and ↓1+2
> Минус не в этом.
Нет, в этом. С одной статической солью мы можем сгенерить для данной базы свою таблицу.
Насчет SHA поясните, почему нет?
This comment wasn’t rated yet0
Да, согласен, и то и другое.

SHA задуман быть быстрым, брутфорсится он тоже быстро. scrypt задуман как алгоритм с регулируемой скоростью (чтобы замедлять его с ростом производительности процессоров), требованиями к памяти, и невозможностью распараллелить на GPU.
Total votes 3: ↑3 and ↓0+3
А если динамическую соль не хранить в базе, а генерировать каждый раз при необходимости? Это разве не лучше, чем хранить в одной таблице хеши паролей и соль?
Total votes 2: ↑1 and ↓10
Вы опять пытаетесь прятать алгоритм.
Total votes 2: ↑2 and ↓0+2
Но ведь если у злоумышленника будут хеши паролей и соли, то потеряется сама суть соли, разве нет? Или я что-то не так понимаю?
Total votes 3: ↑1 and ↓2-1
Вы не так понимаете. Суть соли не в том, что ее никто не знает. Напротив, соль не следует прятать. Соль нужна для того, чтобы сделать невозможным применение заранее сгенерированных радужных таблиц, а также для того, чтобы максимально усложнить жизнь хакеру, если он решит сбрутить пароли пользователей.

Посмотрите вот этот комментарий: habrahabr.ru/post/145648/#comment_4894759 и дискуссию, возникшую на его основе.
Total votes 1: ↑1 and ↓0+1
Все, теперь понял. Большое спасибо.
This comment wasn’t rated yet0
грубо говоря что бы проверить правильно ли пользователь ввёл пароль нужно дописать к нему соль и взять от суммы хеш. Что бы хеши совпали, нужно что бы совпадал и пароль и соль. Т.е. брать соль наугад каждый раз нельзя.
This comment wasn’t rated yet0
Еще для «торможения» процесса брутфорса или усложнения генерации таблицы рекомендуется прогонять хеш функцию не один раз, а так с тысячу другую. Типа «key stretching».
Total votes 3: ↑1 and ↓2-1
И при хорошей посещаемости убить на это все ресурсы)
This comment wasn’t rated yet0
Насколько, интересно, должна быть хорошей посещаемость, чтобы процедура авторизации вызывалась столь часто?
This comment wasn’t rated yet0
Даже при авторизации в 10 человек в секунду, при тысяче-другой прогонов мы получим — 10-20 тысяч прогонов хеш функции в секунду.

Нужно конечно делать исследования, но думаю, ресурсы это нормально кушает)
This comment wasn’t rated yet0
Хотя, конечно, нужно тестировать.
This comment wasn’t rated yet0
Хотя я был не совсем корректен, так как проверял Си'шным брутером, а не php'ным вызовом. PHP тормознее, не спорю… но вот у товарища выше, MD5 через PHP — 1,7 лямов в секунду. Что так же намного больше чем 20 тысяч. Соответственно, по любому — 20 тыщ в секунду не сильно уронит CPU, тем более на сервере 8)
This comment wasn’t rated yet0
Нет, пример у меня ноут 3 ляма в секунду генерит (SHA1) при этом забирая 14% времени CPU (i7 2,6ггц). Так что 20 тыщ хэшиков в секунду для серванта…
Total votes 1: ↑1 and ↓0+1
На том же ноуте — SHA2(516) — Работает 900 тысяч хэшей в секунду, при тех же 14% CPU.
This comment wasn’t rated yet0
MD5 — 7 лямов в секунду…
This comment wasn’t rated yet0
Кол-во пользователей начинающих сессию в каждый момент времени будет не очень велико. Для юзера задержка, скажем в секунду, при логине не имеет значения, а вот злоумышленник уже не сможет эффективно подбирать пароль.
Total votes 2: ↑2 and ↓0+2
Лучше тогда сразу использовать предназначенные для этого средства, а не мастерите велосипед.
Total votes 1: ↑1 and ↓0+1
Есть какие — нибудь среднестатистические данные о том, сколько по времени займет подбор пароля по его хэшу для разных хэш-функций на среднестатистическом ПК?
This comment wasn’t rated yet0
Есть немного данных для размышления:
В интернетах говорят, что MD5 на GPU можно перебирать со скоростью в 200-500 миллионов хешей в секунду.
Немногим выше говорится о 1.7 млн./сек на ноутбуке и php.
This comment wasn’t rated yet0
У меня MD5 — 7 лямов в секунду, без ГПУ на ноуте.
This comment wasn’t rated yet0
ах да… он на пхп это делал… ) Все, понял-понял…
This comment wasn’t rated yet0
Ага, у меня это был PHP-скрипт, процессор: core i3. Так что о реализациях на компилируемых языках с применением GPU и говорить не приходится — 200-500 млн. вполне реальная цифра.
This comment wasn’t rated yet0
Вот вы написали статью, и людей вводите в заблуждение, подумайте, и исправьте пожалуйста:

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

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

У вас, и у многих, какая-то чудодейственная вера в то, что таблицы ускоряют перебор. Но это не так.
В ряде случаев, это не верно, даже для готовых таблиц или при отсутствии соления.

Радужная таблица — это всего-то способ time-memory trade-off хранения предвычисленных хешей. Для того чтобы, найти в таблице один хеш, нужно выполнить O(chain_length) операций хеширования, и затратить до O(log(tables_size)*chain_length) операций сравнения на поиск значения. chain_length обычно варьируется от 2000 до 10000, размер таблиц — сотни гигабайт соответственно. Поиск, обычно, занимает больше времени, чем хеширование, поэтому позволим себе пренебречь временем хеширования.

Пусть у нас есть 10 миллионов слитых хеш-значений. И таблицы на 100Гб при длине цепочки в 5000 (реальная «емкость» таких таблиц едва ли позволит с достаточной вероятностью содержать комбинации диапазона 1-7 алфавитно-цифровых + спец-символов). Для того чтобы проверить всю коллекцию хешей придется совершить
10 000 000 * O(5000 * log(100Gb)) ~= 10e+13 операций. Плюс считывание с диска. И здесь поиск почти никак не ускорить, ибо 100Gb не влезают в разумный размер памяти.

При брутфорсе же, по тому же диапазону, соответственно
100Gb * 5000 * log(log(10 000 000)) ~= 5e+12 операций. То есть, грубо говоря, в два раза меньше. при этом log(log()) для поиска — не самый оптимальный вариант, есть возможность выполнить поиск в пределах O(1) (например хеш-поиск).

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

А если еще и добавить время на генерацию таблицы… Никто и никогда, в здравом уме, не станет генерировать таблицу для статической соли.

Статические соли плохи тем, и только тем, что никак не мешают массовому взлому. Ну а динамические — соответственно делают его очень невыгодным.
Total votes 4: ↑3 and ↓1+2
Я не ввожу людей в заблуждение. Радужные таблицы хешей для паролей без соли _уже_ сгенерированы, надо только найти это значение. В случае применения соли таблицу необходимо генерировать заново.
Total votes 1: ↑1 and ↓0+1
по поводу «только найти» я уже написал — обычно это дольше чем просто массовый брутфорс. Поэтому и начинать заметку следует с того, что мы пытаемся не «защищаться от таблиц», а усложнить массовый перебор. Таблицы здесь не причем.

«необходимо генерировать заново» — вот именно это
1) не необходимо
2) не разумно
3) и, соответственно, никто так делать не будет.
Total votes 1: ↑1 and ↓0+1
В фразе «сгенерировать свою таблицу хешей со статической солью» есть доля истины. Если соль одна — мы можем брутфорсить по словарю все аккаунты сразу. Клеим соль к слову «123456», получаем 4000 попаданий. Клеим к «qwerty», еще 3000. То есть это упрощает нам перебор.
This comment wasn’t rated yet0
да, мы и будем брутфорсить по словарю все аккаунты сразу.

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

а количество попаданий — вообще не очень существенная величина, ведь набор хешей на перебор разумно сначала почистить от дубликатов. и да, именно с разными солями этих дубликатов и не будет. (но это никак к таблицам не относится, о чем я и писал)
This comment wasn’t rated yet0
Э. Как последовательно? А бинарные деревья зачем?

Если соль уникальна для каждого, то набор неразумно чистить от дубликтов, не будет их там. А если соль одинакова для всех, то вопрос «подходит ли пароль 123 юзеру asdf» " превращается в «продходит ли пароль 123 кому-нибудь из пользователей», а это уже куда более высокие шансы на успех. Затраты — сгенерить один хеш, и найти его в дереве за O(log n)
This comment wasn’t rated yet0
Или даже лучше, раз все данные помещаются в память можно использовать тупо хеш-таблицу, поиск за O(1).
This comment wasn’t rated yet0
у нас есть n — хеш значений, и таблица на m — элементов.
грубо говоря, нужно сделать (n*chain_length) * m операций сравнения, и, конечно бинарный поиск позволяет ускорить правую часть: O(n*chain_length * log(m)) операций, но не левую. Если не очевидно, почему так, посмотрите habrahabr.ru/post/82941/
This comment wasn’t rated yet0
Sign up to leave a comment.

Articles

Show the best of all time

Your account

Sections

Information

Services

Support
© 2006–2024, Habr