ША-1

Безопасные алгоритмы хеширования
Концепции
хэш-функции , SHA , DSA
Основные стандарты
ША-0 , ША-1 , ША-2 , ША-3

ША-1

Общий
Дизайнеры	Агентство национальной безопасности
Впервые опубликовано	1993 (ША-0), 1995 (ША-1)
Ряд	( ША-0 ), ША-1, ША-2 , ША-3
Сертификация	FIPS PUB 180-4, КРИПТРЕК (контролируемый)
Деталь шифрования
Размеры дайджеста	160 бит
Размеры блоков	512 бит
Структура	Строительство Меркле – Дамгорда
Раунды	80
Лучший публичный криптоанализ
Атака Марка Стивенса в 2011 году может привести к хеш-коллизиям со сложностью от 2 60.3 и 2 65.3 операции. Первое публичное столкновение было опубликовано 23 февраля 2017 года. SHA-1 подвержен атакам с расширением длины .

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

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

Все основные поставщики веб-браузеров SHA-1 прекратили прием SSL-сертификатов в 2017 году. В феврале 2017 года CWI Amsterdam и Google объявили, что они провели коллизионную атаку на SHA-1, опубликовав два разных PDF-файла, которые создали один и тот же хэш SHA-1. Однако SHA-1 по-прежнему безопасен для HMAC .

Microsoft прекратила поддержку подписи кода SHA-1 для Центра обновления Windows 3 августа 2020 г. что также фактически прекратило работу серверов обновлений для версий Windows , которые не были обновлены до SHA-2, таких как Windows 2000 до Vista , а также версий Windows Server от Windows 2000 Server до Server 2003 .

Разработка

Одна итерация функции сжатия SHA-1:

• A, B, C, D и E — 32-битные слова состояния;
• F — нелинейная функция, которая меняется;
• ⁠ $\lll _{n}$⁠ обозначает поворот левого бита на n мест;
• n варьируется для каждой операции;
• W _t — расширенное слово сообщения раунда t ;
• K _t — константа раунда t раунда ;
• обозначает сложение по модулю 2 ³² .

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

SHA-1 был разработан в рамках проекта правительства США Capstone . Исходная спецификация алгоритма была опубликована в 1993 году под названием Secure Hash Standard , FIPS PUB 180, агентством по стандартизации правительства США NIST (Национальный институт стандартов и технологий). Эту версию теперь часто называют SHA-0 . Он был отозван АНБ вскоре после публикации и заменен пересмотренной версией, опубликованной в 1995 году в FIPS PUB 180-1 и обычно обозначаемой SHA-1 . SHA-1 отличается от SHA-0 лишь одним побитовым вращением в расписании сообщений своей функции сжатия . По данным АНБ, это было сделано для исправления ошибки в исходном алгоритме, которая снижала его криптографическую безопасность, но никаких дополнительных объяснений они не предоставили. Общедоступные методы действительно продемонстрировали компрометацию 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 года». , хотя позже это было смягчено, чтобы позволить использовать SHA-1 для проверки старых цифровых подписей и отметок времени.

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

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

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

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

Если у вас поврежден диск, если у вас поврежден DRAM, если у вас вообще есть какие-либо проблемы, Git их заметит. Это не вопрос , это гарантия. У вас могут быть люди, которые пытаются быть злонамеренными. Им это не удастся. [...] Никто не смог взломать SHA-1, но дело в том, что SHA-1, с точки зрения Git, даже не является функцией безопасности. Это чисто проверка целостности. Компоненты безопасности находятся в другом месте, поэтому многие люди предполагают, что, поскольку Git использует SHA-1, а SHA-1 используется для криптографически безопасных вещей, они думают: «Хорошо, это огромная функция безопасности». Это не имеет никакого отношения к безопасности, это просто лучший хэш, который вы можете получить. ...

Я гарантирую вам, что если вы поместите свои данные в Git, вы можете быть уверены в том, что пять лет спустя, после того, как они были преобразованы с вашего жесткого диска в DVD с использованием какой-либо новой технологии, и вы скопировали их вместе, пять лет спустя вы сможете убедиться, что данные, которые вы получаете обратно, — это те же самые данные, которые вы ввели. [...]

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

Однако Git не требует второго сопротивления прообраза SHA-1 в качестве функции безопасности, поскольку он всегда предпочитает сохранять самую раннюю версию объекта в случае конфликта, не позволяя злоумышленнику тайно перезаписать файлы. Известные атаки (по состоянию на 2020 год) также не сломили сопротивление второго прообраза.

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

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

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

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

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

ША-0

На CRYPTO 98 два французских исследователя, Флоран Шабо и Антуан Жу , представили атаку на SHA1: коллизии можно найти со сложностью 2. ⁶¹ , меньше 2 ⁸⁰ для идеальной хэш-функции того же размера.

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

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

