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

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

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

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

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

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

  • если нет соли, a здесь найдете сразу все пароли (кроме очень длинных).
  • если есть достаточно длинная случайная соль, наиболее эффективным способом узнать пароли является грубая сила или атака по словарю. Ни коллизионные, ни прообразные атаки не помогают в поиске фактического пароля, поэтому криптографические атаки против SHA-1 здесь не помогают. Даже не важно, какой алгоритм используется - можно даже использовать MD5 или MD4, и пароли будут такими же безопасными (есть небольшая разница, потому что вычисление хэша SHA-1 происходит медленнее).
  • чтобы оценить, насколько безопасно "так же безопасно", предположим, что один запуск sha1 занимает 1000 операций, а пароли содержат прописные, строчные и цифры (то есть 60 символов). Это означает, что злоумышленник может проверить 1015*60*60*24 / 1000 ~= 1017 потенциальный пароль в день. Для атаки грубой силы это будет означать тестирование всех паролей до 9 символов за 3 часа, до 10 персонажи в неделю, до 11 символов в год. (Это занимает в 60 раз больше для каждого дополнительного символа.) Атака по словарю намного быстрее (даже злоумышленник с одним компьютером может снять ее за несколько часов), но находит только слабые пароли.
  • чтобы войти в систему как пользователь, злоумышленнику не нужно узнавать точный пароль; достаточно найти строку, которая приводит к тому же хэшу. Это называется первой атакой на прообраз. Насколько я мог найти, нет никакого прообраза атаки против ша-1. (Атака брутфорса займет 2160 операции, что означает, что наш теоретический атакующий потребуется 1030 лет, чтобы снять его. Пределы теоретической возможности составляют около 260 операции, при которых атака займет несколько лет.) Есть preimage атаки против сокращенных версий SHA-1 с незначительным эффектом (для уменьшенного SHA-1, который использует 44 шага вместо 80, время атаки уменьшается от 2160 операции 2157). Есть столкновения атаки против SHA-1, которые находятся в пределах теоретической возможности (лучшее, что я нашел приносит время от 280 в 252), но они бесполезны против хэшей паролей, даже без засолки.

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

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

7 141
hashset cryptography sha1

7 ответов:

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

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

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

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

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

о радужных таблиц:

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

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

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

Если N достаточно большой, что CPU-стоимость хэширования 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μs; но стоимость для злоумышленника выросла на очень заметный фактор 10000. На общих серверах с тысячами клиентов в секунду совокупная стоимость может стать непомерно высокой. Концептуально, повышение планки одним и тем же фактором для законного пользователя и злоумышленника не является в конечном счете хорошей безопасностью; но это может быть полезной идеей в некоторых конкретных ситуациях.

об атаках в интернете:

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

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

203

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

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

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

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

28

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

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

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

7

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

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

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

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

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

6

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

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

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

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

4

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

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

4

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

вот какой НИСТ говорит:

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

3