SHA-1 - SHA-1

[Хеш-алгоритмы]
Концепции
хэш-функции  · SHA  · DSA
Основные стандарты
SHA-0  · SHA-1  · SHA-2  · SHA-3
SHA-1
Общий
ДизайнеровНациональное Агенство Безопасности
Впервые опубликовано1993 (SHA-0),
1995 (SHA-1)
Серии(SHA-0 ), SHA-1, SHA-2, SHA-3
СертификацияFIPS ПАБ 180-4, г. CRYPTREC (Отслеживается)
Деталь шифра
Размеры дайджеста160 бит
Размеры блоков512 бит
СтруктураСтроительство Меркле-Дамгарда
Раундов80
Лучшая публика криптоанализ
Атака Марка Стивенса 2011 года может вызвать хеш-коллизии со сложностью от 260.3 и 265.3 операции.[1] Первое публичное столкновение было опубликовано 23 февраля 2017 года.[2] SHA-1 склонен к атаки удлинения длины.

В криптография, SHA-1 (Алгоритм безопасного хеширования 1) это криптографическая хеш-функция который принимает входные данные и производит 160-кусочек (20-байт ) хеш-значение, известное как Дайджест сообщения - обычно отображается как шестнадцатеричный номер, длина 40 цифр. Он был разработан в США. Национальное Агенство Безопасности, и является США Федеральный стандарт обработки информации.[3]

С 2005 года SHA-1 не считался безопасным против хорошо финансируемых оппонентов;[4] по состоянию на 2010 год многие организации рекомендовали его замену.[5][6][7]NIST официально отказался от использования SHA-1 в 2011 году и запретил его использование для цифровых подписей в 2013 году. По состоянию на 2020 год, атаки с выбранным префиксом против SHA-1 практичны.[8][9] Поэтому рекомендуется как можно скорее удалить SHA-1 из продуктов и вместо этого использовать SHA-2 или же SHA-3. Замена SHA-1 необходима там, где он используется для цифровые подписи.

Все основные веб-браузер поставщики прекратили прием SHA-1 SSL сертификаты в 2017 году.[10][11][12] В феврале 2017 г. CWI Amsterdam и Google объявили, что провели столкновение против SHA-1, опубликовав два непохожих файла PDF с одинаковым хешем SHA-1.[13][2] Но SHA-1 по-прежнему безопасен для HMAC.[14]

Разработка

Одна итерация в функции сжатия SHA-1:
A, B, C, D и E 32-битные слова государства;
F - переменная нелинейная функция;
обозначает левый поворот битов п места;
п варьируется для каждой операции;
Wт - расширенное сообщение раунда t;
Kт - постоянная округления t;
Добавление обозначает сложение по модулю 232.

SHA-1 производит Дайджест сообщения на основе принципов, аналогичных тем, которые используются Рональд Л. Ривест из Массачусетский технологический институт в дизайне MD2, MD4 и MD5 алгоритмы дайджеста сообщения, но генерирует большее хеш-значение (160 бит против 128 бит).

SHA-1 был разработан в рамках правительственной Заключительный проект.[15] Первоначальная спецификация алгоритма была опубликована в 1993 году под названием Стандарт безопасного хеширования, FIPS PUB 180, агентство государственных стандартов США NIST (Национальный институт стандартов и технологий).[16][17] Эта версия сейчас часто называется SHA-0. Он был отозван АНБ вскоре после публикации и был заменен пересмотренной версией, опубликованной в 1995 году в FIPS PUB 180-1 и обычно обозначенной SHA-1. SHA-1 отличается от SHA-0 только одним побитовым чередованием в расписании сообщений своего функция сжатия. По данным АНБ, это было сделано для исправления изъяна в исходном алгоритме, который снижал его криптографическую безопасность, но никаких дополнительных объяснений не предоставили.[18][19] Общедоступные методы действительно продемонстрировали компромисс SHA-0 в 2004 году до SHA-1 в 2017 году. Видеть # Атаки

Приложения

Криптография

Дальнейшая информация: Криптографическая хеш-функция § Приложения

SHA-1 является частью нескольких широко используемых приложений и протоколов безопасности, включая TLS и SSL, PGP, SSH, S / MIME, и IPsec. Эти приложения также могут использовать MD5; оба MD5 и SHA-1 происходят от MD4.

SHA-1 и SHA-2 - это хеш-алгоритмы, требуемые законом для использования в определенных правительство США приложения, в том числе использование в других криптографических алгоритмах и протоколах, для защиты конфиденциальной несекретной информации. FIPS PUB 180-1 также поощрял принятие и использование SHA-1 частными и коммерческими организациями. SHA-1 больше не используется в правительстве; Национальный институт стандартов и технологий США заявил: "Федеральные агентства должен прекратите использование SHA-1 для ... приложений, которые требуют защиты от столкновений как можно скорее, и должны использовать SHA-2 семейство хэш-функций для этих приложений после 2010 г. »(курсив в оригинале),[20] хотя позже это было ослаблено, чтобы позволить использовать SHA-1 для проверки старых цифровых подписей и меток времени.[21]

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

