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

79ddfc96d66a06f73c96d16c13e67310.jpg

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

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

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

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

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

Шпаргалка

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

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

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

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

H

Двойная трубка (double pipe, dp). Изменяющееся значение, которое минимум в два раза шире, чем конечная цифровая подпись в n бит

Q

Счетверенная трубка (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

Сообщение

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

Для ясности

Если описывать алгоритм максимально ёмко, то выйдет что-то вроде
Сообщение 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 следует общему шаблону проектирования большинства хэш-функций.
Два основных этапа:

  1. Первичная обработка

    (а) заполнение сообщения (padding),

    (б) разбиение сообщения на m-битные блоки (parsing),

    (в) установка начальных значений, которые будут использоваться при вычислении хэша

  2. Вычисление хэша

    (а) создание расписания сообщений (message schedule) из дополненного сообщения,

    (б) использование этого расписания вместе с функциями, константами и операциями со словами для итеративного создания серии значений двойной трубки,

    (в) окончательное значение двойной трубки, сгенерированное итеративным процессом в (б) используется в качестве входных данных для функции финализации (определим ее далее);

    (г) n последних значащих бит функции финализации используются для расчета хэша сообщения.

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

версия алгоритма

размерpсообщения, бит

размерmблока, бит

размерwслова, бит

размерnхэша, бит

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.

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

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

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

\overbrace{\overbrace{01101000}^{

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

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

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

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

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

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

Перед началом вычисления хэш-функции для каждого из хэш-алгоритмов должно быть установлено начальное значение dp — H^{(0)}. Размер и значение слов в H^{(0)}зависят от размера дайджеста сообщенияn. 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 может использоваться для хэширования сообщенияMдлинойpбит, где 0<p<2^{64}. Алгоритм использует

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

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

  3. два временных 32-битных слова XLи XH.

Слова счетверённой трубки обозначены как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 битов, текущее значение dpH^{(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}).

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

Заключение

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

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

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

Источники

  1. 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.

  2. https://ieeexplore.ieee.org/document/5683052 — документация с IEEE.

  3. Soren S. Thomsen. Pseudo-cryptanalysis of Blue Midnight Wish. — 2009. — С. 7.

© Habrahabr.ru