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

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

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

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

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

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

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))

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например, сообщение "habr", закодированное в 8-битном ASCII, имеет длину , поэтому сообщение дополняется битом «1», затем нулевыми битами и затем 64-битным двоичным представлением числа 32, чтобы стать 512-битным дополненным сообщением.

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

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

Для BMW256 дополненное сообщение разбирается на512-битных блоков, . Поскольку 512 бит входного блока могут быть выражены шестнадцатью 32-битными словами, первые 32 бита блока сообщенияобозначаются, следующие 32 бита -и так далее до.

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

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

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

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

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

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

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

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

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

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

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

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

2. Вторая функция принимает три аргумента: блокиз m битов, текущее значение dpи значение (первая часть qp), чтобы вычислить вторую часть cчетверённой трубы qp. Эта функция для каждогоделает следующее: для данной пары однозначно вычисляет , затем для данной пары однозначно вычисляет и для данной пары она однозначно вычисляет .

3. отображает 3m бит в m бит. Она принимает два аргумента: блок размером m бит и текущее значение размером 2m бит, чтобы создать новую двойную трубку из m бит.

Конечным результатом BMW256 является 256-битный хэш, который представляет собой 256 младших значащих битов из окончательного хэш-значения , то есть значений .

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)

Заключение

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

Эта статья проба пера и введение к циклу, в скором времени для большей наглядности завезу реализацию 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.