Безопасен ли SHA-1 для хранения паролей?

Вывод: SHA-1 столь же безопасен, как и все остальные, от атак с прообразом, однако его легко вычислить, что означает, что его проще монтировать с помощью грубой силы или атаки по словарю. (То же самое верно для преемников, таких как SHA-256.) В зависимости от обстоятельств, хэш-функция, которая была разработана с учетом вычислительных затрат (например, bcrypt), могла бы быть лучшим выбором.

Некоторые люди часто бросают замечания типа «SHA-1 сломан», поэтому я пытаюсь понять, что именно это означает. Давайте предположим, что у меня есть база данных хэшей паролей SHA-1, и злоумышленник с использованием современного алгоритма взлома SHA-1 и ботнета с 100 000 компьютеров получает доступ к нему. (Наличие 100 тысяч домашних компьютеров означает, что они могут выполнять около 10 ^ 15 операций в секунду.) Сколько времени им потребуется

1. узнать пароль любого пользователя?
2. узнать пароль данного пользователя?
3. узнать пароль всех пользователей?
4. найти способ войти как один из пользователей?
5. найти способ войти как конкретный пользователь?

Как это изменится, если пароли будут засолены? Имеет ли значение метод посола (префикс, постфикс, оба или что-то более сложное, например, хоринг)?

Вот мое текущее понимание, после некоторого поиска в Google. Пожалуйста, исправьте ответы, если я что-то не так понял.

• Если соли нет, атака радуги немедленно найдет все пароли (кроме очень длинных).
• Если случайная соль достаточно длинная, наиболее эффективный способ узнать пароли - это грубая атака или атака по словарю. Ни коллизионные атаки, ни атаки с использованием изображений не помогают найти действительный пароль, поэтому криптографические атаки на SHA-1 здесь не помогут. Даже не имеет значения, какой алгоритм используется - можно даже использовать MD5 или MD4, и пароли были бы столь же безопасными (есть небольшая разница, потому что вычисление хэша SHA-1 медленнее).
• Чтобы оценить, насколько безопасным является «столь же безопасный», давайте предположим, что для одного запуска sha1 требуется 1000 операций, а пароли состоят из прописных, строчных букв и цифр (то есть 60 символов). Это означает, что злоумышленник может проверять 10 ¹⁵ * 60 * 60 * 24/1000 ~ = 10 ¹⁷ потенциальных паролей в день. Для атаки методом перебора это означало бы тестирование всех паролей до 9 символов за 3 часа, до 10 символов в неделю, до 11 символов в год. (Требуется в 60 раз больше для каждого дополнительного символа.) Атака по словарю намного, намного быстрее (даже злоумышленник с одним компьютером может осуществить это за часы), но находит только слабые пароли.
• Чтобы войти в систему как пользователь, злоумышленнику не нужно узнавать точный пароль; достаточно найти строку, которая приводит к тому же хешу. Это называется первой прообразной атакой. Насколько я мог найти, нет никаких прообразных атак против SHA-1. (Атака грубой силы потребует 2 ¹⁶⁰ операций, что означает, что нашему теоретическому злоумышленнику потребуется 10 ³⁰ лет, чтобы осуществить его. Предел теоретической возможности составляет около 2 ⁶⁰ операций, на которые атака может занять несколько лет.) Существуют атаки с прообразом против уменьшенных версий SHA-1 с незначительным эффектом (для уменьшенного SHA-1, который использует 44 шага вместо 80, время атаки уменьшено с 2 ¹⁶⁰ операций до 2 ¹⁵⁷). Существуют коллизионные атаки на SHA-1, которые вполне соответствуют теоретическим возможностям ( лучшее, что я нашел, сокращает время с 2 ⁸⁰ до 2 ⁵² ), но они бесполезны против хэшей паролей, даже без засолки.

Короче говоря, хранение паролей с помощью SHA-1 кажется совершенно безопасным. Я что-то пропустил?

Обновление: Марсело указал на статью, в которой упоминается вторая прообразная атака в 2 ¹⁰⁶ операциях . ( Правка: как объясняет Томас , эта атака является гипотетической конструкцией, которая не применима к сценариям из реальной жизни.) Однако я до сих пор не понимаю, как это представляет опасность для использования SHA-1 в качестве ключевой производной функции. Есть ли вообще веские основания полагать, что атака столкновением или вторая атака с прообразом может в конечном итоге превратиться в первую атаку с прообразом?

