MMH-Badger MAC Information

This page is under construction

To guarantee the integrity of a message, one can use either public key digital signatures or use a Message Authentication Code (MAC). MAC is one of the alternative authentication techniques involving the use of a secret key to generate a small fixed-size block of data. The basic setting of MAC is as follows. Two parties A and B want to communicate by sending a message ${\displaystyle m}$. They share a secret key ${\displaystyle k}$. When A sends a message to B then A calculates the MAC as a function of the message and the key ${\displaystyle MAC=C_{k}}$(m). The message and the key are sent to B. Then B calculates the received message, using the same secret key ${\displaystyle k}$ to generate a new MAC. The received MAC is compared to the new MAC. When it is matched and only the receiver and the sender know the identity of the secret key, then the message is authentic.

Introduction

Carter and Wegman ^[1] introduced universal hashing to construct a Message Authentication Code (MAC). The universal hashing is used to build secure message authentication schemes where opponent’s ability to break messages is bounded by the collision (computer science) probability of the hash family. Actually, there are some works such as UMAC, CRC32, BOB, Poly1305-AES, and IPSX that deal with implementation of universal hashing as a tool for achieving fast and secure message authentication, but this page will discuss more about MMH ^[2] and Badger ^[3].

Universal hash function families ^{[2] [3]}

Universal hashing was first introduced by Carter and Wegman in 1979 and were studied further by Sarwate, Wegman and Carter and Stinson ^[4]. Universal hashing has many important applications in the oretical computer science. In 1981, Wegman and Carter pioneered the study of applying universal hash function in the construction of message authentication codes (MAC) when they published. The universal hashing can be defined as a mapping from a finite set A with size a to a finite set B with size b ^[5].

ϵ-almost ∆-universal (ϵ-A∆U)

Definition of n ϵ-almost ∆-universal (ϵ-A∆U)

