iapetus2 Dec 14 2021 at 14:16

Blue (Голубой) Midnight Wish — еще один алгоритм хэширования (для ценителей)

6 min

2.6K

Information Security*Cryptography*Algorithms*

Привет всем хабровчанам и просто заглянувшим!

Поддавшись осенне-зимнему тренду на Хабре на (около)криптографические статьи, я решил поддержать оный, потому что чем больше ~~годной~~ информации на русском, тем лучше-ж, да..?
Итак, сегодня я хочу рассказать вам о Blue Midnight Wish (BMW, да-да, может кто-то еще не понял). Сразу хочу предупредить - это моя первая статья, поэтому будьте нежнее, по возможности...

Краткий экскурс в контекст

В 2007 году Национальным институтом стандартов и технологий (NIST) был объявлен конкурс на создание нового криптоалгоритма для замены SHA-1 и SHA-2, по итогам которого должен был быть избран алгоритм для SHA-3. Blue Midnight Wish был одним из предложенных алгоритмов, успешно прошедшим первый тур отбора.

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

Шпаргалка

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

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

SHA (Secure Hash Algorithm) - алгоритм безопасного хэширования, на данный момент (декабрь 2021) насчитывает четыре поколения, последнее это SHA-3.

Необходимые далее обозначения

	Двойная трубка(double pipe, dp). Изменяющееся значение, которое минимум в два раза шире, чем конечная цифровая подпись в n бит
	Счетверенная трубка(quadruple pipe, qp) - аналогично, но уже вчетверо
$H^{(i)}$	i-е значение dp, $H^{(0)}$ — начальное значение.
$Q^{(i)}$	i-е значение qp.
$H_j^{(i)}$	j-е слово из $H^{(i)}$ Где $H^{(i)}$ разбивается на заранее определённое количество блоков - слова
$Q_j^{(i)}$	j-е слово qp $Q^{(i)}$
$Q_a^{(i)}$	Первые 16 слов из $Q^{(i)}$
$Q_b^{(i)}$	Последние 16 слов из $Q^{(i)}$
	Сообщение

Что там инженеры наинженерили...

Для ясности

Если описывать алгоритм максимально ёмко, то выйдет что-то вроде
Сообщение M делим на N m-битных блоков и далее