Краткий ответ на ваш вопрос: SHA-1 настолько безопасен, насколько вы можете его получить. MD5 тоже подойдет, даже MD4; но это может заставить некоторых инвесторов нервничать. Для связей с общественностью лучше использовать «лучшую» хеш-функцию, например, SHA-256, даже если вы урезаете ее вывод до 160 или 128 бит (чтобы сэкономить на стоимости хранения). Некоторые из кандидатов второго раунда SHA-3 выглядят быстрее, чем SHA-1, хотя, возможно, «более безопасны»; все же они все еще немного новы, так что придерживаться SHA-256 или SHA-512 было бы более безопасным маршрутом прямо сейчас. Это заставит вас выглядеть профессионально и осторожно, что хорошо.

Обратите внимание, что «настолько безопасно, насколько вы можете получить» - это не то же самое, что «совершенно безопасно». Ниже приведены довольно длинные пояснения.

Об известных атаках:

Известные атаки на MD4, MD5 и SHA-1 касаются столкновений, которые не влияют на сопротивление прообразам. Было показано, что у MD4 есть несколько слабых мест, которые могут (только теоретически) использоваться при попытке взлома HMAC / MD4, но это не относится к вашей проблеме. Атака с прорисовкой в 2 ¹⁰⁶ секунд в статье Кесли и Шнайера - это общий компромисс, который применяется только к очень длинным входам (2 ⁶⁰ байт; это миллион терабайт - обратите внимание, что 106 + 60 превышает 160; вот где вы видите, что в обмене нет ничего волшебного).

В остальной части этого сообщения предполагается, что используемая вами хеш-функция (например, SHA-1) является «черным ящиком» без специального свойства, которое может использовать злоумышленник. Это то, что у вас есть сейчас даже с «сломанными» хеш-функциями MD5 и SHA-1.

О радужных столах:

«Радужная атака» на самом деле является разделением затрат на словарь или атаку грубой силой. Он является производным от компромисса « время-память», впервые описанного Хеллманом в 1980 году. Предполагая, что у вас есть N возможных паролей (это размер вашего словаря или 2 ^n, если вы считаете, что хэш-функция с использованием грубой форсировки выводит n битов), существует атака с разделением времени, при которой вы предварительно вычисляете N хешированных паролей и сохраняете их в большой таблице. Если вы сортируете выходные данные хеша, вы можете получить свой пароль в одном поиске. Стол радуги умный способ сохранить эту таблицу с большим количеством уменьшенном пространства. Вы храните только N / T хешированные пароли, и вы взламываете пароли с помощью O (т ² ) поиски. Радужные столы позволяют вам виртуально обрабатывать предварительно вычисленные таблицы намного больше, чем то, что вы реально можете хранить.

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

1. Атака грубой силы / словаря стоила N за взлом каждого пароля.
2. Используя предварительно вычисленную таблицу, злоумышленник оплачивает стоимость N раз и может после этого атаковать множество паролей с очень небольшими дополнительными затратами на каждый пароль.
3. Если предварительно вычисленная таблица является радужной таблицей, то N может быть несколько больше, поскольку стоимость хранения уменьшается. Узким местом на N становится мощность процессора, которую атакующий может собрать, а не размер его жестких дисков.

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

О солях:

Соли - это способ победить предварительные вычисления. В приведенном выше описании соль возвращает злоумышленника к шагу 1: соление не дает злоумышленнику разделить стоимость O ( N ) между несколькими атакованными паролями. Предварительно вычисленные таблицы, a fortiori радужные таблицы, больше не осуществимы.

Вы хотите солить, потому что, когда хешированные данные состоят из паролей , то есть чего-то, что умещается в мозгу случайного человека, тогда N может быть довольно низким: люди действительно плохо выбирают и запоминают пароли. Вот что такое «атака по словарю»: здесь используется уменьшенное пространство потенциальных паролей («словарь») при условии, что в этом специально выбранном пространстве будет много пользовательских паролей.

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

Кроме того, соление полезно для связей с общественностью.

О стоимости SHA-1:

Элементарная стоимость SHA-1 - это хеширование 64-байтового блока. Вот как работает SHA-1: данные дополняются, затем разделяются на 64-байтовые блоки. Стоимость обработки одного блока составляет около 500 тактов в системе Intel Core2, и это для одного ядра. MD5 и MD4 быстрее, насчитывают около 400 и 250 циклов соответственно. Не забывайте, что большинство современных процессоров имеют несколько ядер, поэтому умножьте соответственно.

