Blue Midnight Wish

BMW (англ. BMW — Blue Midnight Wish) — криптографическая хеш-функция (хф) с выходом в n бит, где n=224,256, 384 или 512. Хеш-функции предназначены для создания «отпечатков» или «дайджестов» сообщений произвольной битовой длины. Применяются в различных приложениях или компонентах, связанных с защитой информации.

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

7 ноября 2008 года Национальный Институт стандартов и технологий США (англ. NIST — National Institute of Standards and Technology) открыл конкурс на новую хеш-функцию SHA-3. SHA-3 должен поддерживать размер выходного блока 224, 256, 384 и 512 битов. 160-битные блоки предусмотрены не были из-за возможности нахождения коллизий атаками грубой силы (перебора вариантов). Сохранились те же требования, что и к предыдущим хеш-функциям:

1. максимальный размер входного значения,
2. коллизионная стойкость,
3. стойкость к нахождению прообраза и второго прообраза
4. потоковый режим вычисления «за один проход».

К функциям были выдвинуты следующие стандартные параметры стойкости:

• Стойкость к нахождению коллизий — не менее n/2 бит.
• Стойкость к нахождению прообраза — n бит.
• Стойкость к нахождению второго прообраза — n-k битов для любого сообщения, короче 2k битов.
• Устойчивость к атакам на изменение длины сообщения.
• Устойчивость к новым типам атак, например, на основе мультиколлизий.

В первом раунде приняли участие 51 кандидат на SHA-3. 14 из них (включая BMW) прошли во второй тур.

Алгоритм BMW работает с сообщениями, разбивая их на блоки. Блок, в свою очередь, делятся на слова. Размеры блоков и слов зависят от конкретной реализации алгоритма. В таблице ниже перечислены основные свойства всех 4х вариаций алгоритма BMW.

1. Побитовая операция XOR
2. Операции побитового сложения + или вычитания — по модулю 32 или 64, в зависимости от модификации алгоритма
3. Операция сдвига влево (вправо) на r бит SHL^r (соответственно SHR^r)
4. Вращение (циклицеский сдвиг влево) ROTL^r

BLUE MIDNIGHT WISH следует общим принципам построения хеш функций, которые часто употребляются на сегодняшний день. А именно, это значит, что алгоритм разбивается на две части:

1. Ввод сообщения
2. Разбор введённого сообщения на m-битовые блоки
3. Инициализация начальных значений, которые будут использоваться при вычислении хф

1. Вычисление регистра сообщения из полученного сообщения
2. Использование этого регистра для вычисления последовательности значений H(i)
3. n наименее значимых бит (англ. LSB — Least Significant Bits) выбираются как цифровая подпись

В зависимости от модификации алгоритма, процесс обработки введённого сообщения выполняется следующим образом:

Пусть длина сообщения l. К сообщению приписывается 1, за которой следует последовательность k нулей, где k — наименьшее неотрицательное решение уравнения l+1+k=448 mod512. Далее приписывается 64-битный блок двоичного представления числа l

Пусть длина сообщения l. К сообщению приписывается 1, за которой следует последовательность k нулей, где k — наименьшее неотриц. решение уравнения l+1+k=960 mod1024. Далее приписывается 64-битный блок двоичного представления числа l. Примером может служить представление пос-ти «abc» (согласно ASCII)

${\displaystyle {\underset {\text{ASCII}}{\underbrace {01100001} _{\mathrm {a} }\,\underbrace {01100010} _{\mathrm {b} }\,\underbrace {01100011} _{\mathrm {c} }}}\,1\,\overbrace {00\ldots 00} ^{935}\,\overbrace {00\ldots \underbrace {011000} _{l=24}} ^{64}}$

Начальное значение H(0) в зависит от модификации алгоритма

В процессе вычислений используются три функции

• Первая функция F₀ : {0,1}^2m→{0,1}^m. Она принимает два аргумента M(i) и H(i−1) и производит биективное отображение M(i) XOR H(i−1). Здесь M(i) — i-й блок сообщения, H(i−1) — текущее значение двоичной трубы. Результат записывается в первую часть учетверенной трубы: Q(i, a)=F₀(M(i), H(i−1))=A2(A1(M(i) XOR H(i−1))).
• Вторая функция F₁ : {0,1}^2m→{0,1}^m. Она принимает в качестве аргументов блок сообщения M(i) (длины m бит) и первую часть учетверенной трубы Q(i, a). Результат записывается во вторую часть учетверенной трубы Q(i, b)=F₁(M(i),Q(i, a)).
• Третья функция F₃ : {0,1}^3m→{0,1}^m. Для неё используется термин сворачивающей (англ. {{{1}}} — folding ) с целью подчеркнуть свойства её свертки 3m-мерного пространства в m-мерное. Она принимает в качестве аргументов две величины: блок сообщения M(i) и текущее значение учетверенной трубы Q(i)=Q(i, a)||Q(i, b). Результат записывается как новое значение H(i): H(i) = F₂(M(i),Q(i))

 Псевдокод вычисления хеш-функции
 for (i=1;i<N;i++)
 {
   Q(i,a)=F0(M(i),H(i-1));
   Q(i,b)=F1(M(i),Q(i,a));
   Q(i)=Q(i,a)||Q(i,b);
   H(i)=F2(M(i),Q(i));
 }
 Hash=N_LeastSignificantBits(H(i));

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