i = 0
while(i < N) {
   Q_a(i) = f0(M(i), H(i-1))
   Q_b(i) = f1(M(i), Q_a(i))
   Q(i) = Q_a(i) concate Q_b(i)
   H(i) = f2(M(i), Q(i))
   i++
 }
 Q_a(final) = f0(H(N), const)
 Q_b(final) = f1(H(N), const, Q_a(final))
 H(final) = f2(H(N), Q_a(final), Q_b(final)
 
 hash = N_Least_Significant_Bits(H(final))

В целом дальше в статье я буду распространяться про все обозначения из этих 13 (тут от страха мог умереть один американец) строчек кода.

Blue Midnight Wish следует общему шаблону проектирования большинства хэш-функций.
Два основных этапа:

Первичная обработка
(а) заполнение сообщения (padding),
(б) разбиение сообщения на m-битные блоки (parsing),
(в) установка начальных значений, которые будут использоваться при вычислении хэша
Вычисление хэша
(а) создание расписания сообщений (message schedule) из дополненного сообщения,
(б) использование этого расписания вместе с функциями, константами и операциями со словами для итеративного создания серии значений двойной трубки,
(в) окончательное значение двойной трубки, сгенерированное итеративным процессом в (б) используется в качестве входных данных для функции финализации (определим ее далее);
(г) n последних значащих бит функции финализации используются для расчета хэша сообщения.

Размеры блоков и слов зависят от конкретной реализации алгоритма BMW, привожу их в таблице:

версия алгоритма	размерсообщения, бит	размерблока, бит	размерслова, бит	размерхэша, бит
BMW224	$< 2^{64}$	512	32	224
BMW256	$< 2^{64}$	512	32	256
BMW384	$< 2^{64}$	1024	64	384
BMW512	$< 2^{64}$	1024	64	512

Далее в статье подробнее разберу весь алгоритм по шагам на примере BMW256.

Заполняем сообщение

Предположим, что длина сообщенияравнабит. Добавляем единичный бит в конец сообщения, далеенулевых бит, где - наименьшее неотрицательное решение уравнения $p + k + 1 \equiv 448\pmod{512}$ . Затем добавляется 64-битный блок, равный числу , выраженному с помощью его двоичного представления.

Например, сообщение "habr", закодированное в 8-битном ASCII, имеет длину $8 \times 4 = 32$ , поэтому сообщение дополняется битом «1», затем 448 - (32 + 1) = 415 нулевыми битами и затем 64-битным двоичным представлением числа 32, чтобы стать 512-битным дополненным сообщением.

$\overbrace{\overbrace{01101000}^{"h"} \space \overbrace{01100001}^{"a"} \space\overbrace{01100010}^{"b"} \space\overbrace{01110010}^{"r"}\space1\underbrace{00...0}_{415}\underbrace{00...0\overbrace{100000}^{p=32}}_{64}}^{512\space бит}$

Разбиваем сообщение на блоки

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

Для BMW256 дополненное сообщение разбирается на512-битных блоков, M_1, M_2, ..., M_N . Поскольку 512 бит входного блока могут быть выражены шестнадцатью 32-битными словами, первые 32 бита блока сообщенияобозначаются $M_0^{(i)}$ , следующие 32 бита - $M_1^{(i)}$ и так далее до $M_{15}^{(i)}$ .

Из-за того, что BMW имеет обратный (little-endian) порядок байтов, обратите внимание на обратный порядок байтов в M_i .

Для нашего сообщения "habr":

	$M_8= \space0х00000000$
	$M_9= \space0х00000000$
	$M_{10}= 0х00000000$
	$M_{11}= 0х00000000$
	$M_{12}= 0х00000000$
	$M_{13}= 0х00000000$
	$M_{14}= 0х02000000$
	$M_{15}= 0х00000000$

Начальное значение двойной трубки

Перед началом вычисления хэш-функции для каждого из хэш-алгоритмов должно быть установлено начальное значение dp - $H^{(0)}$ . Размер и значение слов в $H^{(0)}$ зависят от размера дайджеста сообщения. $H^{(0)}$ для BMW256 начинается с байта 0x40 и принимает все 64 последовательных байтовых значения до 0x7F. $H^{(0)}$ должно состоять из шестнадцати 32-битных слов.

Значение itself:

$H^{(0)}=0х40414243\space0х44454647\space0х48494a4b\space0х4c4d4e4f\\ \space0х50515253\space0х54555657\space0х58595a5b\space0х5c5d5e5f\\\space0х60616263\space0х64656667\space0х68696a6b\space0х6c6d6e6f\\\space0х70717273\space0х74757677\space0х78797a7b\space0х7c7d7e7f$

Непосредственно алгоритм хэширования

BMW256 может использоваться для хэширования сообщениядлинойбит, где $0<p<2^{64}$ . Алгоритм использует

шестнадцать 32-битных слов которые являются частью двойной трубки;
дополнительные шестнадцать 32-битных слов, которые вместе со словами двойной трубки образуют счетверённую трубку;
два временных 32-битных слова и .

Слова счетверённой трубки обозначены как $Q_0^{(i)},Q_1^{(i)},...,Q_{31}^{(i)}$ . Слова двойной трубки обозначенные как $H_0^{(i-1)},H_1^{(i-1)},...,H_{15}^{(i-1)}$ , изначально хранят значение $H^{(0)}$ , которое далее итерационно заменяется промежуточным значением двойной трубки (после обработки каждого блока сообщения), окончательно будут хранить значение двойной трубки $H^{(N)}$ .

Мы используем три функции:

$f_0:\{0,1\}^{2m} \rightarrow \{0,1\}^m\\f_1:\{0,1\}^{3m}\rightarrow\{0,1\}^m \spaceи \space Q_b^{(i)} = f_1(M^{(i)}, H^{(i-1)},Q_a^{(i)})\\f_2:\{0,1\}^{3m}\rightarrow\{0,1\}^m \spaceи\space H^{(i)}=f_2(M^{(i)}, Q^{(i)}) \equiv f_2(M^{(i)},Q_a^{(i)},Q_b^{(i)})$

1. f_0 принимает 2 аргумента - $M^{(i)}$ и $H^{(i-1)}$ каждый из m битов, и для любого значения $H^{(i-1)}$ (текущее значение dp) она биективно преобразует $M^{(i)}$ (i-й блок сообщения). Результат

$Q_a^{(i)} = f_0(M^{(i)}, H^{(i-1)})=A_2(A_1(M^{(i)}\oplus H^{(i-1)})) + ROTL^1(H^{(i-1)})$

является первой частью счетверённой трубки.

2. Вторая функция f_1 принимает три аргумента: блок $M^{(i)}$ из m битов, текущее значение dp $H^{(i-1)}$ и значение $Q_a^{(i)}$ (первая часть qp), чтобы вычислить вторую часть $Q_b^{(i)}=(Q_{16}^{(i)}, Q_{17}^{(i)}, ...,Q_{31}^{(i)})$ cчетверённой трубы qp. Эта функция для каждого $H^{(i-1)}$ делает следующее: для данной пары $(M^{(i)},Q_a^{(i)})$ однозначно вычисляет $Q_b^{(i)}$ , затем для данной пары $(M^{(i)},Q_b^{(i)})$ однозначно вычисляет $Q_a^{(i)}$ и для данной пары $(Q_a^{(i)},Q_b^{(i)})$ она однозначно вычисляет $M^{(i)}$ .

3. f_2 отображает 3m бит в m бит. Она принимает два аргумента: блок $M^{(i)}$ размером m бит и текущее значение $Q^{(i)}=(Q_a^{(i)},Q_b^{(i)})$ размером 2m бит, чтобы создать новую двойную трубку $H^{(i)}$ из m бит.

Конечным результатом BMW256 является 256-битный хэш, который представляет собой 256 младших значащих битов из окончательного хэш-значения $H^{final}$ , то есть значений $(H_8^{final},H_9^{final},...,H_{15}^{final})$ .

Пояснение для тех, кто еще не потерялся

Преобразования $A1\space и \space A2$ , как и конкретную реализацию алгоритма я позволю себе определить картинками из документации IEEE чуть ниже (простите, простите, простите), для любознательных ссылка (на IEEE);

$\oplus$ - операция XOR

$ROTL^1(H^{(i-1)})=(H_1^{(i-1)}, H_2^{(i-1)}, ...,H_{15}^{(i-1)}, H_0^{(i-1)})$ циклически переставляет первый элемент вектора $H^{(i-1)}$ в конец.

SHR^r(x) - сдвиг вправо на бит слова

SHL^r(x) - сдвиг влево на бит слова

Функция f_0 представляет собой композицию преобразований $A_1 \space и \space A_2$

Преобразования A1 и A2 соответственно, их композиция - функция f0

Вычисление вспомогательных функций expand

Для определения функции f_1 еще разок воспользуемся псевдокодом, $ExpandRounds_1 и \space ExpandRounds_2$ - известные выбранные параметры

f1:
for ii = 0 to ExpandRounds_1 - 1 do:
Q(ii+16, i) = expand_1(ii + 16)
for ii = ExpandRounds_1 to ExpandRounds_1 + ExpandRounds_2 - 1 do:
Q(ii+16, i) = expand_2(ii + 16)

Функция f_2 задается следующим образом:

Вычисляются $XL \space и \space XH$

$XL=Q_{16}^{(i)}\oplus Q_{17}^{(i)}\oplus ...\oplus Q_{23}^{(i)}\\XH= XL \oplus Q_{24}^{(i)} \oplus Q_{25}^{(i)} \oplus...\oplus Q_{31}^{(i)}$

Итеративное вычисление нового значения dp - функция f2

Заключение

Алгоритм Blue Midnight Wish достойно показал себя в конкурсе NIST, но в конечном итоге уступил алгоритму Keccak. Причиной стала возможная уязвимость к псевдо-коллизионным атакам.
Такие структуры как BMW, на мой взгляд, ~~заставляют хотя бы проникнуться уважением к труду тех кто угрохал много сил на свое дело~~ на своем примере показывают, что темпы развития технологий сейчас поражают воображение, реально применяется о-малое от создаваемых решений и алгоритмов, при высокой доле отсеивания хороших вариантов, чтобы в конечном счете найти лучший.

Эта статья проба пера и введение к циклу, в скором времени для большей наглядности завезу реализацию BMW и нескольких других алгоритмов участников SHA-3, следите за обновлениями.

Большое спасибо что прочитали, мне очень приятно видеть это:)

Источники

Danilo Gligoroski, Vlastimil Klima, Svein Johan Knapskog, Mohamed El-Hadedy, Jørn Amundsen, Stig Frode Mjølsnes. Blue Midnight Wish. // Trondheim, Norway: Norwegian University of Science and Technology, 2008. — С. 71.
https://ieeexplore.ieee.org/document/5683052 - документация с IEEE.
Soren S. Thomsen. Pseudo-cryptanalysis of Blue Midnight Wish. — 2009. — С. 7.

Tags:

Hubs: