Безопасные алгоритмы хеширования | |
---|---|
Концепции | |
хэш-функции · SHA · DSA | |
Основные стандарты | |
SHA-0 · SHA-1 · SHA-2 · SHA-3 | |
Общий | |
---|---|
Дизайнеров | Национальное Агенство Безопасности |
Впервые опубликовано | 2001 г. |
Ряд | ( SHA-0 ), SHA-1 , SHA-2, SHA-3 |
Сертификация | FIPS PUB 180-4, CRYPTREC , NESSIE |
Деталь | |
Размеры дайджеста | 224, 256, 384 или 512 бит |
Состав | Конструкция Меркла – Дамгарда с функцией сжатия Дэвиса – Мейера. |
Раундов | 64 или 80 |
Лучший публичный криптоанализ | |
Атака 2011 года нарушает сопротивление прообразу для 57 из 80 раундов SHA-512 и 52 из 64 раундов для SHA-256. [1] Атака псевдо-коллизией против до 46 раундов SHA-256. [2] SHA-256 и SHA-512 подвержены атакам на расширение длины . Если угадать скрытую часть состояния, атаки по увеличению длины на SHA-224 и SHA-384 будут успешными с вероятностью 2 - (256−224) = 2 −32 > 2 −224 и 2 - (512−384) = 2 −128. > 2 −384 соответственно. |
SHA-2 ( Secure Hash Algorithm 2 ) - это набор криптографических хэш-функций, разработанный Агентством национальной безопасности США (NSA) и впервые опубликованный в 2001 году. [3] [4] Они построены с использованием конструкции Меркла-Дамгарда , от функция сжатия односторонний сам построена с использованием структуры Davies-Meyer из специализированного блока шифра .
SHA-2 включает в себя значительные изменения по сравнению со своим предшественником SHA-1 . Семейство SHA-2 состоит из шести хэш-функций с дайджестами (хеш-значениями), которые составляют 224, 256, 384 или 512 бит: SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA. -512/256 . SHA-256 и SHA-512 - это новые хэш-функции, вычисляемые с помощью восьми 32-битных и 64-битных слов соответственно. Они используют разные величины сдвига и аддитивные константы, но в остальном их структуры практически идентичны, различаются только количеством раундов. SHA-224 и SHA-384 - это усеченные версии SHA-256 и SHA-512 соответственно, вычисленные с разными начальными значениями. SHA-512/224 и SHA-512/256 также являются усеченными версиями SHA-512, но начальные значения генерируются с использованием метода, описанного вФедеральные стандарты обработки информации (FIPS) PUB 180-4.
SHA-2 был впервые опубликован Национальным институтом стандартов и технологий (NIST) в качестве федерального стандарта США (FIPS). Семейство алгоритмов SHA-2 запатентовано в патенте США 6829355. [5] Соединенные Штаты выпустили патент по бесплатной лицензии. [6]
В настоящее время лучшие публичные атаки нарушают устойчивость к прообразу для 52 из 64 раундов SHA-256 или 57 из 80 раундов SHA-512 и сопротивление столкновениям для 46 из 64 раундов SHA-256. [1] [2]
Стандарт хеширования [ править ]
С публикацией FIPS PUB 180-2 NIST добавил три дополнительных хэш-функции в семейство SHA. Все алгоритмы известны как SHA-2, названные в соответствии с длиной их дайджеста (в битах): SHA-256, SHA-384 и SHA-512.
Алгоритмы были впервые опубликованы в 2001 году в проекте FIPS PUB 180-2, после чего были приняты общественное рассмотрение и комментарии. В августе 2002 года FIPS PUB 180-2 стал новым стандартом Secure Hash Standard , заменив FIPS PUB 180-1, который был выпущен в апреле 1995 года. Обновленный стандарт включал исходный алгоритм SHA-1 с обновленными техническими обозначениями, соответствующими описанию внутренняя работа семейства SHA-2. [4]
В феврале 2004 г. было опубликовано уведомление об изменении для FIPS PUB 180-2, в котором указывается дополнительный вариант, SHA-224, определенный для соответствия длине ключа двухключевого Triple DES . [7] В октябре 2008 года стандарт был обновлен в FIPS PUB 180-3, включая SHA-224 из уведомления об изменении, но в остальном никаких фундаментальных изменений в стандарт не внесено. Основной причиной обновления стандарта было перемещение информации о безопасности хэш-алгоритмов и рекомендаций по их использованию в специальные публикации 800-107 и 800-57. [8] [9] [10] Подробные тестовые данные и примеры дайджестов сообщений также были удалены из стандарта и представлены в виде отдельных документов. [11]
В январе 2011 года NIST опубликовал SP800-131A, в котором определен переход от действующего на тот момент минимального 80-битного уровня безопасности (обеспечиваемого SHA-1), разрешенного для использования федеральным правительством до конца 2013 года, к 112-битному уровню безопасности (предоставляется по SHA-2), являющееся минимальным требованием (начиная с 2014 г.) и рекомендуемым уровнем безопасности (начиная с даты публикации в 2011 г.). [12]
В марте 2012 года стандарт был обновлен в FIPS PUB 180-4, добавлены хэш-функции SHA-512/224 и SHA-512/256 и описан метод генерации начальных значений для усеченных версий SHA-512. Кроме того, было снято ограничение на заполнение входных данных перед вычислением хэша, что позволяет вычислять хеш-данные одновременно с генерацией контента, такого как видео- или аудиопоток в реальном времени. Заполнение последнего блока данных должно происходить до вывода хэша. [13]
В июле 2012 года NIST пересмотрел SP800-57, который предоставляет руководство по управлению криптографическими ключами. Публикация запрещала создание цифровых подписей с хэш-безопасностью ниже 112 бит после 2013 года. В предыдущей редакции 2007 года было указано, что отсечка должна быть до конца 2010 года. [10] В августе 2012 года NIST пересмотрел SP800-107 таким же образом. [9]
Конкурс хеш-функций NIST выбрал новую хеш-функцию, SHA-3 , в 2012 году. [14] Алгоритм SHA-3 не является производным от SHA-2.
Приложения [ править ]
Хэш-функция SHA-2 реализована в некоторых широко используемых приложениях и протоколах безопасности, включая TLS и SSL , PGP , SSH , S / MIME и IPsec .
SHA-256 участвует в процессе аутентификации программных пакетов Debian [15] и в стандарте подписи сообщений DKIM ; SHA-512 является частью системы проверки подлинности архивного видео Международного уголовного трибунала по геноциду в Руанде . [16] SHA-256 и SHA-512 предлагаются для использования в DNSSEC . [17] Производители Unix и Linux переходят на использование 256- и 512-битного SHA-2 для безопасного хеширования паролей. [18]
Некоторые криптовалюты, такие как Биткойн, используют SHA-256 для проверки транзакций и расчета доказательства работы [19] или подтверждения доли . [20] Повышение СИС SHA-2 ускорительных чипов привело к использованию Scrypt -На схем корректуры из-работы.
SHA-1 и SHA-2 - это алгоритмы безопасного хеширования, необходимые по закону для использования в определенных государственных приложениях США , включая использование в других криптографических алгоритмах и протоколах, для защиты конфиденциальной несекретной информации. FIPS PUB 180-1 также поощрял принятие и использование SHA-1 частными и коммерческими организациями. SHA-1 выводится из эксплуатации для большинства государственных нужд; Национальный институт стандартов и технологий США заявляет: «Федеральные агентства должны прекратить использование SHA-1 для ... приложений, требующих защиты от коллизий, как можно скорее, и должны использовать семейство хэш-функций SHA-2 для этих приложений после 2010 года». (курсив в оригинале). [21]Директива NIST о том, что правительственные учреждения США должны прекратить использование SHA-1 после 2010 г. [22], должна была ускорить переход от SHA-1.
Первоначально функции SHA-2 не были быстро приняты, несмотря на лучшую безопасность, чем SHA-1. Причины могут включать отсутствие поддержки SHA-2 в системах под управлением Windows XP SP2 или более ранней версии [23] и отсутствие ощущаемой срочности, поскольку коллизии SHA-1 еще не были обнаружены. Команда Google Chrome объявила о плане постепенного прекращения поддержки их веб-браузером сертификатов TLS, зависящих от SHA-1, в период с конца 2014 по начало 2015 года. [24] [25] [26] Точно так же Microsoft объявила [27], что Интернет Explorer и Edge перестанут принимать общедоступные сертификаты TLS, подписанные SHA-1, с февраля 2017 года. Mozillaотключил SHA-1 в начале января 2016 года, но ему пришлось временно повторно включить его с помощью обновления Firefox после проблем с веб-пользовательскими интерфейсами некоторых моделей маршрутизаторов и устройств безопасности . [28]
Криптоанализ и проверка [ править ]
Для хеш-функции, для которой L - количество битов в дайджесте сообщения , поиск сообщения, которое соответствует заданному дайджесту сообщения, всегда можно выполнить с помощью поиска методом грубой силы в 2L оценках. Это называется атакой по прообразу и может быть практичным или непрактичным в зависимости от L и конкретной вычислительной среды. Второй критерий, обнаружение двух разных сообщений, которые производят один и тот же дайджест сообщения, известный как коллизия , требует в среднем только 2 оценок L / 2 с использованием атаки дня рождения .
Некоторые приложения, использующие криптографические хэши, такие как хранилище паролей, лишь минимально подвержены коллизионной атаке . Создание пароля, который работает для данной учетной записи, требует атаки с использованием прообраза, а также доступа к хешу исходного пароля (обычно в shadow
файле), что может быть или не быть тривиальным. Обратное шифрование пароля (например, для получения пароля для попытки взломать учетную запись пользователя в другом месте) из-за атак невозможно. (Однако даже безопасный хэш пароля не может предотвратить атаки методом перебора слабых паролей .)
В случае подписания документа злоумышленник не может просто подделать подпись существующего документа - злоумышленник должен будет предъявить пару документов, один безобидный и один опасный, и заставить держателя закрытого ключа подписать безобидный документ. Существуют практические обстоятельства, при которых это возможно; до конца 2008 года можно было создавать поддельные сертификаты SSL с использованием коллизии MD5, которые принимались широко используемыми веб-браузерами. [29]
Повышенный интерес к криптографическому анализу хешей во время соревнований SHA-3 привел к появлению нескольких новых атак на семейство SHA-2, лучшие из которых приведены в таблице ниже. Только атаки столкновения имеют практическую сложность; ни одна из атак не распространяется на хеш-функцию полного раунда.
На FSE 2012 исследователи Sony выступили с презентацией, в которой предлагалось расширить возможности псевдоколлизионных атак до 52 раундов на SHA-256 и 57 раундов на SHA-512, опираясь на атаку biclique псевдо-прообразом. [30]
Опубликовано в | Год | Метод атаки | Атака | Вариант | Раундов | Сложность |
---|---|---|---|---|---|---|
Новые коллизионные атаки против 24-шагового SHA-2 [31] | 2008 г. | Детерминированный | Столкновение | SHA-256 | 24/64 | 2 28,5 |
SHA-512 | 24/80 | 2 32,5 | ||||
Прообразы для ступенчато-уменьшенного SHA-2 [32] | 2009 г. | Встреча посередине | Прообраз | SHA-256 | 42/64 | 2 251,7 |
43/64 | 2 254,9 | |||||
SHA-512 | 42/80 | 2 502,3 | ||||
46/80 | 2 511,5 | |||||
Продвинутые атаки на прообраз " встреча посередине" [33] | 2010 г. | Встреча посередине | Прообраз | SHA-256 | 42/64 | 2 248,4 |
SHA-512 | 42/80 | 2 494,6 | ||||
Дифференциальная атака высшего порядка на сокращенный SHA-256 [2] | 2011 г. | Дифференциальный | Псевдо-коллизия | SHA-256 | 46/64 | 2 178 |
33/64 | 2 46 | |||||
Bicliques для прообразов: атаки на Skein-512 и семейство SHA-2 [1] | 2011 г. | Biclique | Прообраз | SHA-256 | 45/64 | 2 255,5 |
SHA-512 | 50/80 | 2 511,5 | ||||
Псевдо-прообраз | SHA-256 | 52/64 | 2 255 | |||
SHA-512 | 57/80 | 2 511 | ||||
Улучшение локальных коллизий: новые атаки на сокращенный SHA-256 [34] | 2013 | Дифференциальный | Столкновение | SHA-256 | 31/64 | 2 65,5 |
Псевдо-коллизия | SHA-256 | 38/64 | 2 37 | |||
Эвристика ветвления в дифференциальном поиске коллизий с приложениями к SHA-512 [35] | 2014 г. | Эвристический дифференциал | Псевдо-коллизия | SHA-512 | 38/80 | 2 40,5 |
Анализ SHA-512/224 и SHA-512/256 [36] | 2016 г. | Дифференциальный | Столкновение | SHA-256 | 28/64 | практичный |
SHA-512 | 27/80 | практичный | ||||
Псевдо-коллизия | SHA-512 | 39/80 | практичный |
Официальная проверка [ править ]
Реализация всех функций безопасности, утвержденных FIPS, может быть официально подтверждена с помощью программы CMVP , совместно управляемой Национальным институтом стандартов и технологий (NIST) и организацией по обеспечению безопасности связи (CSE). Для неформальной проверки пакет для генерации большого количества тестовых векторов доступен для загрузки на сайте NIST; Однако полученная проверка не заменяет формальную проверку CMVP, которая требуется по закону для определенных приложений.
По состоянию на декабрь 2013 [Обновить]года существует более 1300 проверенных реализаций SHA-256 и более 900 SHA-512, при этом только 5 из них способны обрабатывать сообщения с длиной в битах, не кратной восьми, при поддержке обоих вариантов. [37]
Тестовые векторы [ править ]
Хеш-значения пустой строки (т. Е. Входного текста нулевой длины).
SHA224 ("")0x d14a028c2a3a2bc9476102bb288234c415a2b01f828ea62ac5b3e42fSHA256 ("")0x e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855SHA384 ("")0x 38b060a751ac96384cd9327eb1b1e36a21fdb71114be07434c0cc7bf63f6e1da274edebfe76f65fbd51ad2f14898b95bSHA512 ("")0x cf83e1357eefb8bdf1542850d66d8007d620e4050b5715dc83f4a921d36ce9ce47d0d13c5d85f2b0ff8318d2877eec2f63b931bd47417a81a538327af927da3eSHA512 / 224 ("")0x 6ed0dd02806fa89e25de060c19d3ac86cabb87d6a0ddd05c333b84f4SHA512 / 256 ("")0x c672b8d1ef56ed28ab87c3622c5114069bdd3ad7b8f9737498d0c01ecef0967a
Даже небольшое изменение в сообщении (с огромной вероятностью) приведет в основном к другому хешу из-за эффекта лавины . Например, добавление точки в конец следующего предложения изменяет почти половину (111 из 224) бит в хеш-коде:
SHA224 (« Быстрая коричневая лиса перепрыгивает через ленивого пса »)0x 730e109bd7a8a32b1cb9d9a09aa2325d2430587ddbc0c38bad911525SHA224 (« Быстрая коричневая лиса перепрыгивает через ленивую собаку . »)0x 619cba8e8e05826e9b8c519c0a5c68f4fb653e8a3d8aa04bb2c8cd4c
Псевдокод [ править ]
Псевдокод для алгоритма SHA-256 следует ниже. Обратите внимание на значительное увеличение смешивания битов w[16..63]
слов по сравнению с SHA-1.
Примечание 1: все переменные представляют собой 32-битные целые числа без знака, и сложение вычисляется по модулю 2 32 Примечание 2: для каждого цикла существует одна константа цикла k [i] и одна запись в массиве расписания сообщений w [i], 0 ≤ i ≤ 63 Примечание 3: функция сжатия использует 8 рабочих переменных, от a до h Примечание 4: при выражении констант в этом псевдокоде и при анализе данных блока сообщения от байтов к словам, например, первое слово входное сообщение «abc» после заполнения - 0x61626380Инициализировать хеш-значения: (первые 32 бита дробных частей квадратных корней первых 8 простых чисел 2..19):h0: = 0x6a09e667h1: = 0xbb67ae85h2: = 0x3c6ef372h3: = 0xa54ff53ah4: = 0x510e527fh5: = 0x9b05688ch6: = 0x1f83d9abh7: = 0x5be0cd19Инициализировать массив круглых констант: (первые 32 бита дробных частей кубических корней первых 64 простых чисел 2..311):k [0..63]: = 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2Предварительная обработка (Padding):начать с исходного сообщения длиной L битдобавить один бит '1'добавить K '0' битов, где K - минимальное число> = 0, такое, что L + 1 + K + 64 кратно 512добавить L как 64-битное целое число с прямым порядком байтов, сделав общую длину постобработки кратной 512 битамтаким образом, что биты в сообщении равны L 1 00 .. <K 0's> .. 00 <L как 64-битное целое число> = k * 512 всего битОбработайте сообщение последовательными 512-битными фрагментами:разбить сообщение на 512-битные кускиза каждый кусок создать массив расписания сообщений с 64 записями w [0..63] из 32-битных слов (Начальные значения в w [0..63] не имеют значения, поэтому многие реализации обнуляют их здесь) скопировать блок в первые 16 слов w [0..15] массива расписания сообщений Расширьте первые 16 слов до оставшихся 48 слов w [16..63] массива расписания сообщений: для i от 16 до 63 s0: = (w [i-15] правый поворот 7) xor (w [i-15] правый поворот 18) xor (w [i-15] правый сдвиг 3) s1: = (w [i- 2] правый поворот 17) xor (w [i- 2] правый поворот 19) xor (w [i- 2] правый сдвиг 10) w [i]: = w [i-16] + s0 + w [i-7] + s1 Инициализировать рабочие переменные текущим значением хеш-функции: а: = h0 b: = h1 c: = h2 d: = h3 е: = h4 f: = h5 г: = h6 h: = h7 Основной цикл функции сжатия: для i от 0 до 63 S1: = (e правый поворот 6) xor (e правый поворот 11) xor (e правый поворот 25) ch: = (e и f) xor (( не e) и g) temp1: = h + S1 + ch + k [i] + w [i] S0: = ( поворот вправо 2) xor ( поворот вправо 13) xor ( поворот вправо 22) maj: = (a и b) xor (a и c) xor (b и c) temp2: = S0 + maj ч: = г g: = f f: = e e: = d + temp1 d: = c c: = b б: = а a: = temp1 + temp2 Добавьте сжатый фрагмент к текущему хеш-значению: h0: = h0 + a h1: = h1 + b h2: = h2 + c h3: = h3 + d h4: = h4 + e h5: = h5 + f h6: = h6 + g h7: = h7 + hПроизвести окончательное значение хеш-функции (с прямым порядком байтов): digest: = hash: = h0 добавить h1 добавить h2 добавить h3 добавить h4 добавить h5 добавить h6 добавить h7
Вычисление ch
и maj
значений может быть оптимизировано таким же образом , как описано для SHA-1 .
SHA-224 идентичен SHA-256, за исключением того, что:
- начальные значения хеш - функции
h0
черезh7
разные, и - вывод построен путем пропуска
h7
.
Начальные хеш-значения SHA-224 (с прямым порядком байтов): (Вторые 32 бита дробных частей квадратных корней от 9-го до 16-го простых чисел 23..53)h [0..7]: = 0xc1059ed8, 0x367cd507, 0x3070dd17, 0xf70e5939, 0xffc00b31, 0x68581511, 0x64f98fa7, 0xbefa4fa4
SHA-512 идентичен по структуре SHA-256, но:
- сообщение разбито на 1024-битные блоки,
- начальные хеш-значения и круглые константы расширены до 64 бит,
- вместо 64 патронов 80,
- массив расписания сообщений w содержит 80 64-битных слов вместо 64 32-битных слов,
- для расширения массива расписания сообщений w цикл будет от 16 до 79 вместо от 16 до 63,
- округленные константы основаны на первых 80 простых числах 2..409,
- размер слова, используемый для вычислений, составляет 64 бита,
- добавленная длина сообщения (до предварительной обработки) в битах представляет собой 128-битное целое число с прямым порядком байтов, и
- Используемые значения сдвига и поворота различаются.
Начальные хеш-значения SHA-512 (с прямым порядком байтов):h [0..7]: = 0x6a09e667f3bcc908, 0xbb67ae8584caa73b, 0x3c6ef372fe94f82b, 0xa54ff53a5f1d36f1, 0x510e527fade682d1, 0x9b05688c2b3e6c1f, 0x1f83d9abfb41bd6b, 0x5be0cd19137e2179Круглые константы SHA-512:k [0..79]: = [0x428a2f98d728ae22, 0x7137449123ef65cd, 0xb5c0fbcfec4d3b2f, 0xe9b5dba58189dbbc, 0x3956c25bf348b538, 0x59f111f1b605d019, 0x923f82a4af194f9b, 0xab1c5ed5da6d8118, 0xd807aa98a3030242, 0x12835b0145706fbe, 0x243185be4ee4b28c, 0x550c7dc3d5ffb4e2, 0x72be5d74f27b896f, 0x80deb1fe3b1696b1, 0x9bdc06a725c71235, 0xc19bf174cf692694, 0xe49b69c19ef14ad2, 0xefbe4786384f25e3, 0x0fc19dc68b8cd5b5, 0x240ca1cc77ac9c65, 0x2de92c6f592b0275, 0x4a7484aa6ea6e483, 0x5cb0a9dcbd41fbd4, 0x76f988da831153b5, 0x983e5152ee66dfab, 0xa831c66d2db43210, 0xb00327c898fb213f, 0xbf597fc7beef0ee4, 0xc6e00bf33da88fc2, 0xd5a79147930aa725, 0x06ca6351e003826f, 0x142929670a0e6e70, 0x27b70a8546d22ffc, 0x2e1b21385c26c926, 0x4d2c6dfc5ac42aed, 0x53380d139d95b3df, 0x650a73548baf63de, 0x766a0abb3c77b2a8, 0x81c2c92e47edaee6, 0x92722c851482353b, 0xa2bfe8a14cf10364, 0xa81a664bbc423001, 0xc24b8b70d0f89791, 0xc76c51a30654be30, 0xd192e819d6ef5218, 0xd69906245565a910, 0xf40e35855771202a, 0x106aa07032bbd1b8, 0x19a4c116b8d2d0c8, 0x1e376c085141ab53, 0x2748774cdf8eeb99, 0x34b0bcb5e19b48a8, 0x391c0cb3c5c95a63, 0x4ed8aa4ae3418acb, 0x5b9cca4f7763e373, 0x682e6ff3d6b2b8a3, 0x748f82ee5defb2fc, 0x78a5636f43172f60, 0x84c87814a1f0ab72, 0x8cc702081a6439ec, 0x90befffa23631e28, 0xa4506cebde82bde9, 0xbef9a3f7b2c67915, 0xc67178f2e372532b, 0xca273eceea26619c, 0xd186b8c721c0c207, 0xeada7dd6cde0eb1e, 0xf57d4f7fee6ed178, 0x06f067aa72176fba, 0x0a637dc5a2c898a6, 0x113f9804bef90dae, 0x1b710b35131c471b, 0x28db77f523047d84, 0x32caab7b40c72493, 0x3c9ebe0a15c9bebc, 0x431d67c49c100d4c, 0x4cc5d4becb3e42b6, 0x597f299cfc657e2a, 0x5fcb6fab3ad6faec, 0x6c44198c4a475817]Сумма и сигма SHA-512:S0: = ( поворот вправо 28) xor ( поворот вправо 34) xor ( поворот вправо 39)S1: = (e правый поворот 14) xor (e правый поворот 18) xor (e правый поворот 41)s0: = (w [i-15] правый поворот 1) xor (w [i-15] правый поворот 8) xor (w [i-15] правый сдвиг 7)s1: = (w [i-2] правый поворот 19) xor (w [i-2] правый поворот 61) xor (w [i-2] правый сдвиг 6)
SHA-384 идентичен SHA-512, за исключением того, что:
- начальные значения хеш - функции
h0
черезh7
разные (взято с 9 по 16 - простых чисел) и - вывод создается путем опускания
h6
иh7
.
Начальные хеш-значения SHA-384 (с прямым порядком байтов):h [0..7]: = 0xcbbb9d5dc1059ed8, 0x629a292a367cd507, 0x9159015a3070dd17, 0x152fecd8f70e5939, 0x67332667ffc00b31, 0x8eb44a8768581511, 0xdb0c2e0d64f98fa7, 0x47b5481dbefa4fa4
SHA-512 / t идентичен SHA-512, за исключением того, что:
- начальные значения хеш - функции
h0
черезh7
задаются функцией генерации IV ША-512 / т , - выход строится путем усечения конкатенации
h0
сквозногоh7
при т битах, - t равный 384 не допускается, вместо этого следует использовать SHA-384, как указано, и
- Значения t 224 и 256 особо упоминаются как утвержденные.
Функция генерации SHA-512 / t IV оценивает модифицированный SHA-512 в строке ASCII «SHA-512 / t », замененной десятичным представлением t . Модифицированный SHA-512 такого же , как SHA-512 , за исключением начальных значений h0
через h7
которые каждый были операции XOR с константой шестнадцатеричной 0xa5a5a5a5a5a5a5a5
.
Пример реализации C для семейства хэш-функций SHA-2 можно найти в RFC 6234.
Сравнение функций SHA [ править ]
В таблице ниже внутреннее состояние означает «внутреннюю хеш-сумму» после каждого сжатия блока данных.
Алгоритм и вариант | Размер вывода (бит) | Размер внутреннего состояния (биты) | Размер блока (бит) | Раундов | Операции | Защита от коллизионных атак (биты) | Защита от атак с увеличением длины (биты) | Производительность на Skylake (среднее значение CPB ) [38] | Впервые опубликовано | ||
---|---|---|---|---|---|---|---|---|---|---|---|
Длинные сообщения | 8 байт | ||||||||||
MD5 (как ссылка) | 128 | 128 (4 × 32) | 512 | 64 | And, Xor, Rot, Add (mod 2 32 ), Или | ≤ 18 (обнаружены коллизии) [39] | 0 | 4,99 | 55.00 | 1992 г. | |
SHA-0 | 160 | 160 (5 × 32) | 512 | 80 | And, Xor, Rot, Add (mod 2 32 ), Или | <34 (обнаружены коллизии) | 0 | ≈ SHA-1 | ≈ SHA-1 | 1993 г. | |
SHA-1 | <63 (обнаружены коллизии) [40] | 3,47 | 52,00 | 1995 г. | |||||||
SHA-2 | SHA-224 SHA-256 | 224 256 | 256 (8 × 32) | 512 | 64 | And, Xor, Rot, Add (mod 2 32 ), Or, Shr | 112 128 | 32 0 | 7,62 7,63 | 84,50 85,25 | 2004 2001 |
SHA-384 SHA-512 | 384 512 | 512 (8 × 64) | 1024 | 80 | And, Xor, Rot, Add (mod 2 64 ), Or, Shr | 192 256 | 128 (≤ 384) 0 [41] | 5,12 5,06 | 135,75 135,50 | 2001 г. | |
SHA-512/224 SHA-512/256 | 224 256 | 112 128 | 288 256 | ≈ SHA-384 | ≈ SHA-384 | 2012 г. | |||||
SHA-3 | SHA3-224 SHA3-256 SHA3-384 SHA3-512 | 224 256 384 512 | 1600 (5 × 5 × 64) | 1152 1088 832 576 | 24 [42] | И, Xor, Rot, Not | 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 | d (произвольно) d (произвольно) | 1344 1088 | мин ( д / 2, 128) мин ( д / 2, 256) | 256 512 | 7,08 8,59 | 155,25 155,50 |
В столбце поразрядных операций «Rot» обозначает вращение без переноса , а «Shr» обозначает логический сдвиг вправо . Все эти алгоритмы тем или иным образом используют модульное сложение, за исключением SHA-3.
Более подробные измерения производительности на современных архитектурах процессоров приведены в таблице ниже.
Архитектура процессора | Частота | Алгоритм | Размер слова (бит) | Циклов / байт x86 | МиБ / с x86 | Циклов / байт x86-64 | МиБ / с x86-64 |
---|---|---|---|---|---|---|---|
Intel Ivy Bridge | 3,5 ГГц | SHA-256 | 32 | 16,80 | 199 | 13.05 | 256 |
SHA-512 | 64 | 43,66 | 76 | 8,48 | 394 | ||
AMD Piledriver APU | 3,8 ГГц | SHA-256 | 32 | 22,87 | 158 | 18,47 | 196 |
SHA-512 | 64 | 88,36 | 41 год | 12,43 | 292 |
Номера производительности с пометкой «x86» выполнялись с использованием 32-битного кода на 64-битных процессорах, тогда как номера «x86-64» - это собственный 64-битный код. Хотя SHA-256 предназначен для 32-битных вычислений, он действительно выигрывает от кода, оптимизированного для 64-битных процессоров на архитектуре x86. 32-битные реализации SHA-512 значительно медленнее своих 64-битных аналогов. Варианты обоих алгоритмов с разными размерами вывода будут работать одинаково, так как функции расширения и сжатия сообщений идентичны, и различаются только начальные значения хеш-функции и размеры вывода. Лучшие реализации MD5 и SHA-1 выполняют от 4,5 до 6 циклов на байт на современных процессорах.
Тестирование было проведено Иллинойским университетом в Чикаго на их системе Hydra8, работающей на Intel Xeon E3-1275 V2 с тактовой частотой 3,5 ГГц, и на их системе Hydra9 с APU AMD A10-5800K с тактовой частотой 3,8 ГГц. [43] Указанные выше скорости циклов на байт представляют собой среднюю производительность алгоритма, обрабатывающего сообщение размером 4096 байт с использованием программного обеспечения для криптографического тестирования SUPERCOP. [44] Производительность в мегабайтах в секунду экстраполируется из тактовой частоты процессора на одном ядре; реальная производительность будет зависеть от множества факторов.
Реализации [ править ]
Ниже приведен список библиотек криптографии, поддерживающих SHA-2:
- Ботан
- Надувной Замок
- Cryptlib
- Крипто ++
- Libgcrypt
- Mbed TLS [45] [46]
- libsodium
- Крапива
- LibreSSL
- OpenSSL
- GnuTLS
- wolfSSL
Аппаратное ускорение обеспечивается следующими расширениями процессора:
- Расширения Intel SHA : доступны на некоторых процессорах Intel и AMD x86.
- ЧЕРЕЗ PadLock
- Расширения криптографии ARMv8 [47]
См. Также [ править ]
- Сравнение криптографических хеш-функций
- Сравнение криптографических библиотек
- Сводка по безопасности хеш-функции
- Hashcash
- HMAC
- Международная ассоциация криптологических исследований (IACR)
sha1sum
(sha224sum
,sha256sum
,sha384sum
Иsha512sum
) команд- Надежная отметка времени
Ссылки [ править ]
- ^ a b c Дмитрий Ховратович, Кристиан Рехбергер и Александра Савельева (2011). «Bicliques для прообразов: атаки на Skein-512 и семейство SHA-2» (PDF) . IACR Cryptology ePrint Archive . 2011: 286.
- ^ a b c Марио Ламбергер и Флориан Мендель (2011). «Дифференциальная атака высшего порядка на сокращенный SHA-256» (PDF) . IACR Cryptology ePrint Archive . 2011: 37.
- ^ «О семействе алгоритмов безопасного хеширования» (PDF) . Архивировано из оригинального (PDF) 30 марта 2016 года.
- ^ a b Уведомление Федерального реестра 02-21599, объявляющее об утверждении публикации 180-2 FIPS
- ^ США 6829355
- ^ «Заявление о лицензировании патента США 6829355» . Проверено 17 февраля 2008 . Цитировать журнал требует
|journal=
( помощь ) - ^ «FIPS 180-2 с уведомлением об изменении 1» (PDF) . csrc.nist.gov .
- ^ Уведомление Федерального реестра E8-24743, объявляющее об утверждении публикации FIPS 180-3
- ^ a b Рекомендации FIPS SP 800-107 для приложений, использующих утвержденные хеш-алгоритмы
- ^ a b Рекомендации FIPS SP 800-57 по управлению ключами: Часть 1: Общие
- ^ "NIST.gov - Отдел компьютерной безопасности - Центр ресурсов компьютерной безопасности" .
- ^ Рекомендации FIPS SP 800-131A по переходу на использование криптографических алгоритмов и длин ключей
- ^ Уведомление Федерального реестра 2012-5400, Объявление об утверждении Публикации FIPS 180-4
- ^ «NIST выбирает победителя конкурса алгоритмов безопасного хеширования (SHA-3)» . Проверено 24 февраля 2015 года .
- ^ «Кодовая база Debian в Google Code» . Архивировано из оригинала на 7 ноября 2011 года . Проверено 8 ноября 2011 .
- ^ Джон Марков, Инструмент для проверки цифровых записей, даже в качестве технологических сдвигов , Нью - Йорк Таймс , 26 января 2009
- ^ RFC 5702, RFC-Editor.org
- ^ Ульрих Дреппер, крипта Unix с SHA-256/512
- ^ Биткойн, Излишки. «Биткойн не тратит энергию впустую» . Излишки биткойнов . Проверено 20 апреля 2020 .
- ^ «Что такое SHA-256 и как он связан с биткойнами? - Mycryptopedia» . Микриптопедия . 2017-09-21 . Проверено 17 сентября 2018 .
- ^ Национальный институт стандартов и технологий Ресурсный центр по компьютерной безопасности, Политика NIST в отношении хэш-функций, Архивная копия от 09.06.2011 на Wayback Machine , по состоянию на 29 марта 2009 г.
- ^ «Безопасное хеширование» . NIST . Архивировано из оригинала на 2011-06-25 . Проверено 25 ноября 2010 .
- ^ «Обзор Windows XP с пакетом обновления 3» (PDF) . Корпорация Майкрософт. Архивировано из оригинального (PDF) 30 мая 2008 года.
- ^ Chromium Blog, 5 сентября 2014 г., SHA-1 постепенно прекращается.
- ^ Эрик Милл. «ШАААААААААААА» . SHAAAAAAAAAAAAA.com .
- ^ Филиппо Валсорда, Неофициальный FAQ по устареванию Chrome SHA1
- ^ «Обновление нашего плана по прекращению поддержки SHA-1 - Блог разработчиков Microsoft EdgeБлог разработчиков Microsoft Edge» . blogs.windows.com . Проверено 28 ноября 2016 .
- ^ Фабиан А. Шершель, HeiseSecurity: Firefox: Mozilla schaltet SHA-1 ab ... und direkt wieder an (немецкий)
- ↑ Александр Сотиров, Марк Стивенс, Джейкоб Аппельбаум, Арьен Ленстра, Дэвид Мольнар, Даг Арне Освик, Бенн де Вегер, MD5, который сегодня считается вредоносным: Создание поддельного сертификата CA , по состоянию на 29 марта 2009 г.
- ↑ Джи Ли, Таканори Исобе и Кёдзи Шибутани, Китайская исследовательская лаборатория Sony и Sony Corporation, Преобразование атаки по прообразу встречи в середине в атаку с псевдоколлизией: применение к SHA-2
- ^ Сомитра Кумар Санадхья и Палаш Саркар (2008). «Новые коллизионные атаки против 24-шагового SHA-2» (PDF) . IACR Cryptology ePrint Archive . 2008: 270.
- ^ Kazumaro Aoki; Цзянь Го; Кристиан Матусевич; Ю Сасаки и Лей Ван (2009). Прообразы для ступенчатого уменьшается SHA-2 . Достижения в криптологии - ASIACRYPT 2009 . Конспект лекций по информатике. 5912 . Springer Berlin Heidelberg. С. 578–597. DOI : 10.1007 / 978-3-642-10366-7_34 . ISBN 978-3-642-10366-7. ISSN 0302-9743 .
- ^ Цзянь Го; Сан Линг; Кристиан Рехбергер и Хуаксионг Ван (2010). Продвинутые атаки с использованием прообраза «встреча посередине»: первые результаты на полном Tiger и улучшенные результаты на MD4 и SHA-2 (PDF) . Достижения в криптологии - ASIACRYPT 2010 . Конспект лекций по информатике. 6477 . Springer Berlin Heidelberg. С. 56–75. DOI : 10.1007 / 978-3-642-17373-8_4 . ISBN 978-3-642-17373-8. ISSN 0302-9743 .
- ^ Флориан Мендель; Томислав Над; Мартин Шлеффер (2013). Улучшение локальных коллизий: новые атаки на уменьшенный SHA-256 . Достижения в криптологии - EUROCRYPT 2013 . Конспект лекций по информатике. 7881 . Springer Berlin Heidelberg. С. 262–278. DOI : 10.1007 / 978-3-642-38348-9_16 . ISBN 978-3-642-38348-9. ISSN 0302-9743 .
- ^ Мария Eichlseder и Флориан Мендель и Мартин Шлаффер (2014). «Ветвящаяся эвристика в дифференциальном поиске коллизий с приложениями к SHA-512» (PDF) . IACR Cryptology ePrint Archive . 2014: 302.
- ^ Кристоф Добрауниг; Мария Эйхлседер и Флориан Мендель (2016). «Анализ SHA-512/224 и SHA-512/256» (PDF) . Цитировать журнал требует
|journal=
( помощь ) - ^ "Список валидации SHS" . NIST . 2017-06-16. Архивировано из оригинала на 2017-06-17.
- ^ «Таблица измерений» . bench.cr.yp.to .
- ^ Тао, Се; Лю, Фаньбао; Фэн, Дэнго (2013). Fast Collision Attack на MD5 (PDF) . Cryptology ePrint Archive (Технический отчет). МАКР .
- ^ Стивенс, Марк ; Бурштейн, Эли ; Карпман, Пьер; Альбертини, Анж; Марков, Ярик. Первая коллизия для полного SHA-1 (PDF) (Технический отчет). Google Research . Краткое содержание - Блог по безопасности Google (23 февраля 2017 г.).
- ^ Без усечения известно полное внутреннее состояние хеш-функции, независимо от сопротивления столкновениям. Если вывод усечен, удаленная часть состояния должна быть отыскана и найдена до того, как хеш-функция может быть возобновлена, что позволит продолжить атаку.
- ^ "Семейство функций губки Keccak" . Проверено 27 января 2016 .
- ^ SUPERCOP Benchmarks Измерения хэш-функций, индексируемых машиной
- ^ "СУПЕРКОП" . Проверено 24 февраля 2015 года .
- ^ Поддерживаемые наборы шифров SSL / TLS
- ^ Журнал изменений Mbed TLS , 7 июля 2007 г.
- ^ "ARM Cortex-A53 MPCore Processor Техническое справочное руководство Cryptography Extension" .
Дальнейшее чтение [ править ]
- Анри Гилберт, Хелена Хандшу: Анализ безопасности SHA-256 и сестер. Избранные области криптографии 2003: стр. 175–193
- «Предлагаемая редакция Федерального стандарта обработки информации (FIPS) 180, Стандарт безопасного хеширования» . Федеральный регистр . 59 (131): 35317–35318. 1994-07-11 . Проверено 26 апреля 2007 .[ постоянная мертвая ссылка ]
Внешние ссылки [ править ]
- Описание SHA-256, SHA-384 и SHA-512 из NIST
- SHA-2 Checker - SHAChecker для проверки совместимости SSL для SHA-2
- Спецификации стандарта безопасного хеширования (SHS) - проект предлагаемого SHS (SHA-0)
- Стандарт безопасного хеширования (SHS) - Предлагаемый SHS (SHA-0)
- CSRC Cryptographic Toolkit - официальный сайт NIST для стандарта безопасного хеширования
- FIPS PUB 180-4: Secure Hash Standard (SHS) ( PDF , 834 КБ) - Текущая версия Secure Hash Standard (SHA-1, SHA-224, SHA-256, SHA-384 и SHA-512), август 2015 г.
- Тестовые векторы для SHA-256/384/512 из проекта NESSIE
- Тестовые векторы для SHA-1, SHA-2 с сайта NIST
- Проект криптографического хеширования NIST - конкурс SHA-3
- RFC 3874: «224-битная функция одностороннего хеширования: SHA-224»
- RFC 6234: «Американские алгоритмы безопасного хеширования (HMAC и HKDF на основе SHA и SHA)»; содержит пример реализации C