close

Алгоритм безопасного хеширования

Перейти к навигации Перейти к поиску

Термин SHA ( аббревиатура от английского Secure Hash Algorithm ) обозначает семейство из пяти различных криптографических хэш- функций, разработанных с 1993 года Агентством национальной безопасности (АНБ) и опубликованных NIST в качестве федерального стандарта правительством США ( FIPS PUB 180-4). ).

Как и любой алгоритм хеширования , SHA создает дайджест сообщения фиксированной длины или « отпечаток сообщения » из сообщения переменной длины. Безопасность хеш- алгоритма заключается в том, что функция необратима (то есть невозможно вернуться к исходному сообщению, зная только эти данные) и никогда не должно быть возможности преднамеренно создать два разных сообщения с тот же дайджест . Алгоритмы семейства называются SHA-1 , SHA-224 , SHA-256 , SHA-384 и SHA-512 : последние 4 варианта часто называют SHA-2 , чтобы отличить их от первого. Первый выдает дайджест сообщения длиной всего 160 бит , в то время как другие выдают дайджест длиной в битах, равной числу, указанному в их аббревиатуре (SHA-256 выдает дайджест из 256 бит). SHA-1 является наиболее распространенным алгоритмом семейства SHA и используется во многих приложениях и протоколах, хотя сейчас он небезопасен и вскоре будет заменен другими, более современными и эффективными.

Безопасность SHA-1 была скомпрометирована криптоаналитиками . [1] Хотя атаки на варианты SHA-2 еще не известны, они имеют алгоритм, аналогичный алгоритму SHA-1, поэтому предпринимаются усилия по разработке альтернативных и улучшенных алгоритмов хеширования . [2] [3] Открытый конкурс на реализацию новой функции SHA-3 был объявлен в Федеральном реестре 2 ноября 2007 г. [4] NIST и посредством публичного конкурса , аналогичного принятому для процесса разработки 2 октября 2012 года AES [ 5] объявила алгоритм Кекчака победителем . Таким образом, работа группы итальянских и бельгийских аналитиков Keccak [6] , кажется, обречена на постепенное включение и внедрение в самые разнообразные решения по ИТ-безопасности.

23 февраля 2017 года команда Google объявила о первой практической методике генерации хеш-коллизии . [7] [8]

SHA-0 и SHA-1

Image
Итерация в функции сжатия SHA-1. A, B, C, D и E — 32-битные слова состояния; F — нелинейная функция, которая меняется; n обозначает поворот левого бита на n позиций; n меняется для каждой операции. обозначает сложение по модулю 2 32 . К т является константой.Сдвиг влевоДобавление

Первоначальная спецификация алгоритма была опубликована в 1993 году как Secure Hash Standard , FIPS PUB 180, NIST . Эту версию часто называют SHA-0 , чтобы отличить ее от более поздних версий. Он был отозван АНБ вскоре после публикации и заменен исправленной версией, опубликованной в 1995 году (FIPS PUB 180-1) и обычно известной как SHA-1 . SHA-1 отличается от SHA-0 только однократным чередованием битов в процессе подготовки сообщения его функции одностороннего сжатия; это было сделано, по мнению АНБ, для исправления недостатка исходного алгоритма, снижавшего криптографическую безопасность SHA-0. Однако АНБ не предоставило дополнительных уточняющих объяснений. Впоследствии сообщалось о недостатках как в коде SHA-0, так и в коде SHA-1. SHA-1, по-видимому, обеспечивает большую устойчивость к атакам, подтверждая утверждение АНБ о том, что это изменение повысило безопасность.

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

Операция

Шаг 1 (заполнение): биты «заполнения» добавляются к исходному сообщению, так что окончательная длина сообщения соответствует 448 по модулю 512, таким образом, если длина «сообщения + заполнение» в битах, деленная на 512, даст остаток 448.

Шаг 2 (Добавить длину): 64-битное целое число без знака, содержащее длину исходного сообщения, добавляется к битовой последовательности (сообщение + заполнение), созданной на шаге 1. В конце этих первых двух шагов мы получаем последовательность битов, кратную 512.

Шаг 3 (инициализация буфера MD): 160-битный буфер, разделенный на 5 регистров по 32 бита каждый, создается для хранения некоторых промежуточных шагов. 5 регистров обычно обозначаются (A, B, C, D, E) и инициализируются следующими шестнадцатеричными значениями:

  1. А = 67452301
  2. В = EFCDAB89
  3. С = 98BADCFE
  4. Д = 10325476
  5. Е = C3D2E1F0

