Secure Hash Algorithm 1 — алгоритм криптографического хеширования. Описан в RFC 3174. Для входного сообщения произвольной длины (максимум бит, что примерно равно 2 эксабайта) алгоритм генерирует 160-битное (20 байт) хеш-значение, называемое также дайджестом сообщения, которое обычно отображается как шестнадцатеричное число длиной в 40 цифр. Используется во многих криптографических приложениях и протоколах. Также рекомендован в качестве основного для государственных учреждений в США. Принципы, положенные в основу SHA-1, аналогичны тем, которые использовались Рональдом Ривестом при проектировании MD4.
История В 1993 году NSA совместно с NIST разработали алгоритм безопасного хеширования (сейчас известный как SHA-0) (опубликован в документе FIPS PUB 180) для стандарта безопасного хеширования. Однако вскоре NSA отозвало данную версию, сославшись на обнаруженную ими ошибку, которая так и не была раскрыта, и заменило его исправленной версией, опубликованной в 1995 году в документе FIPS PUB 180-1. Эта версия и считается тем, что называют SHA-1. Позже, на конференции CRYPTO в 1998 году два французских исследователя представили атаку на алгоритм SHA-0, которая не работала на алгоритме SHA-1. Возможно, это и была ошибка, открытая NSA.
Описание алгоритма
SHA-1 реализует хеш-функцию, построенную на идее функции сжатия. Входами функции сжатия являются блок сообщения длиной 512 бит и выход предыдущего блока сообщения. Выход представляет собой значение всех хеш-блоков до этого момента. Иными словами, хеш-блок равен . Хеш-значением всего сообщения является выход последнего блока.
Инициализация Исходное сообщение разбивается на блоки по 512 бит в каждом. Последний блок дополняется до длины, кратной 512 бит. Сначала добавляется 1 (бит), а потом — нули, чтобы длина блока стала равной 512 — 64 = 448 бит. В оставшиеся 64 бита записывается длина исходного сообщения в битах (в big-endian формате). Если последний блок имеет длину более 447, но менее 512 бит, то дополнение выполняется следующим образом: сначала добавляется 1 (бит), затем — нули вплоть до конца 512-битного блока; после этого создается ещё один 512-битный блок, который заполняется вплоть до 448 бит нулями, после чего в оставшиеся 64 бита записывается длина исходного сообщения в битах (в big-endian формате). Дополнение последнего блока осуществляется всегда, даже если сообщение уже имеет нужную длину.
Инициализируются пять 32-битовых переменных.
A = 0x67452301 B = 0xEFCDAB89 C = 0x98BADCFE D = 0x10325476 E = 0xC3D2E1F0
Определяются четыре нелинейные операции и четыре константы.
= 0x5A827999 0≤t≤19 = 0x6ED9EBA1 20≤t≤39 = 0x8F1BBCDC 40≤t≤59 = 0xCA62C1D6 60≤t≤79
Главный цикл Главный цикл итеративно обрабатывает каждый 512-битный блок. В начале каждого цикла вводятся переменные a, b, c, d, e, которые инициализируются значениями A, B, C, D, E, соответственно. Блок сообщения преобразуется из 16 32-битовых слов в 80 32-битовых слов по следующему правилу:
при 0≤t≤15 = (-3 -8 -14 -16) << 1 при 16≤t≤79 , где «<<» — это циклический сдвиг влево.
для от 0 до 79 temp = (a<<5) + (b,c,d) + e + e = d d = c c = b<<30 b = a a = temp
, где «+» — сложение беззнаковых 32-битных целых чисел с отбрасыванием избытка (33-го бита).
После этого к A, B, C, D, E прибавляются значения a, b, c, d, e, соответственно. Начинается следующая итерация.
Итоговым значением будет объединение пяти 32-битовых слов (A, B, C, D, E) в одно 160-битное хеш-значение.
Псевдокод SHA-1 Псевдокод алгоритма SHA-1 следующий:
Замечание: Все используемые переменные 32 бита.
Инициализация переменных: h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x10325476 h4 = 0xC3D2E1F0
Предварительная обработка: Присоединяем бит '1' к сообщению Присоединяем k битов '0', где k наименьшее число ≥ 0 такое, что длина получившегося сообщения (в битах) сравнима по модулю 512 с 448 (length mod 512 == 448) Добавляем длину исходного сообщения (до предварительной обработки) как целое 64-битное Big-endian число, в битах.
В процессе сообщение разбивается последовательно по 512 бит: for перебираем все такие части разбиваем этот кусок на 16 частей, слов по 32-бита (big-endian) w[i], 0 <= i <= 15
16 слов по 32-бита дополняются до 80 32-битовых слов: for i from 16 to 79 w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) циклический сдвиг влево 1
Инициализация хеш-значений этой части: a = h0 b = h1 c = h2 d = h3 e = h4
Основной цикл: 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 then f = b xor c xor d k = 0x6ED9EBA1 else if 40 ≤ i ≤ 59 then f = (b and c) or (b and d) or (c and d) k = 0x8F1BBCDC else if 60 ≤ i ≤ 79 then 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
Добавляем хеш-значение этой части к результату: h0 = h0 + a h1 = h1 + b h2 = h2 + c h3 = h3 + d h4 = h4 + e
Итоговое хеш-значение(h0, h1, h2, h3, h4 должны быть преобразованы к big-endian): digest = hash = h0 append h1 append h2 append h3 append h4
Вместо оригинальной формулировки FIPS PUB 180-1 приведены следующие эквивалентные выражения и могут быть использованы на компьютере f в главном цикле:
(0 ≤ i ≤ 19): f = d xor (b and (c xor d)) (альтернатива 1) (0 ≤ i ≤ 19): f = (b and c) xor ((not b) and d) (альтернатива 2) (0 ≤ i ≤ 19): f = (b and c) + ((not b) and d) (альтернатива 3)
(40 ≤ i ≤ 59): f = (b and c) or (d and (b or c)) (альтернатива 1) (40 ≤ i ≤ 59): f = (b and c) or (d and (b xor c)) (альтернатива 2) (40 ≤ i ≤ 59): f = (b and c) + (d and (b xor c)) (альтернатива 3) (40 ≤ i ≤ 59): f = (b and c) xor (b and d) xor (c and d) (альтернатива 4)
Примеры Ниже приведены примеры хешей SHA-1. Для всех сообщений подразумевается использование кодировки UTF-8.
Хеш панграммы на русском:
SHA-1("В чащах юга жил бы цитрус? Да, но фальшивый экземпляр!") = 9e32295f 8225803b b6d5fdfc c0674616 a4413c1b
Хеш панграммы на английском:
SHA-1("The quick brown fox jumps over the lazy dog") = 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12
SHA-1("sha") = d8f45903 20e1343a 915b6394 170650a8 f35d6926
Небольшое изменение исходного текста (одна буква в верхнем регистре) приводит к сильному изменению самого хеша. Это происходит вследствие лавинного эффекта.
SHA-1("Sha") = ba79baeb 9f10896a 46ae7471 5271b7f5 86e74640
Даже для пустой строки вычисляется нетривиальное хеш-значение.
SHA-1("") = da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709
Криптоанализ Криптоанализ хеш-функций направлен на исследование уязвимости для различного вида атак. Основные из них: нахождение коллизий — ситуация, когда двум различным исходным сообщениям соответствует одно и то же хеш-значение. нахождение прообраза — исходного сообщения — по его хешу.
При решении методом «грубой силы»: первая задача требует в среднем 2160/2 = 280 операций, если использовать атаку Дней рождения. вторая требует 2160 операций.
От устойчивости хеш-функции к нахождению коллизий зависит безопасность электронной цифровой подписи с использованием данного хеш-алгоритма. От устойчивости к нахождению прообраза зависит безопасность хранения хешей паролей для целей аутентификации.
В январе 2005 года Винсент Рэймен и Элизабет Освальд опубликовали сообщение об атаке на усечённую версию SHA-1 (53 раунда вместо 80), которая позволяет находить коллизии меньше, чем за 280 операций.
В феврале 2005 года Сяоюнь Ван, Ицюнь Лиза Инь и Хунбо Юй (Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu) представили атаку на полноценный SHA-1, которая требует менее 269 операций.
О методе авторы пишут:
Мы представляем набор стратегий и соответствующих методик, которые могут быть использованы для устранения некоторых важных препятствий в поиске коллизий в SHA-1. Сначала мы ищем близкие к коллизии дифференциальные пути, которые имеют небольшой «вес Хамминга» в «векторе помех», где каждый бит представляет 6-шаговую локальную коллизию. Потом мы соответствующим образом корректируем дифференциальный путь из первого этапа до другого приемлемого дифференциального пути, чтобы избежать неприемлемых последовательных и усеченных коллизий. В конце концов мы преобразуем два одноблоковых близких к коллизии дифференциальных пути в один двухблоковый коллизионный путь с удвоенной вычислительной сложностью.
Также они заявляют:
В частности, наш анализ основан на оригинальной дифференциальной атаке на SHA-0, «near-collision» атаке на SHA-0, мультиблоковой методике, а также методике модификации исходного сообщения, использованных при атаках поиска коллизий на HAVAL-128, MD4, RIPEMD и MD5.
Статья с описанием алгоритма была опубликована в августе 2005 года на конференции CRYPTO.
В этой же статье авторы опубликовали атаку на усечённый SHA-1 (58 раундов), которая позволяет находить коллизии за 233 операций.
В августе 2005 года на CRYPTO 2005 эти же специалисты представили улучшенную версию атаки на полноценный SHA-1, с вычислительной сложностью в 263 операций. В декабре 2007 года детали этого улучшения были проверены Мартином Кохраном.
Кристоф де Каньер и Кристиан Рехберг позже представили усовершенствованную версию атаки на SHA-1, за что были удостоены награды за лучшую статью на конференции ASIACRYPT 2006. Ими была представлена двухблоковая коллизия на 64-раундовый алгоритм с вычислительной сложностью около 235 операций.
Существует масштабный исследовательский проект, стартовавший в технологическом университете австрийского города Грац, который : «… использует компьютеры, соединенные через Интернет, для проведения исследований в области криптоанализа. Вы можете поучаствовать в проекте, загрузив и запустив бесплатную программу на своем компьютере.»
Бурт Калински, глава исследовательского отдела в «лаборатории RSA», предсказывает, что первая атака по нахождению прообраза будет успешно осуществлена в ближайшие 5—10 лет.
Ввиду того, что теоретические атаки на SHA-1 оказались успешными, NIST планирует полностью отказаться от использования SHA-1 в цифровых подписях.
Из-за блочной и итеративной структуры алгоритмов, а также отсутствия специальной обработки в конце хеширования, все хеш-функции семейства SHA уязвимы для атак удлинением сообщения и коллизиям при частичном хешировании сообщения., John Wiley & Sons, 2010. ISBN 978-0-470-47424-2 Эти атаки позволяют подделывать сообщения, подписанные только хешем — или — путём удлинения сообщения и пересчёту хеша без знания значения ключа. Простейшим исправлением, позволяющим защититься от этих атак, является двойное хеширование — ( — блок нулей той же длины, что и блок хеш-функции).
2 ноября 2007 года NIST анонсировал конкурс по разработке нового алгоритма SHA-3, который продлился до 2012 года.
SHAppening 8 октября 2015 Marc Stevens, Pierre Karpman, и Thomas Peyrin опубликовали атаку на функцию сжатия алгоритма SHA-1, которая требует всего 257 вычислений.
Реальный взлом: SHAttered (нахождение коллизий) 23 февраля 2017 года специалисты из Google и CWI объявили о практическом взломе алгоритма, опубликовав 2 PDF-файла с одинаковой контрольной суммой SHA-1. Это потребовало перебора вариантов, что заняло бы 110 лет на 1 GPU.
При помощи Stellora.AI на квантовом компьютере IBM QPU Heron было проделано следующее: Хэшировано в сочетании с алгоритмом Гровера некоторое количество входных данных через SHA-1 Разработана квантовая схема специально под алгоритмизацию с помощью Stellora.AI Реализована разработанная схема на квантовом компьютере IBM Heron QPU Восстановлены исходные входные значения из хэша SHA-1 всего за ~4 секунды работы QPU
Сравнение SHA-1 с другими алгоритмами
Сравнение с MD5 И MD5, и SHA-1 являются, по сути, улучшенными продолжениями MD4.
Сходства: Четыре этапа. Каждое действие прибавляется к ранее полученному результату. Размер блока обработки, равный 512 бит. Оба алгоритма выполняют сложение по модулю 232, они рассчитаны на 32-битную архитектуру.
Различия: