Как соль пароля помогает против атаки радужной таблицы?

Question

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

Я видел много уроков, предлагающих использовать соль следующим образом:

$hash =  md5($salt.$password)

Причина в том, что хеш теперь отображается не на исходный пароль, а на комбинацию пароля и соли. Но скажи $salt=foo и $password=bar и $hash=3858f62230ac3c915f300c664312c63f. Теперь кто-то с радужным столом может поменять хеш и ввести «foobar». Затем они могут попробовать все комбинации паролей (f, fo, foo, ... oobar, obar, bar, ar, ar). Для получения пароля может потребоваться еще несколько миллисекунд, но не более того.

Другое использование, которое я видел, находится в моей системе Linux. В / etc / shadow хешированные пароли на самом деле хранятся с солью. Например, соль "foo" и пароль "bar" должны хэшировать это: $1$foo$te5SBM.7C25fFDu6bIRbX1. Если хакер каким-то образом смог достать этот файл, я не вижу, для чего служит соль, поскольку известно, что обратный хеш te5SBM.7C25fFDu6bIRbX содержит "foo".

Спасибо за любой свет, который может пролить на это кто-либо.

РЕДАКТИРОВАТЬ : Спасибо за помощь. Подводя итог, что я понимаю, соль делает хешированный пароль более сложным, что значительно снижает вероятность его существования в заранее вычисленной радужной таблице. Раньше я неправильно понимал, что я предполагаю, что для ВСЕХ хэшей существует радужный стол.

Answer 1

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

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

Чтобы понять первый, представьте себе один файл паролей, который содержит сотни имен пользователей и паролей. Без соли я мог бы вычислить «md5 (try [0])», а затем просканировать файл, чтобы увидеть, где-нибудь появляется этот хэш. Если соли присутствуют, тогда мне нужно вычислить «md5 (salt [a]. Пытаюсь [0])», сравнить с записью A, затем «md5 (salt [b]. Пытаюсь [0])», сравнить с записью B и т. д. Теперь у меня в n раз больше работы, где n - количество имен пользователей и паролей, содержащихся в файле.

Чтобы понять второй, вы должны понять, что такое радужный стол. Радужная таблица - это большой список предварительно вычисленных хэшей для часто используемых паролей. Представьте себе снова файл паролей без солей. Все, что мне нужно сделать, - это просмотреть каждую строку файла, вытащить хешированный пароль и посмотреть его в радужной таблице. Мне никогда не нужно вычислять один хэш. Если поиск выполняется значительно быстрее, чем хеш-функция (что, вероятно, и есть), это значительно ускорит взлом файла.

Но если файл паролей солен, тогда радужная таблица должна содержать предварительно хэшированный "salt. Пароль". Если соль достаточно случайная, это маловероятно. Возможно, в моем списке часто используемых предварительно хешированных паролей (радужная таблица) будут такие слова, как «привет», «foobar» и «qwerty», но я не собираюсь иметь такие вещи, как «jX95psDZhello» "LPgB0sdgxfoobar" или "dZVUABJtqwerty" предварительно вычислены. Это сделало бы радужный стол слишком большим.

Таким образом, соль сводит атакующего обратно к одному вычислению на строку на попытку, которое, в сочетании с достаточно длинным, достаточно случайным паролем, является (вообще говоря) не взломанным.

Answer 2

Другие ответы, по-видимому, не учитывают ваше недопонимание темы, поэтому здесь идет речь:

Два различных варианта использования соли

Я видел много уроков, предлагающих использовать соль следующим образом:

$hash = md5($salt.$password)

[...]

Другое использование, которое я видел, находится в моей системе Linux. В / etc / shadow хешированные пароли хранятся вместе с солью.

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

Безопасность хеша

Теперь кто-то с радужным столом мог бы поменять хэш и выдать ввод "foobar".

[...]

, поскольку известно, что обратный хеш te5SBM.7C25fFDu6bIRbX содержит "foo".

Невозможно обратить хеш как таковой (по крайней мере, в теории). Хеш "foo" и хеш "saltfoo" не имеют ничего общего. Изменение хотя бы одного бита на входе криптографической хеш-функции должно полностью изменить вывод.

Это означает, что вы не можете создать радужную таблицу с общими паролями, а затем «обновить» ее солью. С самого начала нужно принимать во внимание соль.

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

Качество соли

Но скажи $salt=foo

"foo" было бы крайне плохим выбором соли. Обычно вы используете случайное значение, закодированное в ASCII.

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

Атака

Если хакер каким-то образом смог достать этот файл, я не вижу, для чего служит соль,

Атака радужной таблицы всегда требуется /etc/passwd (или какая база данных паролей используется), или как бы вы сравнили хеши в радужной таблице с хешами реальных паролей?

Что касается цели: допустим, злоумышленник хочет создать радужную таблицу для 100 000 часто используемых английских слов и типичных паролей (подумайте «секретно»). Без соли ей пришлось бы предварительно вычислить 100 000 хешей. Даже с традиционной солью UNIX из 2 символов (каждый из 64 вариантов: [a–zA–Z0–9./]) ей придется вычислять и хранить 4 096 000 000 хешей ... настоящее улучшение.

Answer 3

Идея с солью состоит в том, чтобы с помощью грубой силы угадать ее было намного сложнее, чем обычный символьный пароль. Радужные таблицы часто строятся с учетом специального набора символов и не всегда включают все возможные комбинации (хотя они могут).