17 августа 2004 года на конференции CRYPTO 2004 Ван , Фэн, Лай и Ю объявили предварительные результаты атаки на MD5 , SHA-0 и другие хэш-функции. Сложность их атаки на SHA-0 равна 2. ⁴⁰ , что значительно лучше, чем атака Joux et al.

В феврале 2005 года было объявлено об атаке Сяоюнь Вана , Ицюнь Лизы Инь и Хунбо Юй, которая могла обнаружить коллизии в SHA-0 в 2 ³⁹ операции.

Еще одна атака в 2008 году с использованием атаки бумеранга снизила сложность обнаружения столкновений до 2. ^33.6 , что, по оценкам, занимало 1 час на среднем ПК с 2008 года.

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

Атаки

В начале 2005 года Винсент Реймен и Элизабет Освальд опубликовали атаку на сокращенную версию SHA-1 – 53 раунда из 80 – которая обнаруживает коллизии с вычислительными затратами менее 2 ⁸⁰ операции.

В феврале 2005 года было объявлено о нападении Сяоюнь Вана , Ицюнь Лизы Инь и Хунбо Юя. Атаки могут обнаруживать коллизии в полной версии SHA-1, требуя менее двух ⁶⁹ операции. ( Для поиска методом грубой силы потребуется 2 ⁸⁰ операции.)

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

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

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

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

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

В 2008 году методология атаки Стефана Мануэля сообщила о хэш-коллизиях с оценочной теоретической сложностью 2 ⁵¹ до 2 ⁵⁷ операции. Однако позже он отказался от этого утверждения, обнаружив, что локальные пути столкновений на самом деле не были независимыми, и, наконец, указал в качестве наиболее эффективного вектора столкновений, который уже был известен до этой работы.

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

Одну атаку на SHA-1 совершил Марк Стивенс. с ориентировочной стоимостью 2,77 миллиона долларов (2012 г.) на взлом одного хэш-значения путем аренды мощности ЦП у облачных серверов. Стивенс разработал эту атаку в проекте под названием HashClash. реализация атаки по дифференциальному пути. 8 ноября 2010 года он заявил, что у него была полностью работающая атака, близкая к столкновению, против полного SHA-1, работающего с оценочной сложностью, эквивалентной 2. ^57.5 Сжатие SHA-1. По его оценкам, эту атаку можно расширить до полного столкновения со сложностью около 2 ⁶¹ .

ШАПЕНИНГ

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

Метод был основан на их более ранней работе, а также на методе ускорения вспомогательных путей (или бумерангов) от Жу и Пейрина и использовании высокопроизводительных и экономичных графических карт от Nvidia . Коллизия была обнаружена в кластере из 16 узлов с 64 видеокартами. Авторы подсчитали, что подобную коллизию можно было бы обнаружить, купив 2000 долларов США графического времени на EC2 .

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

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

23 февраля 2017 года CWI (Centrum Wiskunde & Informatica) и Google объявили об атаке SHAttered , в ходе которой они создали два разных PDF-файла с одинаковым хешем SHA-1 примерно за 2 секунды. ^63.1 Оценки SHA-1. Эта атака примерно в 100 000 раз быстрее, чем перебор коллизии SHA-1 с атакой дня рождения , которая, по оценкам, заняла 2 ⁸⁰ Оценки SHA-1. Для атаки потребовалась «вычислительная мощность, эквивалентная 6500 годам однопроцессорных вычислений и 110 годам однопроцессорных вычислений».

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

24 апреля 2019 года в статье Гаэтана Леурана и Томаса Пейрина, представленной на Eurocrypt 2019, было описано усовершенствование ранее использовавшейся атаки с использованием лучшего выбранного префикса в функциях дайджеста, подобных Меркле – Дамгорду, на основе Дэвиса – Мейера блочных шифров . Благодаря этим улучшениям этот метод способен обнаруживать конфликты выбранных префиксов примерно за 2 ⁶⁸ Оценки SHA-1. Это примерно в 1 миллиард раз быстрее (и теперь может использоваться для многих целевых атак благодаря возможности выбора префикса, например, вредоносного кода или поддельных идентификационных данных в подписанных сертификатах), чем предыдущая атака2. ^77.1 оценки (но без выбранного префикса, что было непрактично для большинства целевых атак, поскольку обнаруженные коллизии были почти случайными) и достаточно быстр, чтобы быть практичным для изобретательных злоумышленников, требуя около 100 000 долларов на облачную обработку. Этот метод также способен находить коллизии выбранного префикса в функции MD5 , но со сложностью 2 ^46.3 не превосходит предшествующий наилучший доступный метод на теоретическом уровне (2 ³⁹ ), хотя потенциально на практическом уровне (≤2 ⁴⁹ ). Для этой атаки требуется память более 500 ГБ.

5 января 2020 года авторы опубликовали улучшенную атаку под названием «shambles». В этой статье они демонстрируют атаку коллизией выбранного префикса со сложностью 2. ^63.4 , что на момент публикации будет стоить 45 тысяч долларов США за каждое сгенерированное столкновение.

Официальная валидация

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

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

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

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

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

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

• SHA1("The quick brown fox jumps over the lazy dog")
  • Выведено шестнадцатеричное число: 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
  • Выведенный двоичный файл Base64 в текстовую кодировку ASCII : L9ThxnotKPzthJ7hu3bnORuT6xI=

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

• SHA1("The quick brown fox jumps over the lazy cog")
  • Выведено шестнадцатеричное число: de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3
  • Выведенный двоичный файл Base64 в текстовую кодировку ASCII : 3p8sf9JeGzr60+haC9F9mxANtLM=

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

• SHA1("")
  • Выведено шестнадцатеричное число: da39a3ee5e6b4b0d3255bfef95601890afd80709
  • Выведенный двоичный файл Base64 в текстовую кодировку ASCII : 2jmj7l5rSw0yVb/vlWAYkK/YBwk=

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

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

Note 1: All variables are unsigned 32-bit quantities and wrap modulo 232 when calculating, except for
        ml, the message length, which is a 64-bit quantity, and
        hh, the message digest, which is a 160-bit quantity.
Note 2: All constants in this pseudo code are in big endian.
        Within each word, the most significant byte is stored in the leftmost byte position

Initialize variables:

h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0

ml = message length in bits (always a multiple of the number of bits in a character).

Pre-processing:
append the bit '1' to the message e.g. by adding 0x80 if message length is a multiple of 8 bits.
append 0 ≤ k < 512 bits '0', such that the resulting message length in bits
   is congruent to −64 ≡ 448 (mod 512)
append ml, the original message length in bits, as a 64-bit big-endian integer. 
   Thus, the total length is a multiple of 512 bits.

Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
    break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15

    Message schedule: extend the sixteen 32-bit words into eighty 32-bit words:
    for i from 16 to 79
        Note 3: SHA-0 differs by not having this leftrotate.
        w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

    Initialize hash value for this chunk:
    a = h0
    b = h1
    c = h2
    d = h3
    e = h4

    Main loop:
    for i from 0 to 79
        if 0 ≤ i ≤ 19 then
            f = (b and c) or ((not b) and d)
            k = 0x5A827999
        else if 20 ≤ i ≤ 39
            f = b xor c xor d
            k = 0x6ED9EBA1
        else if 40 ≤ i ≤ 59
            f = (b and c) or (b and d) or (c and d) 
            k = 0x8F1BBCDC
        else if 60 ≤ i ≤ 79
            f = b xor c xor d
            k = 0xCA62C1D6

        temp = (a leftrotate 5) + f + e + k + w[i]
        e = d
        d = c
        c = b leftrotate 30
        b = a
        a = temp

    Add this chunk's hash to result so far:
    h0 = h0 + a
    h1 = h1 + b 
    h2 = h2 + c
    h3 = h3 + d
    h4 = h4 + e

Produce the final hash value (big-endian) as a 160-bit number:
hh = (h0 leftshift 128) or (h1 leftshift 96) or (h2 leftshift 64) or (h3 leftshift 32) or h4

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

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

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

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

Bitwise choice between c and d, controlled by b.
(0  ≤ i ≤ 19): f = d xor (b and (c xor d))                (alternative 1)
(0  ≤ i ≤ 19): f = (b and c) or ((not b) and d)           (alternative 2)
(0  ≤ i ≤ 19): f = (b and c) xor ((not b) and d)          (alternative 3)
(0  ≤ i ≤ 19): f = vec_sel(d, c, b)                       (alternative 4)
 [premo08]
Bitwise majority function.
(40 ≤ i ≤ 59): f = (b and c) or (d and (b or c))          (alternative 1)
(40 ≤ i ≤ 59): f = (b and c) or (d and (b xor c))         (alternative 2)
(40 ≤ i ≤ 59): f = (b and c) xor (d and (b xor c))        (alternative 3)
(40 ≤ i ≤ 59): f = (b and c) xor (b and d) xor (c and d)  (alternative 4)
(40 ≤ i ≤ 59): f = vec_sel(c, b, c xor d)                 (alternative 5)

Также было показано что для раундов 32–79 вычисление:

w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

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

w[i] = (w[i-6] xor w[i-16] xor w[i-28] xor w[i-32]) leftrotate 2

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

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

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

Дополнительная информация: строительство Меркле – Дамгорда.

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