Хэш-функции SHA использовались в качестве основы ШАКАЛ блочные шифры.

Целостность данных

Контроль версий такие системы как Git, Mercurial, и Монотонный используйте SHA-1 не для обеспечения безопасности, а для выявления изменений и обеспечения того, чтобы данные не были изменены из-за случайного повреждения. Линус Торвальдс сказал про Git:

Если у вас есть повреждение диска, если у вас есть повреждение DRAM, если у вас вообще есть какие-либо проблемы, Git их заметит. Это не вопрос если, это гарантия. У вас могут быть люди, которые пытаются быть злыми. У них ничего не получится. ... Никто не смог взломать SHA-1, но дело в том, что SHA-1, с точки зрения Git, даже не является функцией безопасности. Это чистая проверка согласованности. Компоненты безопасности находятся в другом месте, поэтому многие люди предполагают, что, поскольку Git использует SHA-1, а SHA-1 используется для криптографически безопасных вещей, они думают, что, хорошо, это огромная функция безопасности. Это не имеет ничего общего с безопасностью, это просто лучший хэш, который вы можете получить. ...
Я гарантирую вам, что если вы поместите свои данные в Git, вы можете доверять тому факту, что пять лет спустя, после того, как они были преобразованы с вашего жесткого диска на DVD с использованием какой-либо новой технологии и вы скопировали их вместе, через пять лет вы сможете убедиться, данные, которые вы получаете обратно, - это точно такие же данные, которые вы вводите. ...
Одна из причин, по которой я забочусь, - это ядро, мы взломали одну из BitKeeper сайты, на которых люди пытались повредить репозитории исходного кода ядра.[22] Однако Git не требует сопротивление второго прообраза SHA-1 в качестве функции безопасности, так как он всегда будет предпочитать сохранять самую раннюю версию объекта в случае коллизии, предотвращая тайное перезапись файлов злоумышленником.[23]

Криптоанализ и проверка

Для хеш-функции, для которой L - количество бит в дайджесте сообщения, найти сообщение, которое соответствует заданному дайджесту сообщения, всегда можно с помощью поиска грубой силы примерно за 2L оценки. Это называется атака на прообраз и может быть или не быть практичным в зависимости от L и конкретная вычислительная среда. Однако столкновение, состоящий из поиска двух разных сообщений, содержащих один и тот же дайджест сообщения, требует в среднем около 1.2 × 2L/2 оценки с использованием атака на день рождения. Таким образом сила хеш-функции обычно сравнивают с симметричным шифром половинной длины дайджеста сообщения. SHA-1, который имеет 160-битный дайджест сообщения, изначально считался 80-битным.

В 2005 году криптографы Сяоюнь Ван, Ицюнь Лиза Инь, и Хунбо Ю создали пары коллизий для SHA-0 и нашли алгоритмы, которые должны производить коллизии SHA-1 гораздо реже, чем первоначально ожидалось 280 оценки.[24]

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

В случае подписания документа злоумышленник не может просто подделать подпись из существующего документа: злоумышленник должен будет предоставить пару документов, один безобидный и один опасный, и заставить держателя закрытого ключа подписать безобидный документ. Существуют практические обстоятельства, при которых это возможно; до конца 2008 года можно было создавать кованые SSL сертификаты с использованием MD5 столкновение.[25]

Вследствие блочной и итеративной структуры алгоритмов и отсутствия дополнительных финальных шагов все функции SHA (кроме SHA-3[26]) уязвимы для удлинение и атаки с частичным конфликтом сообщений.[27] Эти атаки позволяют злоумышленнику подделать сообщение, подписанное только ключевым хешем - SHA (сообщение || ключ) или же SHA (ключ || сообщение) - расширяя сообщение и пересчитывая хэш, не зная ключа. Простое улучшение для предотвращения этих атак - дважды хешировать: SHAd(сообщение) = SHA (SHA (0б || сообщение)) (длина 0б, нулевой блок, равен размеру блока хеш-функции).

Атаки

В начале 2005 г. Rijmen и Элизабет Освальд опубликовали атаку на сокращенную версию SHA-1 - 53 раунда из 80 - которая обнаруживает коллизии с вычислительными затратами менее 280 операции.[28]

В феврале 2005 г. Сяоюнь Ван, Ицюнь Лиза Инь и Хунбо Ю.[29] Атаки могут находить коллизии в полной версии SHA-1, требуя менее 269 операции. (А перебор потребуется 280 операции.)

Авторы пишут: «В частности, наш анализ основан на исходной дифференциальной атаке на SHA-0, атаке с близким столкновением на SHA-0, методах многоблочных коллизий, а также на методах модификации сообщений, используемых в атаке поиска коллизий на MD5. Взлом SHA-1 был бы невозможен без этих мощных аналитических методов ».[30] Авторы представили коллизию для 58-раундового SHA-1, найденную с 233 хеш-операции. Статья с полным описанием атаки была опубликована в августе 2005 года на конференции CRYPTO.

В интервью Инь заявляет, что «грубо говоря, мы используем следующие два недостатка: первый заключается в том, что этап предварительной обработки файла недостаточно сложен; другой - в том, что некоторые математические операции в первых 20 раундах имеют неожиданные проблемы с безопасностью».[31]

