SHA-2
SHA-2 | |
---|---|
Создан | 2002 |
Опубликован | 2002 |
Предшественник | SHA-1 |
Преемник | Keccak |
Размер хеша | 224, 256, 384 или 512бит |
Число раундов | 64 или 80 |
Тип | семейство хеш-функций |
SHA-2(англ.Secure Hash Algorithm Version 2— безопасный алгоритм хеширования, версия 2) — семействокриптографическихалгоритмов— однонаправленныххеш-функций,включающее в себя алгоритмыSHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256иSHA-512/224.
Хеш-функции предназначены для создания «отпечатков» или «дайджестов» для сообщений произвольной длины. Применяются в различных приложениях или компонентах, связанных сзащитой информации.
История
[править|править код]Хеш-функцииSHA-2разработаныАгентством национальной безопасности СШАи опубликованыНациональным институтом стандартов и технологийвфедеральном стандарте обработки информацииFIPS PUB 180-2в августе 2002 года[1].В этот стандарт также вошла хеш-функцияSHA-1,разработанная в 1995 году. В феврале 2004 года вFIPS PUB 180-2была добавленаSHA-224[2].В октябре 2008 года вышла новая редакция стандарта —FIPS PUB 180-3[3].В марте 2012 года вышла последняя на данный момент редакцияFIPS PUB 180-4,в которой были добавлены функцииSHA-512/256иSHA-512/224,основанные на SHA-512 (поскольку на 64-битных архитектурах SHA-512 работает быстрее, чем SHA-256)[4].
В июле 2006 года появился стандартRFC 4634«Безопасные хеш-алгоритмы США (SHAиHMAC-SHA)», описывающийSHA-1и семействоSHA-2.
Агентство национальной безопасности от лицагосударствавыпустило патент наSHA-2[5]под лицензиейRoyalty-free[6].
Алгоритм
[править|править код]Общее описание
[править|править код]Хеш-функции семейства SHA-2 построены на основеструктуры Меркла — Дамгора.
Исходное сообщение после дополнения разбивается на блоки, каждый блок — на 16 слов. Алгоритм пропускает каждый блок сообщения через цикл с 64 или 80 итерациями (раундами). На каждой итерации 2 слова преобразуются, функцию преобразования задают остальные слова. Результаты обработки каждого блока складываются,суммаявляется значением хеш-функции. Тем не менее, инициализация внутреннего состояния производится результатом обработки предыдущего блока. Поэтому независимо обрабатывать блоки и складывать результаты нельзя. Подробнее — см.псевдокод.
Сравнение хеш-функций
[править|править код]В следующей таблице показаны некоторые технические характеристики различных вариантов SHA-2. «Внутреннее состояние» обозначает промежуточную хеш-сумму после обработки очередного блока данных:
Хеш-функция | Длина дайджеста сообщения (бит) | Длина внутреннего состояния (бит) | Длина блока (бит) | Максимальная длина сообщения (бит) |
Длина слова (бит) | Количество итераций в цикле | Скорость (MiB/s)[7] |
---|---|---|---|---|---|---|---|
SHA‑256,SHA‑224 | 256/224 | 256 (8 × 32) | 512 | 264− 1 | 32 | 64 | 139 |
SHA‑512,SHA‑384,SHA‑512/256,SHA‑512/224 | 512/384/256/224 | 512 (8 × 64) | 1024 | 2128− 1 | 64 | 80 | 154 |
Псевдокод
[править|править код]Псевдокод использует следующие битовые операции:
- ǁ —конкатенация,
- + —сложение,
- and—побитовое «И»,
- xor—исключающее «ИЛИ»,
- shr(shift right) —логический сдвиг вправо,
- rotr(rotate right) —циклический сдвиг вправо.
SHA-256
[править|править код]Пояснения: Все переменные беззнаковые, имеют размер 32 бита и при вычислениях суммируются по модулю 232 message— исходное двоичное сообщение m— преобразованное сообщение Инициализация переменных (первые 32 битадробных частейквадратных корней первых восьми простых чисел [от 2 до 19]): h0:= 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 Предварительная обработка: m:= message ǁ [единичный бит] m:= m ǁ [kнулевых бит],гдеk— наименьшее неотрицательное число, такое, что (L + 1 + K) mod 512 = 448, где L — число бит в сообщении (сравнима по модулю512 c 448) m:= m ǁДлина(message)— длина исходного сообщения в битах в виде 64-битного числа спорядком байтовот старшего к младшему Далее сообщение обрабатывается последовательными порциями по 512 бит: разбить сообщение на куски по 512 бит длякаждого куска разбить кусок на 16 слов длиной 32 бита (спорядком байтовот старшего к младшему внутри слова): w[0..15] Сгенерировать дополнительные 48 слов: дляiот16до63 s0:= (w[i-15]rotr7)xor(w[i-15]rotr18)xor(w[i-15]shr3) s1:= (w[i-2]rotr17)xor(w[i-2]rotr19)xor(w[i-2]shr10) w[i]:= w[i-16]+s0+w[i-7]+s1 Инициализация вспомогательных переменных: a:= h0 b:= h1 c:= h2 d:= h3 e:= h4 f:= h5 g:= h6 h:= h7 Основной цикл: дляiот0до63 Σ0:= (arotr2)xor(arotr13)xor(arotr22) Ma:= (aandb)xor(aandc)xor(bandc) t2:= Σ0 + Ma Σ1:= (erotr6)xor(erotr11)xor(erotr25) Ch:= (eandf)xor((note)andg) t1:= h + Σ1 + Ch + k[i] + w[i] h:= g g:= f f:= e e:= d + t1 d:= c c:= b b:= a a:= t1 + t2 Добавить полученные значения к ранее вычисленному результату: 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
SHA-224идентиченSHA-256,за исключением:
- для инициализации переменных
h0
—h7
используются другие начальные значения, - в итоговом хеше опускается значение
h7
.
Начальные значения переменныхh0
—h7
в SHA-224:
h0:= 0xC1059ED8
h1:= 0x367CD507
h2:= 0x3070DD17
h3:= 0xF70E5939
h4:= 0xFFC00B31
h5:= 0x68581511
h6:= 0x64F98FA7
h7:= 0xBEFA4FA4
SHA-512имеет идентичную структуру, но:
- слова имеют длину 64 бита,
- используется 80 раундов вместо 64,
- сообщение разбито на чанки по 1024 бит,
- начальные значения переменных и константы расширены до 64 бит,
- постоянные для каждого из 80 раундов — 80 первых простых чисел,
- сдвиг в операциях
rotr
иshr
производится на другое число позиций.
Начальные значения переменныхh0
—h7
в SHA-512:
h0:= 0x6a09e667f3bcc908,
h1:= 0xbb67ae8584caa73b,
h2:= 0x3c6ef372fe94f82b,
h3:= 0xa54ff53a5f1d36f1,
h4:= 0x510e527fade682d1,
h5:= 0x9b05688c2b3e6c1f,
h6:= 0x1f83d9abfb41bd6b,
h7:= 0x5be0cd19137e2179
SHA-384 идентичен SHA-512, за исключением:
- переменные
h0
—h7
имеют другие начальные значения, - в итоговом хеше опускаются значения
h6
иh7
.
Начальные значения переменныхh0
—h7
в SHA-384
(первые 64 бита дробных частей квадратных корней простых чисел с 9-го по 16-е [от 23 до 53]):
h0:= CBBB9D5DC1059ED8
h1:= 629A292A367CD507
h2:= 9159015A3070DD17
h3:= 152FECD8F70E5939
h4:= 67332667FFC00B31
h5:= 8EB44A8768581511
h6:= DB0C2E0D64F98FA7
h7:= 47B5481DBEFA4FA4
SHA-512/256идентичен SHA-512, за исключением:
- переменные
h0
—h7
имеют другие начальные значения, - итоговый хеш обрезается до левых 256 бит.
Начальные значения переменныхh0
—h7
в SHA-512/256:
h0:= 22312194FC2BF72C
h1:= 9F555FA3C84C64C2
h2:= 2393B86B6F53B151
h3:= 963877195940EABD
h4:= 96283EE2A88EFFE3
h5:= BE5E1E2553863992
h6:= 2B0199FC2C85B8AA
h7:= 0EB72DDC81C52CA2
SHA-512/224идентичен SHA-512, за исключением:
- переменные
h0
—h7
имеют другие начальные значения, - итоговый хеш обрезается до левых 224 бит.
Начальные значения переменныхh0
—h7
в SHA-512/224:
h0:= 8C3D37C819544DA2
h1:= 73E1996689DCD4D6
h2:= 1DFAB7AE32FF9C82
h3:= 679DD514582F9FCF
h4:= 0F6D2B697BD44DA8
h5:= 77E36F7304C48942
h6:= 3F9D85A86A1D36C8
h7:= 1112E6AD91D692A1
Примеры
[править|править код]Ниже приведены примеры хешей для одинакового текста при различных версиях протоколаSHA-2.Во всех примерах подразумевается использование кодировкиASCII.
SHA-224( "The quick brown fox jumps over the lazy dog") = 730E109B D7A8A32B 1CB9D9A0 9AA2325D 2430587D DBC0C38B AD911525
SHA-256( "The quick brown fox jumps over the lazy dog" ) = D7A8FBB3 07D78094 69CA9ABC B0082E4F 8D5651E4 6D3CDB76 2D02D0BF 37C9E592
SHA-384( "The quick brown fox jumps over the lazy dog" ) = CA737F10 14A48F4C 0B6DD43C B177B0AF D9E51693 67544C49 4011E331 7DBF9A50 9CB1E5DC 1E85A941 BBEE3D7F 2AFBC9B1
SHA-512( "The quick brown fox jumps over the lazy dog" ) = 07E547D9 586F6A73 F73FBAC0 435ED769 51218FB7 D0C8D788 A309D785 436BBB64 2E93A252 A954F239 12547D1E 8A3B5ED6 E1BFD709 7821233F A0538F3D B854FEE6
SHA-512/256( "The quick brown fox jumps over the lazy dog" ) = DD9D67B3 71519C33 9ED8DBD2 5AF90E97 6A1EEEFD 4AD3D889 005E532F C5BEF04D
SHA-512/224( "The quick brown fox jumps over the lazy dog" ) = 944CD284 7FB54558 D4775DB0 485A5000 3111C8E5 DAA63FE7 22C6AA37
Малейшее изменение сообщения в подавляющем большинстве случаев приводит к полному изменению хеша вследствиелавинного эффекта.К примеру, при измененииdog
наcog
(изменение затрагивает лишь один бит из 344 в кодируемой фразе) хеш изменится кардинально:
SHA-256( "The quick brown fox jumps over the lazy cog" ) = E4C4D8F3 BF76B692 DE791A17 3E053211 50F7A345 B46484FE 427F6ACC 7ECC81BE
Криптоанализ
[править|править код]Криптоанализхеш-функции подразумевает исследование устойчивости алгоритма по отношению, по меньшей мере, к следующим видам атак:
- нахождениюколлизий,то есть разных сообщений с одинаковым хешем — от этого зависит безопасность электронной цифровой подписи с использованием данного хеш-алгоритма;
- нахождениюпрообраза,то есть неизвестного сообщения по его хешу — от этого зависит безопасность хранения хешей паролей для целейаутентификации.
В2003 годуГилберт и Хандшух провели исследованиеSHA-2,но не нашли каких-либо уязвимостей[8].Однако в марте 2008 года индийские исследователи Сомитра Кумар Санадия и Палаш Саркар опубликовали найденные ими коллизии для 22 итерацийSHA-256иSHA-512[9].В сентябре того же года они представили метод конструирования коллизий для усечённых вариантовSHA-2(21 итерация)[10][11].Позднее были найдены методы конструирования коллизий для 31 итерацииSHA-256[12]и для 27 итерацийSHA-512[13].
Ввиду алгоритмической схожестиSHA-2сSHA-1и наличия у последней потенциальных уязвимостей принято решение, чтоSHA-3будет базироваться на совершенно ином алгоритме[14][15].2 октября 2012 года NIST утвердил в качестве SHA-3 алгоритмKeccak.
Применение и сертификация
[править|править код]См. такжеПрименение хеширования
SHA-224,SHA-256,SHA-384,SHA-512,SHA-512/256иSHA-512/224законом США допускаются к использованию в некоторых правительственных приложениях, включая использование в рамках других криптографических алгоритмов и протоколов, для защиты информации, не имеющей грифа секретности. Стандарт также допускает использованиеSHA-2частными и коммерческими организациями[16].
Хеш-функцииSHA-2используются для проверки целостности данных и в различных криптографических схемах. На2008 годсемейство хеш-функцийSHA-2не имеет такого широкого распространения, какMD5иSHA-1[17],несмотря на обнаруженные у последних недостатки.
Некоторые примеры примененияSHA-2указаны в таблице:
Область применения | Детали |
---|---|
S/MIME | SHA-224,SHA-256,SHA-384илиSHA-512дайджесты сообщений[18] |
OpenLDAP | SHA-256,SHA-384илиSHA-512хешипаролей[19] |
DNSSEC | SHA-256дайджестыDNSKEYв протоколеDNSSEC[20] |
X.509 | SHA-224,SHA-256,SHA-384иSHA-512используются для созданияэлектронной цифровой подписисертификата[21] |
PGP | SHA-256,SHA-384,SHA-512используются для создания электронной цифровой подписи[22] |
IPSec | Некоторые реализации поддерживаютSHA-256в протоколахESPиIKE[23] |
DSA | СемействоSHA-2используется для создания электронной цифровой подписи[24] |
SHACAL-2 | Блочный алгоритм шифрованияSHACAL-2построен на основе хеш-функцииSHA-256 |
Биткойн | Нахождение комбинации данных,SHA-256-хеш которых удовлетворяет оговоренному условию, являетсядоказательством выполнения работыпри эмиссии криптовалюты |
Как показали исследования[25],алгоритмыSHA-2работают в 2—3 раза медленнее других популярных хеш-алгоритмовMD5,SHA-1,TigerиRIPEMD-160.
Сертификация
[править|править код]Эта статьяописывает ситуацию применительно лишь к одному региону(США), возможно, нарушая при этомправило о взвешенности изложения. |
РеализацииSHA-2,как и всех Федеральных стандартов обработки информации, могут быть сертифицированы для использования в некоторых приложениях на территории США. Сертификация происходит в рамках процедурыCryptographic Module Validation Program[англ.],которая проводится Национальным институтом стандартов и технологий США совместно с канадским Бюро безопасности связи.
На5 ноября2008 года было сертифицировано более 250 реализацийSHA-2,четыре из которых могли оперировать сообщениями с длиной в битах, не кратной восьми[26].
СертифицированоFIPSPUB 180-4,CRYPTRECиNESSIE.
См. также
[править|править код]Примечания
[править|править код]- ↑FIPS PUB 180-2(англ.).— первоначальный вариант стандарта для SHA-2. Дата обращения: 19 ноября 2008.Архивировано18 марта 2012 года.
- ↑FIPS PUB 180-2 with change notice(англ.).— вариант стандарта с SHA-224. Дата обращения: 19 ноября 2008.Архивировано18 марта 2012 года.
- ↑FIPS PUB 180-3(англ.).— редакция Secure Hash Standard от октября 2008 года. Дата обращения: 19 ноября 2008.Архивировано18 марта 2012 года.
- ↑FIPS PUB 180-4(англ.).— редакция Secure Hash Standard от августа 2015 года. Дата обращения: 28 августа 2015. Архивировано изоригинала26 ноября 2016 года.
- ↑US patent 6829355(англ.).— Device for and method of one-way cryptographic hashing. Дата обращения: 14 мая 2017.Архивировано27 июля 2016 года.
- ↑Licensing Declaration for US patent 6829355.(неопр.).Архивировано16 июня 2016 года.(англ.)
- ↑"Crypto++ 5.6.0 Benchmarks". Retrieved 2013-06-13. Дата обращения: 25 сентября 2016.Архивировано14 октября 2016 года.
- ↑Gilbert H.,Handschuh H.Security Analysis of SHA-256 and Sisters(англ.)//Selected Areas in Cryptography:10th Annual International Workshop, SAC 2003, Ottawa, Canada, August 14-15, 2003. Revised Papers/M. Matsui,R. J. Zuccherato— Berlin, Heidelberg, New York City, London:Springer Berlin Heidelberg,2004. — P. 175—193. — (Lecture Notes in Computer Science;Vol. 3006) —ISBN 978-3-540-21370-3— ISSN0302-9743;1611-3349—doi:10.1007/978-3-540-24654-1_13
- ↑Somitra Kumar Sanadhya, Palash Sarkar.22-Step Collisions for SHA-2Архивная копияот 30 марта 2010 наWayback Machine(англ.)
- ↑Somitra Kumar Sanadhya, Palash Sarkar.Deterministic Constructions of 21-Step Collisions for the SHA-2 Hash Family(англ.)
- ↑Презентация «Deterministic Constructions of 21-Step Collisions for the SHA-2 Hash Family»Архивная копияот 3 июля 2010 наWayback Machine(англ.)
- ↑Mendel F.,Nad T.,Schläffer M.Improving Local Collisions: New Attacks on Reduced SHA-256(англ.)//Advances in Cryptology – EUROCRYPT 2013:32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings/T. Johansson,P. Q. Nguyen—Springer Berlin Heidelberg,2013. — P. 262—278. — 736 p. —ISBN 978-3-642-38347-2—doi:10.1007/978-3-642-38348-9_16
- ↑Christoph Dobraunig, Maria Eichlseder, and Florian Mendel.Analysis of SHA-512/224 and SHA-512/256(неопр.).— 2016.Архивировано15 июля 2017 года.
- ↑Schneier on Security: NIST Hash Workshop Liveblogging (5)Архивная копияот 7 октября 2008 наWayback Machine(англ.)
- ↑Hash cracked — heise SecurityАрхивная копияот 6 декабря 2008 наWayback Machine(англ.)
- ↑FIPS 180-2: Secure Hash Standard (SHS): 6. ApplicabilityАрхивная копияот 12 марта 2012 наWayback Machine(англ.)
- ↑SHA-1,SHA-256в результатах поисковой системыGoogle
- ↑draft-ietf-smime-sha2-08Архивная копияот 22 июня 2009 наWayback Machine(англ.):Using SHA2 Algorithms with Cryptographic Message Syntax
- ↑SHA-2 hash support in OpenLDAPАрхивная копияот 27 июля 2010 наWayback Machine(англ.)
- ↑RFC 4509:Use ofSHA-256in DNSSEC Delegation Signer (DS) Resource Records (RRs)
- ↑RFC 4055:Additional Algorithms and Identifiers for RSA Cryptography for use in the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile
- ↑RFC 4880:OpenPGP Message Format
- ↑Overview of Windows Vista Service Pack 1: New StandardsАрхивная копияот 12 марта 2016 наWayback Machine(англ.)
- ↑FIPS-186-2Архивировано18 мая 2009 года.:Digital Signature Standard (DSS)]
- ↑Speed Comparison of Popular Crypto Algorithms[1]Архивная копияот 15 октября 2008 наWayback Machine(англ.)
- ↑SHS Validation ListАрхивная копияот 23 августа 2011 наWayback Machine(англ.)
Литература
[править|править код]- Лапонина О.Р.Криптографические основы безопасности.—М.:Интернет-университет информационных технологий - ИНТУИТ.ру, 2004. — С. 320. —ISBN 5-9556-00020-5.
- Нильс Фергюсон,Брюс Шнайер.Практическая криптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. —М.:Диалектика, 2004. — 432 с. —3000 экз.—ISBN 5-8459-0733-0,ISBN 0-4712-2357-3.
- Анализ усечённого варианта SHA-256(недоступная ссылка)(англ.)
- Коллизии усечённого варианта SHA-256(англ.)
- Нелинейные атаки на усечённые варианты хеш-функций SHA-2(англ.)
- Детерминированное конструирование коллизий для семейства хешей SHA-2 с 21 итерацией(англ.)
Ссылки
[править|править код]- FIPS 180-3Архивировано18 марта 2012 года.:Secure Hash Standard (SHS)
- RFC 3874:A 224-bit One-way Hash Function: SHA-224
- RFC 4634:US Secure Hash Algorithms (SHA and HMAC-SHA)