MMH-Badger MAC

Badger — это код аутентификации сообщений (MAC), основанный на идее универсального хеширования , разработанный ^{[ когда? ]} Боэсгаардом, Скавениусом, Педерсеном, Кристенсеном и Зеннером. ^[1] Он построен путем усиления ∆-универсального хеш-семейства MMH с использованием ϵ-почти сильно универсального (ASU) семейства хеш-функций после применения ENH (см. ниже), где значение ϵ равно . ^[2] Поскольку Badger — это функция MAC, основанная на подходе универсальной хеш- функции, условия, необходимые для безопасности Badger, такие же, как и для других универсальных хеш-функций, таких как UMAC .${\displaystyle 1/(2^{32}-5)}$

MAC Badger обрабатывает сообщение длиной до бит и возвращает тег аутентификации длиной бит, где . В соответствии с требованиями безопасности пользователь может выбрать значение , то есть количество параллельных хэш-деревьев в Badger. Можно выбрать большие значения u , но эти значения не повлияют на безопасность MAC. Алгоритм использует 128-битный ключ, а ограниченная длина сообщения, обрабатываемого с помощью этого ключа, составляет . ^[3]${\displaystyle 2^{64}-1}$${\displaystyle u\cdot 32}$${\displaystyle 1\leq u\leq 5}$${\displaystyle u}$${\displaystyle 2^{64}}$

Настройка ключа должна быть выполнена только один раз для каждого ключа, чтобы запустить алгоритм Badger с данным ключом, поскольку полученное внутреннее состояние MAC можно сохранить для использования с любым другим сообщением, которое будет обработано позже.

Семейства хэшей можно объединять для получения новых семейств хэшей. Для семейств ϵ-AU, ϵ-A∆U и ϵ-ASU последние содержатся в первых. Например, семейство A∆U также является семейством AU, ASU также является семейством A∆U и т. д. С другой стороны, более сильное семейство можно свести к более слабому, если только можно достичь прироста производительности. Метод сведения ∆-универсальной хэш-функции к универсальным хэш- функциям будет описан далее.

Теорема 2 ^[1]

Пусть будет хеш-семейством ϵ-AΔU из множества A в множество B. Рассмотрим сообщение . Тогда семейство H, состоящее из функций, есть ϵ-AU.${\displaystyle H^{\треугольник}}$${\displaystyle (m,m_{b})\in A\times B}$${\displaystyle h(м,м_{б})=H^{\треугольник}(м)+м_{б}}$

