BMW Hash function - Алгоритм

Интернет магазин китайских планшетных компьютеров

Компьютеры - BMW Hash function - Алгоритм

01 мая 2011

Оглавление:
1. BMW Hash function
2. Алгоритм
3. Криптоанализ Blue Midnight Wish

Общие свойства

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

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

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

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

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

Побитовая операция XOR
Операции побитового сложения + или вычитания — по модулю 32 или 64, в зависимости от модификации алгоритма
Операция сдвига влево на r бит SHL
Вращение ROTL

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

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

Preprocessing

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

Hash computition

Вычисление регистра сообщения из полученного сообщения
Использование этого регистра для вычисления последовательности значений H
n наименее значимых бит выбираются как цифровая подпись

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

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

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»

$\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 в зависит от модификации алгоритма

Алгоритм	Начальное значение H
BMW224	0x000120308090A0B1011121318191A1B2021222328292A2B3031323338393A3B040506070C0D0E0F141516171C1D1 E1F242526272C2D2E2F243536373C3D3E3F
BMW256	0x4041424348494A4B5051525358595A5B6061626368696A6B7071727378797A7B444546474C4D4E4F545556575C5D 5E5F646566676C6D6E6F747576777C7D7E7F
BMW384	0x00010203040506071011121314151617202122232425262730313233243536374041424344454647505152535455 56576061626364656667707172737475767708090A0B0C0D0E0F18191A1B1C1D1E1F28292A2B2C2D2E2F38393A3B3C3D3E3F484 94A4B4C4D4E4F58595A5B5C5D5E5F68696A6B6C6D6E6F78797A7B7C7D7E7F
BMW512	0x80818283848586879091929394959697A0A1A2A3A4A5A6A7B0B1B2B3B4B5B6B7C0C1C2C3C4C5C6C7D0D1D2D3 D4D5D6D7E0E1E2E3E4E5E6E7F0F1F2F3F4F5F6F788898A8B8C8D8E8F98999A9B9C9D9E9FA8A9AAABACADAEAFB8B9BABBBCBD BEBFC8C9CACBCCCDCECFD8D9DADBDCDDDEDFE8E9EAEBECEDEEEFF8F9FAFBFCFDFEFF

Этап вычисления Хэш-Фукнции

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

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

 Псевдокод вычисления хэш-функции
 for
 {
   Q=F₀,H);
   Q=F₁,Q);
   Q=Q||Q;
   H=F₂,Q);
 }
 Hash=N_LeastSignificantBits);

Описание функций f₀, f₁ и f₂

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

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

BMW224/BMW256	BMW384/BMW512
$\begin{align} s_0 &= SHR^1 \otimes SHL^3 \otimes ROTL^{4} \otimes ROTL^{19}\\ s_1 &= SHR^1 \otimes SHL^2 \otimes ROTL^{8} \otimes ROTL^{23}\\ s_2 &= SHR^2 \otimes SHL^1 \otimes ROTL^{12} \otimes ROTL^{25}\\ s_3 &= SHR^2 \otimes SHL^2 \otimes ROTL^{15} \otimes ROTL^{29}\\ s_4 &= SHR^1 \otimes x\\ s_5 &= SHR^2 \otimes x\\ r_1 &= ROTL^{3}\\ r_2 &= ROTL^{7}\\ r_3 &= ROTL^{13}\\ r_4 &= ROTL^{16}\\ r_5 &= ROTL^{19}\\ r_6 &= ROTL^{23}\\ r_7 &= ROTL^{27} \end{align}$	$\begin{align} s_0 &= SHR^1 \otimes SHL^3 \otimes ROTL^{4} \otimes ROTL^{37}\\ s_1 &= SHR^1 \otimes SHL^2 \otimes ROTL^{13} \otimes ROTL^{43}\\ s_2 &= SHR^2 \otimes SHL^1 \otimes ROTL^{19} \otimes ROTL^{53}\\ s_3 &= SHR^2 \otimes SHL^2 \otimes ROTL^{28} \otimes ROTL^{59}\\ s_4 &= SHR^1 \otimes x\\ s_5 &= SHR^2 \otimes x\\ r_1 &= ROTL^{5}\\ r_2 &= ROTL^{11}\\ r_3 &= ROTL^{27}\\ r_4 &= ROTL^{32}\\ r_5 &= ROTL^{37}\\ r_6 &= ROTL^{43}\\ r_7 &= ROTL^{53} \end{align}$

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

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

Здесь константа K_j=j × и K_j=j ×. j=16,17,…,31

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

Функция f₀:

Blue mid f0.JPG

Функция f₁:

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

For

  Q=expand₁;

For

  Q=expand₂;

Функция f₂:

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

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

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

$\begin{array} { l c r c r c r} H^{}_0 = & & \big}_{16})& \otimes M^{}_0 \big)&+& \big}_{24} \otimes Q^{}_0\\ H^{}_1 = & & \big}_{17})& \otimes M^{}_1 \big)&+& \big}_{25} \otimes Q^{}_1\\ H^{}_2 = & & \big}_{18})& \otimes M^{}_2 \big)&+& \big}_{26} \otimes Q^{}_2\\ H^{}_3 = & & \big}_{19})& \otimes M^{}_3 \big)&+& \big}_{27} \otimes Q^{}_3\\ H^{}_4 = & & \big}_{20} & \otimes M^{}_4 \big)&+& \big}_{28} \otimes Q^{}_4\\ H^{}_5 = & & \big}_{21})& \otimes M^{}_5 \big)&+& \big}_{29} \otimes Q^{}_5\\ H^{}_6 = & & \big}_{22})& \otimes M^{}_6 \big)&+& \big}_{30} \otimes Q^{}_6\\ H^{}_7 = & & \big\otimes& SHL^2}_{23})& \otimes M^{}_7 \big)&+& \big}_{31} \otimes Q^{}_7\\ H^{}_8 =ROTL^{9}}_4)&+& \big}_{24} & \otimes M^{}_8 \big)&+& \big\otimes Q^{}_{23} \otimes Q^{}_8\\ H^{}_9 =ROTL^{10}}_5)&+& \big}_{25} & \otimes M^{}_9 \big)&+& \big\otimes Q^{}_{16} \otimes Q^{}_9\\ H^{}_{10}=ROTL^{11}}_6)&+& \big}_{26} & \otimes M^{}_{10}\big)&+& \big\otimes Q^{}_{17} \otimes Q^{}_{10}\\ H^{}_{11}=ROTL^{12}}_7)&+& \big}_{27} & \otimes M^{}_{11}\big)&+& \big\otimes Q^{}_{18} \otimes Q^{}_{11}\\ H^{}_{12}=ROTL^{13}}_0)&+& \big}_{28} & \otimes M^{}_{12}\big)&+& \big\otimes Q^{}_{19} \otimes Q^{}_{12}\\ H^{}_{13}=ROTL^{14}}_1)&+& \big}_{29} & \otimes M^{}_{13}\big)&+& \big\otimes Q^{}_{20} \otimes Q^{}_{13}\\ H^{}_{14}=ROTL^{15}}_2)&+& \big}_{30} & \otimes M^{}_{14}\big)&+& \big\otimes Q^{}_{21} \otimes Q^{}_{14}\\ H^{}_{15}=ROTL^{16}}_3)&+& \big}_{31} & \otimes M^{}_{15}\big)&+& \big\otimes Q^{}_{22} \otimes Q^{}_{15} \end{array}$