SHA-2

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

SHA-2 (англ. Secure Hash Algorithm Version 2 — безопасный алгоритм хеширования, версия 2) — семейство криптографических алгоритмов — однонаправленных хеш-функций, включающее в себя алгоритмы SHA-224, SHA-256, SHA-384 и SHA-512. Хеш-функции предназначены для создания «отпечатков» или «дайджестов» сообщений произвольной битовой длины. Применяются в различных приложениях или компонентах, связанных с защитой информации.

История[править | править вики-текст]

Хеш-функции 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]

В июле 2006 года появился стандарт RFC 4634 «Безопасные хеш-алгоритмы США (SHA и HMAC-SHA)», описывающий SHA-1 и семейство SHA-2.

Агентство национальной безопасности от лица государства выпустило патент на SHA-2[4] под лицензией Royalty Free.[5]

Алгоритм[править | править вики-текст]

Общее описание[править | править вики-текст]

Схема одной итерации алгоритмов SHA-2

Хеш-функции семейства SHA-2 построены на основе структуры Меркла — Дамгарда.

Исходное сообщение после дополнения разбивается на блоки, каждый блок — на 16 слов. Алгоритм пропускает каждый блок сообщения через цикл с 64-мя или 80-ю итерациями (раундами). На каждой итерации 2 слова преобразуются, функцию преобразования задают остальные слова. Результаты обработки каждого блока складываются, сумма является значением хеш-функции. Тем не менее, инициализация внутреннего состояния производится результатом обработки предыдущего блока. Поэтому независимо обрабатывать блоки и складывать результаты нельзя. Подробнее — см. псевдокод.

Алгоритм использует следующие битовые операции:

В следующей таблице показаны некоторые технические характеристики различных вариантов SHA-2. «Внутреннее состояние» обозначает промежуточную хеш-сумму после обработки очередного блока данных:

Хеш-функция Длина дайджеста сообщения (бит) Длина внутреннего состояния (бит) Длина блока (бит) Максимальная
длина сообщения (бит)
Длина слова (бит) Количество итераций в цикле
SHA-256/224 256/224 256 512 264 − 1 32 64
SHA-512/384 512/384 512 1024 2128 − 1 64 80

