Русская Википедия:BMW Hash function

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

История

7 ноября 2008 года Национальный Институт стандартов и технологий США (Шаблон:Lang-en — 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.

Алгоритм Размер сообщения Размер блока Размер слова Цифровая подпись
BMW224 <264 512 32 224
BMW384 <264 512 32 384
BMW224 <264 1024 64 224
BMW512 <264 1024 64 512

Параметры, переменные и константы

Переменная Описание
H Двойная труба (Шаблон:Lang-en). Изменяющееся значение, которое минимум в два раза шире, чем конечная цифровая подпись в n бит.
Q Учетверённая труба.
H(i) i-е значение H. H(0) — начальное значение.
H(N) конечное значение H. Оно используется для определения цифровой подписи n бит.
Q(i) i-е значение учетверённой трубы.
H(i, j) je слово из H(i). Где Н(i) разбивается на заранее определённое количество блоков, называемых словами
H(i,0) Самое первое (левое) слово из Н(i)
Q(i, j) j-е слово iй учетверённой трубы Q(i)
Q(i, a) Первые 16 слов из Q(i), те Q(i, j) где j=0..15
Q(i, b) Последние 16 слов из Q(i), те Q(i, j) где j=16..31
l Длина сообщения М в битах
m Количество бит в блоке сообщения M(i)
M Входное сообщения битовой длины l
M(i) iй блок входного сообщения. Битовая длина m
M(i, j) jе слово M(i). M(i)=[M(i,0),M(i,1),..,M(i,15)]
XL,XH Два временных слова (длины 32 или 64 бита, в зависимости от модификации алгоритма), используемые при вычислении H(i)

Операции, используемые в алгоритме

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

Общие особенности структуры BMW

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

Preprocessing

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

Hash computition

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

Этап предварительных вычислений

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

BMW224 или BMW256

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

BMW384 или BMW512

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

<math>

\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}

</math>

Инициализация начальных значений

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

Алгоритм Начальное значение H(0)
BMW224 0x000120308090A0B1011121318191A1B2021222328292A2B3031323338393A3B040506070C0D0E0F141516171C1D1

E1F242526272C2D2E2F243536373C3D3E3F

BMW256 0x4041424348494A4B5051525358595A5B6061626368696A6B7071727378797A7B444546474C4D4E4F545556575C5D

5E5F646566676C6D6E6F747576777C7D7E7F

BMW384 0x00010203040506071011121314151617202122232425262730313233243536374041424344454647505152535455

56576061626364656667707172737475767708090A0B0C0D0E0F18191A1B1C1D1E1F28292A2B2C2D2E2F38393A3B3C3D3E3F484 94A4B4C4D4E4F58595A5B5C5D5E5F68696A6B6C6D6E6F78797A7B7C7D7E7F

BMW512 0x80818283848586879091929394959697A0A1A2A3A4A5A6A7B0B1B2B3B4B5B6B7C0C1C2C3C4C5C6C7D0D1D2D3

D4D5D6D7E0E1E2E3E4E5E6E7F0F1F2F3F4F5F6F788898A8B8C8D8E8F98999A9B9C9D9E9FA8A9AAABACADAEAFB8B9BABBBCBD BEBFC8C9CACBCCCDCECFD8D9DADBDCDDDEDFE8E9EAEBECEDEEEFF8F9FAFBFCFDFEFF


Этап вычисления хеш-функции

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

  • Первая функция F0 : {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)=F0(M(i), H(i−1))=A2(A1(M(i) XOR H(i−1))).
  • Вторая функция F1 : {0,1}2m→{0,1}m. Она принимает в качестве аргументов блок сообщения M(i) (длины m бит) и первую часть учетверенной трубы Q(i, a). Результат записывается во вторую часть учетверенной трубы Q(i, b)=F1(M(i),Q(i, a)).
  • Третья функция F3 : {0,1}3m→{0,1}m. Для неё используется термин сворачивающей (Шаблон:Lang-en — folding ) с целью подчеркнуть свойства её свертки 3m-мерного пространства в m-мерное. Она принимает в качестве аргументов две величины: блок сообщения M(i) и текущее значение учетверенной трубы Q(i)=Q(i, a)||Q(i, b). Результат записывается как новое значение H(i): H(i) = F2(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));

