Хэш-функции

Требования к криптографическим хэш-функциям

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

Хэш-код создается функцией Н:

h = H (M)

гдеМ является сообщением произвольной длины и h является хэш-кодом фиксированной длины.

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

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

Хэш-функция Н должна применяться к блоку данных любой длины.

Хэш-функция Н должна создавать выход фиксированной длины.

Н(М) относительно легко (за полиномиальное время) вычисляется для любого значения М.

Для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н(M)=h.

Для любого данного М вычислительно невозможно найти М′ ≠ M такое, что H(M)=H(M′).

Вычислительно невозможно найти произвольную пару (M,M′) такую, что H(M)=H(M′).

Первые три свойства требуют, чтобы хэш-функция создавала хэш-код для любого сообщения.

Четвертое свойство означает, что хэш-функция должна обладать свойством односторонности: легко создать хэш-код по данному сообщению, но невозможно восстановить сообщение по хэш-коду. Это свойство важно, если для аутентификации с помощью хэш-функции используется секретное значение. Само секретное значение может не посылаться, тем не менее, если хэш-функция не является односторонней, противник может легко раскрыть секретное значение следующим образом. Перехватив передаваемое сообщение, атакующий получает сообщение М и хэш-код h=Н(S||M). Если атакующий может инвертировать хэш-функцию, то он получает S||M=H–1(h). Так как атакующий теперь знает и М, и S||M, получить S совсем просто.

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

Хэш-функция, которая удовлетворяет первым пяти свойствам, называется простой или слабой хэш-функцией. Если кроме того выполняется шестое свойство, то такая функция называется сильной хэш-функцией. Шестое свойство защищает против класса атак, известных как атака "день рождения".

"Парадокс дня рождения"

Так называемый "парадокс дня рождения" состоит в следующем.

Первая задача. Каким должно быть число k, чтобы для данного значения X и значений Y1, …, Yk, каждое из которых принимает значения от 1 до n, вероятность того, что хотя бы для одного Yi выполнялось равенство X=Y

P (X = Y) ≥ 0.5

Для одного значения Y вероятность того, что X=Y, равна 1/n.

P (X = Y) = 1/n

Соответственно, вероятность того, что X ≠ Y, равна 1 – 1/n.

P (X ≠ Y) = 1 – 1/n

Если создать k значений, то вероятность того, что ни для одного из них не будет совпадений, равна произведению вероятностей, соответствующих одному значению, т.е. (1 – 1/n)k.

Следовательно, вероятность по крайней мере одного совпадения равна

P (X = Yi) = 1 – (1 – 1/n)k

По формуле бинома Ньютона

$$(1 – a)k = 1 – ka + \frac {k(k-1)} {2!} a^2 - … \approx 1 – ka$$ $$1 – (1 – k/n) = k/n = 0.5$$ $$k = n/2$$

Таким образом, для хэш-кода длиной m бит достаточно выбрать 2m-1 сообщений, чтобы вероятность совпадения хэш-кодов была больше 0,5.

Теперь рассмотрим вторую задачу. Обозначим P(n,k) вероятность того, что в множестве из k элементов, каждый из которых может принимать n значений, есть хотя бы два с одинаковыми значениями. Чему должно быть равно k, чтобы P(n,k) была бы больше 0,5?

Число различных способов выбора элементов таким образом, чтобы при этом не было дублей, равно

$$n (n-1) … (n-k+1) \frac {n!} {(n-k)!}$$

Всего возможных способов выбора элементов равно

$$n^k$$

Вероятность того, что дублей нет, равна

$$\frac {n!} {(n-k)! n^k}$$

Вероятность того, что есть дубли, соответственно равна

$$1 - \frac {n!} {(n-k)! n^k}$$ $$P (n, k) = 1 – n! / ((n-k)! \times n^k) = 1 – (n \times (n-1) \times … \times (n-k-1)) / n^k = 1 – [ (n-1)/n \times (n-2)/n \times … \times (n-k+1)/n] = 1 – [( 1- 1/n) \times (1 – 2/n) \times … \times (1 – (k-1)/n)]$$

Известно, что Если хэш-код имеет длину m бит, т.е. принимает 2m значений, то