Псевдокод 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] rotr 7) xor (w[i-15] rotr 18) xor (w[i-15] shr 3)
        s1 := (w[i-2] rotr 17) xor (w[i-2] rotr 19) xor (w[i-2] shr 10)
        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 := (a rotr 2) xor (a rotr 13) xor (a rotr 22)
        Ma := (a and b) xor (a and c) xor (b and c)
        t2 := Σ0 + Ma
        Σ1 := (e rotr 6) xor (e rotr 11) xor (e rotr 25)
        Ch := (e and f) xor ((not e) and g)
        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-256 C#[править | править вики-текст]

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace Sha256_Study
{
    public struct Digest
    {
        public uint H0, H1, H2, H3, H4, H5, H6, H7;
    }
 
    public class Sha256Digest
    {
         private byte[] buf, m;
         private Digest digest;
         private ulong messageLength, blocksQty;
         private uint[] W = new uint[64];
 
         public Sha256Digest()
         {
			initHs();
         }
 
         private void initHs()
         {
            /* SHA-256 initial hash value
            * The first 32 bits of the fractional parts of the square roots
            * of the first eight prime numbers
            */            
            digest.H0 = 0x6a09e667;
            digest.H1 = 0xbb67ae85;
            digest.H2 = 0x3c6ef372;
            digest.H3 = 0xa54ff53a;
            digest.H4 = 0x510e527f;
            digest.H5 = 0x9b05688c;
            digest.H6 = 0x1f83d9ab;
            digest.H7 = 0x5be0cd19;
         }
 
        /* SHA-256 Constants
        * (represent the first 32 bits of the fractional parts of the
        * cube roots of the first sixty-four prime numbers)
        */
         private static readonly uint[] K = {
            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
         };
 
         public Digest hash(byte[] message) { //operates only with byte-multiple messages 
             buf = new byte[message.LongLength];
             Array.Copy(message, buf, message.LongLength);
             messageLength = (ulong)message.LongLength;
             completeMessageLength();
             blocksQty = (ulong)m.LongLength / 64;
             for (ulong i = 0; i < blocksQty; i++)
             {
                 expandBlock(i);
                 processBlock();
             }             
             return digest;
         }
 
         private void completeMessageLength()
         {
             int zeroBitsToAddQty = 512 - (int)(((ulong)buf.LongLength * 8 + 1 + 64) % 512);
             m = new byte[((ulong)buf.LongLength * 8 + 1 + 64 + (ulong)zeroBitsToAddQty) / 8];
             Array.Copy(buf, m, buf.LongLength);
 
             m[buf.LongLength] = 128; //set 1-st bit to "1", 7 remaining to "0" (may not work with bit-multiple message!!)
 
             for (ulong i = (messageLength + 1); i < (ulong)m.LongLength; i++)
             {
                 m[i] = 0;
             }
 
             byte[] messageBitLength_little_endian = BitConverter.GetBytes(messageLength * 8);
             byte[] messageBitLength_big_endian = new byte[messageBitLength_little_endian.Length];
             for (int i = 0, j = messageBitLength_little_endian.Length - 1; i < messageBitLength_little_endian.Length; i++, j--)
             {
                 messageBitLength_big_endian[i] = messageBitLength_little_endian[j];
             }
             Array.Copy(messageBitLength_big_endian, 0, m, m.LongLength - 8, 8);
         }
 
         private void expandBlock(ulong blockNumber)
         {
             for (int i = 0; i < 16; i++)
             {
                 W[i] = Bytes_To_UInt32(m, blockNumber * 64 + (ulong)i * 4);
             }
 
             for (int i = 16; i <= 63; i++)
             {
                 W[i] = W[i - 16] + S0(W[i - 15]) + W[i - 7] + S1(W[i - 2]);
             }
         }
 
        internal static uint Bytes_To_UInt32(byte[] bs, ulong off)
        {
            uint n = (uint)bs[off] << 24;
            n |= (uint)bs[++off] << 16;
            n |= (uint)bs[++off] << 8;
            n |= (uint)bs[++off];
            return n;
        }
 
        private static uint rotr(uint x, int n)
        {
            return ((x >> n) | (x << 32 - n));
        }
 
        private static uint S0(uint x)
        {
            return rotr(x, 7) ^ rotr(x, 18) ^ (x >> 3);
        }
 
        private static uint S1(uint x)
        {
            return rotr(x, 17) ^ rotr(x, 19) ^ (x >> 10);
        }
 
        private static uint Ch(uint x, uint y, uint z) {
            return (x & y) ^ ((~x) & z);
        }
 
        private static uint Maj(uint x, uint y, uint z)
        {
            return (x & y) ^ (x & z) ^ (y & z);
        }
 
        private static uint E0(uint x)
        {
            return rotr(x, 2) ^ rotr(x, 13) ^ rotr(x, 22);
        }
 
        private static uint E1(uint x)
        {
            return rotr(x, 6) ^ rotr(x, 11) ^ rotr(x, 25);
        }
 
        private void processBlock()
        {             
             uint a = digest.H0;
             uint b = digest.H1;
             uint c = digest.H2;
             uint d = digest.H3;
             uint e = digest.H4;
             uint f = digest.H5;
             uint g = digest.H6;
             uint h = digest.H7;
 
             uint T1 = 0, T2 = 0;
 
             for (int i = 0; i < 64; i++)
             {
                 T1 = h + E1(e) + Ch(e, f, g) + K[i] + W[i];
                 T2 = E0(a) + Maj(a, b, c);
                 h = g;
                 g = f;
                 f = e;
                 e = d + T1;
                 d = c;
                 c = b;
                 b = a;
                 a = T1 + T2; 
             }
			digest.H0 += a;
            digest.H1 += b;
            digest.H2 += c;
            digest.H3 += d;
            digest.H4 += e;
            digest.H5 += f;
            digest.H6 += g;
            digest.H7 += h;
        } 
    }
}

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

  • для инициализации переменных h0h7 используются другие начальные значения.
  • в итоговом хеше опускается значение h7.
Начальные значения переменных h0h7 в SHA-224:
h0 := 0xC1059ED8
h1 := 0x367CD507
h2 := 0x3070DD17
h3 := 0xF70E5939
h4 := 0xFFC00B31
h5 := 0x68581511
h6 := 0x64F98FA7
h7 := 0xBEFA4FA4

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

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

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

  • переменные h0h7 имеют другие начальные значения.
  • в итоговом хеше опускаются значения h6 и h7.
Начальные значения переменных h0h7 в SHA-384
(первые 64 бита дробных частей квадратных корней простых чисел с 9-го по 16-е [от 23 до 53]):
h0 := CBBB9D5DC1059ED8
h1 := 629A292A367CD507
h2 := 9159015A3070DD17
h3 := 152FECD8F70E5939
h4 := 67332667FFC00B31
h5 := 8EB44A8768581511
h6 := DB0C2E0D64F98FA7
h7 := 47B5481DBEFA4FA4

Примеры[править | править вики-текст]

Ниже приведены примеры хешей 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

Малейшее изменение сообщения в подавляющем большинстве случаев приводит к совершенно другому хешу вследствие лавинного эффекта. К примеру, при изменении dog на cog получится:

SHA-256("The quick brown fox jumps over the lazy cog") 
 = E4C4D8F3 BF76B692 DE791A17 3E053211 50F7A345 B46484FE 427F6ACC 7ECC81BE

Криптоанализ[править | править вики-текст]

В 2003 году Гилберт и Хандшух провели исследование SHA-2, но не нашли каких-либо уязвимостей.[6] Однако в марте 2008 года индийские исследователи Сомитра Кумар Санадия и Палаш Саркар опубликовали найденные ими коллизии для 22 итераций SHA-256 и SHA-512.[7] В сентябре того же года они представили метод конструирования коллизий для усечённых вариантов SHA-2 (21 итерация).[8] [9]

Криптоанализ хеш-функции подразумевает исследование устойчивости алгоритма по отношению, по меньшей мере, к следующим видам атак:

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

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

