Хэш-функции и аутентификация сообщений. Часть 2

A = 67452301
B = EFCDAB89
C = 98BADCFE
D = 10325476
E = C3D2E1F0

0  <= t <= 19 	Kt = 5A827999
(целая часть числа [230 x 21/2])

20 <= t <= 39 	Kt = 6ED9EBA1
(целая часть числа [230 x 31/2])

40 <= t <= 59 	Kt = 8F1BBCDC
(целая часть числа [230 x 51/2])

60 <= t <= 79 	Kt = CA62C1D6
(целая часть числа [230 x 101/2])

Хэш-функции SHA-2

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

Алгоритм	Длина сообщения (в битах)	Длина блока (в битах)	Длина слова (в битах)	Длина дайджеста сообщения (в битах)	Безопасность (в битах)
SHA-1	<264	512	32	160	80
SHA-256	<264	512	32	256	128
SHA-384	<2128	1024	64	384	192
SHA-512	<2128	1024	64	512	256

Под безопасностью здесь понимается стойкость к атакам типа "парадокса дня рождения".

В данных алгоритмах размер блока сообщения равен m бит. Для SHA-256 m = 512, для SHA-384 и SHA-512 m = 1024. Каждый алгоритм оперирует с w-битными словами. Для SHA-256 w = 32, для SHA-384 и SHA-512 w = 64. В алгоритмах используются обычные булевские операции над словами, а также сложение по модулю 2w, правый сдвиг на n бит SHRn (x), где х - w-битное слово, и циклические (ротационные) правый и левый сдвиги на n бит ROTRn (x) и ROTLn (x), где х - w-битное слово.

SHA-256 использует шесть логических функций, при этом каждая из них выполняется с 32-битными словами, обозначенными как x, y и z. Результатом каждой функции тоже является 32-битное слово.

$$Ch (x, y, z) = (x \wedge y) \oplus (\neg x \wedge z) \\ Maj (x, y, z) = (x \wedge y) \oplus (x \wedge z) \oplus (y \wedge z) \\ \Sigma_{0}^{(256)} (x) = ROTR^{2} (x) \oplus ROTR^{13} (x) \oplus ROTR^{22} (x) \\ \Sigma_{1}^{(256)} (x) = ROTR^{6} (x) \oplus ROTR^{11} (x) \oplus ROTR^{25} (x) \\ \sigma_{0}^{(256)} (x) = ROTR^{7} (x) \oplus ROTR^{18} (x) \oplus SHR^{3} (x) \\ \sigma_{1}^{(256)} (x) = ROTR^{17} (x) \oplus ROTR^{19} (x) \oplus SHR^{10} (x)$$

SHA-384 и SHA-512 также используют шесть логических функций, каждая из которых выполняется над 64-битными словами, обозначенными как x, y и z. Результатом каждой функции является 64-битное слово.

$$Ch (x, y, z) = (x \wedge y) \oplus (\neg x \wedge z) \\ Maj (x, y, z) = (x \wedge y) \oplus (x \wedge z) \oplus (y \wedge z) \\ \Sigma _{0}^{(512)} (x) = ROTR^{28} (x) \oplus ROTR^{34} (x) \oplus ROTR^{39} (x) \\ \Sigma _{1}^{(512)} (x) = ROTR^{14} (x) \oplus ROTR^{18} (x) \oplus ROTR^{41} (x) \\ \sigma _{0}^{(512)} (x) = ROTR^{1} (x) \oplus ROTR^{8} (x) \oplus SHR^{7} (x) \\ \sigma _{1}^{(512) } (x) = ROTR^{19} (x) \oplus ROTR^{61} (x) \oplus SHR^{6} (x)$$

Предварительная подготовка сообщения, т.е. добавление определенных битов до целого числа блоков и последующее разбиение на блоки выполняется аналогично тому, как это делалось в SHA-1 (конечно, с учетом длины блока каждой хэш-функции). После этого каждое сообщение можно представить в виде последовательности N блоков M(1), M(2), $$\dots,$$ M(N).

Рассмотрим SHA-256. В этом случае инициализируются восемь 32-битных переменных, которые послужат промежуточным значением хэш-кода:

a, b, c, d, e, f, g, h

Основой алгоритма является модуль, состоящий из 64 циклических обработок каждого блока M(i):

$$T_{1} = h + \Sigma _{1}^{(256)}(e) + Ch(e, f, g) + K_{t}^{(256)} + W_{t} \\ T_{2} = \Sigma _{0}^{(256)}(a) + Maj(a, b, c) \\ h = g \\ g = f \\ f = e \\ e = d + T_{1} \\ d = c \\ c = b \\ b = a \\ a = T_{1} + T_{2}$$

где Ki{256} - шестьдесят четыре 32-битных константы, каждая из которых является первыми 32-мя битами дробной части кубических корней первых 64 простых чисел.

Wt вычисляются из очередного блока сообщения по следующим правилам:

$$W_{t} = M_{t}^{(i)} , 0 \le t \le 15 \\ W_{t} = \sigma _{1}^{(256)}(W_{t-2}) + W_{t-7} + \sigma _{0}^{(256)}(W_{t-15}) + W_{t-16} , \\ 16 \le t \le 63$$

i-ое промежуточное значение хэш-кода H(t) вычисляется следующим образом:

H0(i) = a + H0(i-1)
H1(i) = b + H1(i-1)
H2(i) = c + H2(i-1)
H3(i) = d + H3(i-1)
H4(i) = e + H4(i-1)
H5(i) = f + H5(i-1)
H6(i) = g + H6(i-1)
H7(i) = h + H7(i-1)

Теперь рассмотрим SHA-512. В данном случае инициализируются восемь 64-битных переменных, которые будут являться промежуточным значением хэш-кода:

a, b, c, d, e, f, g, h

Основой алгоритма является модуль, состоящий из 80 циклических обработок каждого блока M(i):

$$T_{1} = h + \Sigma _{1}^{(512) }(e) + Ch(e, f, g) + K_{t}^{(512)} + W_{t} \\ T_{2} = \Sigma _{0}^{(512)}(a) + Maj(a, b, c) \\ h = g \\ g = f \\ f = e \\ e = d + T_{1} \\ d = c \\ c = b \\ b = a \\ a = T_{1} + T_{2}$$

где Ki{512} - восемьдесят 64-битных констант, каждая из которых является первыми 64-мя битами дробной части кубических корней первых восьмидесяти простых чисел.

Wt вычисляются из очередного блока сообщения по следующим правилам:

$$W_{t} = M_{t}^{(i)} , 0 \le t \le 15 \\ W_{t} = \sigma _{1}^{(512) }(W_{t-2}) + W_{t-7} + \sigma _{0}^{(512)}(W_{t-15}) + W_{t-16} , \\ 16 \le t \le 79$$

i-ое промежуточное значение хэш-кода H(t) вычисляется следующим образом:

H0(i) = a + H0(i-1)
H1(i) = b + H1(i-1)
H2(i) = c + H2(i-1)
H3(i) = d + H3(i-1)
H4(i) = e + H4(i-1)
H5(i) = f + H5(i-1)
H6(i) = g + H6(i-1)
H7(i) = h + H7(i-1)

Рассмотрим SHA-384. Отличия этого алгоритма от SHA-512:

Другой начальный хэш-код H(0).

384-битный дайджест получается из левых 384 битов окончательного хэш-кода H(N):

H0(N) || H1(N) || H2(N) || H3(N) || H4(N) || H5(N).

Хэш-функция ГОСТ 34.11

Алгоритм ГОСТ 34.11 является отечественным стандартом для хэш-функций. Его структура довольно сильно отличается от структуры алгоритмов SHA-1, 2 или MD5, в основе которых лежит алгоритм MD4.

Длина хэш-кода, создаваемого алгоритмом ГОСТ 34.11, равна 256 битам. Алгоритм разбивает сообщение на блоки, длина которых также равна 256 битам. Кроме того, параметром алгоритма является стартовый вектор хэширования Н - произвольное фиксированное значение длиной также 256 бит.

Алгоритм обработки одного блока сообщения

Сообщение обрабатывается блоками по 256 бит справа налево.

Каждый блок сообщения обрабатывается по следующему алгоритму.

Генерация четырех ключей длиной 256 бит каждый.

Шифрование 64-битных значений промежуточного хэш-кода H на ключах Ki(i = 1, 2, 3, 4) с использованием алгоритма ГОСТ 28147 в режиме простой замены.

Перемешивание результата шифрования.

Для генерации ключей используются следующие данные:

промежуточное значение хэш-кода Н длиной 256 бит;

текущий обрабатываемый блок сообщения М длиной 256 бит;

параметры - три значения С2, С3 и С4 длиной 256 бит следующего вида: С2 и С4 состоят из одних нулей, а С3 равно

18 08 116 024 116 08 (08 18)2 18 08 (08 18)4 (18 08)4

где степень обозначает количество повторений 0 или 1.

Используются две формулы, определяющие перестановку и сдвиг.

Перестановка Р битов определяется следующим образом: каждое 256-битное значение рассматривается как последовательность тридцати двух 8-битных значений.

Перестановка Р элементов 256-битной последовательности выполняется по формуле $$y = \varphi (x)$$, где x - порядковый номер 8-битного значения в исходной последовательности; y - порядковый номер 8-битного значения в результирующей последовательности.

