MMH-Badger MAC - Википедия - MMH-Badger MAC

Эта статья может требовать уборка встретиться с Википедией стандарты качества. Конкретная проблема: слишком много (конкретного) контента, разделить соответствующим образом Пожалуйста помоги улучшить эту статью если вы можете. (Март 2011 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Если ${ displaystyle m neq m '}$, то вероятность который${ displaystyle h (m, m_ {b}) = h (m ', m' _ {b})}$ не превосходит, так как ${ Displaystyle Н ^ { треугольник}}$ является ϵ-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 (к, m_ {2}, m_ {1})}$ следующее:

${ Displaystyle ч (к, м_ {2}, м_ {1}) = (L (m_ {1}) + _ {32} L (k)) cdot (U (m_ {1}) + _ {32 } U (k)) + _ {64} m_ {2} ,}$

для любого п, ${ displaystyle + _ {n}}$ означает сложение по модулю ${ Displaystyle 2 ^ {п}}$. Учитывая 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} (м)}$ = ${ displaystyle mx mod p}$ = ${ displaystyle sum _ {я = 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} (м)}$ и он знает сообщение Аны ${ 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 {align} { 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 {align}}}$

Чтобы объяснить приведенную выше теорему, возьмем ${ 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 {align} { 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 {выровнено}}}$

Из приведенного выше доказательства ${ 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}$

. Эта идея заимствована из предложения Картера и Вегмана использовать простые числа ${ 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 }} к F_ {p},}$

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

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

${ displaystyle { begin {align} 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 {align}}}$

куда

${ Displaystyle х = (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 приблизительно 2 ^ {k}}$ так увеличивается k затрудняет взлом системы.

Спектакль

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

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

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

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

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

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

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