Если , то вероятность того, что не больше ϵ, так как является семейством ϵ-A∆U. Если же , то вероятность тривиально равна 0. Доказательство теоремы 2 было описано в ^[1]${\displaystyle m\neq m'}$${\displaystyle h(м,м_{б})=h(м',м'_{б})}$${\displaystyle H^{\треугольник}}$${\displaystyle м=м'}$${\displaystyle m_{b}\neq m_{b}'}$

Семейство ENH построено на основе универсального семейства хэшей NH (которое также используется в UMAC ):

${\displaystyle NH_{K}(M)=\sum _{i=1}^{\frac {\ell}{2}}(k_{(2i-1)}+_{w}m_{(2i-1)})\times (k_{2i}+_{w}m_{2i})\mod 2^{2w}}$

Где ' ' означает 'сложение по модулю ', а . Это -A∆U хэш-семейство.${\displaystyle +_{w}}$${\displaystyle 2^{w}}$${\displaystyle m_{i},k_{i}\in {\big \{}0,\ldots ,2^{w}-1{\big \}}}$${\displaystyle 2^{-w}}$

Лемма 1 ^[1]

Следующая версия NH — -A∆U:${\displaystyle 2^{-w}}$

${\displaystyle NH_{K}(M)=(k_{1}+_{w}m_{1})\times (k_{2}+_{w}m_{2})\mod 2^{2w}}$

Выбрав w=32 и применив теорему 1, можно получить семейство функций -AU ENH, которое будет основным строительным блоком MAC барсука:${\displaystyle 2^{-32}}$

${\displaystyle ENH_{k_{1},k_{2}}(m_{1},m_{2},m_{3},m_{4})=(m_{1}+_{32}k_{1})(m_{2}+_{32}k_{2})+_{64}m_{3}+_{64}2^{32}m_{4}}$

где все аргументы имеют длину 32 бита, а выходные данные имеют длину 64 бита.

Badger создан с использованием семейства хэшей строгой универсальности и может быть описан как

${\displaystyle {\mathcal {H}}=H^{*}\times F,}$^[1]

где универсальное семейство функций -AU H* используется для хеширования сообщений любого размера в фиксированный размер, а семейство функций -ASU F используется для гарантии строгой универсальности общей конструкции. NH и ENH используются для построения H* . Максимальный размер входных данных семейства функций H* равен , а размер выходных данных составляет 128 бит, разделенных на 64 бита для сообщения и хеша. Вероятность коллизии для функции H* варьируется от до . Для построения строго универсального семейства функций F , ∆-универсальное хеш-семейство MMH* преобразуется в строго универсальное хеш-семейство путем добавления еще одного ключа.${\displaystyle \epsilon _{H^{*}}}$${\displaystyle \epsilon _{F}}$${\displaystyle 2^{64}-1}$${\displaystyle 2^{-32}}$${\displaystyle 2^{-26.14}}$

Для каждого сообщения необходимо выполнить два шага: фазу обработки и фазу завершения. ^[3]

На этом этапе данные хэшируются в 64-битную строку. Основная функция h  : используется на этом этапе обработки, которая хэширует 128-битную строку в 64-битную строку следующим образом:${\displaystyle \left\{0,1\right\}^{64}\times \left\{0,1\right\}^{128}\to \left\{0,1\right\}^{64}}$${\displaystyle m_{2}\parallel m_{1}}$${\displaystyle h(k,m_{2},m_{1})}$

${\displaystyle h(k,m_{2},m_{1})=(L(m_{1})+_{32}L(k))\cdot (U(m_{1})+_{32}U(k))+_{64}m_{2}\,}$

для любого n означает сложение по модулю . Для ⁠ ⁠ -битовой строки x , ⁠ ⁠ означает n младших бит, а ⁠ ⁠ означает n старших бит.${\displaystyle +_{n}}$${\displaystyle 2^{n}}$${\displaystyle 2n}$${\displaystyle L(x)}$${\displaystyle U(x)}$

Сообщение может быть обработано с помощью этой функции. Обозначим level_key[j][i]через .${\displaystyle k_{j}^{i}}$

Псевдокод этапа обработки выглядит следующим образом.

Л = | М | если  Л = 0 ${\displaystyle M^{1}=\cdots =M^{u}=0}$ Перейти к завершениюr = L mod 64, если  r ≠ 0: для i = 1 для u : для j = 1 для v ′:${\displaystyle M=0^{64-r}\parallel M}$  ${\displaystyle M^{i}=M}$ ${\displaystyle v'=\max\{1,\lceil \log _{2}L\rceil -6\}}$   разделить ⁠ ⁠${\displaystyle M^{i}}$ на 64-битные блоки, ⁠ ⁠ ${\displaystyle M^{i}=m_{t}^{i}\parallel \cdots \parallel m_{1}^{i}}$если  t  четное : ⁠ ⁠ ${\displaystyle M^{i}=h(k_{j}^{i},m_{t}^{i},m_{t-1}^{i})\parallel \cdots \parallel h(k_{j}^{i},m_{2}^{i},m_{1}^{i})}$иначе  ⁠ ⁠${\displaystyle M^{i}=m_{t}^{i}\parallel h(k_{j}^{i},m_{t-1}^{i},m_{t-2}^{i})\parallel \cdots \parallel h(k_{j}^{i},m_{2}^{i},m_{1}^{i})}$

На этом этапе 64-строчный результат обработки преобразуется в желаемый тег MAC. Этот этап финализации использует потоковый шифр Rabbit и использует как настройку ключа, так и настройку IV, принимая ключ финализации как .final_key[j][i]${\displaystyle k_{j}^{i}}$

Псевдокод этапа завершения

RabbitKeySetup(K)RabbitIVSetup(N)для  i = 1 до  u : разделить ⁠ ⁠ на 27-битные блоки, S = S ⨁ RabbitNextbit( u ∙32) вернуть S${\displaystyle Q^{i}=0^{7}\parallel L\parallel M^{i}}$${\displaystyle Q^{i}}$${\displaystyle Q^{i}=q_{5}^{i}\parallel \cdots \parallel q_{1}^{i}}$ ${\displaystyle S^{i}=(\sum _{j=1}^{5}(q_{j}^{i}K_{j}^{i}))+K_{6}^{i}{\bmod {p}}}$${\displaystyle S=S^{u}\parallel \cdots \parallel S^{1}}$

Из приведенного выше псевдокода k обозначает ключ в Rabbit Key Setup(K), который инициализирует Rabbit с 128-битным ключом k . M обозначает сообщение, которое должно быть хэшировано, а | M | обозначает длину сообщения в битах. ⁠ ⁠${\displaystyle q_{i}}$ обозначает сообщение M , которое разделено на i блоков. Для данной ⁠ ⁠${\displaystyle 2n}$ -битной строки x L ( x ) и U ( x ) соответственно обозначают ее n младших бит и n старших бит.

Боесгард, Кристенсен и Зеннер сообщают о производительности Badger, измеренной на процессоре Pentium III 1,0 ГГц и на процессоре Pentium 4 1,7 ГГц . ^[1] Версии с оптимизированной скоростью были запрограммированы на языке ассемблера, встроенном в C, и скомпилированы с использованием компилятора Intel C++ 7.1.

В следующей таблице представлены свойства Badger для различных ограниченных длин сообщений. «Memory req.» обозначает объем памяти, необходимый для хранения внутреннего состояния, включая ключевой материал и внутреннее состояние потокового шифра Rabbit . «Setup» обозначает настройку ключа, а «Fin.» обозначает завершение с помощью IV-setup.

Макс. размер сообщения	Подделка связана	Регистр памяти.	Установка Pentium III	Фин. Pentium III	Установка Pentium III	Фин. Pentium III
${\displaystyle 2^{11}}$байты (например, IPsec)	${\displaystyle 2^{-57.7}}$	400 байт	1133 цикла	409 циклов	1774 цикла	776 циклов
${\displaystyle 2^{15}}$байты (например, TLS)	${\displaystyle 2^{-56.6}}$	528 байт	1370 циклов	421 цикл	2100 циклов	778 циклов
${\displaystyle 2^{32}}$байты	${\displaystyle 2^{-54.2}}$	1072 байта	2376 циклов	421 цикл	3488 циклов	778 циклов
${\displaystyle 2^{61}-1}$байты	${\displaystyle 2^{-52.2}}$	2000 байт	4093 цикла	433 цикла	5854 циклов	800 циклов

Название MMH расшифровывается как Multilinear-Modular-Hashing (Многолинейное-модульное-хеширование). Например, приложения в мультимедиа проверяют целостность онлайн-мультимедийного заголовка. Производительность MMH основана на улучшенной поддержке целочисленных скалярных произведений в современных микропроцессорах.

MMH использует скалярные произведения одинарной точности в качестве своей самой базовой операции. Он состоит из (модифицированного) внутреннего произведения между сообщением и ключом по модулю простого числа . Конструкция MMH работает в конечном поле для некоторого простого целого числа .${\displaystyle p}$ ${\displaystyle F_{p}}$${\displaystyle p}$

MMH* включает в себя построение семейства хэш-функций, состоящих из полилинейных функций на для некоторого положительного целого числа k . Семейство MMH* функций от до определяется следующим образом.${\displaystyle F_{p}^{k}}$${\displaystyle F_{p}^{k}}$${\displaystyle F_{p}}$

${\displaystyle \mathrm {MMH} ^{*}=\{g_{x}:F_{p}^{k}\rightarrow F_{p}|x\in F_{p}^{k}\}}$

где x, m — векторы, а функции определяются следующим образом.${\displaystyle g_{x}}$

${\displaystyle g_{x}(m)=mx{\bmod {p}}=\sum _{i=1}^{n}m_{i}\,x_{i}{\bmod {p}}}$

В случае MAC m — это сообщение, а x — это ключ, где и .${\displaystyle m=(m_{1},\ldots ,m_{k})}$${\displaystyle x=(x_{1},\ldots ,x_{k}),x_{i},m_{i}\in \!F_{p}}$

MMH* должен удовлетворять требованиям безопасности MAC, позволяя, скажем, Ане и Бобу общаться аутентифицированным способом. У них есть секретный ключ x . Допустим, Чарльз слушает разговор Аны и Боба и хочет изменить сообщение на свое собственное сообщение Бобу, которое должно пройти как сообщение от Аны. Таким образом, его сообщение m' и сообщение Аны m будут отличаться по крайней мере одним битом (например, ).${\displaystyle m_{1}\neq m'_{1}}$

Предположим, что Чарльз знает, что функция имеет вид и он знает сообщение Аны m, но не знает ключ x, тогда вероятность того, что Чарльз сможет изменить сообщение или отправить свое собственное сообщение, можно объяснить с помощью следующей теоремы.${\displaystyle g_{x}(m)}$

Теорема 1 ^[4] : ​​Семейство MMH* является ∆-универсальным.

Доказательство:

Возьмем , и пусть будут два разных сообщения. Предположим без потери общности, что . Тогда для любого выбора , существует${\displaystyle a\in F_{p}}$${\displaystyle m,m'}$${\displaystyle m_{1}\neq m'_{1}}$${\displaystyle x_{2},x_{3},\ldots ,x_{s}}$

${\displaystyle {\begin{aligned}{\Pr }_{x_{1}}[g_{x}(m)-g_{x}(m')\equiv a\mod p]&={\Pr }_{x_{1}}[(m_{1}x_{1}+m_{2}x_{2}+\cdots +m_{k}x_{k})-(m'_{1}x_{1}+m'_{2}x_{2}+\cdots +m'_{k}x_{k})\equiv a\mod p]\\&={\Pr }_{x_{1}}[(m_{1}-m'_{1})x_{1}+(m_{2}-m'_{2})x_{2}+\cdots +(m_{k}-m'_{k})x_{k}]\equiv a\mod p]\\&={\Pr }_{x_{1}}[(m_{1}-m'_{1})x_{1}+\textstyle \sum _{k=2}^{s}(m_{k}-m'_{k})x_{k}\equiv a\mod p]\\&={\Pr }_{x_{1}}[(m_{1}-m'_{1})x_{1}\equiv a-\textstyle \sum _{k=2}^{s}(m_{k}-m'_{k})x_{k}\mod p]\\&={\frac {1}{p}}\end{aligned}}}$

Чтобы объяснить теорему выше, возьмем в качестве штриха поле, представим его как . Если взять элемент в , скажем, то вероятность того, что${\displaystyle F_{p}}$${\displaystyle p}$${\displaystyle F_{p}=\underbrace {{\big \{}0,1,\ldots ,p-1{\big \}}} _{p}}$${\displaystyle F_{p}}$${\displaystyle 0\in F_{p}}$${\displaystyle x_{1}=0}$

${\displaystyle {\Pr }_{x_{1}\in \!{F_{p}}}(x_{1}=0)={\frac {1}{p}}}$

Итак, на самом деле нужно вычислить

${\displaystyle {\Pr }_{(x_{1},\ldots ,x_{k})\in \!{F_{p}^{k}}}(g_{x}(m)\equiv g_{x}(m')\mod p)}$

Но,

${\displaystyle {\begin{aligned}{\Pr }_{(x_{1},\ldots ,x_{k})\in \!{F_{p}^{k}}}(g_{x}(m)\equiv g_{x}(m')\mod p)&=\sum _{(x_{2},\ldots ,x_{k})\in \!{F_{p}^{k-1}}}{\Pr }_{(x_{2}^{'}\cdots ,x_{k}^{'})\in \!{F_{p}^{k-1}}}({x_{2}=x_{2}^{'}},\ldots ,{x_{k}=x_{k}^{'}})\cdot {\Pr }_{x_{1}\in \!F_{p}}(g_{x}(m)\equiv g_{x}(m')\mod p)\\&=\sum _{(x_{2},\ldots ,x_{k})\in \!{F_{p}^{k-1}}}{\frac {1}{p^{k-1}}}\cdot {\frac {1}{p}}\\&=p^{k-1}\cdot {\frac {1}{p^{k-1}}}\cdot {\frac {1}{p}}\\&={\frac {1}{p}}\end{aligned}}}$

Из приведенного выше доказательства следует, что вероятность столкновения злоумышленника в 1 раунде, поэтому в среднем p запросов проверки будет достаточно, чтобы принять одно сообщение. Чтобы уменьшить вероятность столкновения, необходимо выбрать большое p или объединить n таких MAC с использованием n независимых ключей, так что вероятность столкновения] становится . В этом случае количество ключей увеличивается в n раз , а выход также увеличивается в n раз .${\displaystyle {\frac {1}{p}}}$ ${\displaystyle {\frac {1}{p^{n}}}}$

Халеви и Кравчик ^[4] строят вариант, называемый . Конструкция работает с 32-битными целыми числами и с простым целым числом . На самом деле простое число p может быть выбрано любым простым числом, удовлетворяющим . Эта идея заимствована из предложения Картера и Вегмана использовать простые числа или .${\displaystyle \mathrm {MMH} _{32}^{*}}$${\displaystyle p=2^{32}+15}$${\displaystyle 2^{32}<p<2^{32}+2^{16}}$${\displaystyle 2^{16}+1}$${\displaystyle 2^{31}-1}$

${\displaystyle \mathrm {MMH} _{32}^{*}}$определяется следующим образом:

${\displaystyle \mathrm {MMH} _{32}^{*}=\left\{g_{x}(\left\{0,1\right\}^{32})^{k}\right\}\to F_{p},}$

где означает (т.е. двоичное представление)${\displaystyle \left\{0,1\right\}^{32}}$${\displaystyle \left\{0,1,\ldots ,2^{32}-1\right\}}$

Функции определяются следующим образом.${\displaystyle g_{x}}$

${\displaystyle {\begin{aligned}g_{x}(m)&\ {\overset {\underset {\mathrm {def} }{}}{=}}\ m\cdot x{\bmod {(}}2^{32}+15)\\&=\textstyle \sum _{i=1}^{k}m_{i}\cdot x_{i}{\bmod {(}}2^{32}+15)\end{aligned}}}$

где

${\displaystyle x=(x_{1},\ldots ,x_{k}),\ m=(m,\ldots ,m_{k})}$

По теореме 1 вероятность столкновения составляет около , а семейство можно определить как ϵ -почти ∆ Universal с .${\displaystyle \epsilon =2^{-32}}$${\displaystyle \mathrm {MMH} _{32}^{*}}$${\displaystyle \epsilon =2^{-32}}$

Значение k , описывающее длину сообщения и ключевых векторов, имеет несколько эффектов:

• Поскольку дорогостоящее модульное сокращение по k представляет собой операции умножения и сложения, увеличение k должно приводить к снижению скорости.
• Поскольку ключ x состоит из k 32-битных целых чисел, увеличение k приведет к получению более длинного ключа.
• Вероятность взлома системы равна , поэтому увеличение k делает систему более трудной для взлома.${\displaystyle 1/p}$${\displaystyle p\approx 2^{k}}$

Ниже приведены результаты расчета времени для различных реализаций MMH ^[4] в 1997 году, разработанных Халеви и Кравчиком.

• Машина PowerPC 604 RISC 150 МГц под управлением AIX

• Машина Pentium-Pro 150 МГц под управлением Windows NT

• Машина Pentium-Pro 200 МГц под управлением Linux

• УМАК
• ВМАЦ
• Поли1305-AES