$$\varphi (i + 1 + 4(k - 1)) = 8i + k \\ i = 0 \div 3, k = 1 \div 8$$

Сдвиг А определяется по формуле

$$A (x) = (x_{1} \oplus x_{2}) || x_{4} || x_{3} || x_{2}$$

Где

xi - соответствующие 64 бита 256-битного значения х,

|| обозначает конкатенацию.

Присваиваются следующие начальные значения:

$$i = 1, U = H, V = M. \\ W = U \oplus V, K_{1} = Р (W)$$

Ключи K2, K3, K4 вычисляются последовательно по следующему алгоритму:

$$U = A(U) \oplus С_{i}, \\ V = A(A(V)), \\ W = U \oplus V, \\ K_{i} = Р(W)$$

Далее выполняется шифрование 64-битных элементов текущего значения хэш-кода Н с ключами K1, K2, K3 и K4. При этом хэш-код Н рассматривается как последовательность 64-битных значений:

H = h4 || h3 || h2 || h1

Выполняется шифрование алгоритмом ГОСТ 28147:

si = EKi [hi]    i = 1, 2, 3, 4
S = s1 || s2 || s3 || s4

Наконец на заключительном этапе обработки очередного блока выполняется перемешивание полученной последовательности. 256-битное значение рассматривается как последовательность шестнадцати 16-битных значений. Сдвиг обозначается $$\Psi$$ и определяется следующим образом:

$$\eta _{16} || \eta _{15} || \dots || \eta _{1}$$ - исходное значение

$$\eta _{1} \oplus \eta _{2} \oplus \eta _{3} \oplus \eta _{4} \oplus \eta _{13} \oplus \eta _{16} || \eta _{16} || \dots || \eta _{2}$$ - результирующее значение

Результирующее значение хэш-кода определяется следующим образом:

$$\chi (M, H) = \psi ^{61} (H \oplus \psi (M \oplus \psi ^{12}(S)))$$

где

H - предыдущее значение хэш-кода,

М - текущий обрабатываемый блок,

$$\Psi ^{i}$$ - i-ая степень преобразования $$\Psi.$$

Логика выполнения ГОСТ 34.11

Входными параметрами алгоритма являются:

исходное сообщение М произвольной длины;

стартовый вектор хэширования Н, длина которого равна 256 битам;

контрольная сумма $$\Sigma,$$ начальное значение которой равно нулю и длина равна 256 битам;

переменная L, начальное значение которой равно длине сообщения.

Сообщение М делится на блоки длиной 256 бит и обрабатывается справа налево. Очередной блок i обрабатывается следующим образом:

$$H = \chi (M_{i}, H)$$

$$\Sigma = \Sigma \oplus ' M_{i}$$

L рассматривается как неотрицательное целое число, к этому числу прибавляется 256 и вычисляется остаток от деления получившегося числа на 2256. Результат присваивается L.

Где $$\oplus '$$ обозначает следующую операцию: $$\Sigma$$ и Mi рассматриваются как неотрицательные целые числа длиной 256 бит. Выполняется обычное сложение этих чисел и находится остаток от деления результата сложения на 2256. Этот остаток и является результатом операции.

Самый левый, т.е. самый последний блок М' обрабатывается следующим образом:

Блок добавляется слева нулями так, чтобы его длина стала равна 256 битам.

Вычисляется $$\Sigma = \Sigma \oplus ' M_{i}$$.

L рассматривается как неотрицательное целое число, к этому числу прибавляется длина исходного сообщения М и находится остаток от деления результата сложения на 2256.

