Почему соли делают атаки по словарю «невозможными»?
Обновление: обратите внимание, я не спрашиваю, что такое соль, что такое радужная таблица, что такое атака по словарю или что цель соли. Я спрашиваю: если вы знаете, что пользователи вводят в заблуждение, не так ли легко рассчитать их пароль?
Я понимаю процесс и сам внедряю его в некоторые из моих проектов.
s = random salt
storedPassword = sha1(password + s)
В базе данных, которую вы храните :
username | hashed_password | salt
Каждая реализация засолки, которую я видел, добавляет соль либо в конце пароля, либо в начале:
hashed_Password = sha1(s + password )
hashed_Password = sha1(password + s)
Therfore, атака по словарю от хакера, который стоит его соли (ха-ха), просто запускает каждое ключевое слово против сохраненных солей в общих перечисленных выше комбинациях.
Конечно, реализация, описанная выше, просто добавляет еще один шаг для хакера, фактически не решая основная проблема? Какие есть альтернативы, чтобы обойти эту проблему, или я неправильно понимаю проблему?
Единственное, что я могу думать, - это использовать секретный алгоритм смешивания, который объединяет соль и пароль в случайный шаблон или добавляет другого пользователя. поля в процессе хеширования, означающие, что хакеру потребуется доступ к базе данных и коду, чтобы связать их, чтобы атака по словарю оказалась плодотворной. (Обновление, как указано в комментариях, лучше предположить, что хакер имеет доступ ко всей вашей информации, так что, вероятно, это не лучший вариант).
Позвольте мне привести пример того, как я предлагаю взломщику взломать базу данных пользователей со списком паролей и хэшей:
Данные из нашей взломанной базы данных:
RawPassword (not stored) | Hashed | Salt
--------------------------------------------------------
letmein WEFLS... WEFOJFOFO...
Словарь общих паролей:
Common Password
--------------
letmein
12345
...
Для каждой записи пользователя зациклите обычные пароли и хэшируйте их:
for each user in hacked_DB
salt = users_salt
hashed_pw = users_hashed_password
for each common_password
testhash = sha1(common_password + salt)
if testhash = hashed_pw then
//Match! Users password = common_password
//Lets visit the webpage and login now.
end if
next
next
Я надеюсь, что это намного лучше иллюстрирует мою точку зрения.
Учитывая 10 000 общих паролей и 10 000 пользовательских записей, нам нужно будет вычислить 100 000 000 хешей, чтобы обнаружить как можно больше пользовательских паролей. , Это может занять несколько часов, но на самом деле это не проблема.
Обновление теории взлома
Предположим, что мы - поврежденный веб-хост, имеющий доступ к базе данных хэшей и солей SHA1, а также ваш алгоритм для смешайте их. База данных содержит 10 000 записей пользователей.
Этот сайт утверждает, что может вычислять 2 300 000 000 хешей SHA1 в секунду, используя графический процессор. Идеальная задача для нескольких систем. (В IE легко настроить 2 компьютера, на которых выполняется атака с разных концов, что вдвое сократит время атаки).
Учитывая случай рекурсивного хеширования пароля 1000 раз, чтобы сделать эту задачу более дорогой в вычислительном отношении:
(((36 ^ 7) / 1 000 000 000) / 2) * 1000 секунд = 10,8839117 часов
Это представляет максимальную длину из 7 буквенно-цифровых символов при скорости выполнения менее половины скорости по сравнению с указанным значением для одного пользователя .
Рекурсивное хеширование 1000 раз эффективно блокирует одеяло атаки, но целевые атаки на пользовательские данные по-прежнему уязвимы.
10 ответов
Да, вам нужно всего 3 дня для sha1 (соль | пароль). Вот почему в хороших алгоритмах хранения паролей используется хеширование в 1000 итераций: вам понадобится 8 лет.
Проще говоря: без соления каждый потенциальный пароль нужно хэшировать только один раз, чтобы проверить его на соответствие каждому пользователю в любом месте «известной вселенной» (совокупность скомпрометированных баз данных), чей пароль хэшируется с помощью того же алгоритма. При использовании соления, если количество возможных значений соли значительно превышает количество пользователей в «известной вселенной», каждый потенциальный пароль должен быть хеширован отдельно для каждого пользователя, против которого он будет проверяться.
Соли реализованы для предотвращения атак радужных таблиц. Радужная таблица представляет собой список предварительно рассчитанных хэшей, что значительно упрощает преобразование хеша в его фразу. Вы должны понимать, что соление не является эффективным современным средством предотвращения взлома пароля, если у нас нет современного алгоритма хеширования.
Итак, допустим, мы работаем с SHA1, используя недавние эксплойты, обнаруженные с помощью этого алгоритма, и предположим, что у нас есть компьютер, работающий со скоростью 1 000 000 хэшей в секунду, потребуется 5,3 миллиона миллионов миллионов лет, чтобы найти столкновение, так что да, php может работать 300 раз в секунду, большое упс, на самом деле это не имеет значения. Причина, по которой мы солим, заключается в том, что если кто-то удосужился сгенерировать все распространенные словарные фразы (2 ^ 160 человек, добро пожаловать в подвиги эпохи 2007 года).
Вот реальная база данных с двумя пользователями, которых я использую для тестирования и администрирования.
RegistrationTime UserName UserPass
1280185359.365591 briang a50b63e927b3aebfc20cd783e0fc5321b0e5e8b5
1281546174.065087 test 5872548f2abfef8cb729cac14bc979462798d023
На самом деле схема засолки - это ваш ша1(время регистрации + имя пользователя). Давай, скажи мне мой пароль, это настоящие пароли в производстве. Вы даже можете сидеть и составлять список слов в php. Неистовствовать.
Я не сумасшедший, я просто знаю, что это безопасно. Ради интереса, пароль теста test.
sha1 (sha1 (1281546174,065087 + тест) + тест) = 5872548f2abfef8cb729cac14bc979462798d023
Вы должны были бы генерировать всю таблицу радуги perpended с 27662aee8eee1cb5ab4917b09bdba31d091ab732 для только этого пользователя.Это означает, что я действительно могу позволить, чтобы не все мои пароли были скомпрометированы одной радужной таблицей, хакеру нужно сгенерировать всю радужную таблицу для 27662aee8eee1cb5ab4917b09bdba31d091ab732 для проверки и снова f3f7735311217529f2e020468004a2aa5b3dee7f для briang. Вспомните 5,3 миллиона миллионов миллионов лет для всех хэшей. Подумайте о размере хранения только 2 ^ 80 хэшей (это намного больше 20 йоттабайт ), этого не произойдет.
Не путайте соление как средство создания хэша, который вы никогда не сможете расшифровать, это средство предотвращения перевода радужной таблицей всех ваших пользовательских паролей. Это невыполнимо на этом уровне технологий.
Также - еще один важный момент - использование соли, специфичной для ПОЛЬЗОВАТЕЛЯ, предотвращает обнаружение двух пользователей с ОДНИМ паролем - их хэши совпадут. Вот почему часто хэш является хэшем (соль + имя пользователя + пароль)
Если вы попытаетесь сохранить хеш в секрете, злоумышленник также не сможет проверить хэши.
Редактировать - только что заметил, что основная мысль была сделана в комментарии выше.
Идея атаки по словарю состоит в том, что вы берете хэш и находите пароль, из которого этот хэш был рассчитан, без вычисления хеша. Теперь сделайте то же самое с соленым паролем - вы не можете.
Отказ от использования соли делает поиск пароля таким же простым, как поиск в базе данных. Добавление соли заставляет злоумышленника вычислять хэши всех возможных паролей (даже для присоединения словаря это значительно увеличивает время атаки).
Если быть более точным, атака по словарю, то есть атака, при которой перебираются все слова в исчерпывающем списке, становится не «невозможной», а становится непрактичной: каждый бит соли удваивает объем памяти и требуемых вычислений.
Это отличается от атак с предварительно вычисленным словарем, таких как атаки с использованием радужных таблиц, когда не имеет значения, является ли соль секретной или нет.
Пример: с 64-битной солью (т.е. 8 байтов) вам нужно проверить 264 дополнительных комбинаций паролей при атаке по словарю. Со словарем, содержащим 200 000 слов, вам придется сделать
200 000 * 264 = 3,69 * 1024
тестов в худшем случае — вместо 200 000 тестов без соли.
Дополнительным преимуществом использования соли является то, что злоумышленник не может предварительно вычислить хэши паролей из своего словаря. Это просто заняло бы слишком много времени и/или места.
Обновление
В вашем обновлении предполагается, что злоумышленник уже знает соль (или украл ее). Это, конечно, другая ситуация. Тем не менее злоумышленник не может использовать предварительно вычисленную радужную таблицу. Здесь очень важна скорость хэш-функции. Чтобы сделать атаку непрактичной, функция хеширования должна быть медленной. MD5 или SHA не являются здесь хорошими кандидатами, потому что они разработаны, чтобы быть быстрыми, лучшими кандидатами для алгоритмов хеширования являются Blowfish или некоторые его разновидности.
Обновление 2
Хорошее чтение по вопросу защиты хэшей ваших паролей в целом (выходя далеко за рамки исходного вопроса, но все же интересно):
Довольно радужными таблицами: что вам нужно знать о безопасном пароле Схемы
Следствие из статьи: Используйте соленые хэши, созданные с помощью bcrypt (на основе Blowfish) или Eksblowfish, что позволяет использовать настраиваемое время установки для замедления хеширования.
Соль значительно усложняет атаки Rainbow table, поскольку взломать один хэш пароля намного сложнее. Представьте, что у вас есть ужасный пароль, состоящий только из цифры 1. Атака с радужным столом мгновенно взломает его.
Теперь представьте, что каждый пароль в базе данных содержит длинное случайное значение из множества случайных символов. Теперь ваш паршивый пароль «1» хранится в базе данных как хэш 1 плюс набор случайных символов (соль), поэтому в этом примере радужная таблица должна иметь хеш для чего-то вроде: 1.
Итак, если ваша соль является чем-то безопасным и случайным, скажем, ()%ISLDGHASKLU(%#%#, в радужной таблице хакера должна быть запись для 1*()%ISLDGHASKLU(*%#%#). , Теперь использование радужной таблицы даже для этого простого пароля больше нецелесообразно
.Не останавливает атаки по словарю.
Что он делает, так это не дает кому-то, кому удастся получить копию вашего файла паролей, использовать радужную таблицу для выяснения паролей из хэшей.
Однако, в конце концов, это можно сделать методом грубой силы. Ответ на этот вопрос заключается в том, чтобы заставить ваших пользователей не использовать словарные слова в качестве паролей (например, минимальные требования по крайней мере одного числа или специального символа).
Обновление:
Я должен был упомянуть об этом раньше, но некоторые (большинство?) систем паролей используют разные соли для каждого пароля, которые, вероятно, хранятся вместе с самим паролем. Это делает единственную радужную таблицу бесполезной. Вот как работает библиотека UNIX crypt, и современные UNIX-подобные ОС расширили эту библиотеку новыми алгоритмами хеширования.
Я точно знаю, что поддержка SHA-256 и SHA-512 была добавлена в новые версии GNU crypt.
Смысл засолки состоит в том, чтобы предотвратить амортизацию усилий злоумышленника.
Без соли, одна таблица предварительно вычисленных хэш-паролей (например, MD5 всех буквенно-цифровых 5-символьных строк, которые легко найти в Интернете) может быть использована для каждого пользователя в каждой базе данных в мире.
С солью, специфичной для сайта, злоумышленник должен сам вычислить таблицу и затем может использовать ее на всех пользователях сайта.
С солью на пользователя, злоумышленник должен потратить эти усилия на каждого пользователя отдельно.
Конечно, это мало что делает для защиты действительно слабых паролей прямо из словаря, но это защищает достаточно надежные пароли от этой амортизации.
Словарь — это структура, в которой значения индексируются по ключам. В случае атаки с предварительным вычислением по словарю каждый ключ представляет собой хэш, а соответствующее значение — пароль, результатом которого является хэш. Имея в руках предварительно вычисленный словарь, злоумышленник может «мгновенно» найти пароль, который создаст необходимый хэш для входа в систему.
При использовании соли пространство, необходимое для хранения словаря, быстро растет… предварительное вычисление словаря паролей вскоре становится бессмысленным.
Лучшие соли выбираются случайным образом из криптографического генератора случайных чисел. Восемь байтов — это практичный размер, а более 16 байтов не имеют смысла.
Salt делает гораздо больше, чем просто «делает работу злоумышленника более раздражающей». Он устраняет целый класс атак — использование предварительно вычисленных словарей.
Для полной защиты паролей необходим еще один элемент — «усиление ключа». Одного раунда SHA-1 недостаточно: безопасный алгоритм хеширования паролей должен быть очень медленным в вычислительном отношении.
Многие люди используют PBKDF2, функцию получения ключей, которая возвращает результаты хэш-функции тысячи раз. Алгоритм «bcrypt» аналогичен, он использует медленное итеративное получение ключа.
Когда операция хеширования выполняется очень медленно, предварительно вычисленная таблица становится все более и более привлекательной для злоумышленника. Но правильная соль побеждает этот подход.
Комментарии
Ниже приведены комментарии, которые я сделал по этому вопросу.
Без соли злоумышленник не стал бы использовать метод, продемонстрированный в «Обновлении 2».Он просто выполнял поиск в предварительно вычисленной таблице и получал пароль за время O(1) или O(log n) (n — количество возможных паролей). Соль предотвращает это и заставляет его использовать подход O (n), показанный в «Обновлении 2».
После того, как атака сведена к O(n), мы должны учитывать, сколько времени занимает каждая попытка. Усиление ключей может привести к тому, что каждая попытка в цикле будет занимать целую секунду, а это означает, что время, необходимое для проверки 10 000 паролей на 10 000 пользователей, увеличится с 3 дней до 3 лет... скорее всего за это время взломать ноль паролей.
Вы должны учитывать, что атакующий будет использовать самые быстрые инструменты, а не PHP, поэтому тысячи итераций, а не 100, будут хорошим параметром для усиления ключей. Вычисление хэша для одного пароля должно занимать большую долю секунды.
Усиление ключа является частью стандартных алгоритмов получения ключей PBKDF1 и PBKDF2 из PKCS #5, которые создают отличные алгоритмы запутывания пароля («производный ключ» — это «хэш»).
Многие пользователи StackOverflow ссылаются на эту статью, поскольку она была ответом на сообщение Джеффа Этвуда об опасностях радужных таблиц. Это не моя любимая статья, но в ней эти концепции обсуждаются более подробно.
Конечно, вы предполагаете, что у злоумышленника есть все: соль, хэш, имя пользователя. Предположим, злоумышленник является коррумпированным сотрудником хостинговой компании, который сбросил таблицу пользователей на ваш фан-сайт myprettypony.com.Он пытается восстановить эти пароли, потому что собирается развернуться и посмотреть, использовали ли ваши поклонники пони тот же пароль на своих учетных записях citibank.com.
При хорошо продуманной схеме паролей этот парень не сможет восстановить какие-либо пароли.