Шаг 4 (обработка 512-битных блоков). Битовая последовательность «сообщение + заполнение + длина сообщения» делится на 512-битные блоки, которые мы будем идентифицировать с помощью B n с n в диапазоне от 0 до L. Ядро алгоритма SHA-1 это называется функцией сжатия и состоит из 4 циклов по 20 шагов каждый. Циклы имеют очень похожую структуру друг на друга, за исключением того факта, что они используют другую примитивную логическую функцию. Каждый блок принимается в качестве входного параметра всеми 4-мя циклами вместе с константой K и значениями 5-ти регистров. В конце вычисления мы получим новые значения для A, B, C, D, E, которые мы будем использовать для вычисления следующего блока до конечного блока F.

Набор SHA-2

Image
Итерация функции сжатия в алгоритмах семейства SHA-2.

В 2001 году NIST выпустил четыре дополнительные хеш- функции из семейства SHA, каждая из которых имеет более длинный дайджест , чем исходная, которые вместе именуются SHA-2 (хотя этот термин никогда не был официально стандартизирован). Эти варианты известны, как уже упоминалось, с длиной в битах дайджеста , сгенерированного после официальной аббревиатуры хэша : SHA-224 , SHA-256 , SHA-384 и SHA-512 , с хэшами соответственно 224, 256, 384. и 512 бит. Следует отметить, что последние три алгоритма были формализованы как стандартные в 2002 году, а SHA-224 был представлен в феврале 2004 года: последний имеет хэш такой же длины, что и 2 ключа Triple DES .

Все эти варианты запатентованы правительством США, но публикуются под свободной лицензией. [9] .

Алгоритмы SHA-256 и SHA-512 работают соответственно с 32- и 64-битными словами : они используют разное количество оборотов и дополнительные константы, но их структура практически идентична. Алгоритмы SHA-224 и SHA-384 — это просто усеченные версии двух предыдущих, в которых хэши вычисляются с разными начальными значениями.

Алгоритмы SHA-2, в отличие от SHA-1, не получили большого внимания со стороны сообщества криптоаналитиков, поэтому их криптографическая безопасность не была полностью доказана. Gilbert and Handschuh ( 2003 ) изучили эти новые варианты и не обнаружили уязвимостей [10] .

SHA-3

Конкурс , который привел к выпуску нового стандарта SHA-3 , был официально запущен 2 ноября 2007 г. [4] . 2 октября 2012 года NIST объявил алгоритм Keccak SHA-3 победителем .

Сравнение функций SHA

В таблице ниже приведены основные характеристики алгоритмов семейства SHA ( Внутреннее состояние означает внутреннюю сумму после каждого сжатия блока данных).

Алгоритм и
вариант 		Размер вывода (бит) Размер внутреннего состояния (бит) Размер блока (бит) Максимальный размер сообщения (бит) Размер слова (бит) Шаги Операции Найдено столкновений
ША-0 160 160 512 2 64 - 1 32 80 +, и, или, xor, rotl Ага
ША-1 160 160 512 2 64 - 1 32 80 +, и, или, xor, rotl Атака 2 53 [11]
ША-2 ША-256/224 256/224 256 512 2 64 - 1 32 64 +, и, или, xor, шр, ротр Никто
ША-512/384 512/384 512 1024 2 128 - 1 64 80 +, и, или, xor, шр, ротр Никто

Приложения

SHA-1 является наиболее часто используемым алгоритмом семейства SHA. Он лежит в основе многих приложений и протоколов, включая TLS и SSL , PGP , SSH , S/MIME и IPsec . SHA-1 также используется в системах контроля версий , таких как Git , для определения версии программного обеспечения и в качестве контрольной суммы для проверки целостности больших файлов в онлайн-каталогах.

Алгоритмы SHA также используются в алгоритмах цифровой подписи документов, таких как HMAC , и были взяты за основу для блочных шифров SHACAL .

Примеры и псевдокод

Пример хэша

Это пример дайджеста , сгенерированного SHA-1 (все сообщения закодированы в ASCII ): 

SHA1 («Cantami o diva pelide Ахилла, фатальный гнев»)
 = 1f8a690b7366a2323e2d5b045120da7e93896f47

