MMH-Барсук MAC - MMH-Badger MAC

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

Вступление

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

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

ENH

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

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

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

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

Семейство 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}}$

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

Лемма 1.^[1]

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

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

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

${\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]

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

Два шага на барсуке

Для каждого сообщения необходимо выполнить два этапа: этап обработки и этап завершения.

Фаза обработки^[3]На этом этапе данные хешируются в 64-битную строку. Основная функция ${\displaystyle h}$ : ${\displaystyle {\big \{}0,1{\big \}}^{64}\times {\big \{}0,1{\big \}}^{128}\to {\big \{}0,1{\big \}}^{64}}$ используется на этом этапе обработки, который хеширует 128-битную строку ${\displaystyle m_{2}\parallel m_{1}}$ в 64-битную строку ${\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}\,}$

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

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

Псевдокод этапа обработки следующий.

L = | M |, если L = 0M ^ 1 = ⋯ = M ^ u = 0 Перейти к финализации r = L mod 64, если r ≠ 0: M = 0 ^ (64-r) ∥Mfor i = 1 to u: M ^ i = Mv ^ '= max {1, ⌈log_2 L⌉-6} для j = 1 до v ^': разделите M ^ i на 64-битные блоки, M ^ i = m_t ^ i∥ ⋯ ∥m_1 ^ i, если t четное : M ^ i = h (k_j ^ i, m_t ^ i, m_ (t-1) ^ i) ∥ ⋯ ∥ h (k_j ^ i, m_2 ^ i, m_1 ^ i) elseM ^ i = m_t ^ i∥h (k_j ^ i, m_ (t-1) ^ i, m_ (t-2) ^ i) ∥ ⋯ ∥ h (k_j ^ i, m_2 ^ i, m_1 ^ i)

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

Псевдокод этапа финализации

RabbitKeySetup (K) RabbitIVSetup (N) для i = от 1 до u: Q ^ i = 0 ^ 7L∥M ^ разделить Q ^ i на 27-битные блоки, Q ^ i = q_5 ^ i∥ ⋯ ∥q_1 ^ iS ^ i = (∑_ (j = 1) ^ 5 (q_j ^ i K_j ^ i)) + K_6 ^ i mod pS = S ^ u∥ ⋯ ∥S ^ 1S = S ⨁ RabbitNextbit (u ∙ 32) return S

Обозначение:

Из псевдокода выше, k обозначает ключ в настройке Rabbit Key (K), который инициализирует Rabbit 128-битным ключом k. M обозначает сообщение, которое нужно хешировать, а |M| обозначает длину сообщения в битах. q_i обозначает сообщение M который разделен на я блоки. Для данного 2n-битовая строка Икс тогда L (Икс) и ты(Икс) соответственно обозначали его младшие n битов и старшие п биты.

Спектакль

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

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

Максимум. Размер сообщения	Подделка связана	Рег. Памяти	Настройка 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 (мультилинейное модульное хеширование)

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

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

MMH *

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

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

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

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

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

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

Предположим, что Чарльз знает, что функция имеет вид ${\displaystyle g_{x}(m)}$ и он знает сообщение Аны ${\displaystyle 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}}}$

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

MMH * 32

Галеви и Кравчик^[4] создать вариант под названием ${\displaystyle MMH_{32}^{*}}$. Конструкция работает с 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 MMH_{32}^{*}={\big \{}g_{x}({\big \{}0,1{\big \}}^{32})^{k}{\big \}}\to F_{p},}$

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

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

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

куда

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

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

Значение k

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

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

Спектакль

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

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

150 МГц PowerPC 604	Сообщение в памяти	Сообщение в кэше
64-битный	390 Мбит / сек	417 Мбит / сек
32-битный вывод	597 Мбит / сек	820 Мбит / сек

• Машина Pentium-Pro 150 МГц работает Windows NT

150 МГц PowerPC 604	Сообщение в памяти	Сообщение в кэше
64-битный	296 Мбит / сек	356 Мбит / сек
32-битный вывод	556 Мбит / сек	813 Мбит / сек

• Машина Pentium-Pro 200 МГц работает Linux

150 МГц PowerPC 604	Сообщение в памяти	Сообщение в кэше
64-битный	380 Мбит / сек	500 Мбит / сек
32-битный вывод	645 Мбит / сек	1080 Мбит / сек

Смотрите также

• UMAC
• VMAC
• Поли1305-AES

Рекомендации

1. Босгаард, Мартин; Скавениус, Уве; Педерсен, Томас; Кристенсен, Томас; Зеннер, Эрик (2005). "Badger - быстрый и надежно защищенный MAC" (PDF).
2. Удачи, Стефан; Раймен, Винсент (2005). «Оценка барсука» (PDF).
3. «Код аутентификации сообщения барсука, спецификация алгоритма» (PDF). 2005.
4. Халеви, Шай; Кравчик, Хьюго (1997). «MMH: Программная аутентификация сообщений со скоростью Гбит / с». MMH: программная проверка подлинности сообщений со скоростью Гбит / с. Конспект лекций по информатике. 1267. С. 172–189. Дои:10.1007 / BFb0052345. ISBN  978-3-540-63247-4.