$$k_1 – x \leg e^-^x$$ $$P (n, k) > 1 – [e^-1^/^n \times e^-^2^/^n \times … \times e^-^k^/^n]$$ $$P (n, k) > 1 – e^-^k^(^k^-^1^)^/^n$$ $$\frac 1 2 = 1 – e^-^k^(^k^-^1^)^/^n$$ $$2 = e^k^(^k^-^1^)^/^n$$ $$ln 2 = k (k-1) / 2n$$ $$k (k-1) \approx k^2$$ $$k = \sqrt {(2n \times ln 2)} = 1,17 \sqrt n \approx \sqrt n = \sqrt {2^m} = 2^m^/^2$$

Подобный результат называется "парадоксом дня рождения", потому что в соответствии с приведенными выше рассуждениями для того, чтобы вероятность совпадения дней рождения у двух человек была больше 0,5, в группе должно быть всего 23 человека. Этот результат кажется удивительным, возможно, потому, что для каждого отдельного человека вероятность того, что с его днем рождения совпадет день рождения у кого-то другого в группе, достаточно мала.

Вернемся к рассмотрению свойств хэш-функций. Предположим, что используется 64-битный хэш-код. Можно считать, что это вполне достаточная и, следовательно, безопасная длина для хэш-кода. Например, если защищенный хэш-код h передается с соответствующим незашифрованным сообщением М, то противнику необходимо будет найти М ′ такое, что

Н (М′) = Н (М)

для того, чтобы подменить сообщение и обмануть получателя. В среднем противник должен перебрать 2⁶³ сообщений для того, чтобы найти другое сообщение, у которого хэш-код равен перехваченному сообщению.

Тем не менее, возможны различного рода атаки, основанные на "парадоксе дня рождения". Возможна следующая стратегия:

Противник создает 2m/2 вариантов сообщения, каждое из ко-торых имеет некоторый определенный смысл. Противник под-готавливает такое же количество сообщений, каждое из которых является поддельным и предназначено для замены насто-ящего сообщения.

Два набора сообщений сравниваются в поисках пары сообщений, имеющих одинаковый хэш-код. Вероятность успеха в соответствии с "парадоксом дня рождения" больше, чем 0,5. Если соответствующая пара не найдена, то создаются дополни-тельные исходные и поддельные сообщения до тех пор, пока не будет найдена пара.

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

Таким образом, если используется 64-битный хэш-код, то для подбора двух сообщений с одинаковым хэш-кодом в среднем необходимо перебрать 2³² сообщений.

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

Хэш-функция MD5

Рассмотрим алгоритм получения дайджеста сообщения MD5 (RFC 1321), разработанный Роном Ривестом из MIT.

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

(рис 3.1) Логика выполнения MD5

Шаг 1: добавление недостающих битов

Сообщение дополняется таким образом, чтобы его длина стала равна 448 по модулю 512 (длина = 448 (mod 512)). Это означает, что длина добавленного сообщения на 64 бита меньше, чем число, кратное 512. Добавление производится всегда, даже если сообщение имеет нужную длину. Например, если длина сообщения 448 битов, оно дополняется 512 битами до 960 битов. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512.

Добавление состоит из единицы, за которой следует необходимое ко-личество нулей.

Шаг 2: добавление длины

64-битное представление длины исходного (до добавления) сообщения в битах присоединяется к результату первого шага. Если первоначальная длина больше, чем 2⁶⁴, то используются только последние 64 бита. Таким образом, поле содержит длину исходного сообщения по модулю 2⁶⁴.

В результате первых двух шагов создается сообщение, длина которого кратна 512 битам. Это расширенное сообщение представляется как после-довательность 512-битных блоковY0, Y1, . . ., YL-1, при этом общая длина расширенного сообщения равна L * 512 битам. Таким образом, длина полученного расширенного сообщения кратна шестнадцати 32-битным словам.

(рис 3.2) Структура расширенного сообщения

Шаг 3: инициализация MD-буфера

Используется 128-битный буфер для хранения промежуточных и окон-чательных результатов хэш-функции. Буфером являются четыре 32-битных регистра (A, B, C, D). Эти регистры инициализируются следующими шестнадцатеричными числами:

А = 01234567

В = 89ABCDEF

C = FEDCBA98

D = 76543210

Шаг 4: обработка последовательности 512-битных (16-словных) блоков

Основой алгоритма является модуль, состоящий из четырех циклических обработок, обозначенный как H_MD5. Четыре цикла имеют похожую структуру, но каждый цикл использует свою элементарную логическую функцию, обозначаемую fF, fG, fH и fI соответственно (рис. 3.3).