Описание функций f0, f1 и f2

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

Для определения функций f0, f1 и f2 сначала вводятся дополнительные функции Файл:BMW additional func.JPG

BMW224/BMW256 BMW384/BMW512
<math>\begin{align}
 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{align}</math> || <math>\begin{align}

 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{align}</math>

<math>\begin{align}

 \begin{array}{rccccccc}
   \text{expand}_1(j) =& s_1 (Q^{(i)}_{j-16}) &+& s_2 (Q^{(i)}_{j-15}) &+& s_3 (Q^{(i)}_{j-14}) &+& s_0 (Q^{(i)}_{j-13}) \\
   +& s_1 (Q^{(i)}_{j-12}) &+& s_2 (Q^{(i)}_{j-11}) &+& s_3 (Q^{(i)}_{j-10}) &+& s_0 (Q^{(i)}_{j-9}) \\
   +& s_1 (Q^{(i)}_{j-8}) &+& s_2 (Q^{(i)}_{j-7}) &+& s_3 (Q^{(i)}_{j-6}) &+& s_0 (Q^{(i)}_{j-5}) \\
   +& s_1 (Q^{(i)}_{j-4}) &+& s_2 (Q^{(i)}_{j-3}) &+& s_3 (Q^{(i)}_{j-2}) &+& s_0 (Q^{(i)}_{j-1}) \\
   +& M^{(i)}_{(j-16)\mathtt{mod} 16} &+& M^{(i)}_{(j-13)\mathtt{mod} 16} &-& M^{(i)}_{(j-6)\mathtt{mod} 16} &+& K_j
 \end{array}

\end{align}</math>

<math>\begin{align}

 \begin{array}{rccccccc}
   \text{expand}_2(j) =& Q^{(i)}_{j-16} &+& r_1 (Q^{(i)}_{j-15}) &+& (Q^{(i)}_{j-14}) &+& r_2 (Q^{(i)}_{j-13}) \\
   +& Q^{(i)}_{j-12} &+& r_3 (Q^{(i)}_{j-11}) &+&    Q^{(i)}_{j-10}&+& r_4 (Q^{(i)}_{j-9}) \\
   +& Q^{(i)}_{j-8}  &+& r_5 (Q^{(i)}_{j-7})  &+&    Q^{(i)}_{j-6} &+& r_6 (Q^{(i)}_{j-5}) \\
   +& Q^{(i)}_{j-4}  &+& r_7 (Q^{(i)}_{j-3})  &+&s_5(Q^{(i)}_{j-2} &+& r_4 (Q^{(i)}_{j-1}) \\
   +& M^{(i)}_{(j-16)\mathtt{mod} 16} &+& M^{(i)}_{(j-13)\mathtt{mod} 16} &-& M^{(i)}_{(j-6)\mathtt{mod} 16} &+& K_j
 \end{array}

\end{align}</math>


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

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

Функция f0:

Файл:Blue mid f0.JPG

Функция f1:

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

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

Функция f2:

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

<math>\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}</math>


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

