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

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

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

$hash = md5($salt.$password) 

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

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

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

EDIT : Спасибо за помощь. Подводя итог тому, что я понимаю, соль делает хешированный пароль более сложным, что делает его гораздо менее вероятным для существования в предварительно вычисленном радужном столе. То, что я неправильно понял раньше, было то, что я принимал радужный стол, существовавший для ВСЕХ хешей.

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

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

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

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

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

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

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

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

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

$hash = md5($salt.$password)

[…]

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

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

Безопасность hashа

Теперь кто-то с радужным столом может перевернуть hash и придумать вход «foobar».

[…]

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

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

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

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

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

Но скажем $salt=foo

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

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

Атака

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

Атака радужного стола всегда нужна /etc/passwd (или какая-либо firebase database паролей), или как бы вы сравнили hashи в таблице радуги с hashами настоящих паролей?

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

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

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

Еще один большой вопрос, с множеством очень вдумчивых ответов – +1 к SO!

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

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

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

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

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

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

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

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

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

Проверка пароля:

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

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

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

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

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

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

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

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

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

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

Еще одна цель, как упоминает Carl S, – сделать грубый заставлять список хешей дороже. (дать им все разные соли)

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

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

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

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

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

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

Я предполагаю, что вы используете PHP — md5 () и переменные, предшествующие переменным, – тогда вы можете попробовать посмотреть эту статью Shadow Password HOWTO. В частности, 11-й абзац.

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

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

Давайте будем гением компьютера.