Для определения функций f₀, f₁ и f₂ сначала вводятся дополнительные функции

BMW224/BMW256

BMW384/BMW512

${\displaystyle {\begin{aligned}s_{0}(x)&=SHR^{1}(x)\otimes SHL^{3}(x)\otimes ROTL^{4}(x)\otimes ROTL^{19}(x)\\s_{1}(x)&=SHR^{1}(x)\otimes SHL^{2}(x)\otimes ROTL^{8}(x)\otimes ROTL^{23}(x)\\s_{2}(x)&=SHR^{2}(x)\otimes SHL^{1}(x)\otimes ROTL^{12}(x)\otimes ROTL^{25}(x)\\s_{3}(x)&=SHR^{2}(x)\otimes SHL^{2}(x)\otimes ROTL^{15}(x)\otimes ROTL^{29}(x)\\s_{4}(x)&=SHR^{1}(x)\otimes x\\s_{5}(x)&=SHR^{2}(x)\otimes x\\r_{1}(x)&=ROTL^{3}(x)\\r_{2}(x)&=ROTL^{7}(x)\\r_{3}(x)&=ROTL^{13}(x)\\r_{4}(x)&=ROTL^{16}(x)\\r_{5}(x)&=ROTL^{19}(x)\\r_{6}(x)&=ROTL^{23}(x)\\r_{7}(x)&=ROTL^{27}(x)\end{aligned}}}$

${\displaystyle {\begin{aligned}s_{0}(x)&=SHR^{1}(x)\otimes SHL^{3}(x)\otimes ROTL^{4}(x)\otimes ROTL^{37}(x)\\s_{1}(x)&=SHR^{1}(x)\otimes SHL^{2}(x)\otimes ROTL^{13}(x)\otimes ROTL^{43}(x)\\s_{2}(x)&=SHR^{2}(x)\otimes SHL^{1}(x)\otimes ROTL^{19}(x)\otimes ROTL^{53}(x)\\s_{3}(x)&=SHR^{2}(x)\otimes SHL^{2}(x)\otimes ROTL^{28}(x)\otimes ROTL^{59}(x)\\s_{4}(x)&=SHR^{1}(x)\otimes x\\s_{5}(x)&=SHR^{2}(x)\otimes x\\r_{1}(x)&=ROTL^{5}(x)\\r_{2}(x)&=ROTL^{11}(x)\\r_{3}(x)&=ROTL^{27}(x)\\r_{4}(x)&=ROTL^{32}(x)\\r_{5}(x)&=ROTL^{37}(x)\\r_{6}(x)&=ROTL^{43}(x)\\r_{7}(x)&=ROTL^{53}(x)\end{aligned}}}$

${\displaystyle {\begin{aligned}{\begin{array}{rccccccc}{\text{expand}}_{1}(j)=&s_{1}(Q_{j-16}^{(i)})&+&s_{2}(Q_{j-15}^{(i)})&+&s_{3}(Q_{j-14}^{(i)})&+&s_{0}(Q_{j-13}^{(i)})\\+&s_{1}(Q_{j-12}^{(i)})&+&s_{2}(Q_{j-11}^{(i)})&+&s_{3}(Q_{j-10}^{(i)})&+&s_{0}(Q_{j-9}^{(i)})\\+&s_{1}(Q_{j-8}^{(i)})&+&s_{2}(Q_{j-7}^{(i)})&+&s_{3}(Q_{j-6}^{(i)})&+&s_{0}(Q_{j-5}^{(i)})\\+&s_{1}(Q_{j-4}^{(i)})&+&s_{2}(Q_{j-3}^{(i)})&+&s_{3}(Q_{j-2}^{(i)})&+&s_{0}(Q_{j-1}^{(i)})\\+&M_{(j-16){\mathtt {mod}}16}^{(i)}&+&M_{(j-13){\mathtt {mod}}16}^{(i)}&-&M_{(j-6){\mathtt {mod}}16}^{(i)}&+&K_{j}\end{array}}\end{aligned}}}$

