Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Безопасные алгоритмы хеширования
Концепции
хэш-функции  · 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 PUB 180-4, CRYPTREC (отслеживается)
Деталь шифра
Размеры дайджеста160 бит
Размеры блоков512 бит
СтруктураСтроительство Меркле-Дамгарда
Раундов80
Лучший публичный криптоанализ
Атака Марка Стивенса 2011 года может вызвать коллизии хэшей со сложностью от 2 60,3 до 2 65,3 операций. [1] Первая публичная коллизия была опубликована 23 февраля 2017 года. [2] SHA-1 подвержен атакам с расширением длины .

В криптографии , SHA-1 ( Secure Hash Algorithm 1 ) является криптографической хэш - функция , которая принимает входной сигнал и производит 160- бит (20- байт ) хэш - значение , известное как Message Digest - как правило , вынесенное в шестнадцатеричном числа, длиной 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 актуальна там, где он используется для цифровых подписей .

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

Microsoft прекратила поддержку подписи кода SHA-1 для Центра обновления Windows 7 августа 2020 г.

Развитие [ править ]

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




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

SHA-1 был разработан в рамках проекта Capstone правительства США . [15] Первоначальная спецификация алгоритма была опубликована в 1993 году под названием Secure Hash Standard , 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 году. См. #Attacks

Приложения [ править ]

Криптография [ править ]

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

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 использовались в качестве основы блочных шифров SHACAL .

Целостность данных [ править ]

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

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

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

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

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

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

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

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

Атаки [ править ]

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

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

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

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

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

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

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

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

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

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

Шаппенинг [ править ]

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

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

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

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

23 февраля 2017 года КРИ (Центр Wiskunde и Informatica) и Google объявили о расколотой атаке, в котором они генерируемую два различных PDF - файлы с тем же SHA-1 хэшем в примерно 2 63,1 оценках SHA-1. Эта атака примерно в 100000 раз быстрее, чем грубое форсирование коллизии SHA-1 с атакой дня рождения , которая, по оценкам, потребовала 2 80 оценок SHA-1. Атака потребовала «вычислительной мощности, эквивалентной 6500 годам вычислений на одном процессоре и 110 годам вычислений на одном графическом процессоре». [2]

Атака на день рождения - первая практическая атака с выбранным префиксом [ править ]

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

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

SHA-0 [ править ]

На CRYPTO 98 два французских исследователя, Флоран Шабо и Антуан Жу , представили атаку на SHA-0: коллизии могут быть обнаружены со сложностью 2 61 , меньшей, чем 2 80 для идеальной хеш-функции того же размера. [51]

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

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

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

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

