Солим пароли

    Данная заметка призвана пролить свет на использование соли при хешировании пароля. Если посмотреть в комментарии к этому топику habrahabr.ru/post/145642, то возникает подозрение, что некоторые люди неправильно понимают предназначение соли. На примерах постараюсь показать, для чего используется этот механизм. Всех заинтересовавшихся прошу под кат.

    Представим простую авторизацию. От пользователя к нам приходит связка значений логин/пароль, мы получаем хеш пароля и сравниваем данную связку с данными, хранящимися в базе. Для простоты будем использовать MD5 и примеры кода на PHP.
           $password = md5($password);
    

    В данном случае, если у пользователя пароль qwerty, мы получим следующий хеш: d8578edf8458ce06fbc5bb76a58c5ca4. Если злоумышленник получит доступ к нашей базе, для подбора паролей он может воспользоваться уже готовыми сервисами(http://wordd.org/D8578EDF8458CE06FBC5BB76A58C5CA4), в которых уже есть значения, дающие данный хеш, либо сбрутить самому.
    Для защиты от уже готовых таблиц хешей с значениями, можно использовать статическую соль:
           $password = md5($password . "MyUniqueSault");
    

    Сейчас при том же пароле qwerty мы получим совершенно другой хеш bdadb0330124cda0e8499c9cd118f7bd. Готовые таблицы уже не помогут злоумышленнику, ему придется использовать брутфорс. Вот здесь и кроется минус статической соли: злоумышленник сможет сгенерировать свою таблицу хешей со статической солью и получить значения большинства паролей из базы. Для устранения этого минуса используется уникальная соль к каждому хешу:
           $sault = GenerateRandomString();
           $password = md5($password . $sault);
    

    Т.е. теперь помимо логина/хеша пароля в базе необходимо будет хранить значение сгенерированной соли для каждого пользователя. Разберем пример: у нас два пользователя: user1 и user2. Оба используют пароль qwerty. Но у первого была сгенерирована соль zxcv а у второго asdf. В итоге у пользователей при одинаковом пароле будут различные хеши: 1d8f3272b013387bbebcbedb4758586d и a192862aa3bf46dffb57b12bdcc4c199.Что это дает: теперь нельзя будет сгененерировать одну таблицу хешей, для нахождения значения хеша с динамической солью придется генерировать заново. Все это направлено на увеличение времени подбора значений в случае «слива» базы, при использовании «хороших» алгоритмов хеширования, на подбор хотя бы пары паролей уже может уйти значительное количество времени. Важно понимать, что генерируемая соль защищает не одного единственного пользователя, а всех вместе от массового брута. На этом все, хочу напомнить что используйте криптостойкие алгоритмы хеширования SHA1, SHA512. Используемый выше MD5 к использованию не желателен, т.к. признан устаревшим.


    Хорошо резюмировал Kolonist в своем комментарии habrahabr.ru/post/145648/#comment_4894759 ( за что ему отдельное спасибо и плюс):
    Еще раз.

    1. Нет соли — используем уже готовые радужные таблицы.
    2. Есть одна на всех соль — генерируем одну радужную таблицу и «ломаем» по ней всех пользователей.
    3. Есть отдельная соль для каждого пользователя — отдельно брутфорсим каждого пользователя.
    Поделиться публикацией

    Комментарии 87

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

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

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

                    0
                    Если база не утекла, то можно и в открытом виде держать.
                    –3
                    эм… немного не понял, ну будет у вас в таблице еще одно боле с солью (обычное нехешированое поле) и в чем тогда выигрыш? т.е. слив базу злоумышленник получает связки пароль + соль для пароля, остается только разгадать алгоритм как соль участвует в получении пароля + сам пароль, разве не так?
                      +1
                      Если соль статическая (одинаковая для всех юзеров), то у всех паролей qwerty в базе будет хэш bdadb0330124cda0e8499c9cd118f7bd, подобрав пароль для одного пользователя мы получим пароли остальных с таким же хэшем. А будет соль у каждого своя — нужно будет подбирать у каждого.
                        +11
                        Еще раз.

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

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

                                Для вас радужные таблицы это что-ли какая-то магия? Почитайте хотя-бы вот этот раздел на вики. Я посмотрю как вы будете составлять таблицу для строк у которых длина больше 20 символов в которые входит длинное случайное сочетание символов и особенно мне интересно откуда вы достанете столько памяти.
                                  0
                                  Нет не магия я про это и говорю, что особого смысла в этом и нет. Там ниже описали как составлять. habrahabr.ru/post/145648/#comment_4894829
                                    0
                                    В чём нет смысла? Процитирую вас:
                                    >поэтому как-то совсем не выигрышно, ну будет 2 польз. с разной солью, но одинаковыми паролями и что? зная алгоритм как соль применяется в пароле тут они абсолютно ничем не защищены.
                                    В среднем пользователи будут защищены лучше, т.к. что бы взломать эти два пароля злоумышленнику придётся брутфорсить в два раза дольше, а значит стоимость взлома одного пароля станет больше, что равнозначно лучшей защищённости паролей в данной схеме.
                                    Упреждая уже приевшуюся риторику: когда говорят о схемах защиты и соления подразумевается что защищается вся база целиком, а не какой-то отдельный пользователь. Для защиты одного пользователя соли мало спасают, в т.ч. и ваши «динамически генерируемые», единственный путь здесь это использовать медленные хеш-функции.

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

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

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

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

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

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

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

                                      А вот ситуацию, при которой с сайта крадут базу данных, чтобы найти пароль какого-то одного пользователя, мне как-то сложно представить — цель не оправдывает средства.
                        0
                        А нельзя использовать в качестве соли уже существующие данные? Например, логин
                          0
                          Можно, используют. Но лучше всего случайные числа. Так даже удобнее, хранятся с хешем одной строкой.
                        +1
                        Чаще используется «засаливание» не самого пароля, а хэша от него:

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

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

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

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

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

                                      SHA* не подходят для хеширования паролей. Автор заметки плохо осведомлен. Годные алгоритмы — это PBKDF2, bcrypt и scrypt.
                                        0
                                        > Минус не в этом.
                                        Нет, в этом. С одной статической солью мы можем сгенерить для данной базы свою таблицу.
                                        Насчет SHA поясните, почему нет?
                                          +2
                                          Слишком быстрый.
                                            +3
                                            Да, согласен, и то и другое.

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

                                                  Посмотрите вот этот комментарий: habrahabr.ru/post/145648/#comment_4894759 и дискуссию, возникшую на его основе.
                                                    0
                                                    Все, теперь понял. Большое спасибо.
                                                0
                                                грубо говоря что бы проверить правильно ли пользователь ввёл пароль нужно дописать к нему соль и взять от суммы хеш. Что бы хеши совпали, нужно что бы совпадал и пароль и соль. Т.е. брать соль наугад каждый раз нельзя.
                                                –1
                                                Еще для «торможения» процесса брутфорса или усложнения генерации таблицы рекомендуется прогонять хеш функцию не один раз, а так с тысячу другую. Типа «key stretching».
                                                  0
                                                  И при хорошей посещаемости убить на это все ресурсы)
                                                    0
                                                    Насколько, интересно, должна быть хорошей посещаемость, чтобы процедура авторизации вызывалась столь часто?
                                                      0
                                                      Даже при авторизации в 10 человек в секунду, при тысяче-другой прогонов мы получим — 10-20 тысяч прогонов хеш функции в секунду.

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

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

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

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

                                                                    Радужная таблица — это всего-то способ 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) (например хеш-поиск).

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

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

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

                                                                        «необходимо генерировать заново» — вот именно это
                                                                        1) не необходимо
                                                                        2) не разумно
                                                                        3) и, соответственно, никто так делать не будет.
                                                                        0
                                                                        В фразе «сгенерировать свою таблицу хешей со статической солью» есть доля истины. Если соль одна — мы можем брутфорсить по словарю все аккаунты сразу. Клеим соль к слову «123456», получаем 4000 попаданий. Клеим к «qwerty», еще 3000. То есть это упрощает нам перебор.
                                                                          0
                                                                          да, мы и будем брутфорсить по словарю все аккаунты сразу.

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

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

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

                                                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                        Самое читаемое