Каждый цикл принимает в качестве входа текущий 512-битный блок Yq, обрабатывающийся в данный момент, и 128-битное значение буфера ABCD, которое является промежуточным значением дайджеста, и изменяет содержимое этого буфера. На каждом цикле также используется четвертая часть 64-элементной таблицы T[1] ... T[64], построенной на основе функции sin.

$$T[i] = [2^{32} * abs (sin(i))]$$

Где [ ] в правой части означает целую часть числа, i задано в радианах. Так как abs (sin(i))является числом между 0 и 1, каждый элемент Т [i] является целым, которое может быть представлено 32 битами. Таблица обеспечивает "случайный" набор 32-битных значений, которые должны ликвидировать любую регулярность во входных данных.

Для получения MDq+1 выход четырех циклов складывается по модулю 2³² с MDq. Сложение выполняется независимо для каждого из четырех слов в буфере.

(рис 3.3) Обработка очередного 512-битного блока

Шаг 5: выход

После обработки всех L 512-битных блоков выходом L-ой стадии является 128-битный дайджест сообщения.

Рассмотрим более детально логику каждого из четырех циклов выполнения одного 512-битного блока. Каждый цикл состоит из 16 шагов, оперирующих с буфером ABCD. Каждый шаг представлен на рис. 3.4.

$$A \leftarrow B + CLS_s (A + f (B, C, D) + X [k] + T [i])$$

где A, B, C, D - четыре слова буфера; после выполнения каждого отдельного шага происходит циклический сдвиг влево на одно слово.

f - одна из элементарных функций fF, fG, fH, fI.

CLSs- циклический сдвиг влево на s битов 32-битного аргумента.

X[k] - M[q*16 + k] - k-ое 32-битное слово в q-ом 512 блоке сообщения.

T[i]- i-ое 32-битное слово в таблице Т.

+ - сложение по модулю 2³².

(рис 3.4) Логика выполнения отдельного шага

В каждом из четырех циклов алгоритма используется одна из четырех так называемых элементарных логических функций. Каждая элементарная функция получает три 32-битных слова на входе и на выходе создает одно 32-битное слово. Каждая функция является набором побитовых логических операций, т.е. n-ый бит выхода является функцией от n-ого бита трех входов. Элементарные функции следующие:

$$f_F = (B\C) V (not B \ D)\\ f_G = (B\D) V (C \ not D)\\ f_H = B \oplus C \oplus D\\ f_I = C \oplus (B \ not D)$$

Массив из 32-битных слов X[0..15] содержит значение текущего 512-битного входного блока, который обрабатывается в настоящий момент. Каждый цикл выполняется 16 раз, а так как каждый блок входного сообщения обрабатывается в четырех циклах, то каждый блок входного сообщения обрабатывается по описанной выше схеме 64 раза. Если представить входной 512-битный блок в виде шестнадцати 32-битный слов, то каждое входное 32-битное слово используется четыре раза, по одному разу в каждом цикле, и каждый элемент таблицы Т, состоящей из 64 32-битных слов, используется только один раз. После каждого шага цикла происходит циклический сдвиг влево четырех слов A, B, C и D. На каждом шаге изменяется только одно из четырех слов буфера ABCD. Следовательно, каждое слово буфера изменяется 16 раз, и затем 17-ый раз в конце для получения окончательного выхода данного блока.

Можно суммировать алгоритм MD5 следующим образом:

$$MD_0 = IV\\ MD_q_+_1 = MD_q+f_I[ Y_q, f_H[ Y_q, f G[Y_q, f_F[Y_q, MD_q] ] ] ]\\ MD = MD_L-_1$$

Где

IV - начальное значение буфера ABCD, определенное на шаге 3.

Yq - q-ый 512-битный блок сообщения.

L - число блоков в сообщении (включая поля дополнения и длины).

MD - окончательное значение дайджеста сообщения.

Хэш-функция SHA-1

Безопасный хэш-алгоритм (Secure Hash Algorithm) был разработан NIST и опубликован в качестве федерального информационного стандарта (FIPS PUB 180) в 1993 году. У алгоритмов MD5 и SHA-1 много общего.

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

Алгоритм состоит из следующих шагов:

(рис 3.5) Логика выполнения SHA-1

Шаг 1: добавление недостающих битов

Сообщение добавляется таким образом, чтобы его длина была кратна 448 по модулю 512 (длина = 448 (mod 512)). Добавление осуществля-ется всегда, даже если сообщение уже имеет нужную длину. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512.

Добавление состоит из единицы, за которой следует необходимое количество нулей.

Шаг 2: добавление длины

К сообщению добавляется блок из 64 битов. Этот блок трактуется как беззнаковое 64-битное целое и содержит длину исходного сообщения до добавления.

Результатом первых двух шагов является сообщение, длина которого кратна 512 битам. Расширенное сообщение может быть представлено как последовательность 512-битных блоков Y0, Y1, . . . ,YL-1, так что общая длина расширенного сообщения есть L * 512 бит. Таким образом, результат кратен шестнадцати 32-битным словам.

Шаг 3: инициализация SHA-1 буфера

Используется 160-битный буфер для хранения промежуточных и окон-чательных результатов хэш-функции. Буфер может быть представлен как пять 32-битных регистров A, B, C, D и E. Эти регистры инициализируются следующими шестнадцатеричными числами:

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

обработка сообщения в 512-битных (16-словных) блоках

Основой алгоритма является модуль, состоящий из 80 циклических обработок, обозначенный как HSHA. Все 80 циклических обработок имеют одинаковую структуру (рис. 3.6).

Каждый цикл получает на входе текущий 512-битный обрабатываемый блок Yq и 160-битное значение буфера ABCDE, и изменяет содержимое этого буфера.

В каждом цикле используется дополнительная константа Кt которая принимает только четыре различных значения:

$$ 0 \leq t \leq 19 K_t = 5A827999 (целая часть числа [2^3^0 \times \sqrt 2])\\ 20 \leq t \leq 39 K_t = 6ED9EBA1 (целая часть числа [2^3^0 \times \sqrt 3])\\ 40 \leq t \leq 59 K_t = 8F1BBCDC (целая часть числа [2^3^0 \times \sqrt 5])\\ 60 \leq t \leq 79 K_t = CA62C1D6 (целая часть числа [2^3^0 \times \sqrt 10]) $$

Для получения SHAq+1 выход 80-го цикла складывается со значением SHAq. Сложение по модулю 2³² выполняется независимо для каждого из пяти слов в буфере с каждым из соответствующих слов в SHAq.

(рис 3.6) Обработка очередного 512-битного блока

Шаг 5: выход

После обработки всех 512-битных блоков выходом L-ой стадии является 160-битный дайджест сообщения.

Рассмотрим более детально логику в каждом из 80 циклов обработки одного 512-битного блока. Каждый цикл можно представить в виде:

$$A,B,C,D,E \leftarrow (CLS_5 (A) + f_t (B, C, D) + E + W_t + K_t), A, CLS_{30} (B), C, D$$

Где

A,B,C,D,E - пять слов из буфера.

t - номер цикла, 0 ≤ t ≤ 779.

ft - элементарная логическая функция.

CLSs - циклический левый сдвиг 32-битного аргумента на s битов.

Wt - 32-битное слово, полученное из текущего входного 512-битного блока.

Kt - дополнительная константа.

+ - сложение по модулю 2³².

(рис 3.7) Логика выполнения отдельного цикла

Каждая элементарная функция получает на входе три 32-битных слова и создает на выходе одно 32-битное слово. Элементарная функция выполняет набор побитных логических операций, т.е. n-ый бит выхода является функцией от n-ых битов трех входов. Функции следующие:

Таблица 3.1

На самом деле используются только три различные функции. Для 0 ≤ t ≤ 19 функция является условной: if B then C else D Для 20 ≤ t ≤ 39 и 60 ≤ t ≤ 79 функция создает бит четности. Для 40 ≤ t ≤ 59 функция является истинной, если два или три аргумента истинны.

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

(рис 3.9) Получение входных значений каждого цикла из очередного блока

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

$$W_t = W_t_-_{16} \oplus W_t_-_{14} \oplus W_t_-_8 \oplus W_t_-_3$$

В первых 16 циклах вход состоит из 32-битного слова данного блока. Для оставшихся 64 циклов вход состоит из XOR нескольких слов из блока сообщения.

Алгоритм SHA-1 можно суммировать следующим образом:

SHA0= IV
SHAq+1= ∑ 32(SHAq, ABCDEq)
SHA = SHAL-1

Где

IV - начальное значение буфера ABCDE.

ABCDEq - результат обработки q-того блока сообщения.

