SHA-1
SHA-1 | |
---|---|
Разработчики | NSAсовместно сNIST |
Создан | 1995 |
Опубликован | 1995 |
Предшественник | SHA-0[вд] |
Преемник | SHA-2 |
Размер хеша | 160 бит |
Число раундов | 80 |
Тип | хеш-функция |
Secure Hash Algorithm 1— алгоритмкриптографического хеширования.Описан вRFC 3174.Для входного сообщения произвольной длины (максимумбит, что примерно равно 2эксабайта) алгоритм генерирует 160-битное (20 байт) хеш-значение, называемое такжедайджестомсообщения, которое обычно отображается как шестнадцатеричное число длиной в 40 цифр. Используется во многих криптографических приложениях и протоколах. Также рекомендован в качестве основного для государственных учреждений вСША.Принципы, положенные в основу SHA-1, аналогичны тем, которые использовалисьРональдом Ривестомпри проектированииMD4.
История
[править|править код]В1993 годуNSAсовместно сNISTразработали алгоритм безопасного хеширования (сейчас известный как SHA-0) (опубликован в документеFIPSPUB 180) для стандарта безопасного хеширования. Однако вскореNSAотозвало данную версию, сославшись на обнаруженную ими ошибку, которая так и не была раскрыта, и заменило его исправленной версией, опубликованной в1995 годув документеFIPSPUB 180-1. Эта версия и считается тем, что называют SHA-1. Позже, на конференцииCRYPTOв1998 годудва французских исследователя представили атаку на алгоритм SHA-0, которая не работала на алгоритме SHA-1. Возможно, это и была ошибка, открытаяNSA.
Описание алгоритма
[править|править код]![](https://upload.wikimedia.org/wikipedia/commons/thumb/e/e2/SHA-1.svg/300px-SHA-1.svg.png)
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-битовых слов: forifrom16to79 w[i] = (w[i-3]xorw[i-8]xorw[i-14]xorw[i-16])циклический сдвиг влево1 Инициализация хеш-значений этой части: a = h0 b = h1 c = h2 d = h3 e = h4 Основной цикл: forifrom0to79 if0 ≤ i ≤ 19then f = (bandc)or((notb)andd) k = 0x5A827999 else if20 ≤ i ≤ 39then f = bxorcxord k = 0x6ED9EBA1 else if40 ≤ i ≤ 59then f = (bandc)or(bandd)or(candd) k = 0x8F1BBCDC else if60 ≤ i ≤ 79then f = bxorcxord k = 0xCA62C1D6 temp = (aleftrotate5) + f + e + k + w[i] e = d d = c c = bleftrotate30 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 = h0appendh1appendh2appendh3appendh4
Вместо оригинальной формулировки FIPS PUB 180-1 приведены следующие эквивалентные выражения и могут быть использованы на компьютереf
в главном цикле:
(0 ≤ i ≤ 19): f = dxor(band(cxord))(альтернатива 1) (0 ≤ i ≤ 19): f = (bandc)xor((notb)andd)(альтернатива 2) (0 ≤ i ≤ 19): f = (bandc) + ((notb)andd)(альтернатива 3) (40 ≤ i ≤ 59): f = (bandc)or(dand(borc))(альтернатива 1) (40 ≤ i ≤ 59): f = (bandc)or(dand(bxorc))(альтернатива 2) (40 ≤ i ≤ 59): f = (bandc) + (dand(bxorc))(альтернатива 3) (40 ≤ i ≤ 59): f = (bandc)xor(bandd)xor(candd)(альтернатива 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-шаговую локальную коллизию. Потом мы соответствующим образом корректируем дифференциальный путь из первого этапа до другого приемлемого дифференциального пути, чтобы избежать неприемлемых последовательных и усеченных коллизий. В конце концов мы преобразуем два одноблоковых близких к коллизии дифференциальных пути в один двухблоковый коллизионный путь с удвоенной вычислительной сложностью.[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,MD4,RIPEMDи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 раундов), которая позволяет находить коллизии за 233операций.
В августе2005 годанаCRYPTO2005 эти же специалисты представили улучшенную версию атаки на полноценный SHA-1, с вычислительной сложностью в 263операций. В декабре2007 годадетали этого улучшения были проверены Мартином Кохраном.
Кристоф де Каньер и Кристиан Рехберг позже представили усовершенствованную версию атаки на SHA-1, за что были удостоены награды за лучшую статью на конференцииASIACRYPT2006.Ими была представлена двухблоковая коллизия на 64-раундовый алгоритм с вычислительной сложностью около 235операций.[2]
Существует масштабный исследовательский проект, стартовавший втехнологическом университете австрийского города Грац,который: «… использует компьютеры, соединенные черезИнтернет,для проведения исследований в области криптоанализа. Вы можете поучаствовать в проекте, загрузив и запустив бесплатную программу на своем компьютере.»[3]
Бурт Калински,глава исследовательского отдела в «лабораторииRSA», предсказывает, что первая атака по нахождению прообраза будет успешно осуществлена в ближайшие 5—10 лет.
Ввиду того, что теоретические атаки на SHA-1 оказались успешными,NISTпланирует полностью отказаться от использования SHA-1 в цифровых подписях.[4]
Из-за блочной и итеративной структуры алгоритмов, а также отсутствия специальной обработки в конце хеширования, все хеш-функции семейства SHA уязвимы дляатак удлинением сообщенияи коллизиям при частичном хешировании сообщения.[5]Эти атаки позволяют подделывать сообщения, подписанные только хешем —или— путём удлинения сообщения и пересчёту хеша без знания значения ключа. Простейшим исправлением, позволяющим защититься от этих атак, является двойное хеширование —(— блок нулей той же длины, что и блок хеш-функции).
2 ноября2007 годаNISTанонсировал конкурс по разработке нового алгоритмаSHA-3,который продлился до2012 года.[6]
SHAppening
[править|править код]8 октября 2015 Marc Stevens, Pierre Karpman, и Thomas Peyrin опубликовали атаку на функцию сжатия алгоритма SHA-1, которая требует всего 257вычислений.
Реальный взлом: SHAttered (нахождение коллизий)
[править|править код]23 февраля 2017 года специалисты изGoogleиCWIобъявили о практическом взломе алгоритма, опубликовав 2PDF-файла с одинаковойконтрольной суммойSHA-1. Это потребовало переборавариантов, что заняло бы 110 лет на 1GPU[7].
Сравнение SHA-1 с другими алгоритмами
[править|править код]Сравнение с MD5
[править|править код]ИMD5,и SHA-1 являются, по сути, улучшенными продолжениямиMD4.
Сходства:
- Четыре этапа.
- Каждое действие прибавляется к ранее полученному результату.
- Размер блока обработки, равный 512 бит.
- Оба алгоритма выполняют сложение по модулю 232,они рассчитаны на 32-битную архитектуру.
Различия:
- В SHA-1 на четвёртом этапе используется та же функция f, что и на втором этапе.
- ВMD5в каждом действии используется уникальная прибавляемая константа. В SHA-1 константы используются повторно для каждой из четырёх групп.
- В SHA-1 добавлена пятая переменная.
- SHA-1 используетциклический кодисправления ошибок.
- ВMD5четыре сдвига, используемые на каждом этапе, отличаются от значений, используемых на предыдущих этапах. ВSHAна каждом этапе используется постоянное значение сдвига.
- ВMD5— четыре различных элементарных логических функции, в SHA-1 — три.
- ВMD5длина дайджеста составляет 128 бит, в SHA-1 — 160 бит.
- SHA-1 содержит больше раундов (80 вместо 64) и выполняется на 160-битном буфере по сравнению со 128-битным буферомMD5.Таким образом, SHA-1 должен выполняться приблизительно на 25 % медленнее, чемMD5на той же аппаратуре.
Брюс Шнайерделает следующий вывод: «SHA-1 — этоMD4с добавлением расширяющего преобразования, дополнительного этапа и улучшенным лавинным эффектом.MD5— этоMD4с улучшенным битовым хешированием, дополнительным этапом и улучшенным лавинным эффектом.»
Сравнение с ГОСТ Р 34.11-94
[править|править код]Ряд отличительных особенностейГОСТ Р 34.11-94:
- При обработке блоков используются преобразования по алгоритмуГОСТ 28147—89;
- Обрабатывается блок длиной 256 бит, и выходное значение тоже имеет длину 256 бит.
- Применены меры борьбы против поиска коллизий, основанном на неполноте последнего блока.
- Обработка блоков происходит по алгоритму шифрованияГОСТ 28147—89,который содержит преобразования наS-блоках,что существенно осложняет применение методадифференциального криптоанализак поиску коллизий алгоритмаГОСТ Р 34.11-94.Это существенный плюс по сравнению с SHA-1.
- Теоретическая криптостойкостьГОСТ Р 34.11-94равна 2128,что во много раз превосходит 280для SHA-1.
Сравнение с другими 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операций | |
SHA-2 | SHA-256/224 | 256/224 | 256 | 512 | 264− 1 | 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— дайджесты сообщений.
- SSL— дайджесты сообщений.
- IPSec— для алгоритма проверки целостности в соединении «точка-точка».
- SSH— для проверки целостности переданных данных.
- PGP— для создания электронной цифровой подписи.
- Git— для идентификации каждого объекта по SHA-1-хешу от хранимой в объекте информации.
- Mercurial— для идентификации ревизий
- BitTorrent— для проверки целостности загружаемых данных.
SHA-1является основой блочного шифраSHACAL.
Отказ от использования
[править|править код]КомпанияGoogleдавно выразила своё недоверие SHA-1, особенно для использования этой функции для подписи сертификатовTLS.Ещё в 2014 году, вскоре после публикации работы Марка Стивенса, группа разработчиковChromeобъявила о постепенном отказе от использования SHA-1.
С 25 апреля 2016 годаЯндекс Почтаперестала поддерживать старые почтовые программы, использующие SHA-1[8].
Примечания
[править|править код]- ↑Finding Collisions in the Full SHA-1(англ.).— Статья китайских исследователей о взломе SHA-1. Архивировано изоригинала23 августа 2011 года.
- ↑Finding SHA-1 Characteristics: General Results and Applications(англ.).Дата обращения: 4 октября 2017.Архивировано26 июля 2008 года.
- ↑SHA-1 Collision Search Graz(англ.).— Исследовательский проект технологического университета Граца.Архивировано7 ноября 2008 года.
- ↑NIST Comments on Cryptanalytic Attacks on SHA-1(англ.).— Официальный комментарий NIST по поводу атак на SHA-1. Архивировано изоригинала13 октября 2012 года.
- ↑Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno, Cryptography Engineering(англ.).Архивировано изоригинала13 октября 2012 года.,John Wiley & Sons, 2010.ISBN 978-0-470-47424-2
- ↑NIST Hash Competition(англ.).— Конкурс на разработку SHA-3. Архивировано изоригинала13 октября 2012 года.
- ↑Первый способ генерации коллизий для SHA-1 .Дата обращения: 9 марта 2017.Архивировано10 марта 2017 года.
- ↑Обновление почтовых программ — Почта — Яндекс.Помощь .yandex.ru. Дата обращения: 7 апреля 2016.Архивировано20 апреля 2016 года.
Литература
[править|править код]- Шнайер Б.Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = 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 с. —3000 экз.—ISBN 5-8459-0733-0,ISBN 0-4712-2357-3.
Ссылки
[править|править код]- RFC 3174(англ.)
- Обзор SHA-1 от Консорциума Всемирной паутиныАрхивная копияот 4 марта 2005 наWayback Machine(англ.)
- Взлом SHA-1Архивная копияот 5 мая 2017 наWayback Machine(англ.)
- Доклад о взломе SHA1(англ.)
- Брюс Шнайер о взломе SHAАрхивировано1 декабря 2012 года.(англ.)
- Последствия удачных атак на SHA-1Архивная копияот 26 декабря 2008 наWayback Machine(англ.)