Является ли SHA-1 безопасным для хранения паролей?

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

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

узнать пароль любого пользователя?
узнать пароль данного пользователя?
узнать пароль всех пользователей?
найти способ войти в систему как один из пользователей?
найти способ входа в систему как конкретного пользователя?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

О солях:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вычислить hash из streamа неизвестной длины в C #

Сложность выполнения таблицы hash-таблицы (вставка, поиск и удаление)

Почему hashCode () возвращает одно и то же значение для разных объектов в Java?

Функция хеша пароля для Excel VBA

Компиляция времени

Как работает оператор double arrow (=>) в Perl?

Общий форум

Получение URL-адреса хеша и использование его в jQuery

Как hash и сравнить функцию-указатель-член?

Как реализована функция GetHashCode () из строки C #?

Как я могу поддерживать порядок ключей, которые я добавляю к hashу Perl?