17 августа 2005 г. было объявлено об улучшении атаки SHA-1 от имени Сяоюнь Ван, Эндрю Яо и Фрэнсис Яо на CRYPTO 2005 Rump Session, снизив сложность, необходимую для обнаружения коллизии в SHA-1, до 263.[32] 18 декабря 2007 года подробности этого результата были объяснены и подтверждены Мартином Кокраном.[33]

Кристоф Де Канньер и Кристиан Рехбергер усовершенствовали атаку на SHA-1 в статье «Поиск характеристик SHA-1: общие результаты и приложения».[34] получение награды за лучшую работу ASIACRYPT 2006. Была представлена ​​коллизия двух блоков для 64-раундового SHA-1, обнаруженная неоптимизированными методами с 235 оценки функции сжатия. Поскольку для этой атаки требуется примерно 235 оценок, это считается значительным теоретическим прорывом.[35] Их атака была продлена Гречниковым до 73 раундов (из 80) в 2010 году.[36] Однако для того, чтобы найти реальную коллизию в полных 80 раундах хэш-функции, требуется огромное количество компьютерного времени. Для этого выполняется поиск коллизий для SHA-1 с использованием платформы распределенных вычислений. BOINC началось 8 августа 2007 г., организовано Технологический университет Граца. Работа была прекращена 12 мая 2009 г. из-за отсутствия прогресса.[37]

На Rump Session CRYPTO 2006 Кристиан Рехбергер и Кристоф Де Канньер заявили, что обнаружили коллизионную атаку на SHA-1, которая позволит злоумышленнику выбрать хотя бы части сообщения.[38][39]

В 2008 году методология атаки Стефана Мануэля сообщила о хэш-конфликтах с расчетной теоретической сложностью 251 до 257 операции.[40] Однако позже он отказался от этого утверждения после того, как обнаружил, что локальные пути столкновения на самом деле не являются независимыми, и, наконец, процитировал наиболее эффективный вектор столкновения, который был уже известен до этой работы.[41]

Кэмерон Макдональд, Филип Хоукс и Йозеф Пиепшик представили атаку хеш-коллизии заявленной сложности 252 на большой сессии Eurocrypt 2009.[42] Однако в сопроводительной статье «Дифференциальный путь для SHA-1 со сложностью О (252) "был отозван в связи с тем, что авторы обнаружили, что их оценка неверна.[43]

Одна атака против SHA-1 была Marc Stevens.[44] с ориентировочной стоимостью 2,77 млн ​​долларов (2012 г.) для взлома одного хеш-значения за счет аренды мощности ЦП у облачных серверов.[45] Стивенс разработал эту атаку в проекте под названием HashClash,[46] реализация атаки по дифференциальному пути. 8 ноября 2010 года он заявил, что у него есть полностью работающая атака с приближением к столкновению с полным SHA-1, работающая со сложностью, эквивалентной 257.5 Сжатия SHA-1. По его оценкам, эту атаку можно расширить до полного столкновения со сложностью около 261.

Шаппенинг

8 октября 2015 года Марк Стивенс, Пьер Карпман и Томас Пейрин опубликовали независимую атаку на столкновение с функцией сжатия SHA-1, для которой требуется только 257 Оценки SHA-1. Это не приводит напрямую к конфликту с полной хэш-функцией SHA-1 (когда атакующий нет может свободно выбирать начальное внутреннее состояние), но подрывает требования безопасности для SHA-1. В частности, это была первая атака на полный SHA-1. продемонстрировал; все предыдущие атаки были слишком дорогими для их авторов. Авторы назвали этот значительный прорыв в криптоанализе SHA-1 Шаппенинг.[6]

Этот метод был основан на их более ранних работах, а также на технике ускорения вспомогательных путей (или бумерангов) от Joux и Peyrin, а также на использовании высокопроизводительных / экономичных видеокарт от NVIDIA. Коллизия была обнаружена в кластере из 16 узлов с 64 видеокартами. По оценкам авторов, аналогичную коллизию можно обнаружить, купив 2 000 долларов США графического процессора на EC2.[6]

Авторы подсчитали, что стоимость аренды достаточного количества времени CPU / GPU EC2 для генерации полной коллизии для SHA-1 на момент публикации составляла от 75 до 120 тысяч долларов США, и отметили, что это было в пределах бюджета преступных организаций, а не упомянуть национальный спецслужбы. Таким образом, авторы рекомендовали как можно скорее отказаться от SHA-1.[6]

SHAttered - первое публичное столкновение

23 февраля 2017 г. CWI (Centrum Wiskunde & Informatica) и Google объявили SHAttered атака, в ходе которой они сгенерировали два разных файла PDF с одинаковым хешем SHA-1 примерно за 263.1 Оценки SHA-1. Эта атака примерно в 100000 раз быстрее, чем грубое форсирование коллизии SHA-1 с атака на день рождения, что, по оценкам, заняло 280 Оценки SHA-1. Атака потребовала «вычислительной мощности, эквивалентной 6500 годам вычислений на одном процессоре и 110 годам вычислений на одном GPU».[2]