<math> \begin{array} { l c r c r c r} H^{(i)}_0 = & & \big( SHL^5 (XH)\otimes& SHR^5(Q^{(i)}_{16})& \otimes M^{(i)}_0 \big)&+& \big( XL \otimes Q^{(i)}_{24} \otimes Q^{(i)}_0\\ H^{(i)}_1 = & & \big( SHR^7 (XH)\otimes& SHL^8(Q^{(i)}_{17})& \otimes M^{(i)}_1 \big)&+& \big( XL \otimes Q^{(i)}_{25} \otimes Q^{(i)}_1\\ H^{(i)}_2 = & & \big( SHR^5 (XH)\otimes& SHL^5(Q^{(i)}_{18})& \otimes M^{(i)}_2 \big)&+& \big( XL \otimes Q^{(i)}_{26} \otimes Q^{(i)}_2\\ H^{(i)}_3 = & & \big( SHR^1 (XH)\otimes& SHL^5(Q^{(i)}_{19})& \otimes M^{(i)}_3 \big)&+& \big( XL \otimes Q^{(i)}_{27} \otimes Q^{(i)}_3\\ H^{(i)}_4 = & & \big( SHR^3 (XH)\otimes& Q^{(i)}_{20} & \otimes M^{(i)}_4 \big)&+& \big( XL \otimes Q^{(i)}_{28} \otimes Q^{(i)}_4\\ H^{(i)}_5 = & & \big( SHL^6 (XH)\otimes& SHR^6(Q^{(i)}_{21})& \otimes M^{(i)}_5 \big)&+& \big( XL \otimes Q^{(i)}_{29} \otimes Q^{(i)}_5\\ H^{(i)}_6 = & & \big( SHR^4 (XH)\otimes& SHL^6(Q^{(i)}_{22})& \otimes M^{(i)}_6 \big)&+& \big( XL \otimes Q^{(i)}_{30} \otimes Q^{(i)}_6\\ H^{(i)}_7 = & & \big( SHR^{11}(XH)\otimes& SHL^2(Q^{(i)}_{23})& \otimes M^{(i)}_7 \big)&+& \big( XL \otimes Q^{(i)}_{31} \otimes Q^{(i)}_7\\ H^{(i)}_8 =ROTL^{9} (H^{(i)}_4)&+& \big( XH \otimes& Q^{(i)}_{24} & \otimes M^{(i)}_8 \big)&+& \big( SHR^8(XL)\otimes Q^{(i)}_{23} \otimes Q^{(i)}_8\\ H^{(i)}_9 =ROTL^{10}(H^{(i)}_5)&+& \big( XH \otimes& Q^{(i)}_{25} & \otimes M^{(i)}_9 \big)&+& \big( SHR^6(XL)\otimes Q^{(i)}_{16} \otimes Q^{(i)}_9\\ H^{(i)}_{10}=ROTL^{11}(H^{(i)}_6)&+& \big( XH \otimes& Q^{(i)}_{26} & \otimes M^{(i)}_{10}\big)&+& \big( SHR^6(XL)\otimes Q^{(i)}_{17} \otimes Q^{(i)}_{10}\\ H^{(i)}_{11}=ROTL^{12}(H^{(i)}_7)&+& \big( XH \otimes& Q^{(i)}_{27} & \otimes M^{(i)}_{11}\big)&+& \big( SHR^4(XL)\otimes Q^{(i)}_{18} \otimes Q^{(i)}_{11}\\ H^{(i)}_{12}=ROTL^{13}(H^{(i)}_0)&+& \big( XH \otimes& Q^{(i)}_{28} & \otimes M^{(i)}_{12}\big)&+& \big( SHR^3(XL)\otimes Q^{(i)}_{19} \otimes Q^{(i)}_{12}\\ H^{(i)}_{13}=ROTL^{14}(H^{(i)}_1)&+& \big( XH \otimes& Q^{(i)}_{29} & \otimes M^{(i)}_{13}\big)&+& \big( SHR^4(XL)\otimes Q^{(i)}_{20} \otimes Q^{(i)}_{13}\\ H^{(i)}_{14}=ROTL^{15}(H^{(i)}_2)&+& \big( XH \otimes& Q^{(i)}_{30} & \otimes M^{(i)}_{14}\big)&+& \big( SHR^7(XL)\otimes Q^{(i)}_{21} \otimes Q^{(i)}_{14}\\ H^{(i)}_{15}=ROTL^{16}(H^{(i)}_3)&+& \big( XH \otimes& Q^{(i)}_{31} & \otimes M^{(i)}_{15}\big)&+& \big( SHR^2(XL)\otimes Q^{(i)}_{22} \otimes Q^{(i)}_{15} \end{array} </math>

Конечное значение хеш-функции

После того, как посчитано конечное значение 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



Криптоанализ Blue Midnight Wish

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

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

Решение конкурсной комиссии NIST

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

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

Литература

Шаблон:Хеш-алгоритмы