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

220

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

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

$hash =  md5($salt.$password)

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

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

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

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

Богатый
источник
См. Также stackoverflow.com/questions/213380/…
erickson
И см. Также: stackoverflow.com/questions/1645161/…
Jacco
Кроме того, здесь обновлено - использование хеширования md5 больше не является лучшей практикой. stackoverflow.com/questions/12724935/salt-and-passwords
StuartLC
Спасибо за редактирование. У меня было то же самое сомнение, которое теперь проясняется. Таким образом, смысл «соли» на самом деле состоит в том, чтобы крайне маловероятно, чтобы таблица Rainbow содержала хеш фальсифицированного (соленого) пароля, во-первых. : D
Вайбхав

Ответы:

237

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

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

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

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

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

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

Росс
источник
15
Я не уверен, что я сказал в своем ответе, чтобы подразумевать, что они были?
Росс
2
Эриксон, я думаю, что редактирование сбивало с толку - я не думаю, что большинство людей считают атаку «радужным столом» своего рода атакой по словарю. Дайте мне знать, если что-то конкретное, по вашему мнению, сбивает с толку в моем ответе, и я постараюсь исправить это.
Росс
Я хотел бы дать больше, чем один голос! Особенно по первому абзацу. Вот и подведем итоги ИМХО
Цезарь
5
Я знаю, что это старо, но ваше описание радужных таблиц неверно. Вместо этого вы описываете хеш-таблицы. Радужный стол см. На security.stackexchange.com/questions/379/… . Хеш-таблица имеет 1: 1 сопоставление паролей с хешами (как вы описали), но для радужных таблиц требуется функция сокращения, которая преобразует хеш-код обратно в открытый текст, а затем перефразируется тысячи раз, сохраняя только начальный открытый текст и окончательный хэш. Поиск в вычислительном отношении длиннее хеш-таблиц, но «захватывает» много открытых текстов на хеш.
Марк Фишер
1
В этом ответе пропущен тот факт, что не использование соли (связанной с созданием хэша пароля для конкретного пользователя) также предоставляет дубликаты паролей даже для нескольких таблиц, хранящих эти пароли. Как минимум, вы сможете идентифицировать пароли, повторно используемые человеком, но, что еще хуже, вы также идентифицируете пароли, используемые разными людьми в разных базах данных.
Maarten Bodewes
119

Другие ответы, кажется, не обращаются к вашему недопониманию темы, поэтому здесь идет:

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

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

$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 хешей ... это значительное улучшение.

Сообщество
источник
2
Действительно хороший ответ. Это помогло мне понять вещи намного лучше. +1
wcm
Если у хакера был доступ к соли и как она использовалась в функции хеширования, не могли бы они просто использовать ее для создания таблицы соленых хешей и сравнения этих хешей с радужной таблицей?
Джонни
5
@ Джонни, нет "соли". Суть в том, что соль отличается для каждой записи пароля.
86

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

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

Карл Селеборг
источник
1
+1: Соль может быть частью шестнадцатеричного дайджеста некоторой случайной строки, созданной генератором случайных чисел. Каждый бит случайный.
S.Lott
5
«Радужные таблицы - это одна из форм атаки по словарю, которая снижает скорость, чтобы сэкономить место на диске». - напротив, хорошая радужная таблица может занимать более 1 ГБ для хранения, чтобы сэкономить время на повторное хеширование всех возможных значений.
AviD
2
Согласен - @erickson, я думаю, что ваше редактирование там неверно. Радужный стол требует огромного количества памяти, но позволяет быстро получить сообщение за хешем.
Карл Селеборг
3
Ну, вы оба правы. По сравнению со стандартной атакой по словарю радужные таблицы жертвуют скоростью, чтобы сэкономить место для хранения. С другой стороны, по сравнению с атакой грубой силой, радужные таблицы используют (много) места для увеличения скорости. Сегодня радужные таблицы почти синонимичны словарю ...
Расмус Фабер
... атаки, но вам не нужны радужные таблицы для атак по словарю.
Расмус Фабер
35

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

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

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

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

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

Адам Лисс
источник
То же самое для двух пользователей, которые выбирают другой пароль, и, вероятно, они имеют одинаковый хешированный пароль, сохраненный в БД. (Бесполезно ... я знаю)
Муравей
15

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

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

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

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

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

Чтобы подтвердить пароль:

  • Получить соль пользователя и хэш из базы данных.
  • Добавьте соль к заданному паролю и хешируйте его, используя ту же хеш-функцию.
  • Сравните хеш данного пароля с хешем из базы данных. Если они совпадают, пароль правильный. В противном случае пароль неверен.
MytyMyky
источник
3
Hashcat может использовать почти 17 миллиардов хешей SHA256 в секунду, используя один компьютер. Об этом рассказывает автор связанной статьи под заголовком «Усиление взлома паролей: медленные хэш-функции». scrypt, bcrypt и PBKDF2 являются хорошим выбором и более чем оправдывают дополнительные циклы ЦП на сервере IMHO. Argon2 в настоящее время является современным, но не так проверен в бою, как другие.
кгрифы
12

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

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

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

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

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

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

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

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

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

Клин
источник
3

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

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

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

рекурсивный
источник
1

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

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

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

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

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

rgargente
источник
-2

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

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

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

Даниил
источник