Birthday-Near-Collision Attack - первая практическая атака с выбранным префиксом

24 апреля 2019 года в докладе Гаэтана Леурента и Томаса Пейрина, представленного на Eurocrypt 2019, описывалось улучшение ранее существовавшего атака с выбранным префиксом в Меркл-Дамгард –Подобные дайджест-функции на основе Дэвис-Мейер блочные шифры. Благодаря этим улучшениям, этот метод способен обнаруживать коллизии с выбранным префиксом примерно за 268 Оценки SHA-1. Это примерно в 1 миллиард раз быстрее (и теперь его можно использовать для многих целевых атак благодаря возможности выбора префикса, например вредоносного кода или поддельных идентификаторов в подписанных сертификатах), чем в предыдущей атаке 2.77.1 оценки (но без выбранного префикса, что было непрактично для большинства целевых атак, поскольку обнаруженные коллизии были почти случайными)[47] и достаточно быстр, чтобы быть практичным для находчивых злоумышленников, требуя около 100 000 долларов на облачную обработку. Этот метод также может обнаруживать коллизии с выбранным префиксом в MD5 функция, но при сложности 246.3 не превосходит предыдущий наилучший доступный метод на теоретическом уровне (239), хотя потенциально на практическом уровне (≤249).[48][49] Для этой атаки требуется 500+ ГБ памяти.

5 января 2020 года авторы опубликовали улучшенную атаку.[50] В этой статье они демонстрируют атаку столкновения с выбранным префиксом со сложностью 263.4, что на момент публикации будет стоить 45 тысяч долларов за сгенерированное столкновение.

SHA-0

В КРИПТО 98, два французских исследователя, Флоран Шабо и Антуан Жу, представил атаку на SHA-0: столкновения можно найти со сложностью 261, меньше 280 для идеальной хеш-функции того же размера.[51]

В 2004 г. Бихам и Чен обнаружили близкие к конфликту конфликты для SHA-0 - два сообщения, хэш которых имеет почти одинаковое значение; в этом случае 142 из 160 битов равны. Они также обнаружили, что количество полных коллизий SHA-0 уменьшено до 62 из 80 раундов.[52]

Впоследствии, 12 августа 2004 г., Жу, Каррибо, Лемуэ и Джалби объявили о конфликте полного алгоритма SHA-0. Это было сделано с использованием обобщения атаки Шабо и Жу. Сложность обнаружения столкновения 251 и потребовало около 80 000 процессорных часов на суперкомпьютер с 256 Itanium 2 процессоров (эквивалентно 13 дням непрерывного использования компьютера).

17 августа 2004 г., на большой сессии CRYPTO 2004, предварительные результаты были объявлены Ван, Фэн, Лай и Ю о нападении на MD5, SHA-0 и другие хэш-функции. Сложность их атаки на SHA-0 равна 2.40, значительно лучше, чем атака Жу и другие.[53][54]

В феврале 2005 г. Сяоюнь Ван, Ицюнь Лиза Инь, и было объявлено, что Хунбо Ю может найти коллизии в SHA-0 за 239 операции.[29][55]

Еще одна атака в 2008 году с применением атака бумерангом снизил сложность поиска коллизий до 233.6, что, по оценкам, на среднем ПК занимает 1 час.[56]

В свете результатов SHA-0 некоторые эксперты[ВОЗ? ] предположил, что планы по использованию SHA-1 в новых криптосистемы следует пересмотреть. После того, как результаты CRYPTO 2004 были опубликованы, NIST объявил, что они планируют постепенно отказаться от использования SHA-1 к 2010 году в пользу вариантов SHA-2.[57]

Официальная проверка

Основная статья: Программа проверки криптографических модулей

Реализация всех функций безопасности, утвержденных FIPS, может быть официально подтверждена через Программа CMVP, совместно управляемыми Национальный институт стандартов и технологий (NIST) и Организация безопасности связи (CSE). Для неформальной проверки пакет для генерации большого количества тестовых векторов доступен для загрузки на сайте NIST; Однако полученная проверка не заменяет формальную проверку CMVP, которая требуется по закону для определенных приложений.

По состоянию на декабрь 2013 г., существует более 2000 проверенных реализаций SHA-1, 14 из которых способны обрабатывать сообщения с длиной в битах, не кратной восьми (см. Список валидации SHS ).

Примеры и псевдокод

Примеры хешей

Это примеры SHA-1 дайджесты сообщений в шестнадцатеричном и в Base64 двоичный в ASCII кодировка текста.

