SHA1

Криптографическая хеш-функция
Название	SHA-1
Разработчик	NSA совместно с NIST
Создан	1995
Опубликован	1995
Размер хеша	160 бит
Число раундов	80
Тип	хеш-функция

Secure Hash Algorithm 1 — алгоритм криптографического хеширования. Описан в RFC 3174. Для входного сообщения произвольной длины (максимум 2⁶⁴ − 1 бит) алгоритм генерирует 160-битное хеш-значение, называемое также дайджестом сообщения. Используется во многих криптографических приложениях и протоколах. Также рекомендован в качестве основного для государственных учреждений в США. Принципы, положенные в основу SHA-1, аналогичны тем, которые использовались Рональдом Ривестом при проектировании

Содержание

• 1 История
• 2 Описание алгоритма
  • 2.1 Инициализация
  • 2.2 Главный цикл
  • 2.3 Псевдокод SHA-1
• 3 Примеры
• 4 Криптоанализ
• 5 Сравнение SHA-1 с другими алгоритмами
  • 5.1 Сравнение с MD5
  • 5.2 Сравнение с ГОСТ Р 34.11-94
  • 5.3 Сравнение с другими SHA
• 6 Использование
• 7 Примечания
• 8 Ссылки
• 9 Литература

История

В 1993 году NSA совместно с NIST разработали алгоритм безопасного хеширования (сейчас известный как SHA-0) (опубликован в документе FIPS PUB 180) для стандарта безопасного хеширования. Однако вскоре NSA отозвало данную версию, сославшись на обнаруженную ими ошибку, которая так и не была раскрыта. И заменило его исправленной версией, опубликованной в 1995 году в документе FIPS PUB 180-1. Эта версия и считается тем, что называют SHA-1. Немного спустя, на конференции CRYPTO в 1998 году два французских исследователя представили атаку на алгоритм SHA-0, которая не работала на алгоритме SHA-1 Возможно, это и была ошибка, открытая NSA.

Описание алгоритма

Одна итерация алгоритма SHA1

SHA-1 реализует однонаправленную хеш-функцию, построенную на идее функции сжатия. Входами функции сжатия являются блок сообщения длиной 512 бит и выход предыдущего блока сообщения. Выход представляет собой значение всех хеш-блоков до этого момента. Иными словами хеш блока M_i равен h_i = f(M_i,h_{i − 1}). Хеш-значением всего сообщения является выход последнего блока.

Инициализация

Исходное сообщение разбивается на блоки по 512 бит в каждом. Последний блок дополняется до длины, кратной 512 бит. Сначала добавляется 1 а потом нули, чтобы длина блока стала равной 512 — 64 бит. В оставшиеся 64 бита записывается длина исходного сообщения в битах. Дополнение последнего блока осуществляется всегда, даже если сообщение уже имеет нужную длину. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512.

Инициализируются пять 32-битовых переменных.

A = a = 0x67452301
B = b = 0xEFCDAB89
C = c = 0x98BADCFE
D = d = 0x10325476
E = e = 0xC3D2E1F0

Определяются четыре нелинейные операции и четыре константы.

$F_t(m, l, k) = (m \wedge l) \vee (\neg{m} \wedge k)$	Kt = 0x5A827999	0≤t≤19
$F_t(m, l, k) = m \oplus l \oplus k$	Kt = 0x6ED9EBA1	20≤t≤39
$F_t(m, l, k) = (m \wedge l) \vee (m \wedge k) \vee (l \wedge k)$	Kt = 0x8F1BBCDC	40≤t≤59
$F_t(m, l, k) = m \oplus l \oplus k$	Kt = 0xCA62C1D6	60≤t≤79

Главный цикл

Главный цикл итеративно обрабатывает каждый 512-битный блок. Итерация состоит из четырех этапов по двадцать операций в каждом. Блок сообщения преобразуется из 16 32-битовых слов M_i в 80 32-битовых слов W_j по следующему правилу:

Wt = Mt                                      при 0≤t≤15
Wt = (Wt-3 $\oplus$ Wt-8 $\oplus$ Wt-14 $\oplus$ Wt-16) << 1     при 16≤t≤79

здесь << – это циклический сдвиг влево

для t от 0 до 79 
	temp = (a<<5) + Ft(b,c,d) + e + Wt + Kt   
	e = d 
	d = c 
	c = b<<30                                
	b = a 
	a = temp 

После этого a, b, c, d, e прибавляются к A, B, C , D , E соответственно. Начинается следующая итерация.

Итоговым значением будет объединение пяти 32-битовых слов в одно 160-битное хеш-значение.

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

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

Замечание: Все используемые переменные 32 бита.

Инициализация переменных:
h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0

Предварительная обработка:
Присоединяем бит '1' к сообщению
присоединяем k битов '0', где k наименьшее число ≥ 0 такое что длина получившегося сообщения(в битах) сравнима с 448 (mod 512)
добавленная длина сообщения в битах, (после предварительной обработки), в битах.

В процессе сообщение разбивается последовательно по 512 бит:
for перебираем все такие части
    разбиваем этот кусок на 16 частей, слов по 32-бита 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
            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

    Добавляем хеш-значение этой части к результату:
    h0 = h0 + a
    h1 = h1 + b 
    h2 = h2 + c
    h3 = h3 + d
    h4 = h4 + e

Итог конечное хеш-значение:
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. Для всех сообщений подразумевается использование кодировки панграммы на русском:

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

Криптоанализ

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

• нахождение коллизий — ситуация, когда двум различным исходным сообщениям соответствует одно и то же хеш-значение.
• нахождение прообраза — исходного сообщения — по его хешу.

При решении методом «грубой силы»:

• вторая задача требует 2¹⁶⁰ операций.
• первая же требует в среднем 2^160/2 = 2⁸⁰ операций, если использовать парадокс дней рождения.

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

В январе 2005 года Vincent Rijmen и Elisabeth Oswald опубликовали сообщение об атаке на усеченную версию SHA-1 (53 раунда вместо 80), которая позволяет находить коллизии меньше, чем за 2⁸⁰ операций.

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

О методе авторы пишут:

Мы представляем набор стратегий и соответствующих методик, которые могут быть использованы для устранения некоторых важных препятствий в поиске коллизий в SHA-1. Сначала мы ищем близкие к коллизии дифференциальные пути, которые имеют небольшой "вес Хамминга" в "векторе помех", где каждый 1-бит представляет 6-шаговую локальную коллизию. Потом, мы соответствующим образом корректируем дифференциальный путь из первого этапа до другого приемлемого дифференциального пути, чтобы избежать неприемлемых последовательных и усеченных коллизий. В конце концов мы преобразуем два одноблоковых близких к коллизии дифференциальных пути в один двухблоковый коллизионный путь с удвоенной вычислительной сложностью.^[1]

Оригинальный текст (англ.)  

We introduce a set of strategies and corresponding techniques that can be used to remove some major obstacles in collision search for SHA-1. Firstly, we look for a near-collision differential path which has low Hamming weight in the "disturbance vector" where each 1-bit represents a 6-step local collision. Secondly, we suitably adjust the differential path in the first round to another possible differential path so as to avoid impossible consecutive local collisions and truncated local collisions. Thirdly, we transform two one-block near-collision differential paths into a twoblock collision differential path with twice the search complexity.

Также они заявляют:

В частности, наш анализ основан на оригинальной дифференциальной атаке на SHA-0, "near-collision" атаке на SHA-0, мультиблоковой методике, а также методикам модификации исходного сообщения, использованных при атаках поиска коллизий на HAVAL-128, MD5.

Оригинальный текст (англ.)  

In particular, our analysis is built upon the original differential attack on SHA-0, the near collision attack on SHA-0, the multi-block collision techniques, as well as the message modification techniques used in the collision search attacks on HAVAL-128, MD4, RIPEMD and MD5.

Статья с описанием алгоритма была опубликована в августе 2005 года на конференции CRYPTO.

В этой же статье авторы опубликовали атаку на усеченный SHA-1 (58 раундов), которая позволяет находить коллизии за 2³³ операций.

В августе 2005 года на CRYPTO 2005 эти же специалисты представили улучшенную версию атаки на полноценный SHA-1, с вычислительной сложностью в 2⁶³ операций. В декабре 2007 года детали этого улучшения были проверены Мартином Кохраном.

Кристоф де Каньер и Кристиан Рехберг позже представили усовершенствованную версию атаки на SHA-1, за что были удостоены награды за лучшую статью на конференции ASIACRYPT 2006. Ими была представлена двух-блоковая коллизия на 64-раундовый алгоритм с вычислительной сложностью около 2³⁵ операций.^[2]

Существует масштабный исследовательский проект, стартовавший в технологическом университете австрийского города Грац, который : «… использует компьютеры соединенные через Интернет, для проведения исследований в области криптоанализа. Вы можете поучаствовать в проекте загрузив и запустив бесплатную программу на своем компьютере.»^[3]

Хотя теоретически SHA-1 считается взломанным (количество вычислительных операций сокращено в 2^80-63 = 131 000 раз), на практике подобный взлом неосуществим, так как займет пять миллиардов лет.

Бурт Калински, глава исследовательского отдела в «лаборатории RSA» предсказывает, что первая атака по нахождению прообраза будет успешно осуществлена в ближайшие 5-10 лет.

