ММХ-Барсук MAC

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

Введение

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

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

ЭНХ

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

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

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

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

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

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}

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

Лемма 1 ^[1]

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

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

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

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 построен с использованием семейства хэшей строгой универсальности и может быть описан как

{\mathcal {H}}=H^{*}\times F,

^[1]

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

Два шага к Барсуку

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

Этап обработки

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

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

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

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

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

L = |M|
if L = 0
     $M^{1}=\cdots =M^{u}=0$ 
    Go to finalization
r = L mod 64
if r ≠ 0:
     $M=0^{64-r}\parallel M$ 
for i = 1 to u:
     $M^{i}=M$ 
     $v'=\max\{1,\lceil \log _{2}L\rceil -6\}$ 
for j = 1 to v′:
    divide ⁠ $M^{i}$ ⁠ into 64-bit blocks, ⁠ $M^{i}=m_{t}^{i}\parallel \cdots \parallel m_{1}^{i}$ ⁠
if t is even:
    ⁠ $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})$ ⁠
else
    ⁠ $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] как $k_{j}^{i}$ .

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

RabbitKeySetup(K)
RabbitIVSetup(N)
for i = 1 to u:
     $Q^{i}=0^{7}\parallel L\parallel M^{i}$ 
    divide ⁠ $Q^{i}$ ⁠ into 27-bit blocks,  $Q^{i}=q_{5}^{i}\parallel \cdots \parallel q_{1}^{i}$ 
     $S^{i}=(\sum _{j=1}^{5}(q_{j}^{i}K_{j}^{i}))+K_{6}^{i}{\bmod {p}}$ 
 $S=S^{u}\parallel \cdots \parallel S^{1}$ 
S = S ⨁ RabbitNextbit(u∙32)
return S

Обозначения

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

Производительность

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

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

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

MMH (многолинейное модульное хеширование)

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

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

ММХ*

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Но,

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

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

ММХ*32

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

\mathrm {MMH} _{32}^{*}

определяется следующим образом:

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

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

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

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

где

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

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

Значение к

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

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

Производительность

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

частотой 150 МГц под управлением AIX. Машина PowerPC 604 RISC с

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

Машина Pentium-Pro с тактовой частотой 150 МГц под управлением Windows NT.

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

Машина Pentium-Pro с тактовой частотой 200 МГц под управлением Linux.

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

См. также

Ссылки

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

[BS05-1] Jump up to: ^а ^б ^с ^д ^и ^ж Боесгор, Мартин ; Скавениус, Уве ; Педерсен, Томас ; Кристенсен, Томас ; Зеннер, Эрик (2005). «Badger — быстрый и доказуемо безопасный MAC» (PDF) .

[SV05-2] Удачи, Стефан ; Реймен, Винсент (2005). «Оценка Барсука» (PDF) .

[B-3] Jump up to: ^а ^б «Код аутентификации сообщения барсука, спецификация алгоритма» (PDF) . 2005.

[HK97-4] Jump up to: ^а ^б ^с Халеви, Шай ; Кравчик, Хьюго (1997). «MMH: Программная аутентификация сообщений со скоростью Гбит/секунда». MMH:Программная аутентификация сообщений со скоростью Гбит/с . Конспекты лекций по информатике. Том. 1267. стр. 172–189. дои : 10.1007/BFb0052345 . ISBN 978-3-540-63247-4 .

[1]

[2]

[3]

[4]