Ввиду алгоритмической схожести SHA-2 с SHA-1 и наличия у последней потенциальных уязвимостей принято решение, что SHA-3 будет базироваться на совершенно ином алгоритме.[10][11] 2 Октября 2012 года NIST утвердил в качестве SHA-3 алгоритм Keccak.

Применение и сертификация[править | править вики-текст]

См. также Применение хеширования

SHA-224, SHA-256, SHA-384 и SHA-512 законом США допускаются к использованию в некоторых правительственных приложениях, включая использование в рамках других криптографических алгоритмов и протоколов, для защиты информации, не имеющей грифа секретности. Стандарт также допускает использование SHA-2 частными и коммерческими организациями.[12]

Хеш-функции SHA-2 используются для проверки целостности данных и в различных криптографических схемах. На 2008 год семейство хеш-функций SHA-2 не имеет такого широкого распространения, как MD5 и SHA-1[13], несмотря на обнаруженные у последних недостатки.

Некоторые примеры применения SHA-2 указаны в таблице:

Область применения Детали
S/MIME SHA-224, SHA-256, SHA-384 или SHA-512 дайджесты сообщений[14]
OpenLDAP SHA-256, SHA-384 или SHA-512 хеши паролей[15]
DNSSEC SHA-256 дайджесты DNSKEY в протоколе DNSSEC[16]
X.509 SHA-224, SHA-256, SHA-384 и SHA-512 используются для создания электронной цифровой подписи сертификата[17]
PGP SHA-256, SHA-384, SHA-512 используются для создания электронной цифровой подписи[18]
IPSec Некоторые реализации поддерживают SHA-256 в протоколах ESP и IKE[19]
DSA Семейство SHA-2 используется для создания электронной цифровой подписи[20]
SHACAL-2 Блочный алгоритм шифрования SHACAL-2 построен на основе хеш-функции SHA-256
Bitcoin Эмиссия криптовалюты Bitcoin осуществляется посредством поиска строк, SHA-256-хеш которых имеет заданную структуру

Как показали исследования[21], алгоритмы SHA-2 работают в 2—3 раза медленнее других популярных хеш-алгоритмов MD5, SHA-1, Tiger и RIPEMD-160.

Сертификация[править | править вики-текст]

Реализации SHA-2, как и всех Федеральных стандартов обработки информации, могут быть сертифицированы для использования в некоторых приложениях на территории США. Сертификация происходит в рамках процедуры Cryptographic Module Validation Program (англ.), которая проводится Национальным институтом стандартов и технологий США совместно с канадским Бюро безопасности связи.

На 5 ноября 2008 года было сертифицировано более 250 реализаций SHA-2, четыре из которых могли оперировать сообщениями с длиной в битах, не кратной восьми.[22]

Примечания[править | править вики-текст]

  1. FIPS PUB 180-2 (англ.). — первоначальный вариант стандарта для SHA-2. Проверено 19 ноября 2008. Архивировано из первоисточника 18 марта 2012.
  2. FIPS PUB 180-2 with change notice (англ.). — вариант стандарта с SHA-224. Проверено 19 ноября 2008. Архивировано из первоисточника 18 марта 2012.
  3. FIPS PUB 180-3 (англ.). — редакция Secure Hash Standard от октября 2008 года. Проверено 19 ноября 2008. Архивировано из первоисточника 18 марта 2012.
  4. U.S. Patent 6 829 355
  5. «Licensing Declaration for US patent 6829355.». Проверено 2008-02-17. (англ.)
  6. Henri Gilbert; Helena Handschuh. «Security analysis of SHA-256 and sisters» (fee required). Lecture notes in computer science (Springer, Berlin). ISSN 0302-9743. Проверено 2008-01-30.
  7. Somitra Kumar Sanadhya, Palash Sarkar. 22-Step Collisions for SHA-2  (англ.)
  8. Somitra Kumar Sanadhya, Palash Sarkar. Deterministic Constructions of 21-Step Collisions for the SHA-2 Hash Family  (англ.)
  9. Презентация «Deterministic Constructions of 21-Step Collisions for the SHA-2 Hash Family» (англ.)
  10. Schneier on Security: NIST Hash Workshop Liveblogging (5) (англ.)
  11. Hash cracked — heise Security (англ.)
  12. FIPS 180-2: Secure Hash Standard (SHS): 6. Applicability (англ.)
  13. SHA-1, SHA-256 в результатах поисковой системы Google
  14. draft-ietf-smime-sha2-08 (англ.): Using SHA2 Algorithms with Cryptographic Message Syntax
  15. SHA-2 hash support in OpenLDAP (англ.)
  16. RFC 4509: Use of SHA-256 in DNSSEC Delegation Signer (DS) Resource Records (RRs)
  17. 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
  18. RFC 4880: OpenPGP Message Format
  19. Overview of Windows Vista Service Pack 1: New Standards (англ.)
  20. FIPS-186-2: Digital Signature Standard (DSS)]
  21. Speed Comparison of Popular Crypto Algorithms [1] (англ.)
  22. SHS Validation List (англ.)

Литература[править | править вики-текст]

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

  • FIPS 180-3: 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)