${\displaystyle {\begin{aligned}{\begin{array}{rccccccc}{\text{expand}}_{2}(j)=&Q_{j-16}^{(i)}&+&r_{1}(Q_{j-15}^{(i)})&+&(Q_{j-14}^{(i)})&+&r_{2}(Q_{j-13}^{(i)})\\+&Q_{j-12}^{(i)}&+&r_{3}(Q_{j-11}^{(i)})&+&Q_{j-10}^{(i)}&+&r_{4}(Q_{j-9}^{(i)})\\+&Q_{j-8}^{(i)}&+&r_{5}(Q_{j-7}^{(i)})&+&Q_{j-6}^{(i)}&+&r_{6}(Q_{j-5}^{(i)})\\+&Q_{j-4}^{(i)}&+&r_{7}(Q_{j-3}^{(i)})&+&s_{5}(Q_{j-2}^{(i)}&+&r_{4}(Q_{j-1}^{(i)})\\+&M_{(j-16){\mathtt {mod}}16}^{(i)}&+&M_{(j-13){\mathtt {mod}}16}^{(i)}&-&M_{(j-6){\mathtt {mod}}16}^{(i)}&+&K_{j}\end{array}}\end{aligned}}}$

Здесь константа K_j=j × (0x05555555) (для 32 битовых версий) и K_j=j × (0x0555555555555555) (для 64 битовых версий). j=16,17,…,31

Функции expand₁ и expand₂ используются на этапе вычисления функции F₁, то есть на этапе расширения учетверенной трубы. Первая функция, expand₁, является вычислительно гораздо более сложной, чем вторая, но даёт значительно лучшие результаты.

Функция f₀:

Функция f₁:

Параметры ExpandRound1 и ExpandRound2 определяют, сколько итераций будет выполнено каждым из алгоритмов expand₁ и expand₂, описанных выше.

For (j=0;j<ExpandRound1;j++)

  Q(i,j)=expand1(j+16);

For (j=ExpandRound1;j<ExpandRound2+ExpandRound1;j++)

  Q(i,j)=expand2(j+16);

Функция f₂:

1. Подсчёт дополнительных переменных XL и XH

${\displaystyle {\begin{array}{rcccccccccc}XL&=&&&Q_{16}^{\left(i\right)}&\oplus &Q_{17}^{\left(i\right)}&\oplus &\cdots &\oplus &Q_{23}^{\left(i\right)}\\XH&=&XL&\oplus &Q_{24}^{\left(i\right)}&\oplus &Q_{25}^{\left(i\right)}&\oplus &\cdots &\oplus &Q_{31}^{\left(i\right)}\end{array}}}$

2. Вычисление нового значения H(i)

${\displaystyle {\begin{array}{l c r c r c r}H_{0}^{(i)}=&&{\big (}SHL^{5}(XH)\otimes &SHR^{5}(Q_{16}^{(i)})&\otimes M_{0}^{(i)}{\big )}&+&{\big (}XL\otimes Q_{24}^{(i)}\otimes Q_{0}^{(i)}\\H_{1}^{(i)}=&&{\big (}SHR^{7}(XH)\otimes &SHL^{8}(Q_{17}^{(i)})&\otimes M_{1}^{(i)}{\big )}&+&{\big (}XL\otimes Q_{25}^{(i)}\otimes Q_{1}^{(i)}\\H_{2}^{(i)}=&&{\big (}SHR^{5}(XH)\otimes &SHL^{5}(Q_{18}^{(i)})&\otimes M_{2}^{(i)}{\big )}&+&{\big (}XL\otimes Q_{26}^{(i)}\otimes Q_{2}^{(i)}\\H_{3}^{(i)}=&&{\big (}SHR^{1}(XH)\otimes &SHL^{5}(Q_{19}^{(i)})&\otimes M_{3}^{(i)}{\big )}&+&{\big (}XL\otimes Q_{27}^{(i)}\otimes Q_{3}^{(i)}\\H_{4}^{(i)}=&&{\big (}SHR^{3}(XH)\otimes &Q_{20}^{(i)}&\otimes M_{4}^{(i)}{\big )}&+&{\big (}XL\otimes Q_{28}^{(i)}\otimes Q_{4}^{(i)}\\H_{5}^{(i)}=&&{\big (}SHL^{6}(XH)\otimes &SHR^{6}(Q_{21}^{(i)})&\otimes M_{5}^{(i)}{\big )}&+&{\big (}XL\otimes Q_{29}^{(i)}\otimes Q_{5}^{(i)}\\H_{6}^{(i)}=&&{\big (}SHR^{4}(XH)\otimes &SHL^{6}(Q_{22}^{(i)})&\otimes M_{6}^{(i)}{\big )}&+&{\big (}XL\otimes Q_{30}^{(i)}\otimes Q_{6}^{(i)}\\H_{7}^{(i)}=&&{\big (}SHR^{11}(XH)\otimes &SHL^{2}(Q_{23}^{(i)})&\otimes M_{7}^{(i)}{\big )}&+&{\big (}XL\otimes Q_{31}^{(i)}\otimes Q_{7}^{(i)}\\H_{8}^{(i)}=ROTL^{9}(H_{4}^{(i)})&+&{\big (}XH\otimes &Q_{24}^{(i)}&\otimes M_{8}^{(i)}{\big )}&+&{\big (}SHR^{8}(XL)\otimes Q_{23}^{(i)}\otimes Q_{8}^{(i)}\\H_{9}^{(i)}=ROTL^{10}(H_{5}^{(i)})&+&{\big (}XH\otimes &Q_{25}^{(i)}&\otimes M_{9}^{(i)}{\big )}&+&{\big (}SHR^{6}(XL)\otimes Q_{16}^{(i)}\otimes Q_{9}^{(i)}\\H_{10}^{(i)}=ROTL^{11}(H_{6}^{(i)})&+&{\big (}XH\otimes &Q_{26}^{(i)}&\otimes M_{10}^{(i)}{\big )}&+&{\big (}SHR^{6}(XL)\otimes Q_{17}^{(i)}\otimes Q_{10}^{(i)}\\H_{11}^{(i)}=ROTL^{12}(H_{7}^{(i)})&+&{\big (}XH\otimes &Q_{27}^{(i)}&\otimes M_{11}^{(i)}{\big )}&+&{\big (}SHR^{4}(XL)\otimes Q_{18}^{(i)}\otimes Q_{11}^{(i)}\\H_{12}^{(i)}=ROTL^{13}(H_{0}^{(i)})&+&{\big (}XH\otimes &Q_{28}^{(i)}&\otimes M_{12}^{(i)}{\big )}&+&{\big (}SHR^{3}(XL)\otimes Q_{19}^{(i)}\otimes Q_{12}^{(i)}\\H_{13}^{(i)}=ROTL^{14}(H_{1}^{(i)})&+&{\big (}XH\otimes &Q_{29}^{(i)}&\otimes M_{13}^{(i)}{\big )}&+&{\big (}SHR^{4}(XL)\otimes Q_{20}^{(i)}\otimes Q_{13}^{(i)}\\H_{14}^{(i)}=ROTL^{15}(H_{2}^{(i)})&+&{\big (}XH\otimes &Q_{30}^{(i)}&\otimes M_{14}^{(i)}{\big )}&+&{\big (}SHR^{7}(XL)\otimes Q_{21}^{(i)}\otimes Q_{14}^{(i)}\\H_{15}^{(i)}=ROTL^{16}(H_{3}^{(i)})&+&{\big (}XH\otimes &Q_{31}^{(i)}&\otimes M_{15}^{(i)}{\big )}&+&{\big (}SHR^{2}(XL)\otimes Q_{22}^{(i)}\otimes Q_{15}^{(i)}\end{array}}}$

После того, как посчитано конечное значение H(N), необходимо выбрать n бит, соответствующих значению хеш-функции Hash=Hash(H(N))

• Hash=H(N,8)||H(N,9)||…||H(n,15) — для версий BMW256 и BMW512
• Hash=H(N,10)||H(N,11)||…||H(n,15) — для версии BMW384
• Hash=H(N,9)||H(N,10)||…||H(n,15) — для версии BMW224

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

1. Устойчивость к коллизиям примерно n/2 бит
2. Устойчивость к нахождению прообразов n бит
3. Повторное нахождение прообразов n-k бит для всех сообщений короче 2^n-k бит
4. Устойчивость к увеличению длины
5. Устойчивость к мультиколлизионным атакам

«BMW обладает очень хорошей производительностью и, по-видимому, подходит для большинства платформ. Имеет современные требования к памяти. Наиболее серьёзные криптоаналитические результаты против BMW — это на практике не важные псевдо-коллизионные атаки. Эти атаки ставят под вопрос безопасность функции.»

«BMW оказывается неустойчивой к псевдо-атакам — коллизиям и 2 м прообразам. Уровень безопасности является ниже ожидаемого: BMW-256 понижается до 65 бит, BMW-512 — до 128 бит. Затраты памяти, необходимые для совершения этих атак, являются несущественными»

• 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.
• Søren S. Thomsen. Pseudo-cryptanalysis of Blue Midnight Wish. — 2009. — С. 7. Архивная копия от 2 сентября 2009 на Wayback Machine