Таким образом, хорошим значением соли будет случайное 128-битное или более длинное целое число. Это то, что делает атаки на радужных столах неудачными. Используя разные значения соли для каждого сохраненного пароля, вы также гарантируете, что радужная таблица, построенная для одного конкретного значения соли (как в случае популярной системы с одним значением соли), не даст вам доступ ко всем пароли сразу.

Answer 4

Еще один замечательный вопрос со многими очень продуманными ответами - +1 к SO!

Одна небольшая вещь, которую я не упоминал в явном виде, заключается в том, что, добавляя случайную соль к каждому паролю, вы фактически гарантируете, что два пользователя , которые случайно выбрали один и тот же пароль, будут производить разные хэши. 1004 *

Почему это важно?

Представьте себе базу паролей в крупной компании по разработке программного обеспечения на северо-западе США. Предположим, он содержит 30 000 записей, из которых 500 имеют пароль bluescreen . Предположим далее, что хакеру удается получить этот пароль, скажем, прочитав его по электронной почте от пользователя в ИТ-отдел. Если пароли несоленые, хакер может найти хеш-значение в базе данных, а затем просто сопоставить его с шаблоном, чтобы получить доступ к другим 499 учетным записям.

Соляция паролей гарантирует, что каждая из 500 учетных записей имеет уникальный (соль + пароль), генерируя разные хеш-коды для каждой из них и, таким образом, сводя взлом к ​​одной учетной записи. И давайте будем надеяться, что, по всей вероятности, любой пользователь, достаточно наивный, чтобы написать открытый текст в сообщении электронной почты, не имеет доступа к недокументированному API для следующей ОС.

Answer 5

Я искал хороший способ применения солей и нашел эту замечательную статью с примером кода:

http://crackstation.net/hashing-security.htm

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

Чтобы сохранить пароль:

• Создание длинной случайной соли с использованием CSPRNG.
• Добавьте соль к паролю и добавьте стандартное значение криптографическая хеш-функция, такая как SHA256.
• Сохраните соль и хеш в записи базы данных пользователя.

Для подтверждения пароля:

• Получить соль пользователя и хэш из базы данных.
• Добавьте соль к заданному паролю и хешируйте его, используя ту же хеш-функцию.
• Сравните хеш данного пароля с хешем из базы данных. Если они совпадают, пароль правильный. В противном случае пароль неверен.

Answer 6

Причина, по которой соль может провалить атаку по радужному столу, состоит в том, что для n-битов соли радужный стол должен быть в 2 ^ n раз больше размера стола без соли.

Ваш пример использования 'foo' в качестве соли может увеличить радужный стол в 16 миллионов раз.

Учитывая пример Карла о 128-битной соли, это делает таблицу в 2 ^ 128 раз больше - теперь она велика - или, другими словами, сколько времени до того, как у кого-то будет такое портативное хранилище?

Answer 7

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

Такие атаки неэффективны в случае, когда пароли содержат намного больше символов и не соответствуют распространенным форматам на основе слов. Пользователь с надежным паролем для начала не будет уязвим для этого стиля атаки. К сожалению, многие люди не выбирают хорошие пароли. Но есть компромисс: вы можете улучшить пароль пользователя, добавив к нему случайный мусор. Так что теперь вместо «hunter2» их пароль может стать «hunter2908! Fld2R75 {R7 /; 508PEzoz ^ U430», который является гораздо более надежным паролем. Однако, поскольку теперь вам нужно хранить этот дополнительный компонент пароля, это снижает эффективность более надежного составного пароля. Как выясняется, такая схема все еще дает чистую выгоду, поскольку теперь каждый пароль, даже слабый, больше не уязвим к одной и той же предварительно вычисленной хэш-таблице / радуге. Вместо этого каждая запись хеша пароля уязвима только для уникальной хеш-таблицы.

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

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

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

Answer 8

Одна из целей засолки - победить предварительно вычисленные хеш-таблицы. Если у кого-то есть список миллионов предварительно вычисленных хэшей, он не сможет найти в своей таблице $ 1 $ foo $ te5SBM.7C25fFDu6bIRbX1, даже если он знает хэш и соль. Им все равно придется переборщить.

Другая цель, как упоминает Карл С., - сделать грубое форсирование списка хэшей более дорогим. (дайте им все разные соли)

Обе эти цели все еще выполнены, даже если соли являются публичными.

Answer 9

Насколько я знаю, соль предназначена для усложнения атак по словарю.

Это известный факт, что многие люди будут использовать общие слова для паролей вместо, казалось бы, случайных строк.

Таким образом, хакер может использовать это в своих интересах вместо того, чтобы использовать только грубую силу. Он не будет искать пароли, такие как aaa, aab, aac ..., но вместо этого будет использовать слова и общие пароли (например, имена властелинов колец!

Так что, если мой пароль - Леголас, хакер мог бы попробовать это и угадать это с "несколькими" попытками. Однако если мы солим пароль и он становится fooLegolas, хэш будет другим, поэтому атака по словарю будет неудачной.

Надеюсь, это поможет!

Answer 10

Я предполагаю, что вы используете PHP --- функцию md5 () и переменные $ preced --- тогда вы можете попробовать просмотреть эту статью Shadow Password HOWTO Специально для 11-го абзаца.

Кроме того, вы боитесь использовать алгоритмы дайджеста сообщений, вы можете попробовать реальные алгоритмы шифрования, такие как те, которые предусмотрены модулем mcrypt , или более надежные алгоритмы дайджеста сообщений, такие как те, модуль mhash (sha1, sha256 и другие).

Я считаю, что необходим более сильный алгоритм дайджеста сообщений. Известно, что у MD5 и SHA1 есть проблемы со столкновениями.