Ввиду того, что теоретические атаки на SHA-1 оказались успешными, NIST планирует полностью отказаться от использования SHA-1 в цифровых подписях.^[4]

2 ноября 2007 года NIST анонсировало конкурс по разработке нового алгоритма SHA-3, который продлится до 2012 года.^[5]

Сравнение SHA-1 с другими алгоритмами

Сравнение с MD5

И MD4.

Сходства:

1. Четыре этапа.
2. Каждое действие прибавляется к ранее полученному результату.
3. Размер блока обработки равный 512 бит.
4. Оба алгоритма выполняют сложение по модулю 2³², они рассчитаны на 32-битную архитектуру.

Различия:

1. В SHA-1 на четвертом этапе используется та же функция f, что и на втором этапе.
2. В
3. В SHA-1 добавлена пятая переменная.
4. SHA-1 использует циклический код исправления ошибок.
5. В SHA на каждом этапе используется постоянное значение сдвига.
6. В
7. В
8. SHA-1 содержит больше раундов (80 вместо 64) и выполняется на 160-битном буфере по сравнению со 128-битным буфером MD5 на той же аппаратуре.

Брюс Шнайер делает следующий вывод : «SHA-1 — это MD5 — это

Сравнение с ГОСТ Р 34.11-94

Ряд отличительных особенностей ГОСТ Р 34.11-94:

1. При обработке блоков используются преобразования по алгоритму ГОСТ 28147—89;
2. Обрабатывается блок длиной 256 бит, и выходное значение тоже имеет длину 256 бит.
3. Применены меры борьбы против поиска коллизий, основанном на неполноте последнего блока.
4. Обработка блоков происходит по алгоритму шифрования ГОСТ 28147—89, который содержит преобразования на S - боксах, что существенно осложняет применение метода дифференциального криптоанализа к поиску коллизий алгоритма ГОСТ Р 34.11-94. Это существенный плюс по сравнению с SHA-1.
5. Теоретическая криптостойкость ГОСТ Р 34.11-94 равна 2¹²⁸, что во много раз превосходит 2⁸⁰для SHA-1.
6. Скорость обработки данных для SHA-1 - 48.462*2²⁰ байт/с, а для ГОСТ Р 34.11-94 - 9.977*2²⁰ байт/с.

Сравнение с другими SHA

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

Вариации алгоритма		Размер выходного хеша (бит)	Промежуточный размер хеша (бит)	Размер блока (бит)	Максимальная длина входного сообщения (бит)	Размер слова (бит)	Количество раундов	Используемые операции	Найденные коллизии
SHA-0		160	160	512	264 − 1	32	80	+,and,or,xor,rotl	Есть
SHA-1		160	160	512	264 − 1	32	80	+,and,or,xor,rotl	252 операций
	32	64	+,and,or,xor,shr,rotr	Нет
	SHA-512/384	512/384	512	1024	2128 − 1	64	80	+,and,or,xor,shr,rotr	Нет

Использование

Хеш-функции используются в системах контроля версий, системах электронной подписи, а также для построения кодов аутентификации.

SHA-1 является наиболее распространенным из всего семейства SHA и применяется в различных широко распространенных криптографических приложениях и алгоритмах.

SHA-1 используется в следующих приложениях:

• S/MIME — дайджесты сообщений.
• IPSec — для алгоритма проверки целостности в соединении «точка-точка».

SHA-1 является основой блочного шифра

Примечания

1. ↑ Finding Collisions in the Full SHA-1 (англ.). — Статья китайских исследователей о взломе SHA-1.
2. ↑ Finding SHA-1 Characteristics: General Results and Applications (англ.).
3. ↑ SHA-1 Collision Search Graz (англ.). — Исследовательский проект технологического университета Граца.
4. ↑ NIST Comments on Cryptanalytic Attacks on SHA-1 (англ.). — Официальный комментарий NIST по поводу атак на SHA-1.
5. ↑ NIST Hash Competition (англ.). — Конкурс на разработку SHA-3.

Ссылки

• RFC 3174(англ.)
• Обзор SHA-1 от Консорциума Всемирной паутины(англ.)
• Взлом SHA-1(англ.)
• Онлайн Взлом SHA1
• Поиск по базам и восстановление SHA1
• Доклад о взломе SHA1(англ.)
• Брюс Шнайер о взломе SHA(англ.)
• Последствия удачных атак на SHA-1(англ.)

Литература

• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4
• Нильс Фергюсон, Брюс Шнайер Практическая криптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М.: «Диалектика», 2004. — С. 432. — ISBN 0-471-22357-3

Хеш-функции

CRC | HAVAL | LM-хеш | MD4 | MD6 | PJW-32 | RIPEMD-256 | SHA-1 | Skein | TTH | Whirlpool | ГОСТ Р 34.11-94