Let ${\displaystyle (B,+)}$ be an Abelian group. A family H of hash functions that maps from a set A to a set B is said to be ϵ-almost ∆-universal (ϵ-A∆U) w.r.t. ${\displaystyle (B,+)}$, if for any distinct elements ${\displaystyle a,a^{'}\in A}$ and for all ${\displaystyle \delta \in B}$:

${\displaystyle Pr_{h\in H}[h(a)-h(a^{'})=\delta ]\leq \epsilon }$

H is ∆-universal (∆U) if ${\displaystyle \epsilon ={\frac {1}{\left\vert B\right\vert }}}$.

ϵ-almost universal family or (ϵ-AU) family

An ϵ-almost universal family or (ϵ-AU) family is one type of family in the universal hash function.

Definition of (ϵ-AU)family

Let ϵ be any positive real number. An ϵ-almost universal (ϵ-AU) family H of hash functions mapping from a set A to a set B is a family of functions from A to B, such that for any distinct elements ${\displaystyle a,a^{'}\in A}$:

${\displaystyle Pr_{h\in H}[h(a)=h(a^{'})]\leq \epsilon }$

H is universal (U) if ${\displaystyle \epsilon ={\frac {1}{\left\vert B\right\vert }}}$.

The definition above states that the probability of a collision is at most ϵ for any two distinct inputs. In the case ${\displaystyle \epsilon ={\frac {1}{\left\vert B\right\vert }}}$ is called universal, the smallest possible value for ${\displaystyle \epsilon ={\frac {a-b}{b(a-1)}}}$

ϵ-almost strongly-universal family or (ϵ-ASU)family

An ϵ-almost strongly universal family or (ϵ-ASU)family is one type of family in the universal hash function.

Definition of (ϵ-ASU)family

Let ϵ be any positive real number. An ϵ-almost strongly-universal (ϵ-ASU) family H of Hash functions maps from a set A to a set B is a family of functions from A to B, such that for any distinct elements ${\displaystyle a,a^{'}\in A}$ and all ${\displaystyle b,b^{'}\in B}$:

${\displaystyle Pr_{h\in H}[h(a)=b]={\frac {1}{\left\vert B\right\vert }}}$

and ${\displaystyle Pr_{h\in H}[h(a)=b,h(a')=b']={\frac {\epsilon }{\left\vert B\right\vert }}}$

H is strongly universal (SU) if ${\displaystyle \epsilon ={\frac {1}{\left\vert B\right\vert }}}$.

The first condition states that the probability that a given input a is mapped to a given output b equals ${\displaystyle {\frac {1}{\left\vert B\right\vert }}}$. The second condition implies that if a is mapped to b, then the conditional probability that ${\displaystyle a^{'}(a\neq a^{'})}$ is mapped to ${\displaystyle b^{'}(b\neq b^{'})}$ is upper bounded by ϵ.

MMH (Multilinear Modular Hashing)

The name MMH stands for Multilinear-Modular-Hashing. MMH is intended to hint to Multimedia applications, for example: to verify the integrity of an on-line multimedia title, and for the improved support of integer scalar- products in modern microprocessors which is a crucial factor for high performance of MMH.

MMH uses single precision scalar-products as its most basic operation. It is consist of a (modified) inner product between message and key modulo a prime ${\displaystyle p}$. The construction of MMH works in the finite field ${\displaystyle F_{p}}$ for some prime integer ${\displaystyle p}$.

MMH*

MMH* involves a construction of a family of hash functions consisting of all multilinear functions on ${\displaystyle F_{p}^{k}}$ for some positive integer ${\displaystyle k}$. The family MMH* of functions from ${\displaystyle F_{p}^{k}}$ to ${\displaystyle F_{p}}$ is defined as follows.

MMH* = {${\displaystyle g_{x}}$ : ${\displaystyle F_{p}^{k}}$ → ${\displaystyle F_{p}}$ | ${\displaystyle x}$ ϵ ${\displaystyle F_{p}^{k}}$}

where x, m are vectors, and the functions ${\displaystyle g_{x}}$ are defines as follows.

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

In the case of MAC, ${\displaystyle m}$ is a message and ${\displaystyle x}$ is a key where ${\displaystyle m=(m_{1},\cdots ,m_{k})}$ and ${\displaystyle x=(x_{1},\cdots ,x_{k}),x_{i},m_{i}\in \!F_{p}}$.

MMH* works with the same basic rules of MAC, so let say Ana and Bob want to communicate in an authenticated way. They have a secret key ${\displaystyle x}$. Say Charles listens to the conversation between Ana and Bob and wants to change the message into his own message to Bob which should pass as a message from Ana. So, his message ${\displaystyle m'}$ and Ana's message ${\displaystyle m}$ will differ in at least one bit (eg. ${\displaystyle m_{1}\neq m_{1}^{'}}$).

Assume that Charles knows the hash function ${\displaystyle g_{x}(m)}$ and he knows Ana's message ${\displaystyle m}$ then the probability that Charles can change the message or send his own message can be explained by the following theorem.

Theorem ^[2]:The family MMH* is ∆-universal.

Proof:

Take ${\displaystyle a\in F_{p}}$, and let ${\displaystyle m,m'}$ be two different messages. Assume without loss of generality that ${\displaystyle m_{1}\neq m_{1}^{'}}$. Then for any choice of ${\displaystyle x_{2},x_{3},...,x_{s}}$, there is

${\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}+...+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}}}$

To make a simple analog to explain the theorem above, take ${\displaystyle F_{p}}$ for ${\displaystyle p}$ prime ${\displaystyle F_{p}=\underbrace {{\big \{}0,1,\cdots ,p-1{\big \}}} _{p}}$ and if one takes an element in ${\displaystyle F_{p}}$, let say ${\displaystyle x_{1}=0}$ then

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

So, what one actually needs to compute is

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

But,

${\displaystyle {\begin{aligned}Pr_{(x_{1},\cdots ,x_{k})\in \!{F_{p}^{k}}}(g_{x}(m)\equiv g_{x}(m')\mod p)&=\sum _{(x_{2},\cdots ,x_{k})\in \!{F_{p}^{k-1}}}Pr_{(x_{2}^{'}\cdots ,x_{k}^{'})\in \!{F_{p}^{k-1}}}({x_{2}=x_{2}^{'}},\cdots ,{x_{k}=x_{k}^{'}})\cdot Pr_{x_{1}\in \!F_{p}}(g_{x}(m)\equiv g_{x}(m')\mod p)\\&=\sum _{(x_{2},\cdots ,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}}}$

From the proof above, ${\displaystyle {\frac {1}{p}}}$ is the collision probability of attacker to perform in ${\displaystyle p}$ verification queries. To reduce the collision probability, it is needed to hash the message into ${\displaystyle n}$ factors using ${\displaystyle n}$ independent keys. So the collision probability becomes ${\displaystyle {\frac {1}{p^{n}}}}$ for any integer value ${\displaystyle n}$. In this case the keys are increased with ${\displaystyle n}$ times the number of key factors of a message so as the computational work and output are increased by ${\displaystyle n}$ factors of a message.

${\displaystyle MMH_{32}^{*}}$

Halevi and Krawczyk ^[2] construct a variant called ${\displaystyle MMH_{32}^{*}}$. The construction works with 32-bit integers and with the prime integer ${\displaystyle p=2^{32}+15}$. Actually the prime numbers can be chosen from any prime which satisfies ${\displaystyle 2^{32}<p<2^{32}+2^{16}}$. This idea is adopted from a suggestion by Carter and Wegman to use the primes ${\displaystyle 2^{16}+1}$ or ${\displaystyle 2^{31}-1}$.

${\displaystyle MMH_{32}^{*}}$ is defined as follows.

${\displaystyle MMH_{32}^{*}={\big \{}g_{x}({\big \{}0,1{\big \}}^{32})^{k}{\big \}}\to F_{p}\in ({\big \{}0,1{\big \}}^{32})^{k}}$

Where ${\displaystyle {\big \{}0,1{\big \}}^{32}}$ means ${\displaystyle {\big \{}0,1,...,2^{32}-1{\big \}}}$ (i.e., binary representation)

The functions ${\displaystyle g_{x}}$ are defined as follows.

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

where

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

Refering to the theorem.1, the collision probability is ϵ = ${\displaystyle 2^{-32}}$, and the family of ${\displaystyle MMH_{32}^{*}}$ can be defined as ϵ-almost ∆ Universal with ϵ = ${\displaystyle 2^{-32}}$.

The value of k

The value of k that describes the length of the message and key vectors has two effects on the implementation namely:

• Since the costly modular reduction over k is multiply and add operations, then increasing k should decrease the speed.
• Since the key x consist of k 32-bit integers then increasing k will results in a longer key.

Performance

Below are the timing results for various implementations of MMH ^[2] in 1997, designed by Halevi and Krawczyk.

• A 150 Mhz PowerPC 604 RISC machine running AIX

• A 150 MHz Pentium-Pro machine running Windows NT

• A 200 MHz Pentium-Pro machine running Linux

Badger

Badger is a Message Authentication Code (MAC) based on the universal hashing, developed by Boesgaard, Christensen, and Zenner ^[3]. It is constructed by strengthening the ∆-universal hash family MMH using an ϵ-almost strongly universal (ASU) hash function family after the application of ENH, where the value of ϵ is ${\displaystyle (2^{32}-5)}$ ^[6]. Since Badger is one of the MAC functions based on the universal hash function approach, the conditions needed for the security of Badger is the same with those in the universal hash function such as UMAC.

The Badger MAC processes a message of length up to ${\displaystyle 2^{64}-1}$ bits into an authentication tag of length ${\displaystyle u\cdot 32}$ bits, where ${\displaystyle 1\leq u\leq 5}$. According to the security needs, user can choose the values of ${\displaystyle u}$, that is the number of parallel hash tree in Badger. One can choose larger values of u, but those values do not influence further the security of MAC. The algorithm uses a 128-bit key and the limited message length to be processed under this key is ${\displaystyle 2^{64}}$ ^[7].

The key setup has to be run just once in order to run the Badger algorithm under a given key, so that the resulting internal state of the MAC can be saved to be used with any other message that will be processed later.

ENH

Hash families can be combined in order to obtain new hash families. For the ϵ-AU, ϵ-A∆U, and ϵ-ASU families, the latter are contained in the former. For instance, an A∆U family is also an AU family, an ASU is also an A∆U family, and so forth. On the other hand, a stronger family can be reduced to a weaker one, as long as a performance gain can be reached. A method to reduce ∆-universal hash function to universal hash functions will be described as follows.

Theorem.1 ^[3]

Let ${\displaystyle H^{\triangle }}$ be an ϵ-AΔU hash family from a set A to a set B. Consider a message ${\displaystyle (m,m_{b})\in A\times B}$. Then the family H consisting of the functions ${\displaystyle h(m,m_{b})=H^{\triangle }(m)+m_{b}}$ is ϵ-AU.

If ${\displaystyle m\neq m^{'}}$, then this probability is at most ϵ, since ${\displaystyle H^{\triangle }}$ is an ϵ-A∆U family. If ${\displaystyle m\neq m^{'}}$ but ${\displaystyle m_{b}=m_{b}^{'}}$, then the probability is trivially 0. The proof for Theorem was described in [1]

ENH- family is a very fast universal hash family is the NH family used in UMAC:

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

Where ‘${\displaystyle +_{w}}$’ means ‘addition modulo ${\displaystyle 2^{w}}$’, and ${\displaystyle m_{i},k_{i}\in {\big \{}0,\cdots ,2^{w}-1{\big \}}}$. It is a ${\displaystyle 2^{-w}}$-A∆U hash family.

Lemma.1 ^[3]

The following version of NH is ${\displaystyle 2^{-w}}$-A∆U:

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

The proof for lemma.1 was described in[1]

Choosing w=32 and applying Theorem.1, One can obtain the ${\displaystyle 2^{-32}}$-AU function family ENH, which will be the basic building block of 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}}$

where all arguments are 32-bit and the output is 64-bit.

Construction

Badger which is constructed using the strongly universality hash family can be describe as

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

Where an ${\displaystyle \epsilon _{H^{*}}}$-AU universal function family H* to hash messages of all sizes onto a fixed size and ${\displaystyle \epsilon _{F}}$-ASU function family F to guarantee for the strong universality of the overall construction. NH and ENH are used to construct H*. The maximum input size of the function family H* is ${\displaystyle 2^{64}-1}$ and the output size is 128 bit, 64 bit each for the message and the hash. The collsion probability for the H*-function ranges from ${\displaystyle 2^{-32}}$ to ${\displaystyle 2^{-26.14}}$. Then to construct the strongly universal function family F, ∆-universal hash family, MMH*, is transformed into a strongly universal hash family by adding an additional key.

Two steps on Badger

There are two steps that have to be executed for every message: processing phase and finalize phase.

Processing phase ^[7]

In this phase, the data is hashed onto a 64-bit string. A core function ${\displaystyle h}$ : ${\displaystyle {\big \{}0,1{\big \}}^{64}\times {\big \{}0,1{\big \}}^{128}\to {\big \{}0,1{\big \}}^{64}}$ is used in this processing phase, that hashes a 128-bit string ${\displaystyle m_{2}\parallel m_{1}}$ under a 64-bit string ${\displaystyle h(k,m_{2},m_{1})}$ as follows:

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

for any n, ${\displaystyle +_{n}}$ means addition modulo ${\displaystyle 2^{n}}$. Given a 2n-bit string x, L(x) means least significant n bits, and U(x) means most significant n bits.

A message can be proceed by using this function and by denoting level_key [j][i] by ${\displaystyle k_{j}^{i}}$.

Pseudo-code of the processing phase is as follow.

L=|M|
if L=0
M^1=⋯=M^u=0 
Go to finalization
r=L mod 64
if r≠0:
M=0^(64-r)∥M
for i=1 to u:
M^i=M
v^'=max{1,⌈log_2 L⌉-6}
for j=1 to v^':
divide M^i into 64-bit blocks, M^i=m_t^i∥⋯∥m_1^i
if t is even:
M^i=h(k_j^i,m_t^i,m_(t-1)^i )∥⋯∥h(k_j^i,m_2^i,m_1^i )
else
M^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 )

Finalize phase ^[7]

In this phase, the 64-string hashed in the processing phase is transformed into the desired MAC tag. This finalization phase requires the Rabbit (cipher) stream cipher and uses both key setup and IV setup by denoting the finalization key final_key[j][i] by ${\displaystyle k_{j}^{i}}$.

Pseudo-code of the finalization phase

RabbitKeySetup(K)
RabbitIVSetup(N)
for i=1 to u:
Q^i=0^7∥L∥M^i
divide Q^i into 27-bit blocks, Q^i=q_5^i∥⋯∥q_1^i
S^i=(∑_(j=1)^5 (q_j^i K_j^i))+K_6^i mod p
S=S^u∥⋯∥S^1
S=S ⨁ RabbitNextbit(u∙32)
return S

Notation:

From the pseudocode above, k denotes key in Rabbit Key Setup(K) which initializes Rabbit with the 128-bit key K. M denotes as message to be hashed and |M| denotes the length of a message in bits. q_i denotes a message M that is divided into i blocks. For the given 2n-bit string x then L(x)and U(x) respectively denoted its least significant n bits and most significant n bits.

Performance

Boesgard, Christensen and Zenner recorded the performance of the Badger algorithm which measured on a 1.0 GHz Pentium III and on a 1.7 Ghz Pentium 4 processor ^[3]. The speed-optimized versions were programmed in assembly language inlined in C and compiled using the Intel C++ 7.1 compiler.

Badger properties for various restricted message lengths. “Memory req.”denotes the amount of memory required to store the internal state including key material and the inner state of the Rabbit (cipher) stream cipher . “Setup” denotes the key setup, and “Fin.” denotes finalization with IV-setup.

Max. Message Size	Forgery Bound	Memory Reg.	Setup Pentium III	Fin. Pentium III	Setup Pentium III	Fin. Pentium III
${\displaystyle 2^{11}}$ bytes (e.g.IPsec)	${\displaystyle 2^{-57.7}}$	400 bytes	1133 cycles	409 cycles	1774 cycles	776 cycles
${\displaystyle 2^{15}}$ bytes (e.g.TLS)	${\displaystyle 2^{-56.6}}$	528 bytes	1370 cycles	421 cycles	2100 cycles	778 cycles
${\displaystyle 2^{32}}$ bytes	${\displaystyle 2^{-54.2}}$	1072 bytes	2376 cycles	421 cycles	3488 cycles	778 cycles
${\displaystyle 2^{61}-1}$ bytes	${\displaystyle 2^{-52.2}}$	2000 bytes	4093 cycles	433 cycles	5854 cycles	800 cycles

see also

• UMAC
• VMAC
• Poly1305-AES

External link

• Cryptico re-thinking encryption

References