Вычисляется $$Н = \chi (М', Н)$$.

Вычисляется $$Н = \chi (L, Н)$$.

Вычисляется $$Н = \chi (\Sigma , Н)$$.

Значением функции хэширования является Н.

Коды аутентификации сообщений - МАС

Требования к МАС

Напомним, что обеспечение целостности сообщения - это невозможность изменения сообщения так, чтобы получатель этого не обнаружил. Под аутентификацией понимается подтверждение того, что информация получена от законного источника, и получателем является тот, кто нужно. Один из способов обеспечения целостности - это вычисление МАС (Message Authentication Code). В данном случае под МАС понимается некоторый аутентификатор, являющийся определенным способом вычисленным блоком данных, с помощью которого можно проверить целостность сообщения. В некоторой степени симметричное шифрование всего сообщения может выполнять функцию аутентификации этого сообщения. Но в таком случае сообщение должно содержать достаточную избыточность, которая позволяла бы проверить, что сообщение не было изменено. Избыточность может быть в виде определенным образом отформатированного сообщения, текста на конкретном языке и т.п. Если сообщение допускает произвольную последовательность битов (например, зашифрован ключ сессии), то симметричное шифрование всего сообщения не может обеспечивать его целостность, так как при дешифровании в любом случае получится последовательность битов, правильность которой проверить нельзя. Поэтому гораздо чаще используется криптографически созданный небольшой блок данных фиксированного размера, так называемый аутентификатор или имитовставка, с помощью которого проверяется целостность сообщения. Этот блок данных может создаваться с помощью секретного ключа, который разделяют отправитель и получатель. МАС вычисляется в тот момент, когда известно, что сообщение корректно. После этого МАС присоединяется к сообщению и передается вместе с ним получателю. Получатель вычисляет МАС, используя тот же самый секретный ключ, и сравнивает вычисленное значение с полученным. Если эти значения совпадают, то с большой долей вероятности можно считать, что при пересылке изменения сообщения не произошло.

MAC = CK (M)

Рассмотрим свойства, которыми должна обладать функция МАС. Если длина ключа, используемого при вычислении МАС, равна k, то при условии сильной функции МАС противнику потребуется выполнить 2k попыток для перебора всех ключей. Если длина значения, создаваемого МАС, равна n, то всего существует 2n различных значений МАС.

Предположим, что конфиденциальности сообщения нет, т.е. оппонент имеет доступ к открытому сообщению и соответствующему ему значению МАС. Определим усилия, необходимые оппоненту для нахождения ключа МАС. Предположим, что k > n, т.е. длина ключа больше длины МАС. Тогда, зная М1 и МАС1 = СK (M1), оппонент может вычислить МАС1 = СKi (M1) для всех возможных ключей Ki. При этом, по крайней мере, для одного из ключей будет получено совпадение MACi = MAC1. Оппонент вычислит 2k значений МАС, тогда как при длине МАС n битов существует всего 2n значений МАС. Мы предположили, что k > n, т.е. 2k > 2n. Таким образом, правильное значение МАС будет получено для нескольких значений ключей. В среднем совпадение будет иметь место для 2k / 2n = 2(k-n) ключей. Поэтому для вычисления единственного ключа оппоненту требуется знать несколько пар сообщений и соответствующий ему МАС.

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

Функция вычисления МАС должна обладать следующими свойствами:

Должно быть вычислительно трудно, зная М и СK (M), найти сообщение М', такое, что СK(M) = СK(M').

Значения СK(M) должны быть равномерно распределенными в том смысле, что для любых сообщений М и M' вероятность того, что СK(M) = СK(M'), должна быть равна 2-n, где n - длина значения МАС.

МАС на основе алгоритма симметричного шифрования

Для вычисления МАС может использоваться алгоритм симметричного шифрования (например, DES) в режиме СВС и нулевой инициализационный вектор. В этом случае сообщение представляется в виде последовательности блоков, длина которых равна длине блока алгоритма шифрования. При необходимости последний блок дополняется справа нулями, чтобы получился блок нужной длины. Вычисление МАС происходит по следующей схеме:

$$МАС_{1} = E_{K} [P_{1}] \\ МАС_{2} = E_{K} [P_{2} \oplus MAC_{1}] \\ . . . \\ МАС_{N} = E_{K} [P_{N} \oplus MAC_{N-1}] \\ MAC = МАС_{N}$$

МАС на основе хэш-функции

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

НМАС

Еще один вариант использования хэш-функции для получения МАС состоит в том, чтобы определенным образом добавить секретное значение к сообщению, которое подается на вход хэш-функции. Такой алгоритм носит название НМАС, и он описан в RFC 2104.

При разработке алгоритма НМАС преследовались следующие цели:

возможность использовать без модификаций уже имеющиеся хэш-функции;

возможность легкой замены встроенных хэш-функций на более быстрые или более стойкие;

сохранение скорости работы алгоритма, близкой к скорости работы соответствующей хэш-функции;

возможность применения ключей и простота работы с ними.

В алгоритме НМАС хэш-функция представляет собой "черный ящик". Это, во-первых, позволяет использовать существующие реализации хэш-функций, а во-вторых, обеспечивает легкую замену существующей хэш-функции на новую.

Введем следующие обозначения:

Н - встроенная хэш-функция.

b - длина блока используемой хэш-функции.

n - длина хэш-кода.

K - секретный ключ. К этому ключу слева добавляют нули, чтобы получить b-битовый ключ K+.

Вводится два вспомогательных значения:

Ipad - значение '00110110', повторенное b/8 раз.

Opad - значение '01011010', повторенное b/8 раз.

Далее НМАС вычисляется следующим образом:

$$НМАС = Н ((K^{+} \oplus Opad) || H ((K^{+} \oplus Ipad) || M))$$