SHA1 («Быстрая коричневая лиса перепрыгивает через ленивого dog ") дает шестнадцатеричное значение: 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12gives Base64 двоичный в ASCII кодировка текста: L9ThxnotKPzthJ7hu3bnORuT6xI =

Даже небольшое изменение в сообщении с огромной вероятностью приведет к изменению многих битов из-за лавинный эффект. Например, изменение собака к винтик создает хеш с разными значениями для 81 из 160 бит:

SHA1 («Быстрая коричневая лиса перепрыгивает через ленивого cog ") дает шестнадцатеричный: de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3gives Base64 двоичный в ASCII кодировка текста: 3p8sf9JeGzr60 + haC9F9mxANtLM =

Хеш строки нулевой длины:

SHA1 ("") дает шестнадцатеричное значение: da39a3ee5e6b4b0d3255bfef95601890afd80709gives Base64 двоичный в ASCII кодировка текста: 2jmj7l5rSw0yVb / vlWAYkK / YBwk =

Псевдокод SHA-1

Псевдокод для алгоритма SHA-1:

Примечание 1: все переменные представляют собой 32-битные величины без знака и переносятся по модулю 2.32 при расчете, кроме        ml, длина сообщения, которая является 64-битной величиной, и        hh, дайджест сообщения, представляющий собой 160-битное количество.Примечание 2: все константы в этом псевдокоде находятся в прямой порядок байтов.        В каждом слове старший байт хранится в самой левой позиции байта.Инициализировать переменные:h0 = 0x67452301h1 = 0xEFCDAB89h2 = 0x98BADCFEh3 = 0x10325476h4 = 0xC3D2E1F0ml = длина сообщения в битах (всегда кратна количеству битов в символе).Предварительная обработка:добавьте к сообщению бит '1', например добавив 0x80, если длина сообщения кратна 8 битам. добавьте 0 ≤ k <512 битов '0', чтобы длина результирующего сообщения биты   является конгруэнтный до −64 ≡ 448 (mod 512) добавить ml, исходную длину сообщения, как 64-битное прямой порядок байтов целое число. Таким образом, общая длина кратна 512 битам.Обработайте сообщение последовательными 512-битными блоками:разбить сообщение на 512-битные кускиза каждый фрагмент разбивает фрагмент на шестнадцать 32-битных слов с прямым порядком байтов w [i], 0 ≤ i ≤ 15 Расписание сообщений: расширьте шестнадцать 32-битных слов до восьмидесяти 32-битных слов:    за я из От 16 до 79 Примечание 3: SHA-0 отличается отсутствием поворота влево.        w [i] = (w [i-3] xor w [i-8] xor w [i-14] xor w [i-16]) повернуть влево 1    Инициализировать хеш-значение для этого чанка:    а = h0 b = h1 c = h2 d = h3 e = h4 Основной цикл:[3][58]    за я из 0 к 79        если 0 ≤ я ≤ 19 тогда            f = (b и в) или же ((нет б) и г) к = 0x5A827999 иначе если 20 ≤ я ≤ 39 f = b xor c xor d k = 0x6ED9EBA1 иначе если 40 ≤ я ≤ 59 f = (b и в) или же (б и г) или же (c и г) k = 0x8F1BBCDC иначе если 60 ≤ я ≤ 79 f = b xor c xor d k = 0xCA62C1D6 temp = (a повернуть влево 5) + f + e + k + w [i] e = d d = c c = b повернуть влево 30 b = a a = температура Добавьте к результату хеш этого чанка:    h0 = h0 + a h1 = h1 + b h2 = h2 + c h3 = h3 + d h4 = h4 + eПроизведите окончательное значение хеш-функции (с прямым порядком байтов) как 160-битное число:hh = (h0 левый "шифт 128) или же (h1 левый "шифт 96) или же (h2 левый "шифт 64) или же (h3 левый "шифт 32) или же h4

Номер чч дайджест сообщения, который может быть записан в шестнадцатеричной системе счисления (основание 16).

Выбранные значения констант, использованные в алгоритме, были приняты равными ничего в моем рукаве номера:

  • Четыре круглые константы k 230 умноженные на квадратные корни из 2, 3, 5 и 10. Однако они были неправильно округлены до ближайшего целого числа вместо округления до ближайшего нечетного целого числа, с уравновешенными пропорциями нуля и единицы битов. Кроме того, выбор квадратного корня из 10 (который не является простым) сделал его общим множителем для двух других выбранных квадратных корней из простых чисел 2 и 5, с возможно используемыми арифметическими свойствами в последовательных раундах, снижая эффективность алгоритма по сравнению обнаружение коллизий на некоторых битах.
  • Первые четыре начальных значения для h0 через h3 такие же с алгоритмом MD5, а пятая и шестая (для h4 и h5) похожи. Однако они не были должным образом проверены на устойчивость к инверсии нескольких первых раундов, чтобы сделать вывод о возможных конфликтах на некоторых битах, которые могут использоваться для многоблочных дифференциальных атак.

Вместо формулировки из оригинального показанного документа FIPS PUB 180-1, следующие эквивалентные выражения могут использоваться для вычисления ж в основном цикле выше:

Побитовый выбор между c и d, контролируемый б.(0 ≤ я ≤ 19): f = d xor (б и (c xor г)) (вариант 1)(0 ≤ я ≤ 19): f = (b и в) xor ((нет б) и г) (вариант 2)(0 ≤ я ≤ 19): f = (b и в) xor ((нет б) и г) (вариант 3)(0 ≤ я ≤ 19): f = vec_sel (d, c, b) (вариант 4) Побитовая мажоритарная функция.(40 ≤ i ≤ 59): f = (b и в) или же (d и (б или же в)) (вариант 1)(40 ≤ i ≤ 59): f = (b и в) или же (d и (б xor в)) (вариант 2)(40 ≤ i ≤ 59): f = (b и в) xor (d и (б xor в)) (вариант 3)(40 ≤ i ≤ 59): f = (b и в) xor (d и (б xor в)) (вариант 4)(40 ≤ i ≤ 59): f = (b и в) xor (б и г) xor (c и г) (вариант 5)(40 ≤ я ≤ 59): f = vec_sel (c, b, c xor г) (вариант 6)

Было также показано[59] что для раундов 32–79 вычисление:

w [i] = (w [i-3] xor w [i-8] xor w [i-14] xor w [i-16]) повернуть влево 1

можно заменить на:

w [i] = (w [i-6] xor w [i-16] xor w [i-28] xor w [i-32]) повернуть влево 2

Это преобразование сохраняет все 64-битные операнды выровненными и, удаляя зависимость w [i] на w [i-3], позволяет эффективно реализовать SIMD с длиной вектора 4, например x86 SSE инструкции.

Сравнение функций SHA

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

Дальнейшая информация: Строительство Меркле-Дамгарда
Сравнение функций SHA
Алгоритм и вариантРазмер вывода
(биты)		Размер внутреннего состояния
(биты)		Размер блока
(биты)		РаундовОперацииБезопасность (в биты) против столкновения атакЕмкость
против атаки удлинения длины		Производительность на Skylake (медиана cpb )[60]Впервые опубликовано
длинные сообщения8 байт
MD5 (как ссылки)128128
(4 × 32)		51264И, Xor, Rot, Добавить (мод 232), Или же≤18
(обнаружены коллизии)[61]		04.9955.001992
SHA-0160160
(5 × 32)		51280И, Xor, Rot, Добавить (мод 232), Или же<34
(обнаружены коллизии)		0≈ SHA-1≈ SHA-11993
SHA-1<63
(обнаружены коллизии)[62]		3.4752.001995
SHA-2SHA-224
SHA-256		224
256		256
(8 × 32)		51264И, Xor, Rot, Добавить (мод 232), Или, Shr112
128		32
0		7.62
7.63		84.50
85.25		2004
2001
SHA-384
SHA-512		384
512		512
(8 × 64)		102480И, Xor, Rot, Добавить (мод 264), Или, Shr192
256		128 (≤ 384)
0[63]		5.12
5.06		135.75
135.50		2001
SHA-512/224
SHA-512/256		224
256		112
128		288
256		≈ SHA-384≈ SHA-3842012
SHA-3SHA3-224
SHA3-256
SHA3-384
SHA3-512		224
256
384
512		1600
(5 × 5 × 64)		1152
1088
832
576		24[64]И, Xor, Rot, Not112
128
192
256		448
512
768
1024		8.12
8.59
11.06
15.88		154.25
155.50
164.00
164.00		2015
Встряхивание128
Встряхивание256		d (произвольный)
d (произвольный)		1344
1088		мин (d/2, 128)
мин (d/2, 256)		256
512		7.08
8.59		155.25
155.50

Реализации

Ниже приведен список библиотек криптографии, поддерживающих SHA-1:

Аппаратное ускорение обеспечивается следующими расширениями процессора:

Смотрите также

Примечания

  1. ^ Стивенс, Марк (19 июня 2012 г.). Атаки на хеш-функции и приложения (PDF) (Тезис). Лейденский университет. HDL:1887/19093. ISBN  9789461913173. OCLC  795702954.
  2. ^ а б c Стивенс, Марк; Бурштейн, Эли; Карпман, Пьер; Альбертини, Анж; Марков, Ярик (2017). Кац, Джонатан; Шахам, Ховав (ред.). Первая коллизия для полного SHA-1 (PDF). Достижения в криптологии - КРИПТО 2017. Конспект лекций по информатике. 10401. Springer. С. 570–596. Дои:10.1007/978-3-319-63688-7_19. ISBN  9783319636870. Архивировано из оригинал (PDF) 15 мая 2018 г.. Получено 23 февраля, 2017. Сложить резюме – Блог по безопасности Google (23 февраля 2017 г.).
  3. ^ а б https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf
  4. ^ Шнайер, Брюс (18 февраля 2005 г.). «Шнайер о безопасности: криптоанализ SHA-1».
  5. ^ «NIST.gov - Отдел компьютерной безопасности - Ресурсный центр по компьютерной безопасности». Архивировано из оригинал на 2011-06-25. Получено 2019-01-05.
  6. ^ а б c d Стивенс1, Марк; Карпман, Пьер; Пейрин, Томас. "Шаппенинг: столкновения сторонних движений для SHA-1". Получено 2015-10-09.
  7. ^ Шнайер, Брюс (8 октября 2015 г.). "Столкновение со свободным движением SHA-1". Шнайер о безопасности.
  8. ^ «В общем алгоритме цифровой безопасности продемонстрирована критическая ошибка». media.ntu.edu.sg.
  9. ^ https://eprint.iacr.org/2020/014.pdf
  10. ^ Гудин, Дэн (04.05.2016). «Microsoft прекратит поддержку сертификатов SHA1 в ближайшие 4 месяца». Ars Technica. Получено 2019-05-29.
  11. ^ "Google откажется от шифрования SHA-1 в Chrome к 1 января 2017 г.". VentureBeat. 2015-12-18. Получено 2019-05-29.
  12. ^ «Конец SHA-1 в общедоступной сети». Блог о безопасности Mozilla. Получено 2019-05-29.
  13. ^ «CWI и Google объявляют о первом столкновении с отраслевым стандартом безопасности SHA-1». Получено 2017-02-23.
  14. ^ Баркер, Элейн (май 2020 г.). «Рекомендации по управлению ключами: Часть 1 - Общие, Таблица 3». NIST, Технический отчет: 56. Дои:10.6028 / NIST.SP.800-57pt1r5.
  15. ^ RSA FAQ по Capstone
  16. ^ Selvarani, R .; Ашватха, Кумар; Т. В. Суреш, Кумар (2012). Труды Международной конференции по достижениям в вычислительной технике. Springer Science & Business Media. п. 551. ISBN  978-81-322-0740-5.
  17. ^ Стандарт безопасного хеширования, публикация федеральных стандартов обработки информации FIPS PUB 180, Национальный институт стандартов и технологий, 11 мая 1993 г.
  18. ^ Крамер, Сэмюэл (11 июля 1994). «Предлагаемая редакция Федерального стандарта обработки информации (FIPS) 180, стандарта безопасного хеширования». Федеральный регистр.
  19. ^ fgrieu. "Где я могу найти описание хеш-алгоритма SHA-0?". Обмен криптографическим стеком.
  20. ^ Ресурсный центр по компьютерной безопасности Национального института стандартов и технологий, Политика NIST в отношении хэш-функций от марта 2006 г. В архиве 2014-01-02 в Wayback Machine, по состоянию на 28 сентября 2012 г.
  21. ^ Ресурсный центр по компьютерной безопасности Национального института стандартов и технологий, Политика NIST в отношении хеш-функций В архиве 2011-06-09 на Wayback Machine, по состоянию на 28 сентября 2012 г.
  22. ^ "Tech Talk: Линус Торвальдс на git". Получено 13 ноября, 2013.
  23. ^ Торвальдс, Линус. "Re: Начинаешь думать о ша-256?". marc.info. Получено 30 мая 2016.
  24. ^ Ван, Сяоюнь; Инь, Ицюнь Лиза; Ю, Хунбо (2005-08-14). Поиск коллизий в полном SHA-1 (PDF). Достижения в криптологии - CRYPTO 2005. Конспект лекций по информатике. 3621. Шпрингер, Берлин, Гейдельберг. С. 17–36. Дои:10.1007/11535218_2. ISBN  978-3-540-28114-6.
  25. ^ Сотиров Александр; Стивенс, Марк; Аппельбаум, Иаков; Ленстра, Арьен; Мольнар, Дэвид; Освик, Даг Арне; де Вегер, Бенн (30 декабря 2008 г.). «MD5 сегодня считается опасным: создание поддельного сертификата CA». Получено 29 марта, 2009.
  26. ^ «Сильные стороны Keccak - Дизайн и безопасность». Семейство губок Keccak. Команда Keccak. Получено 20 сентября 2015. В отличие от SHA-1 и SHA-2, Keccak не имеет недостатка в расширении длины, следовательно, не требует вложенной конструкции HMAC. Вместо этого можно выполнить вычисление MAC, просто добавив к сообщению ключ.
  27. ^ Нильс Фергюсон, Брюс Шнайер и Тадаёши Коно, специалист по криптографии, Джон Вили и сыновья, 2010 г. ISBN  978-0-470-47424-2
  28. ^ "Архив Cryptology ePrint: отчет 2005/010".
  29. ^ а б "SHA-1 Broken - Schneier on Security".
  30. ^ Атаки поиска коллизий на SHA1 В архиве 2005-02-19 в Wayback Machine, Массачусетский Институт Технологий
  31. ^ Лемос, Роберт. «Устранение бреши в безопасности». ZDNet.
  32. ^ «Новые результаты криптоаналитики против SHA-1 - Шнайер о безопасности».
  33. ^ Примечания к Wang et al. 263 Дифференциальный путь SHA-1
  34. ^ Де Канньер, Кристоф; Рехбергер, Кристиан (15 ноября 2006 г.). «Нахождение характеристик SHA-1: общие результаты и приложения». Достижения в криптологии - ASIACRYPT 2006. Конспект лекций по информатике. 4284. С. 1–20. Дои:10.1007/11935230_1. ISBN  978-3-540-49475-1.
  35. ^ "IAIK Krypto Group - Описание проекта поиска коллизий SHA-1". Архивировано из оригинал на 2013-01-15. Получено 2009-06-30.
  36. ^ «Коллизии для 72-шагового и 73-шагового SHA-1: улучшения в методе характеристик». Получено 2010-07-24.
  37. ^ "Поиск столкновений SHA-1 в Граце". Архивировано из оригинал на 2009-02-25. Получено 2009-06-30.
  38. ^ "heise online - IT-News, Nachrichten und Hintergründe". Heise онлайн.
  39. ^ "Расписание Crypto 2006 Rump".
  40. ^ Мануэль, Стефан. «Классификация и создание векторов помех для коллизионных атак против SHA-1» (PDF). Получено 2011-05-19. Цитировать журнал требует | журнал = (помощь)
  41. ^ Мануэль, Стефан (2011). «Классификация и генерация векторов возмущений для коллизионных атак против SHA-1». Конструкции, коды и криптография. 59 (1–3): 247–263. Дои:10.1007 / s10623-010-9458-9. S2CID  47179704. наиболее эффективный вектор возмущений - это Codeword2, о котором впервые сообщили Ютла и Паттхак.
  42. ^ Коллизии SHA-1 теперь 2 ^ 52
  43. ^ «Архив Cryptology ePrint: отчет 2009/259».
  44. ^ Криптоанализ MD5 и SHA-1
  45. ^ «Когда мы увидим коллизии для SHA-1? - Шнайер о безопасности».
  46. ^ «Хостинг проектов Google».
  47. ^ Марк Стивенс (19.06.2012). «Атаки на хеш-функции и приложения» (PDF). Докторская диссертация.
  48. ^ Леурент, Гаэтан; Пейрин, Томас (2019). «От коллизий к применению коллизий с выбранным префиксом к полному SHA-1» (PDF). Достижения в криптологии - EUROCRYPT 2019. Конспект лекций по информатике. 11478. С. 527–555. Дои:10.1007/978-3-030-17659-4_18. ISBN  978-3-030-17658-7.
  49. ^ Гаэтан Леурент; Томас Пейрин (24.04.2019). «От коллизий к коллизиям с выбранным префиксом - применение к полному SHA-1» (PDF). Еврокрипт 2019.
  50. ^ Гаэтан Леурент; Томас Пейрин (05.01.2020). «SHA-1 - это коллизия первого выбранного префикса Shambles в SHA-1 и приложении к сети доверия PGP» (PDF). Cryptology ePrint Archive, Отчет 2020/014.
  51. ^ Шабо, Флоран; Жу, Антуан (1998). Krawczyk, Хьюго (ред.). Дифференциальные коллизии в SHA-0 (PDF). Достижения в криптологии - КРИПТО 1998. Конспект лекций по информатике. 1462. Springer. С. 56–71. CiteSeerX  10.1.1.138.5141. Дои:10.1007 / bfb0055720. ISBN  9783540648925.
  52. ^ Бихам, Эли; Чен, Рафи. «Ближайшие столкновения SHA-0» (PDF).
  53. ^ «Репортаж из Crypto 2004». Архивировано из оригинал на 21.08.2004.
  54. ^ Гриё, Франсуа (18 августа 2004 г.). «Re: Есть какие-нибудь предварительные новости о криптовалютной сессии?». Группа новостей: sci.crypt. Событие происходит в 05:06:02 +0200. Usenet:  [email protected].
  55. ^ Эффективные атаки поиска коллизий на SHA-0 В архиве 2005-09-10 на Wayback Machine, Шаньдунский университет
  56. ^ Мануэль, Стефан; Пейрин, Томас (11 февраля 2008 г.). «Коллизии на SHA-0 за один час» (PDF). Быстрое программное шифрование. Конспект лекций по информатике. 5086. С. 16–35. Дои:10.1007/978-3-540-71039-4_2. ISBN  978-3-540-71038-7.
  57. ^ «Краткие комментарии NIST о недавних криптоаналитических атаках на функции безопасного хеширования и непрерывную безопасность, обеспечиваемую SHA-1» (PDF). Архивировано из оригинал (PDF) на 2011-06-04. Получено 2010-05-05.
  58. ^ «RFC 3174 - US Secure Hash Algorithm 1 (SHA1)».
  59. ^ Локтюхин, Макс; Фаррел, Кэти (31.03.2010), «Повышение производительности алгоритма безопасного хеширования (SHA-1)», База знаний по программному обеспечению Intel, получено 2010-04-02
  60. ^ «Таблица измерений». bench.cr.yp.to.
  61. ^ Тао, Се; Лю, Фаньбао; Фэн, Дэнго (2013). Быстрая атака коллизией на MD5 (PDF). Архив криптологии ePrint (Технический отчет). МАКР.
  62. ^ Стивенс, Марк; Бурштейн, Эли; Карпман, Пьер; Альбертини, Анж; Марков, Ярик. Первая коллизия для полного SHA-1 (PDF) (Технический отчет). Google Research. Сложить резюме – Блог по безопасности Google (23 февраля 2017 г.).
  63. ^ Без усечения известно полное внутреннее состояние хэш-функции, независимо от сопротивления столкновениям. Если вывод усечен, удаленная часть состояния должна быть отыскана и найдена до того, как хэш-функция может быть возобновлена, что позволит продолжить атаку.
  64. ^ «Семейство функций губки Keccak». Получено 2016-01-27.
  65. ^ "Расширение криптографии для процессора ARM Cortex-A53 MPCore. Техническое руководство".

Рекомендации

внешняя ссылка