Некоторые схемы соления предписывают огромные соли; Например, в хэш-функцию входят 40000 последовательных копий одной 128-битной соли, за которыми следует сам пароль. Это делает хеширование пароля более дорогим (в моем случае в 10000 раз), как для законного пользователя, так и для злоумышленника. Является ли это хорошей идеей, зависит от настройки. Для входа в систему на настольном компьютере это хорошо: пользователь даже не заметит, что для хэширования его пароля потребовалось 10 мс, вместо 1 мкс; но стоимость для злоумышленника возросла на очень заметный показатель - 10000. На общих серверах с тысячами клиентов в секунду совокупные затраты могут стать чрезмерно высокими. Концептуально, повышение планки одним и тем же фактором для законного пользователя и злоумышленника не является в конечном счете хорошей безопасностью; но это может быть полезной идеей в некоторых конкретных ситуациях.

О сетевых атаках:

Все вышеперечисленное касается победы над оффлайн- атаками. Оффлайн-атака - это атака, при которой у злоумышленника есть все данные, необходимые ему для «проверки» паролей; например, злоумышленник может получить копию базы данных, содержащей хешированные пароли. В автономной атаке злоумышленник ограничен только своими вычислительными ресурсами. И наоборот, онлайн- атака - это атака, при которой каждое предположение злоумышленника должно пройти через честного верификатора (например, злоумышленник просто пытается войти в атакуемую систему). Онлайновые атаки предотвращаются путем введения ограничений на количество попыток ввода паролей в секунду. Крайними примерами являются смарт-карты, которые закрываются после трех неправильных ПИН-кодов.

Обычно для обеспечения безопасности паролей гораздо выгоднее организовать систему, не позволяющую злоумышленнику создать автономную атаку. Это то, что делают системы Unix: хешированные пароли, которые раньше были в общедоступном /etc/passwordфайле, теперь находятся в /etc/shadowфайле, защищенном от доступа для чтения, за исключением нескольких привилегированных приложений. Здесь предполагается, что если злоумышленник может читать /etc/shadow, то он, вероятно, имеет достаточный контроль над системой, так что ему больше не нужны пароли ...

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

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

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

Для дальнейшего чтения:

• /crypto/400/why-cant-one-implement-bcrypt-in-cuda
• http://codahale.com/how-to-safely-store-a-password/
• http://www.codinghorror.com/blog/2012/04/speed-hashing.html
• /security/4781/do-any-security-experts-recommend-bcrypt-for-password-storage/6415#6415

Ваше описание звучит точно для текущего уровня техники.

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

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

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

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

В настоящее время лучшим выбором, вероятно, является Argon2 . Это семейство функций хеширования паролей выиграло конкурс хэширования паролей в 2015 году.

Если Argon2 недоступен, единственной другой стандартизированной функцией хеширования пароля или получения ключа является PBKDF2 , который является старым стандартом NIST. Другие варианты, если использование стандарта не требуется, включают bcrypt и scrypt .

В Википедии есть страницы для этих функций:

• https://en.wikipedia.org/wiki/Argon2
• https://en.wikipedia.org/wiki/Bcrypt
• https://en.wikipedia.org/wiki/Scrypt
• https://en.wikipedia.org/wiki/PBKDF2

В SHA-1 были обнаружены серьезные уязвимости, которые делают поиск намного быстрее, чем грубая сила. Это все еще в значительной степени неразрешимо, но это, как ожидают, не будет иметь место слишком долго; Программисты-параноики предпочитают что-то из семейства SHA-2.

Из этой статьи относительно оригинального результата 2005 года:

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

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

Короче говоря, SHA-1 сейчас безопасен, и, вероятно, еще какое-то время придет, но крипто-сообществу не нравится прогноз.

По состоянию на февраль 2017 года SHA-1 больше не должен считаться безопасным. Google сообщил об успешных атаках соударений против полного SHA-1 без округления ( ссылка на отчет ). Для объявления Google, нажмите здесь .

Редактировать: Как отмечают другие, пароли не уязвимы для атак хеш-коллизий. Однако в качестве общего руководства я бы не выбрал SHA-1 для приложений, связанных с безопасностью. Есть лучшие альтернативы там.

Если вы храните соленый пароль, SHA-1 подходит для практических целей. SHA-2 считается более безопасным, но SHA-1 не является проблемой, если у вас нет причин быть действительно параноиком.

Вот что говорит NIST :

Результаты, представленные до настоящего времени на SHA-1, не ставят под сомнение его безопасность. Однако из-за технологических достижений NIST планирует отказаться от SHA-1 в пользу более крупных и сильных хеш-функций (SHA-224, SHA-256, SHA-384 и SHA-512) к 2010 году.