Другая атака в 2008 году с применением атаки бумерангом снизила сложность обнаружения коллизий до 2 33,6 , что, по оценкам, заняло 1 час на среднем ПК с 2008 года [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 ( «быстрая коричневая лиса прыгает через ленивый г OG»)дает шестнадцатеричный: 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12передает двоичный код Base64 в текстовую кодировку ASCII : L9ThxnotKPzthJ7hu3bnORuT6xI =

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

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

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

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

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

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

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

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

Побитовый выбор между c и d , управляемый b .
(0 ≤ i ≤ 19): f = d xor (b and (c xor d))  (альтернатива 1)
(0 ≤ i ≤ 19): f = (b и c) xor (( не b) и d)  ( альтернатива 2)
(0 ≤ i ≤ 19): f = (b и c) xor (( не b) и d)  (альтернатива 3)
(0 ≤ i ≤ 19): f = vec_sel (d, c, b)  ( альтернатива 4) Побитовая мажоритарная функция.
(40 ≤ i ≤ 59): f = (b и c) или (d и (b или c))  (вариант 1)
(40 ≤ i ≤ 59): f = (b и c) или (d и (b xor c))  (альтернатива 2)
(40 ≤ i ≤ 59): f = (b и c) xor (d и (b xor c))  (альтернатива 3)
(40 ≤ i ≤ 59): f = (b и c) xor (d и (b xor c))  (вариант 4)(40 ≤ i ≤ 59): f = (b и c) xor (b и d) xor (c и d) (вариант 5)
(40 ≤ i ≤ 59): f = vec_sel (c, b, c xor d ) (вариант 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]on w[i-3], обеспечивает эффективную реализацию SIMD с длиной вектора 4, как инструкции x86 SSE .

Сравнение функций SHA [ править ]

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

Дополнительная информация: Строительство Меркле-Дамгарда.
Сравнение функций SHA
  • Посмотреть
  • разговаривать
  • редактировать
Алгоритм и вариантРазмер вывода
(бит)		Размер внутреннего состояния
(биты)		Размер блока
(бит)		РаундовОперацииБезопасность (в  битах) от атак столкновенияСпособность
противостоять атакам увеличения длины		Производительность на Skylake (средняя цена за клик ) [60]Впервые опубликовано
Длинные сообщения8 байт
MD5 (как ссылка)128128
(4 × 32)		51264And, Xor, Rot, Add (mod 2 32 ), Или≤18
(обнаружено коллизий) [61]		04,9955.001992 г.
SHA-0160160
(5 × 32)		51280And, Xor, Rot, Add (mod 2 32 ), Или<34
(обнаружены коллизии)		0≈ SHA-1≈ SHA-11993 г.
SHA-1<63
(обнаружены коллизии) [62]		3,4752,001995 г.
SHA-2SHA-224
SHA-256		224
256		256
(8 × 32)		51264And, Xor, Rot, Add (mod 2 32 ), Or, Shr112
128		32
0		7,62
7,63		84,50
85,25		2004
2001
SHA-384
SHA-512		384
512		512
(8 × 64)		102480And, Xor, Rot, Add (mod 2 64 ), Or, 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 г.
SHAKE128
SHAKE256		d (произвольно)
d (произвольно)		1344
1088		мин ( д / 2, 128)
мин ( д / 2, 256)		256
512		7,08
8,59		155,25
155,50

Реализации [ править ]

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

  • Ботан
  • Надувной Замок
  • cryptlib
  • Крипто ++
  • Libgcrypt
  • Мбед TLS
  • Крапива
  • LibreSSL
  • OpenSSL
  • GnuTLS
  • wolfSSL

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

  • Расширения Intel SHA : доступны на некоторых процессорах Intel и AMD x86.
  • ЧЕРЕЗ PadLock
  • Расширения криптографии ARMv8 [65]

См. Также [ править ]

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

Заметки [ править ]

  1. ↑ Стивенс, Марк (19 июня 2012 г.). Атаки на хеш-функции и приложения (PDF) (Диссертация). Лейденский университет . hdl : 1887/19093 . ISBN 9789461913173. OCLC  795702954 .
  2. ^ a b c Стивенс, Марк ; Бурштейн, Эли ; Карпман, Пьер; Альбертини, Анж; Марков, Ярик (2017). Кац, Джонатан ; Шахам, Ховав (ред.). Первое столкновение для полного SHA-1 (PDF) . Достижения в криптологии - CRYPTO 2017. Конспект лекций по информатике . 10401 . Springer . С. 570–596. DOI : 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 . Проверено 5 января 2019 .
  6. ^ а б в г Стивенс1, Марк; Карпман, Пьер; Пейрин, Томас. «Шаппенинг: свободные столкновения для SHA-1» . Проверено 9 октября 2015 .
  7. Рианна Шнайер, Брюс (8 октября 2015 г.). «Столкновение со свободным движением SHA-1» . Шнайер о безопасности .
  8. ^ «Критический недостаток, продемонстрированный в общем алгоритме цифровой безопасности» . media.ntu.edu.sg .
  9. ^ Гаэтан Леурент; Томас Пейрин (2020-01-08). «SHA-1 - это руины» (PDF) .
  10. ^ Гудин, Дэн (2016-05-04). «Microsoft прекращает поддержку сертификатов SHA1 в ближайшие 4 месяца» . Ars Technica . Проверено 29 мая 2019 .
  11. ^ "Google откажется от шифрования SHA-1 в Chrome до 1 января 2017 г." . VentureBeat . 2015-12-18 . Проверено 29 мая 2019 .
  12. ^ «Конец SHA-1 в общедоступной сети» . Блог по безопасности Mozilla . Проверено 29 мая 2019 .
  13. ^ «CWI, Google объявляет о первом столкновении с отраслевым стандартом безопасности SHA-1» . Проверено 23 февраля 2017 .
  14. ↑ Баркер, Элейн (май 2020 г.). «Рекомендации по управлению ключами: Часть 1 - Общие, Таблица 3» . NIST, технический отчет : 56. doi : 10.6028 / NIST.SP.800-57pt1r5 .
  15. ^ Часто задаваемые вопросы RSA по Capstone
  16. ^ Selvarani, R .; Ашватха, Кумар; ТВ Суреш, Кумар (2012). Труды международной конференции по достижениям в вычислительной технике . Springer Science & Business Media. п. 551. ISBN. 978-81-322-0740-5.
  17. ^ Стандарт безопасного хеширования, публикация федеральных стандартов обработки информации FIPS PUB 180 , Национальный институт стандартов и технологий, 11 мая 1993 г.
  18. Перейти ↑ Kramer, Samuel (11 июля 1994). «Предлагаемая редакция Федерального стандарта обработки информации (FIPS) 180, Стандарт безопасного хеширования» . Федеральный регистр .
  19. ^ fgrieu. «Где я могу найти описание хеш-алгоритма SHA-0?» . Обмен криптографическим стеком .
  20. ^ Национальный институт стандартов и технологий Ресурсный центр компьютерной безопасности, Политика NIST в отношении хэш-функций от марта 2006 г. Архивировано 2 января 2014 г. на Wayback Machine , по состоянию на 28 сентября 2012 г.
  21. ^ Национальный институт стандартов и технологий Ресурсный центр по компьютерной безопасности, Политика NIST в отношении хэш-функций, Архивная копия от 09.06.2011 на 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. DOI : 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. ^ Нильс Фергюсон, Брюс Шнайер и Тадаёши Коно, Cryptography Engineering , John Wiley & Sons, 2010. ISBN 978-0-470-47424-2 
  28. ^ «Архив криптологии ePrint: отчет 2005/010» .
  29. ^ a b «SHA-1 Broken - Schneier on Security» .
  30. ↑ Collision Search Attacks на SHA1. Архивировано 19 февраля2005 г. в Wayback Machine , Массачусетский технологический институт.
  31. ^ Лемос, Роберт. «Устранение бреши в безопасности» . ZDNet .
  32. ^ «Новые результаты криптоанализа против SHA-1 - Шнайер о безопасности» .
  33. ^ Примечания к Wang et al. 2 63 SHA-1 Дифференциальный тракт
  34. ^ Де Канньер, Кристоф; Рехбергер, Кристиан (15 ноября 2006 г.). «Поиск характеристик SHA-1: общие результаты и приложения». Достижения в криптологии - ASIACRYPT 2006 . Конспект лекций по информатике. 4284 . С. 1–20. DOI : 10.1007 / 11935230_1 . ISBN 978-3-540-49475-1.
  35. ^ "IAIK Krypto Group - Описание проекта поиска столкновений SHA-1" . Архивировано из оригинала на 2013-01-15 . Проверено 30 июня 2009 .
  36. ^ «Столкновения для 72-шагового и 73-шагового SHA-1: Улучшения в методе характеристик» . Проверено 24 июля 2010 .
  37. ^ "Поиск столкновений SHA-1 Грац" . Архивировано из оригинала на 2009-02-25 . Проверено 30 июня 2009 .
  38. ^ "heise online - IT-News, Nachrichten und Hintergründe" . heise онлайн .
  39. ^ "График Крипто 2006 Rump" .
  40. ^ Мануэль, Стефан. «Классификация и генерация векторов нарушений для коллизионных атак против SHA-1» (PDF) . Проверено 19 мая 2011 . Цитировать журнал требует |journal=( помощь )
  41. ^ Мануэль, Стефан (2011). «Классификация и генерация векторов возмущений для коллизионных атак против SHA-1». Конструкции, коды и криптография . 59 (1–3): 247–263. DOI : 10.1007 / s10623-010-9458-9 . S2CID 47179704 .  наиболее эффективным вектором возмущения является Codeword2, о котором впервые сообщили Ютла и Паттхак.
  42. ^ Коллизии SHA-1 теперь 2 ^ 52
  43. ^ «Cryptology ePrint Archive: Report 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. DOI : 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, отчет 2020/014 .
  51. ^ Шабо, Флоран; Жу, Антуан (1998). Krawczyk, Хьюго (ред.). Дифференциальные коллизии в SHA-0 (PDF) . Достижения в криптологии - CRYPTO 1998. Конспект лекций по информатике . 1462 . Springer . С. 56–71. CiteSeerX 10.1.1.138.5141 . DOI : 10.1007 / bfb0055720 . ISBN   9783540648925.
  52. ^ Бихам, Эли; Чен, Рафи. "Ближайшие столкновения SHA-0" (PDF) .
  53. ^ «Отчет из Crypto 2004» . Архивировано из оригинала на 2004-08-21 . Проверено 23 августа 2004 .
  54. ^ Grieu, Francois (18 августа 2004). «Re: Есть какие-нибудь предварительные новости о криптовалютной сессии?». Группа новостей :  sci.crypt . Событие происходит в 05:06:02 +0200. Usenet: [email protected] . 
  55. ^ Эффективные атаки поиска столкновений на SHA-0. Архивировано 10 сентября2005 г. на Wayback Machine , Шаньдунский университет.
  56. ^ Мануэль, Стефан; Пейрин, Томас (11 февраля 2008 г.). «Коллизии на SHA-0 за один час» (PDF) . Быстрое программное шифрование . Конспект лекций по информатике. 5086 . С. 16–35. DOI : 10.1007 / 978-3-540-71039-4_2 . ISBN  978-3-540-71038-7.
  57. ^ «Краткие комментарии NIST о недавних криптоаналитических атаках на функции безопасного хеширования и непрерывную безопасность, обеспечиваемую SHA-1» (PDF) . Архивировано из оригинального (PDF) 04.06.2011 . Проверено 5 мая 2010 .
  58. ^ «RFC 3174 - US Secure Hash Algorithm 1 (SHA1)» .
  59. ^ Локтюхин, Макс; Фаррел, Кэти (31 марта 2010 г.), «Повышение производительности алгоритма безопасного хеширования (SHA-1)» , база знаний по программному обеспечению Intel , получено 2 апреля 2010 г.
  60. ^ «Таблица измерений» . bench.cr.yp.to .
  61. ^ Тао, Се; Лю, Фаньбао; Фэн, Дэнго (2013). Fast Collision Attack на MD5 (PDF) . Cryptology ePrint Archive (Технический отчет). МАКР .
  62. ^ Стивенс, Марк ; Бурштейн, Эли ; Карпман, Пьер; Альбертини, Анж; Марков, Ярик. Первая коллизия для полного SHA-1 (PDF) (Технический отчет). Google Research . Краткое содержание - Блог по безопасности Google (23 февраля 2017 г.).
  63. ^ Без усечения известно полное внутреннее состояние хеш-функции, независимо от сопротивления столкновениям. Если вывод усечен, удаленная часть состояния должна быть отыскана и найдена до того, как хеш-функция может быть возобновлена, что позволит продолжить атаку.
  64. ^ "Семейство функций губки Keccak" . Проверено 27 января 2016 .
  65. ^ "ARM Cortex-A53 MPCore Processor Техническое справочное руководство Cryptography Extension" .

Ссылки [ править ]

  • Эли Бихам , Рафи Чен, Near-Collisions of SHA-0, Cryptology ePrint Archive, Report 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. 1994-07-11 . Проверено 26 апреля 2007 .[ постоянная мертвая ссылка ]
  • А. Чилардо, Л. Эспозито, А. Вениеро, А. Маццео, В. Белтран, Э. Аюгаде, HPC-приложение на основе CellBE для анализа уязвимостей в криптографических хэш-функциях , Международная конференция по высокопроизводительным вычислениям и коммуникациям, август 2010 г.

Внешние ссылки [ править ]

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