Даже малейшее изменение в сообщении неизбежно приводит к созданию совершенно другого хэша из-за цепной реакции , известной как эффект лавины . Например, заменив Cantamiна Contamiполучим: 

SHA1 (« Контами или дива пелиса Ахиллес фатальный гнев»)
 = e5f08d98bf18385e2f26b904cad23c734d530ffb

Дайджест , соответствующий пустой строке: 

SHA1 ("")
 = da39a3ee5e6b4b0d3255bfef95601890afd80709

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

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

Примечания: Все переменные являются 32-битными без знака и переносятся по модулю 2 32 при вычислении .

Инициализировать переменные:
ч0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0

Предварительная обработка:
добавить бит '1' к сообщению
добавить k битов '0', где k — минимальное число ≥ 0, такое, что результирующее сообщение
    длина (в битах ) соответствует 448 (mod 512 )
добавить длину сообщения (до предварительной обработки) в битах как 64-битное целое число
 с обратным порядком байтов
Обработайте сообщение в последующих 512-битных фрагментах:
разбить сообщение на 512-битные куски
для каждого куска
    разбить фрагмент на шестнадцать 32-битных слов с обратным порядком байтов w [i], 0 <= i <= 15

    Расширьте шестнадцать 32-битных слов до восьмидесяти 32-битных слов:
     для i от 16 до 79
        w [i] = (w [i-3] xor w [i-8] xor w [i-14] xor w [i-16]) повернуть влево 1

    Инициализируйте хеш-значение для этого фрагмента:
    а = h0
    б = h1
    с = h2
    д = h3
    е = h4

    Основной цикл:
     для i от 0 до 79
         , если 0 ≤ i ≤ 19 , то 
            f = (b и c) или (( не b) и d)
            к = 0x5A827999
        иначе, если 20 ≤ i ≤ 39
            f = b xor c xor d
            к = 0x6ED9EBA1
        иначе, если 40 ≤ i ≤ 59
            f = (b и c) или (b и d) или (c и d)
            к = 0x8F1BBCDC
        иначе, если 60 ≤ i ≤ 79
            f = b xor c xor d
            к = 0xCA62C1D6

        temp = (a левый поворот 5) + f + e + k + w [i]
        е = д
        д = с
        c = b поворот влево 30
        б = а
        а = температура

    Добавьте хэш этого чанка к результату на данный момент:
    h0 = h0 + а
    h1 = h1 + b
    h2 = h2 + с
    h3 = h3 + d
    h4 = h4 + е

Вывести окончательное хеш-значение (с прямым порядком байтов): 
дайджест = хэш = h0 добавить h1 добавить h2 добавить h3 добавить h4

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

(0 ≤ i ≤ 19): f = d xor (b и (c xor d))                 (вариант 1) 
(0 ≤ i ≤ 19): f = (b и c) xor (( не b) и d)           ( варианты 2) 
(0 ≤ i ≤ 19): f = (b и c) + (( не b) и d)             (варианты 3)
 
(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) + (d и (b xor c))           (варианты 3) 
(40 ≤ i ≤ 59): f = (b и c) xor (b и d) xor (c и d)   (вариант 4)

Псевдокод SHA-256 (вариант SHA-2)

Псевдокод алгоритма SHA-256. Обратите внимание на увеличение смешивания битов слов w[16..63]по сравнению с SHA-1. 

Примечания: Все переменные являются 32-битными без знака и переносятся по модулю 2 32 при вычислении .

Инициализировать переменные
 (первые 32 бита дробных частей квадратных корней первых 8 простых чисел 2..19):
ч0: = 0x6a09e667
h1: = 0xbb67ae85
h2: = 0x3c6ef372
h3: = 0xa54ff53a
h4: = 0x510e527f
h5: = 0x9b05688c
h6: = 0x1f83d9ab
h7: = 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

Предварительная обработка:
добавить бит '1' к сообщению
добавить k битов '0', где k — минимальное число> = 0, такое, что результирующее сообщение
    длина (в битах ) соответствует 448 (mod 512 )
добавить длину сообщения (до предварительной обработки) в битах как 64-битное целое число с обратным порядком байтов

