Солим пароли
Данная заметка призвана пролить свет на использование соли при хешировании пароля. Если посмотреть в комментарии к этому топику habrahabr.ru/post/145642, то возникает подозрение, что некоторые люди неправильно понимают предназначение соли. На примерах постараюсь показать, для чего используется этот механизм. Всех заинтересовавшихся прошу под кат.
Представим простую авторизацию. От пользователя к нам приходит связка значений логин/пароль, мы получаем хеш пароля и сравниваем данную связку с данными, хранящимися в базе. Для простоты будем использовать MD5 и примеры кода на PHP.
$password = md5($password);
В данном случае, если у пользователя пароль qwerty, мы получим следующий хеш: d8578edf8458ce06fbc5bb76a58c5ca4. Если злоумышленник получит доступ к нашей базе, для подбора паролей он может воспользоваться уже готовыми сервисами(http://wordd.org/D8578EDF8458CE06FBC5BB76A58C5CA4), в которых уже есть значения, дающие данный хеш, либо сбрутить самому.
Для защиты от уже готовых таблиц хешей с значениями, можно использовать статическую соль:
$password = md5($password . "MyUniqueSault");
Сейчас при том же пароле qwerty мы получим совершенно другой хеш bdadb0330124cda0e8499c9cd118f7bd. Готовые таблицы уже не помогут злоумышленнику, ему придется использовать брутфорс. Вот здесь и кроется минус статической соли: злоумышленник сможет сгенерировать свою таблицу хешей со статической солью и получить значения большинства паролей из базы. Для устранения этого минуса используется уникальная соль к каждому хешу:
$sault = GenerateRandomString(); $password = md5($password . $sault);
Т.е. теперь помимо логина/хеша пароля в базе необходимо будет хранить значение сгенерированной соли для каждого пользователя. Разберем пример: у нас два пользователя: user1 и user2. Оба используют пароль qwerty. Но у первого была сгенерирована соль zxcv а у второго asdf. В итоге у пользователей при одинаковом пароле будут различные хеши: 1d8f3272b013387bbebcbedb4758586d и a192862aa3bf46dffb57b12bdcc4c199.Что это дает: теперь нельзя будет сгененерировать одну таблицу хешей, для нахождения значения хеша с динамической солью придется генерировать заново. Все это направлено на увеличение времени подбора значений в случае «слива» базы, при использовании «хороших» алгоритмов хеширования, на подбор хотя бы пары паролей уже может уйти значительное количество времени. Важно понимать, что генерируемая соль защищает не одного единственного пользователя, а всех вместе от массового брута. На этом все, хочу напомнить что используйте криптостойкие алгоритмы хеширования SHA1, SHA512. Используемый выше MD5 к использованию не желателен, т.к. признан устаревшим.
Хорошо резюмировал Kolonist в своем комментарии habrahabr.ru/post/145648/#comment_4894759 ( за что ему отдельное спасибо и плюс):
Еще раз.
1. Нет соли — используем уже готовые радужные таблицы.
2. Есть одна на всех соль — генерируем одну радужную таблицу и «ломаем» по ней всех пользователей.
3. Есть отдельная соль для каждого пользователя — отдельно брутфорсим каждого пользователя.
Соль (криптография)
Соль (также модификатор входа хэш-функции) — строка данных, которая передаётся хеш-функции вместе с входным массивом данных (прообразом) для вычисления хэша (образа).
Используется для усложнения определения прообраза хэш-функции методом перебора по словарю возможных входных значений (прообразов), включая атаки с использованием радужных таблиц. Позволяет скрыть факт использования одинаковых прообразов при использовании для них разной соли. Различают статическую соль (одна и та же для всех входных значений) и динамическую (генерируется для каждого входного значения персонально).
Пример использования
Пусть пароли хешируются по алгоритму MD5 и хранятся в виде хэш-значений в базе данных. В случае кражи базы исходные пароли могут быть восстановлены с помощью заранее подготовленных радужных таблиц, так как зачастую пользователи используют ненадёжные, легко подбираемые по словарям пароли. Если же пароль «посолить», то есть при вычислении хэш-значений присоединить к входным данным строку из нескольких случайных символов, которые будут являться значением соли, то результирующее значения не будут совпадать с распространёнными словарями хэш-значений. Знание соли позволяет сгенерировать новые словари для перебора, поэтому значение соли должно храниться в тайне. Для соли верны те же рекомендации к сложности, что и для сложности пароля, то есть значение соли должно обладать хорошей энтропией и длиной.
Пример создания хеша с использованием статичной соли на языке PHP по принципу конкатенации (соединения) с входными данными:
$password1 = ‘12345’; $password2 = ‘67890’; $salt = ‘sflpr9fhi2’; // «Соль» $password1_saltedHash = md5($password1 . $salt); // Соединяем входную строку с «солью» и пропускаем через хэш-функцию md5() $password2_saltedHash = md5($password2 . $salt);
В данном примере соль является детерминированной строкой, то есть значение соли постоянно для всех входных данных.
Динамическая соль
Существуют схемы формирования динамической соли, при которых значения соли генерируются для каждого входного значения индивидуально, что затрудняет составление словарей перебора, а также скрывает факт хранения одинаковых паролей, используемых разными пользователями. Также эффективность схемы увеличивается, если используется нетривиальное подмешивание по некоторому алгоритму. Например, соль можно не просто приписывать к концу пароля, а «подмешивать» в определённые промежутки пароля. К тому же хэш можно вычислять циклически, подмешивая соль частями с некоторыми изменениями, зависящими от номера итерации хэширования.
Один из известных стандартов PBKDF2 описывает подмешивание соли в несколько итераций.
Из таблицы выше видно, что одинаковые пароли пользователей при разной динамической соли будут в итоге давать разные хэш-значения.
Проблемы, связанные с солью и надёжностью паролей
При несанкционированном доступе к базе данных системы авторизации злоумышленник может получить сведения, необходимые для прохождения авторизации от имени пользователей из данной базы. Если пароли хранятся в изначальном (открытом) виде, злоумышленник может использовать их для доступа к другим ресурсам, так как пользователи зачастую используют одинаковые пароли для разных веб-сервисов. Использование динамической соли позволяет избежать компрометации аккаунтов пользователя на нескольких веб-сервисах сразу.
При плохо продуманной системе применения соли её преимущества теряются:
Малая длина соли и низкая энтропия
Если соль имеет малую длину, злоумышленнику будет легко создать радужную таблицу, состоящую из всех возможных солей определённой длины, добавляемых к каждому вероятному паролю. К тому же использование соли с низкой энтропией увеличит вероятность успешного нахождения соли по словарю, поэтому значение соли в идеале должно генерироваться с использованием ДСЧ. Использование длинной соли с хорошей энтропией гарантирует, что радужная таблица для базы данных будет слишком большой и потребует для своей генерации и хранения значительных ресурсов злоумышленника.
Повторное использование соли для разных прообразов
Хотя использование статической соли для одинаковых прообразов сделает некоторые существующие радужные таблицы бесполезными, следует заметить, что если соль статично вписана в исходный код популярного продукта, то она может быть рано или поздно извлечена, после чего на основе этой соли можно создать новую радужную таблицу. Если же соль генерируется динамически для каждого прообраза индивидуально, используя некоторые уникальные параметры для каждого пользователя, то стойкость системы повышается.
Использование одной фиксированной соли также означает, что каждый пользователь, вводящий один и тот же пароль, будет иметь один и тот же хэш. Это упрощает атаку на нескольких пользователей, путём взлома только одного из повторяющихся хэшей.
Преимущества использования соли в системах авторизации
Чтобы понять разницу между взломом одного пароля и их набором, рассмотрим файл паролей, содержащий сотни имен пользователей и хэшированных паролей. Без соли злоумышленник может вычислить хэш от некоторого значения (например, из словаря), а затем проверить, встречается ли этот хэш в любом месте файла. Вероятность совпадения, то есть взлома одного из паролей, очевидно увеличивается с количеством паролей в файле. Если же используется соль, при чём динамическая, то есть имеющая как минимум несколько возможных значений для одного хэша, то злоумышленник должен вычислить хэш для каждой возможной пары соли и перебираемого пароля, что резко увеличивает трудоёмкость перебора.
Соль также позволяет противодействовать использованию хэш-таблиц для взлома паролей. В случае с паролями пользователей, хэш-таблица представляет собой набор предварительно вычисленных хэшей для часто используемых паролей. Для файла паролей без применения соли злоумышленник может пройти через каждую запись и найти соответствующий хэшированный пароль в хэш-таблице. Так как поиск выполняется значительно быстрее, чем вычисление хэш-функции, это значительно ускорит процесс взлома паролей. Но если файл пароля формируется с участием соли, то хэш-таблица должна содержать предварительно хэшированные значения с участием соли. Если соль достаточно длинная и имеет высокую энтропию (является случайной), то вероятность взлома резко уменьшается. Несоленые пароли, выбранные людьми, как правило уязвимы для словарных атак, поскольку они обычно выбираются короткими и достаточно простыми для запоминания. Даже небольшой словарь (или его хэшированный эквивалент, хэш-таблица) является значительной помощью для взлома наиболее часто используемых паролей.
С технической точки зрения, соль защищает от хэш-таблиц и радужных таблиц, поскольку, по сути, расширяют длину и потенциально сложность пароля. Если в радужных таблицах нет паролей, соответствующих длине (например, 8-байтовый пароль и 12-байтовая соль, что по сути является 20-байтовым паролем) и сложности ( сложная соль с высокой энтропией увеличивает сложность простых строго буквенно-цифровых паролей) соленого пароля, то пароль не будет найден.
Современная система теневых паролей, в которой хэши паролей и другие данные безопасности хранятся в непубличном файле, отчасти решает проблему несанкционированного доступа к файлу с хэшами. В то же время они остаются актуальными в многосерверных установках, использующих централизованные системы управления паролями для передачи паролей или хэшей паролей в несколько систем.
Соль также делает словарные атаки и атаки грубой силы для взлома большого количества паролей крайне медленными (но не в случае взлома только одного пароля). Не имея соль, злоумышленник, взламывающий большой набор паролей, вынужден производить сравнение каждый раз со всеми кандидатами. Если учесть, что соль может быть динамической, то каждый вариант соли нужно пытаться применить каждому паролю из списка.
Другое преимущество соли заключается в следующем: два пользователя могут выбрать одинаковую строку в качестве своего пароля, или один и тот же пользователь может использовать один и тот же пароль на двух компьютерах. Без соли этот пароль будет сохранен в виде той же хэш-строки в файле паролей. Это раскрыло бы тот факт, что у двух учетных записей есть один и тот же пароль, что позволяет любому, кто знает один из паролей учетной записи, получить доступ к другой учетной записи. При подмешивании соли, даже если две учетные записи используют один и тот же пароль, никто не может обнаружить это простым рассмотрением значений хэшей.
Соль в системах UNIX
В большинстве UNIX-систем в качестве односторонней функции используется системная библиотека crypt(3). Изначально эта библиотека использовала хеш-функцию на базе алгоритма DES. При этом пароль был ограничен 8 символами (по 7 бит на символ, то есть 56 бит), и использовалась 12-битная соль.
В 1994 году Poul-Henning Kamp на базе MD5 создал новый алгоритм хеширования паролей, который позволял использовать пароли любой длины и использовал тысячу итераций MD5. Результатом работы функции стала строка, содержащая метку алгоритма хеширования (версию), соль и хеш.
По тем временам задержка для вычисления такого хеша была достаточной для эффективного противостояния нахождению пароля полным перебором. Однако по мере роста вычислительных способностей время нахождения MD5 сильно упало. Это привело к появлению в crypt вычислительно более сложных алгоритмов и управления числом итераций.
Сейчас библиотека поддерживает несколько хеш-функций на базе алгоритмов: MD5, SHA-256, SHA-512, Blowfish (в некоторых дистрибутивах Linux, OpenBSD и некоторых других UNIX-подобных системах). Результатом работы функции является строка, содержащая метку алгоритма хеширования, соль, хеш и другие данные (например, число раундов хеш-функции).
В 2012 году Poul-Henning Kamp призвал полностью отказаться от созданного им алгоритма md5crypt, как не обеспечивающего в современных условиях ощутимого увеличения времени вычисления хеша, а значит, и не защищающего от полного перебора.
Зачем нужна соль при хешировании
Очень часто можно встретить различного рода соль при хешировании паролей.
Как она выглядит?
Соль это набор случайно подобранных символов, который конкатенируется с паролем при хешировании. Обычно конструкция выглядит где-то так:
$salt = '&WsWЗачем она все таки нужна?
Криптографическая соль нужна только для одной цели: защита от радужных таблиц. Дублируя википедию, скажу что радужная таблица — это набор готовых (предрассчитанных) хешей и их оригинальных значений. Такие таблицы генерируются обычным брут форсом, часто по словарю (Пример: http://md5decrypt.net). Быстрота определения оригинальной фразы по хешу осуществляется индексированным поиском по всей базе.
Зачастую пароли пользователей очень просты — словарь очень узок и часто пользуются шаблонные слова и словосочетания. В случае, если соль не была добавлена к оргинальному паролю, есть большая вероятность что такой хеш уже скомпрометирован (например хеш от «mypassword» 34819D7BEEABB9260A5C854BC85B3E44 уже есть в базе данных md5decrypt.net).
В случае добавления соли, особенно если она находится в окружении сервера и никогда не покидает его пределы (не публична), мы получаем широкий исходный алфавит и большую длинну исходного значения.
Какие к ней требования?
Требования к соли следующие:
- приватную соль не ставить соль в начало фразы, поскольку в таком случае возможна атака удлиннением сообщения
- соль должна иметь достаточную длину, хотя бы 10 символов, больше — лучше.
- алфавит лучше использовать из всех возможных символов.
2030039 — не очень хорошая соль
codedokode / Как солить и хешировать пароли.md
Здесь старая версия урока, которая больше не обновляется.
Итак, ты решил сделать авторизацию и регистрацию через пароли. Как максимально обезопасить пароли пользователей от взлома и от своих же любопытных сотрудников (если ты работаешь не один, а в большой компании)?
Для начала, никогда не храни открытые пароли. Храни соленые хеши от них. Хеш-функция, например md5, sha1 (про них написано в вики, почитай) — это практически необратимая функция. То есть получить хеш по паролю просто, а вот восстановить пароль, имея хеш практически невозможно — надо перебирать все возможные варианты паролей и сравнивать получившиеся хеши.
Какой смысл в хэше, если md5 все равно можно расшифровать? Пусть даже перебором?
Это займет много или очень много времени. Может, взломщик устанет ждать или пароли потеряют актуальность. Например, если хорошо шифровать, то годы (по идее там перебирать можно и 100 лет, но я думаю скоро изобретут какую-нибудь штуку для ускоренного перебора), вместо того чтобы взять и увидеть пароли в открытую.
Ок, достаточно ли использовать хеширование и хранить только хеши?
Нет! Без так называемой «соли» многие пароли можно подобрать за секунду если там использовать просто md5(pass). Не веришь? Читай ниже.
Что такое соль? Что значит «соленый хеш»?
Соль — случайно сгенерированная последовательность символов, которая хранится рядом с хешем. Дан пароль $pass = "123456" , мы генерируем случайную соль например $salt = 'A&%6t*(k:' и получаем хеш от «соль + пароль»: $hash = md5($salt . $pass) . В базу сохраняется отдельно использованная соль (она для каждого пользователя своя), отдельно хеш.
Теперь попробуем применить математику и посчитать насколько надежны разные способы хеширования. Сейчас подбор пароля делается 2 способами:
Перебираем все возможные пароли, начиная например с 1111111 и заканчивая zzzzzzz и вычисляем от каждого md5-хеш. При этом число вариантов, которые надо подобрать, зависит от длины и набора символов (чем их больше тем больше перебирать). Скорость перебора md5 на топовых видеокартах составляет около 10 миллиардов в секунду ( http://www.opennet.ru/opennews/art.shtml?num=30201 и http://hashcat.net/oclhashcat/ ). А ведь можно взять не одну видеокарту, а много, если очень надо.
Заметь, что если у тебя база с кучей хешей, то их все можно проверять их все одновременно примерно с такой же скоростью как и один хеш.
Считаем число вариантов.
36^6 — значит 36 в 6-й степени, то есть 36*36*36*36*36*36 если что.
- Если в пароле 12 цифр 0-9 : число комбинаций = 10^12 = 1000 миллиардов = 100 секунд перебора на 1 видеокарте (1 секунда на 100 карточках параллельно).
- Если 6 букв a-z или цифр 0-9 . Число вариантов = 36^6 (считаем гуглом) = 2 млрд. Хехе, меньше секунды.
- Если 6 букв a-zA-Z (добавим маленькие и большие буквы) и 0-9 . Комбинаций 62^6 = 56 млрд. 6 секунд перебора.
- Если в пароле 8 букв a-zA-Z и цифр 0-9 . Комбинаций уже 62^8 = 218 триллионов. Это 22000 секунд перебора (в часе 3600 секунд, так что выходит 6 часов) на 1 карточке или 220 секунд на 100 карточках. Ого, не очень-то надежно.
- Если в пароле 10 символов a-zA-Z0-9 + 20 знаков вроде минус, плюс.. то выходит 82^10 комбинаций ~ 10^19 и перебирать их 10^9 секунд на одной карте (11500 дней) или 115 дней на сотне карточек.
Люди часто ставят паролем не бредовый набор букв, а слова или куски слов. Значит, какие-то символы рядом встречаются чаще, их можно перебирать в первую очередь тем самым сокращая число вариантов и ускоряя время нахождения.
В общем, видишь, без добавления соли пароли подберутся на раз. И не все же ставят 10-символьные пароли, у многих там просто слово или цифры.
Есть еще другой вариант — скачать огромные радужные таблицы (читай в вики про них) где хранятся уже рассчитанные цепочки хешей (для простых паролей). И конечно все хеши от обычных паролей длиной до 10 символов там уже есть (больше нету, так как они начинают занимать гигабайты. Но это вопрос времени, когда жесткие диски станут больше). Если ты хранишь в базе md5(pass) она вскроется мигом. Таблицы можно скачать тут: https://www.freerainbowtables.com/en/tables2/ (если не открывается, выбери английский язык и открой ссылку еще раз).
Вот пример такой таблицы: md5_loweralpha-numeric#1-10 588 GB - подбирает пароли без соли до 10 символов [a-z0-9].
Заметь что в будущем компьютеры будут мощнее, и значит подбираться пароли будут быстрее. Теперь подумаем как защититься и усложнить жизнь взломщикам:
- разрешаем использовать больше видов символов в паролях
- добавляем соль. С солью не получится параллельно подбирать все хеши так как у каждого юзера соль своя и каждый хеш надо перебирать отдельно, что сильно замедляет взлом. Также, при добавлении соли даже к простому паролю он по сути становится длинным и сложным и его не будет в радужных таблицах (123456 → Y^juYUHkd%$fdtd123456). Опять же, соль должна быть подлиннее и содержать спецсимволы чтобы было больше комбинаций для перебора. Ну конечно, простые пароли типа 123456 все равно вскроют, так как их при переборе проверяют в первую очередь. А вот сложные придется подбирать долго.
- используем вместо md5 более тяжелые для вычисления алгоритмы вроде bcrypt, который сделан так, что его нельзя перебрать быстрее чем за опредеенное время (и ты можешь указать требемый уровень сложности).
С правильным подходом даже простой md5 замучаешься расшифровывать.