L - число блоков в сообщении, включая поля добавления и длины.

∑32 - сумма по модулю 2³², выполняемая отдельно для каждого слова буфера.

SHA - значение дайджеста сообщения.

Сравнение SHA-1 и MD5

Оба алгоритма, SHA-1 и MD5, произошли от MD4, поэтому имеют много общего.

Можно суммировать ключевые различия между алгоритмами.

Таблица 3.2

Сравним алгоритмы MD5 и SHA-1.

Безопасность: наиболее очевидное и наиболее важное различие состоит в том, что дайджест SHA-1 на 32 бита длиннее, чем дайджест MD5. Если предположить, что оба алгоритма не содержат каких-либо структурированных данных, которые уязвимы для аналитиче-ских атак, то SHA-1 является более стойким алгоритмом. Используя лобовую атаку, труднее создать произвольное сообщение, имеющее данный дайджест, если требуется порядка 2159 операций, как в случае алгоритма SHA-1, чем порядка 2127 операций, как в случае алгоритма MD5. Используя лобовую атаку, труднее создать два сообщения, имеющие одинаковый дайджест, если требуется порядка 280 как в случае алгоритма SHA-1, чем порядка 264 операций как в случае алгоритма MD5.

Скорость: так как оба алгоритма выполняют сложение по модулю 232, они рассчитаны на 32-битную архитектуру. SHA-1 содержит больше шагов (80 вместо 64) и выполняется на 160-битном буфере по сравнению со 128-битным буфером MD5. Таким образом, SHA-1 должен выполняться приблизительно на 25% медленнее, чем MD5 на той же аппаратуре.

Простота и компактность: оба алгоритма просты и в описании, и в реализации, не требуют больших программ или подстановочных таблиц. Тем не менее, SHA-1 применяет одношаговую структуру по сравнению с четырьмя структурами, используемыми в MD5. Более того, обработка слов в буфере одинаковая для всех шагов SHA-1, в то время как в MD5 структура слов специфична для каждого шага.

Архитектуры little-endian и big-endian: MD5 использует little-endian схему для интерпретации сообщения как последовательности 32-битных слов, в то время как SHA-1 задействует схему big-endian. Каких-либо преимуществ в этих подходах не существует.

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

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

Таблица 3.3

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

В 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)$$ $$\sum _0^\left{ ^2^5^6^ \right} (x) = ROTR2 (x) \oplus ROTR13 (x) \oplus ROTR22 (x) \\ \sum _1^\left{^2^5^6^\right} (x) = ROTR^6 (x) \oplus ROTR^1^1 (x) \oplus ROTR^2^5 (x) \\ \sigma_0^\left{^2^5^6^\right} (x) = ROTR^7 (x) \oplus ROTR^1^8 (x) \oplus SHR^3 (x) \\ \sigma_1^\left{^2^5^6^\right} (x)= ROTR^1^7 (x) \oplus ROTR^1^9 (x) \oplus SHR^1^0 (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)$$ $$\sum _0^\left{ ^5^1^2^ \right} (x) = ROTR^2^8 (x) \oplus ROTR^3^4 (x) \oplus ROTR^3^9 (x) \\ \sum _1^\left{ ^5^1^2^ \right} (x) = ROTR^1^4 (x) \oplus ROTR^1^8 (x) \oplus ROTR^4^1 (x) \\ \sigma_0^\left{ ^5^1^2^ \right} (x) = ROTR^1 (x) \oplus ROTR^1^8 (x) \oplus SHR^7 (x) \\ \sigma_1^\left{ ^5^1^2^ \right} (x)= ROTR^1^9 (x) \oplus ROTR^6^1 (x) \oplus SHR^6 (x)$$

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

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

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

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

$$T_1= h + \sum_1^ \lbrace ^2^5^6^ \rbrace(e) + Ch (e, f, g) + K_t\sum_0^ \lbrace ^2^5^6^ \rbrace+ W_t \\ T_2= \sum_0^ \lbrace ^2^5^6^ \rbrace (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^)\quad 0 \le t \le15 \\ W_t= s_1^ \lbrace ^2^5^6^ \rbrace (W_t_-_2) + W_t_-_7 + s_0^ \lbrace ^2^5^6^ \rbrace (W_t_-_1_5) + W_t_-_1_6 \quad 16\le t\le 63$$

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