Обработайте сообщение в последующих 512-битных фрагментах:
разбить сообщение на 512-битные куски
для каждого куска
    разбить фрагмент на шестнадцать 32-битных слов с обратным порядком байтов w [0..15]

    Расширьте шестнадцать 32-битных слов до шестидесяти четырех 32-битных слов:
     для 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
    б: = h1
    с: = h2
    д: = h3
    е: = h4
    ф: = h5
    г: = h6
    ч: = ч7

    Основной цикл:
     for i от 0 до 63
        s0: = ( правый поворот 2) xor ( правый поворот 13) xor ( правый поворот 22)
        maj: = (a и b) xor (a и c) xor (b и c)
        t2: = s0 + май
        s1: = (e поворот вправо 6) xor (e поворот вправо 11) xor (e поворот вправо 25)
        ch: = (e и f) xor (( не e) и g)
        t1: = h + s1 + ch + k [i] + w [i]

        ч: = г
        г: = ф
        е: = е
        е: = d + t1
        д: = с
        с: = б
        б: = а
        а: = t1 + t2

    Добавьте хэш этого чанка к результату на данный момент:
    h0: = h0 + а
    h1: = h1 + b
    h2: = h2 + с
    h3: = h3 + d
    h4: = h4 + e
    h5: = h5 + f
    h6: = h6 + g
    h7: = h7 + h

Получение конечного хеш-значения (обратный порядок байтов): 
дайджест = хэш = h0 добавить h1 добавить h2 добавить h3 добавить h4 добавить h5 добавить h6 добавить h7

Функции chи majможно оптимизировать, как описано для функций SHA-1.

SHA-224 идентичен SHA-256, за исключением:

  • начальные значения переменных h0- h7разные и
  • вывод построен путем опускания h7.

SHA-512 идентичен по конструкции, но:

  • все числа имеют длину 64 бита,
  • выполняется 80 шагов вместо 64,
  • начальные значения и добавляемые константы расширены до 64 бит и
  • количества вращений и перемещений различны .

SHA-384 идентичен SHA-512, за исключением:

  • начальные значения h0- h7разные и
  • вывод построен путем опускания h6и h7.

Примечания

  1. ^ Криптоанализ SHA-1 (Шнайер)
  2. ^ Шнайер о безопасности: ведение блога NIST Hash Workshop (5)
  3. ^ The H: Новости безопасности и разработки с открытым исходным кодом
  4. ^ а б Документ
  5. ^ Перейти к index.html . Архивировано 5 февраля 2008 г. в Интернет-архиве .
  6. ^ Семейство губчатых функций Кекчака
  7. ↑ Объявление о первом столкновении SHA1 на сайте security.googleblog.com , 23 февраля 2017 г. Проверено 17 марта 2017 г.
  8. ^ Shattered , на shattered.it . _ _ Проверено 17 марта 2017 г. .
    «Мы взломали SHA-1 на практике».
  9. ^ Декларация о лицензировании патента США 6829355 .. Проверено 17 февраля 2008 г.
  10. ^ Анри Гилберт, Хелена Хандшу, Анализ безопасности SHA-256 и сестер , в Конспектах лекций по информатике , Springer, Берлин , ISSN  0302-9743  ( WC  ACNP ) . Проверено 30 января 2008 г. (архивировано из оригинала 18 октября 2011 г.) .
  11. ^ Блог для dkg — подготовка HOWTO к миграции с SHA-1 в OpenPGP , на debian-administration.org . Проверено 4 мая 2019 г. (архивировано из оригинала 3 мая 2019 г.) .

Библиография

Связанные элементы

Внешние ссылки

Сайты хеширования в Интернете

Стандарт: SHA-0, SHA-1, SHA-2, SHA-3...

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

Реализации

  • Проект OpenSSL — широко распространенная библиотека OpenSSL включает в себя бесплатное программное обеспечение с открытым исходным кодом с реализацией SHA-1, SHA-224, SHA-256, SHA-384 и SHA-512.
  • Crypto++ Crypto++, бесплатная библиотека C++ с криптографическими схемами
  • Библиотека Bouncy Castle Библиотека Bouncy Castle — это бесплатная библиотека Java и C#, которая содержит реализации алгоритмов SHA-1, SHA-224, SHA-256, SHA-384 и SHA-512 и других алгоритмов хеширования.

Учебник и образцы кода

Тестовые векторы

Тестовые векторы проекта NESSIE для SHA - 1 , SHA-256 , SHA-384 и SHA-512 .

Получено с https://it.wikipedia.org/w/index.php?title=Secure_Hash_Algorithm&oldid=128383531 "