Алгоритм и вариант		Выходной размер (биты)	Внутренний размер штата (биты)	Размер блока (биты)	Раунды	Операции	Защита от столкновений (биты)	Защита от атак расширения длины (биты)	Производительность на Skylake (медиана cpb )		Впервые опубликовано
									Длинные сообщения	8 байт
MD5 (для справки)		128	128 (4 × 32)	512	4 (16 операций в каждом раунде)	И, Xor, Or, Rot, Add (мод 2 32 )	≤ 18 (обнаружены столкновения)	0	4.99	55.00	1992
ША-0		160	160 (5 × 32)	512	80	И, Xor, Or, Rot, Add (мод 2 32 )	< 34 (обнаружены столкновения)	0	≈ ША-1	≈ ША-1	1993
ША-1							< 63 (обнаружены столкновения)		3.47	52.00	1995
ША-2	ША-224 ША-256	224 256	256 (8 × 32)	512	64	И, Ксор, Или, Рот, Шр, Адд (мод 2 32 )	112 128	32 0	7.62 7.63	84.50 85.25	2004 2001
	ША-384	384	512 (8 × 64)	1024	80	И, Ксор, Или, Рот, Шр, Адд (мод 2 64 )	192	128	5.12	135.75	2001
	ША-512	512					256	0	5.06	135.50	2001
	ША-512/224 ША-512/256	224 256					112 128	288 256	≈ ША-384	≈ ША-384	2012
ША-3	SHA3-224 SHA3-256 SHA3-384 SHA3-512	224 256 384 512	1600 (5 × 5 × 64)	1152 1088 832 576	24	И, Ксор, Гниль, Не	112 128 192 256	448 512 768 1024	8.12 8.59 11.06 15.88	154.25 155.50 164.00 164.00	2015
	SHAKE128 SHAKE256	д (произвольно) д (произвольно)		1344 1088			мин( д /2, 128) мин( д /2, 256)	256 512	7.08 8.59	155.25 155.50

Реализации

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

• Ботан
• Надувной замок
• криптлиб
• Крипто++
• Libgcrypt
• Мбед ТЛС
• Крапива
• LibreSSL
• OpenSSL
• ГнуTLS

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

• Расширения Intel SHA : доступны на некоторых процессорах Intel и AMD x86.
• ВИА PadLock
• IBM z/Architecture : доступен с 2003 года как часть расширения Message-Security-Assist Extension.

Меры противодействия столкновениям

После SHAttered Марк Стивенс и Дэн Шумоу опубликовали «sha1collisiondetection» (SHA-1CD), вариант SHA-1, который обнаруживает атаки коллизий и изменяет вывод хеш-функции при их обнаружении. Ложноположительный уровень равен 2. ^-90 . SHA-1CD используется GitHub с марта 2017 года, а git — с версии 2.13.0 от мая 2017 года.

См. также

• Сравнение криптографических хэш-функций
• Сводка безопасности хеш-функции
• Международная ассоциация криптологических исследований
• Стандарт безопасного хеширования

Ссылки

• Эли Бихам , Рафи Чен, Почти коллизии SHA-0, Архив электронной печати криптологии, отчет 2004/146, 2004 г. (появился на CRYPTO 2004), IACR.org
• Сяоюнь Ван , Хунбо Ю и Ицюнь Лиза Инь, Эффективные атаки поиска коллизий на SHA-0 , Crypto 2005
• Сяоюнь Ван , Ицюнь Лиза Инь и Хунбо Ю, Поиск коллизий в полном SHA-1 , Crypto 2005
• Анри Жильбер , Хелена Хандшу : Анализ безопасности SHA-256 и сестер . Избранные области криптографии , 2003 г.: стр. 175–193.
• Иллюстрированное руководство по криптографическим хешам
• «Предлагаемая редакция Федерального стандарта обработки информации (FIPS) 180, Стандарт безопасного хеширования» . Федеральный реестр . 59 (131): 35317–35318. 11 июля 1994 г. Проверено 26 апреля 2007 г.
• А. Силардо, Л. Эспозито, А. Веньеро, А. Маццео, В. Бельтран, Э. Аюгаде, Приложение HPC на базе CellBE для анализа уязвимостей в криптографических хеш-функциях , Международная конференция High Performance Computing and Communication, август 2010 г.

Внешние ссылки

• CSRC Cryptographic Toolkit - Официальный сайт NIST по стандарту Secure Hash
• FIPS 180-4: Стандарт безопасного хеширования (SHS)
• RFC 3174 (с примером реализации C)
• Интервью с Ицюнь Лизой Инь по поводу атаки на SHA-1
• Объяснение успешных атак на SHA-1 (3 страницы, 2006 г.)
• Криптографические исследования – вопросы и ответы по хеш-коллизиям
• SHA-1 в Керли
• о SHA-1 (1 час 18 минут) на YouTube. Лекция Кристофа Паара Архивировано 24 апреля 2017 г. в Wayback Machine.