Почему соли делают словарные атаки "невозможными"?
Обновление: обратите внимание, я не спрашиваю, что такое соль, что такое радужный стол, что такое атака по словарю или какова цель соли. Я спрашиваю: если вы знаете пользователей соль и хэш, не так ли просто вычислить их пароль?
Я понимаю этот процесс и сам внедряю его в некоторых своих проектах.
s = random salt
storedPassword = sha1(password + s)
В базе данных вы храните:
username | hashed_password | salt
Каждая реализация соления, которую я видел, добавляет соль либо в конце пароля, либо в начале:
hashed_Password = sha1(s + password )
hashed_Password = sha1(password + s)
Поэтому атака по словарю от хакера, который стоит его соли (ха-ха), просто запускает каждое ключевое слово против сохраненных солей в общих комбинациях, перечисленных выше.
Конечно, реализация, описанная выше, просто добавляет еще один шаг для хакера, фактически не решая основную проблему? Какие есть альтернативы, чтобы обойти эту проблему, или я неправильно понимаю проблему?
Единственное, что я могу подумать, это иметь секретный алгоритм смешивания, который объединяет соль и пароль в случайный шаблон или добавляет другие пользовательские поля в процесс хеширования, что означает, что хакер должен иметь доступ к базе данных и коду для кружева их словарная атака оказалась плодотворной. (Обновление, как указано в комментариях, лучше предположить, что хакер имеет доступ ко всей вашей информации, так что, вероятно, это не лучший вариант).
Позвольте мне привести пример того, как я предлагаю взломщику взломать базу данных пользователей со списком паролей и хэшей:
Данные из нашей взломанной базы данных:
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
Я надеюсь, что это намного лучше иллюстрирует мою точку зрения.
Учитывая 10000 общих паролей и 10000 пользовательских записей, нам нужно будет вычислить 100 000 000 хешей, чтобы обнаружить как можно больше пользовательских паролей. Это может занять несколько часов, но это не проблема.
Обновление теории взлома
Предположим, что мы испорченный веб-хост, у которого есть доступ к базе данных хэшей и солей SHA1, а также ваш алгоритм их смешивания. База данных насчитывает 10000 записей пользователей.
Этот сайт утверждает, что может вычислять 2 300 000 000 хэшей SHA1 в секунду, используя графический процессор. (В реальной ситуации ситуация, вероятно, будет медленнее, но пока мы будем использовать эту цифру).
(((95 ^ 4) / 2300000000) / 2) * 10000 = 177 секунд
Учитывая полный диапазон из 95 печатных символов ASCII, с максимальной длиной 4 символа, деленный на скорость вычисления (переменную), деленную на 2 (при условии, что среднее время на обнаружение пароля в среднем потребует 50% перестановок) для 10000 пользователям потребуется 177 секунд, чтобы определить пароли всех пользователей, длина которых <= 4.
Давайте немного подстроим его под реализм.
(((36 ^ 7) / 1000000000) / 2) * 10000 = 2 дня
При условии отсутствия учета регистра, с длиной пароля <= 7, только буквенно-цифровыми символами, для 10000 пользовательских записей потребуется 4 дня, и я сократил скорость алгоритма вдвое, чтобы отразить накладные расходы и неидеальные обстоятельства.
Важно признать, что это линейная атака методом грубой силы, все расчеты не зависят друг от друга, поэтому это идеальная задача для нескольких систем. (IE легко настроить на 2 компьютера, на которых выполняется атака с разных концов, что вдвое меньше времени).
Учитывая случай рекурсивного хеширования пароля 1000 раз, чтобы сделать эту задачу более дорогой в вычислительном отношении:
(((36 ^ 7) / 1 000 000 000) / 2) * 1000 секунд = 10,8839117 часов
Это представляет собой максимальную длину 7 буквенно-цифровых символов при скорости выполнения менее чем вдвое по сравнению с указанным значением для одного пользователя.
Рекурсивное хеширование 1000 раз эффективно блокирует полную атаку, но целевые атаки на пользовательские данные по-прежнему уязвимы.
11 ответов
Да, вам нужно всего 3 дня для sha1(соль | пароль). Вот почему хорошие алгоритмы хранения паролей используют 1000-итерационное хеширование: вам понадобится 8 лет.
Это не останавливает атаки по словарю.
Что он делает, так это останавливает того, кому удается получить копию вашего файла паролей, используя радужную таблицу, чтобы выяснить, какие пароли есть из хешей.
В конце концов, это может быть грубой силой. Ответ на этот вопрос заключается в том, чтобы заставить ваших пользователей не использовать словарные слова в качестве паролей (например, минимальные требования, по крайней мере, одного числа или специального символа).
Обновление:
Я должен был упомянуть об этом раньше, но некоторые (большинство?) Парольные системы используют разные соли для каждого пароля, вероятно, хранящиеся вместе с самим паролем. Это делает один радужный стол бесполезным. Так работает библиотека шифрования UNIX, и современные UNIX-подобные ОС расширили эту библиотеку новыми алгоритмами хеширования.
Я точно знаю, что поддержка SHA-256 и SHA-512 была добавлена в более новые версии криптографии GNU.
Точнее говоря, атака по словарю, то есть атака, при которой пробуются все слова в исчерпывающем списке, становится не "невозможной", а непрактичной: каждый бит соли удваивает объем памяти и требуемые вычисления.
Это отличается от заранее вычисленных словарных атак, таких как атаки с использованием радужных таблиц, где не имеет значения, является ли соль секретной или нет.
Пример: с 64-битной солью (т.е. 8 байтами) вам необходимо проверить 264 дополнительных комбинации паролей в атаке по словарю. Со словарем, содержащим 200 000 слов, вам придется сделать
200 000 * 264 = 3,69 * 1024
тесты в худшем случае - вместо 200 000 тестов без соли.
Дополнительным преимуществом использования соли является то, что злоумышленник не может предварительно вычислить хэши паролей из своего словаря. Это просто заняло бы слишком много времени и / или пространства.
Обновить
Ваше обновление предполагает, что злоумышленник уже знает соль (или украл ее). Это конечно другая ситуация. Тем не менее, злоумышленник не может использовать предварительно вычисленный радужный стол. Здесь важна скорость хеширования. Чтобы атака была непрактичной, функция хеширования должна быть медленной. MD5 или SHA не являются хорошими кандидатами здесь, потому что они разработаны, чтобы быть быстрыми, более подходящими кандидатами для алгоритмов хеширования являются Blowfish или некоторые его варианты.
Обновление 2
Хорошее прочтение по вопросу защиты ваших хэшей паролей в целом (выходит далеко за рамки первоначального вопроса, но все еще интересно):
Достаточно таблиц Rainbow: что нужно знать о безопасных схемах паролей
Следствие из статьи: Используйте соленые хэши, созданные с помощью bcrypt (на основе Blowfish) или Eksblowfish, что позволяет вам использовать настраиваемое время установки, чтобы замедлять хеширование.
Словарь - это структура, в которой значения индексируются по ключам. В случае атаки по предварительно вычисленному словарю каждый ключ является хешем, а соответствующее значение - паролем, который приводит к хешу. Имея в руках предварительно вычисленный словарь, злоумышленник может "мгновенно" найти пароль, который выдаст необходимый хэш для входа в систему.
С солью пространство, необходимое для хранения словаря, быстро растет... настолько быстро, что попытка предварительного вычисления словаря паролей вскоре становится бессмысленной.
Лучшие соли выбираются случайным образом из криптографического генератора случайных чисел. Восемь байтов - это практический размер, а более 16 байтов не имеют смысла.
Соль делает гораздо больше, чем просто "делает работу злоумышленника более раздражающей". Это исключает целый класс атак - использование предварительно вычисленных словарей.
Еще один элемент необходим для полной защиты паролей, и это "усиление ключа". Один раунд SHA-1 недостаточно хорош: алгоритм надежного хеширования пароля должен быть очень медленным в вычислительном отношении.
Многие люди используют PBKDF2, ключевую функцию деривации, которая возвращает результаты в хэш-функцию тысячи раз. Алгоритм "bcrypt" аналогичен, используя медленный итеративный вывод ключа.
Когда операция хеширования выполняется очень медленно, предварительно вычисленная таблица становится все более желательной для злоумышленника. Но правильная соль побеждает этот подход.
Комментарии
Ниже приведены комментарии, которые я сделал по этому вопросу.
Без соли злоумышленник не использовал бы метод, показанный в "Обновлении 2". Он просто сделал бы поиск в предварительно вычисленной таблице и получил бы пароль за O(1) или O(log n) времени (n - число паролей-кандидатов). Соль - то, что предотвращает это и заставляет его использовать подход O(n), показанный в "Обновлении 2".
После того, как мы свелись к атаке O(n), мы должны рассмотреть, сколько времени занимает каждая попытка. Усиление ключа может привести к тому, что каждая попытка в цикле займет целую секунду, а это означает, что время, необходимое для тестирования паролей 10k на пользователях 10k, будет увеличиваться с 3 дней до 3 лет... и только с паролями 10k вы, вероятно, достигнете нуля пароли в то время.
Вы должны учитывать, что злоумышленник собирается использовать самые быстрые инструменты, которые он может, а не PHP, поэтому тысячи итераций, а не 100, были бы хорошим параметром для усиления ключа. Требуется большая доля секунды, чтобы вычислить хэш для одного пароля.
Усиление ключей является частью стандартных алгоритмов получения ключей PBKDF1 и PBKDF2 из PKCS #5, которые создают отличные алгоритмы обфускации паролей ("производный ключ" - это "хеш").
Многие пользователи Stackru ссылаются на эту статью, потому что это был ответ на пост Джеффа Этвуда об опасностях радужных таблиц. Это не моя любимая статья, но она обсуждает эти концепции более подробно.
Конечно, вы предполагаете, что у злоумышленника есть все: соль, хэш, имя пользователя. Предположим, злоумышленник - сотрудник коррумпированной хостинговой компании, который сбросил таблицу пользователей на вашем фан-сайте myprettypony.com. Он пытается восстановить эти пароли, потому что собирается развернуться и посмотреть, не использовали ли ваши поклонники пони один и тот же пароль в своих учетных записях на citibank.com.
С хорошо разработанной схемой паролей для этого парня будет невозможно восстановить любые пароли.
Точка засолки состоит в том, чтобы предотвратить амортизацию усилий атакующего.
Без соли, одна таблица предварительно вычисленных записей хеш-пароля (например, MD5 из всех буквенно-цифровых 5-символьных строк, легко найти в Интернете) может использоваться для каждого пользователя в каждой базе данных в мире.
Используя специфичную для сайта соль, злоумышленник должен сам вычислить таблицу и затем использовать ее для всех пользователей сайта.
С солью для каждого пользователя, злоумышленник должен затратить эти усилия для каждого пользователя отдельно.
Конечно, это не очень помогает защитить действительно слабые пароли прямо из словаря, но защищает достаточно надежные пароли от этой амортизации.
Кроме того - еще один важный момент - использование соли, специфичной для пользователя, предотвращает обнаружение двух пользователей с тем же паролем - их хэши будут совпадать. Вот почему много раз хэш хэш (соль + имя пользователя + пароль)
Если вы попытаетесь сохранить хеш в секрете, злоумышленник также не сможет проверить хеш.
Редактировать - только что заметил, что главное было сделано в комментарии выше.
Соли реализованы, чтобы предотвратить атаки радужного стола. Радужный стол - это список предварительно рассчитанных хэшей, что делает перевод хеша в его фразу намного проще. Вы должны понимать, что засолка не эффективна как современная профилактика взлома пароля, если у нас нет современного алгоритма хеширования.
Допустим, мы работаем с SHA1, воспользовавшись преимуществами недавних эксплойтов, обнаруженных с помощью этого алгоритма, и предположим, что у нас есть компьютер, работающий с 1 000 000 хешей в секунду, для обнаружения коллизии потребуется 5,3 млн. Миллионов лет, так что да, php может работать 300 в секунду, большой woop, на самом деле не имеет значения. Причина, по которой мы солим, заключается в том, что если кто-то потрудился сгенерировать все общие словарные фразы (2^160 человек, добро пожаловать в подвиги эпохи 2007 года)
Итак, вот фактическая база данных с двумя пользователями, которых я использую для тестирования и администрирования.
RegistrationTime UserName UserPass
1280185359.365591 briang a50b63e927b3aebfc20cd783e0fc5321b0e5e8b5
1281546174.065087 test 5872548f2abfef8cb729cac14bc979462798d023
На самом деле схема засолки - это ваш sha1(время регистрации + имя пользователя). Давай, скажи мне мой пароль, это настоящие пароли в производстве. Вы можете даже сидеть там и хэшировать список слов в php. Неистовствовать.
Я не сумасшедший, я просто знаю, что это безопасно. Ради интереса, пароль для теста test, sha1(sha1(1281546174.065087 + test) + test) = 5872548f2abfef8cb729cac14bc979462798d023
Вам нужно будет создать весь радужный стол с 27662aee8eee1cb5ab4917b09bdba31d091ab732 только для этого пользователя. Это означает, что я действительно могу позволить, чтобы все мои пароли не были скомпрометированы одной радужной таблицей, хакеру нужно сгенерировать целую радужную таблицу для теста 27662aee8eee1cb5ab4917b09bdba31d091ab732 и снова f3f7735311217529f2e020468004a2aa5b3rief для. Вспомните 5,3 миллиона миллионов лет для всех хэшей. Подумайте о размерах хранения только 2^80 хешей (это более 20 йотбайт), этого не произойдет.
Не путайте засолку как средство создания хеш-кода, которое вы никогда не сможете декодировать, это средство предотвращения преобразования радужным столом всех ваших пользовательских паролей. На этом уровне технологий это невозможно.
Идея атаки по словарю состоит в том, что вы берете хеш и находите пароль, из которого был вычислен этот хеш, без вычисления хеша. Теперь сделайте то же самое с посоленным паролем - вы не можете.
Отсутствие соли делает поиск паролей таким же простым, как поиск в базе данных. При добавлении солевой команды злоумышленник выполняет вычисление хеша всех возможных паролей (даже для словарного вложения это значительно увеличивает время атаки).
Проще говоря, засолка не предотвращает хэш-атаки (брутфорс или словарь), а только усложняет; злоумышленнику нужно будет либо найти алгоритм посола (который при правильной реализации будет использовать больше итераций), либо использовать алгоритм, который, если не очень прост, практически невозможен. Соление также почти полностью исключает возможность поиска по радужным таблицам...
Проще говоря: без засолки каждый кандидатный пароль необходимо хэшировать только один раз, чтобы проверить его для каждого пользователя в любом месте "известного юниверса" (набора скомпрометированных баз данных), чей пароль хэшируется по тому же алгоритму. При использовании солей, если число возможных значений солей существенно превышает количество пользователей в "известном юниверсе", каждый кандидатный пароль должен хэшироваться отдельно для каждого пользователя, против которого он будет проверен.
Соль значительно усложняет атаку с помощью таблиц Rainbow, поскольку усложняет взлом одного пароля. Представьте, что у вас есть ужасный пароль только из числа 1. Атака с радужного стола немедленно взломает это.
Теперь представьте, что каждый пароль в БД содержит длинную случайную величину из множества случайных символов. Теперь ваш паршивый пароль "1" хранится в БД в виде хэша 1 плюс несколько случайных символов (соль), поэтому в этом примере в радужной таблице должен быть хэш для чего-то вроде: 1.
Поэтому, если предположить, что ваша соль является чем-то безопасным и случайным, скажем, ()% ISLDGHASKLU (% #% #), в радужной таблице хакера должна быть запись для 1*()%ISLDGHASKLU(*%#%#. Теперь используется радужная таблица даже этот простой пароль уже не практичен.