$$H_0^(^i^)= a + H_0^(^i^-^1^)\\ H_1^(^i^)= b + H_1^(^i^-^1^)\\ H_2^(^i^)= c + H_2^(^i^-^1^)\\ H_3^(^i^)= d + H_3^(^i^-^1^)\\ H_4^(^i^)= e + H_4^(^i^-^1^)\\ H_5^(^i^)= f + H_5^(^i^-^1^)\\ H_6^(^i^)= g + H_6^(^i^-^1^)\\ H_7^(^i^)= h + H_7^(^i^-^1^)$$

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

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

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

$$T_1= h+ \sum_1^ \lbrace ^5^1^2^ \rbrace(e) + Ch (e, f, g) + K_t^ \lbrace ^5^1^2^ \rbrace + W_t\\ T_2= \sum_0^ \lbrace ^5^1^2^ \rbrace(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^) \quad 0 \le t \le 15\\ W_t= \sigma_1^ \lbrace ^5^1^2^ \rbrace(W_t_-_2)+ W_t_-_7 + \sigma_0^\lbrace ^5^1^2^ \rbrace(W_t_-_1_5) + W_t_-_1_6 \quad 16 \le t \le 79$$

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

$$H_0^(^i^)= a + H_0^(^i^-^1^)\\ H_1^(^i^)= b + H_1^(^i^-^1^)\\ H_2^(^i^)= c + H_2^(^i^-^1^)\\ H_3^(^i^)= d + H_3^(^i^-^1^)\\ H_4^(^i^)= e + H_4^(^i^-^1^)\\ H_5^(^i^)= f + H_5^(^i^-^1^)\\ H_6^(^i^)= g + H_6^(^i^-^1^)\\ H_7^(^i^)= h + H_7^(^i^-^1^)$$

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

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

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

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

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

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

Длина хэш-кода, создаваемого алгоритмом ГОСТ 3411, равна 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=φ(x), где x – порядковый номер 8-битного значения в исходной последовательности; y – порядковый номер 8-битного значения в результирующей последовательности.

$$\phi (i + 1 + 4(k – 1)) = 8i + k \quad i = 0 \div 3, k = 1 \div 8$$

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

$$A (x) = (x1 \oplus x2) || x4 || x3 || x2$$

Где xi – соответствующие 64 бита 256-битного значения х, || обозначает конкатенацию.

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

$$i = 1,\quad U = H, \quad V = M.\\ W = U \oplus V,\quad K1 = Р (W)$$

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

$$U = A (U) \oplus Сi,\quad V = A (A (V)),\quad W = U \oplus V,\quad Ki = Р (W)$$

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

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

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

$$s_i = EK_i [h_i] \quad i = 1, 2, 3, 4\\ S = s_1 || s_2 || s_3 || s_4$$

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

$$\eta 16 || \eta 15 || … || \eta1$$ -исходное значение

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

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

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

Где H – предыдущее значение хэш-кода, М – текущий обрабатываемый блок, ψi – i-ая степень преобразования y.

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

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

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

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

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

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

H = χ (Mi, H)

∑ = ∑⊕' Mi

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

Где ⊕' обозначает следующую операцию: ∑ и Mi рассматриваются как неотрицательные целые числа длиной 256 бит. Выполняется обычное сложение этих чисел и находится остаток от деления результата сложения на 2²⁵⁶. Этот остаток и является результатом операции.

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

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

Вычисляется ∑ = ∑ ⊕' M'.

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

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

Вычисляется Н = χ (L, Н)

Вычисляется Н = χ (∑, Н).

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

Код аутентификации сообщения

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

MAC = CK (M)

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

Предположим, что конфиденциальности сообщения нет, т.е. оппонент имеет доступ к открытому сообщению и соответствующему ему значению МАС. Определим усилия, необходимые оппоненту для нахождения ключа МАС.

Предположим, что k > n, т.е. длина ключа больше длины МАС. Тогда, зная М1 и МАС1= СK(M1), оппонент может вычислить МАС1= СKi(M1) для всех возможных ключей Ki. При этом, по крайней мере, для одного из ключей будет получено совпадение MACi = MAC1. Оппонент вычислит 2^k значений МАС, тогда как при длине МАС n битов существует всего 2ⁿ значений МАС. Мы предположили, что 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 – длина значения МАС.

Стандарт НМАС

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Opad – значение ‘01011010’, повторенное b/8 раз.

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

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