BMW Hash function

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

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

ИсторияПравить

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

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

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

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

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

АлгоритмПравить

Общие свойстваПравить

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

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

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

Переменная	Описание
H	Двойная труба (англ. pipe). Изменяющееся значение, которое минимум в два раза шире, чем конечная цифровая подпись в 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)

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

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

Общие особенности структуры BMWПравить

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

PreprocessingПравить

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

Hash computitionПравить

Вычисление регистра сообщения из полученного сообщения
Использование этого регистра для вычисления последовательности значений H(i)
n наименее значимых бит (англ. LSB — 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)

$\text{[math]}$ $\text{[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}$

Инициализация начальных значенийПравить

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

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

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

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

Первая функция 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)=F₀(M(i),H(i-1));
   Q(i,b)=F₁(M(i),Q(i,a));
   Q(i)=Q(i,a)||Q(i,b);
   H(i)=F₂(M(i),Q(i));
 }
 Hash=N_LeastSignificantBits(H(i));

Описание функций f₀, f₁ и f₂Править

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

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

BMW224/BMW256	BMW384/BMW512
$\text{[math]}$ $\text{[math]}$ ${\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}}$	$\text{[math]}$ $\text{[math]}$ ${\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}}$

$\text{[math]}$ $\text{[math]}$ ${\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}}$

$\text{[math]}$ $\text{[math]}$ ${\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)=expand₁(j+16);

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

  Q(i,j)=expand₂(j+16);

Функция f₂:

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

$\text{[math]}$ $\text{[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}}$

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

$\text{[math]}$ $\text{[math]}$ ${\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

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

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

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

Решение конкурсной комиссии NISTПравить

«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