MMH-Badger MAC

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 in the following.

Theorem 2

Let ${\displaystyle H^{\mathrm{△}}}$ 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^{\mathrm{△}}(m)+m_b}$ is ϵ-AU.

If ${\displaystyle m\ne m^{\prime }}$, then the probability that ${\displaystyle h(m,m_b)=h(m^{\prime },m_b^{\prime })}$ is at most ϵ, since ${\displaystyle H^{\mathrm{△}}}$ is an ϵ-A∆U family. If ${\displaystyle m=m^{\prime }}$ but ${\displaystyle m_b\ne m_b^{\prime }}$, then the probability is trivially 0. The proof for Theorem 2 was described in

The ENH-family is constructed based on the universal hash family NH (which is also used in UMAC):

${\displaystyle N{H}_K(M)=\sum _{i=1}^{\frac{\ell }{2}}(k_{(2i-1)}{+}_w{m}_{(2i-1)})\times (k_{2i}{+}_w{m}_{2i})\mathrm{mod}{2}^{2w}}$

Where '${\displaystyle {+}_w}$' means 'addition modulo ${\displaystyle 2^w}$', and ${\displaystyle m_i,k_i\in \{0,\dots ,2^w-1\}}$. It is a ${\displaystyle 2^{-w}}$-A∆U hash family.

Lemma 1

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

${\displaystyle N{H}_K(M)=(k_1{+}_w{m}_1)\times (k_2{+}_w{m}_2)\mathrm{mod}{2}^{2w}}$

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 the badger MAC:

${\displaystyle EN{H}_{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-bits long and the output has 64-bits.

Construction

Badger is constructed using the strongly universality hash family and can be described as

${\displaystyle \mathcal{H}=H^{\ast }\times F,}$

where an ${\displaystyle {ϵ}_{H^{\ast }}}$-AU universal function family H* is used to hash messages of any size onto a fixed size and an ${\displaystyle {ϵ}_F}$-ASU function family F is used to guarantee 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 bits, split into 64 bits each for the message and the hash. The collision probability for the H*-function ranges from ${\displaystyle 2^{-32}}$ to ${\displaystyle 2^{-26.14}}$. To construct the strongly universal function family F, the ∆-universal hash family MMH* is transformed into a strongly universal hash family by adding another key.

Two steps on Badger

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

Processing phase

In this phase, the data is hashed to a 64-bit string. A core function h : ${\displaystyle {\left\{0,1\right\}}^{64}\times {\left\{0,1\right\}}^{128}\to {\left\{0,1\right\}}^{64}}$ is used in this processing phase, that hashes a 128-bit string ${\displaystyle m_2\parallel m_1}$ to 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 ⁠${\displaystyle 2n}$⁠-bit string x, ⁠${\displaystyle L(x)}$⁠ means least significant n bits, and ⁠${\displaystyle U(x)}$⁠ means most significant n bits.

A message can be processed by using this function. Denote level_key[j][i] by ${\displaystyle k_j^i}$.

Pseudo-code of the processing phase is as follow.

<i id="mwlQ">L</i> = |<i id="mwlg">M</i>| <b id="mwlw">if</b> <i id="mwmA">L</i> = 0 <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt62" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"M^1 = \\cdots = M^u = 0"}}' id="mwmQ"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle M^{1}=\cdots =M^{u}=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>=</mo> <mo>⋯<!-- ⋯ --></mo> <mo>=</mo> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>u</mi> </mrow> </msup> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle M^{1}=\cdots =M^{u}=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/18bdf620ea658b5cdccfa97136a1cb2cfdcc42a4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:20.405ex; height:2.676ex;" alt="{\displaystyle M^{1}=\cdots =M^{u}=0}"/></span> Go to finalization <i id="mwmg">r</i> = <i id="mwmw">L</i> mod 64 <b id="mwnA">if</b> <i id="mwnQ">r</i> ≠ 0: <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt63" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"M = 0^{64-r} \\parallel M"}}' id="mwng"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle M=0^{64-r}\parallel M}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>M</mi> <mo>=</mo> <msup> <mn>0</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>64</mn> <mo>−<!-- − --></mo> <mi>r</mi> </mrow> </msup> <mo>∥<!-- ∥ --></mo> <mi>M</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle M=0^{64-r}\parallel M}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3fd15a7809f7a212cca921b6eb3b97dcd52130bb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.494ex; height:3.176ex;" alt="{\displaystyle M=0^{64-r}\parallel M}"/></span> <b id="mwnw">for</b> <i id="mwoA">i</i> = 1 <b id="mwoQ">to</b> <i id="mwog">u</i>: <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt64" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"M^i = M"}}' id="mwow"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle M^{i}=M}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> <mo>=</mo> <mi>M</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle M^{i}=M}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/efecaca46267306d17ed58be7a83b94709c85029" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.839ex; height:2.676ex;" alt="{\displaystyle M^{i}=M}"/></span> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt65" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"v' = \\max\\{ 1, \\lceil\\log_2 L\\rceil - 6 \\}"}}' id="mwpA"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle v'=\max\{1,\lceil \log _{2}L\rceil -6\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>v</mi> <mo>′</mo> </msup> <mo>=</mo> <mo movablelimits="true" form="prefix">max</mo> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mo fence="false" stretchy="false">⌈<!-- ⌈ --></mo> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡<!-- ⁡ --></mo> <mi>L</mi> <mo fence="false" stretchy="false">⌉<!-- ⌉ --></mo> <mo>−<!-- − --></mo> <mn>6</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v'=\max\{1,\lceil \log _{2}L\rceil -6\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b39a68cea6b1661497d504d0c9518fbc3b34d686" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.821ex; height:3.009ex;" alt="{\displaystyle v'=\max\{1,\lceil \log _{2}L\rceil -6\}}"/></span> <b id="mwpQ">for</b> <i id="mwpg">j</i> = 1 <b id="mwpw">to</b> <i id="mwqA">v</i><span typeof="mw:Entity" id="mwqQ">′</span>: divide <span class="nowrap" about="#mwt66" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"tmath","href":"./Template:Tmath"},"params":{"1":{"wt":"M^i"}},"i":0}}]}' id="mwqg"><span typeof="mw:Entity">⁠</span><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt67" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"M^i"}}'><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle M^{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle M^{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6ca8d01c874ab0936f926652def44bcbc5f43874" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.298ex; height:2.676ex;" alt="{\displaystyle M^{i}}"/></span><span typeof="mw:Entity">⁠</span></span> into 64-bit blocks, <span class="nowrap" about="#mwt68" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"tmath","href":"./Template:Tmath"},"params":{"1":{"wt":"M^i = m_t^i \\parallel \\cdots \\parallel m_1^i"}},"i":0}}]}' id="mwqw"><span typeof="mw:Entity">⁠</span><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt69" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"M^i = m_t^i \\parallel \\cdots \\parallel m_1^i"}}'><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle M^{i}=m_{t}^{i}\parallel \cdots \parallel m_{1}^{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> <mo>=</mo> <msubsup> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo>∥<!-- ∥ --></mo> <mo>⋯<!-- ⋯ --></mo> <mo>∥<!-- ∥ --></mo> <msubsup> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle M^{i}=m_{t}^{i}\parallel \cdots \parallel m_{1}^{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d31066d6cee530acd6861d11db51768426d297c4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:19.987ex; height:3.343ex;" alt="{\displaystyle M^{i}=m_{t}^{i}\parallel \cdots \parallel m_{1}^{i}}"/></span><span typeof="mw:Entity">⁠</span></span> <b id="mwrA">if</b> <i id="mwrQ">t</i> <b id="mwrg">is</b> even: <span class="nowrap" about="#mwt70" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"tmath","href":"./Template:Tmath"},"params":{"1":{"wt":"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)"}},"i":0}}]}' id="mwrw"><span typeof="mw:Entity">⁠</span><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt71" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"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)"}}'><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\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})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> <mo>=</mo> <mi>h</mi> <mo stretchy="false">(</mo> <msubsup> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo>,</mo> <msubsup> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo>,</mo> <msubsup> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−<!-- − --></mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo stretchy="false">)</mo> <mo>∥<!-- ∥ --></mo> <mo>⋯<!-- ⋯ --></mo> <mo>∥<!-- ∥ --></mo> <mi>h</mi> <mo stretchy="false">(</mo> <msubsup> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo>,</mo> <msubsup> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo>,</mo> <msubsup> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\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})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/874557223cf905d6840283f30b3b5f867b6f69c7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:42.722ex; height:3.676ex;" alt="{\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})}"/></span><span typeof="mw:Entity">⁠</span></span> <b id="mwsA">else</b> <span class="nowrap" about="#mwt72" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"tmath","href":"./Template:Tmath"},"params":{"1":{"wt":"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)"}},"i":0}}]}' id="mwsQ"><span typeof="mw:Entity">⁠</span><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt73" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"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)"}}'><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\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})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> <mo>=</mo> <msubsup> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo>∥<!-- ∥ --></mo> <mi>h</mi> <mo stretchy="false">(</mo> <msubsup> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo>,</mo> <msubsup> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−<!-- − --></mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo>,</mo> <msubsup> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−<!-- − --></mo> <mn>2</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo stretchy="false">)</mo> <mo>∥<!-- ∥ --></mo> <mo>⋯<!-- ⋯ --></mo> <mo>∥<!-- ∥ --></mo> <mi>h</mi> <mo stretchy="false">(</mo> <msubsup> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo>,</mo> <msubsup> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo>,</mo> <msubsup> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\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})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a4ebc831aeae0af11b0924b27b91220d4db1e29e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:50.142ex; height:3.676ex;" alt="{\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})}"/></span><span typeof="mw:Entity">⁠</span></span>

Finalize phase

In this phase, the 64-string resulting from the processing phase is transformed into the desired MAC tag. This finalization phase uses the Rabbit stream cipher and uses both key setup and IV setup by taking the finalization key final_key[j][i] as ${\displaystyle k_j^i}$.

Pseudo-code of the finalization phase

RabbitKeySetup(K) RabbitIVSetup(N) <b id="mwug">for</b> <i id="mwuw">i</i> = 1 <b id="mwvA">to</b> <i id="mwvQ">u</i>: <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt77" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"Q^i =0^7 \\parallel L \\parallel M^i"}}' id="mwvg"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle Q^{i}=0^{7}\parallel L\parallel M^{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> <mo>=</mo> <msup> <mn>0</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>7</mn> </mrow> </msup> <mo>∥<!-- ∥ --></mo> <mi>L</mi> <mo>∥<!-- ∥ --></mo> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q^{i}=0^{7}\parallel L\parallel M^{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2c06f0a3efbf4f4f670f622707f580089b2b0bde" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.74ex; height:3.176ex;" alt="{\displaystyle Q^{i}=0^{7}\parallel L\parallel M^{i}}"/></span> divide <span class="nowrap" about="#mwt78" typeof="mw:Transclusion" data-mw='{"parts":[{"template":{"target":{"wt":"tmath","href":"./Template:Tmath"},"params":{"1":{"wt":"Q^i"}},"i":0}}]}' id="mwvw"><span typeof="mw:Entity">⁠</span><span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt79" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"Q^i"}}'><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle Q^{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q^{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/abb70ea7b2ffe99d21a1dce964012c84c9b1eee0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.638ex; height:3.009ex;" alt="{\displaystyle Q^{i}}"/></span><span typeof="mw:Entity">⁠</span></span> into 27-bit blocks, <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt80" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"Q^i=q_5^i \\parallel \\cdots \\parallel q_1^i"}}' id="mwwA"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle Q^{i}=q_{5}^{i}\parallel \cdots \parallel q_{1}^{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> <mo>=</mo> <msubsup> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo>∥<!-- ∥ --></mo> <mo>⋯<!-- ⋯ --></mo> <mo>∥<!-- ∥ --></mo> <msubsup> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q^{i}=q_{5}^{i}\parallel \cdots \parallel q_{1}^{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4497bf0cfc27c3b18f8a8966c31489a49934e5d4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.548ex; height:3.343ex;" alt="{\displaystyle Q^{i}=q_{5}^{i}\parallel \cdots \parallel q_{1}^{i}}"/></span> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt81" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"S^i =(\\sum_{j=1}^5 (q_j^i K_j^i))+K_6^i \\bmod p"}}' id="mwwQ"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle S^{i}=(\sum _{j=1}^{5}(q_{j}^{i}K_{j}^{i}))+K_{6}^{i}{\bmod {p}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> <mo>=</mo> <mo stretchy="false">(</mo> <munderover> <mo>∑<!-- ∑ --></mo> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> </munderover> <mo stretchy="false">(</mo> <msubsup> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <msubsup> <mi>K</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>+</mo> <msubsup> <mi>K</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>6</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msubsup> <mrow class="MJX-TeXAtom-ORD"> <mo lspace="thickmathspace" rspace="thickmathspace">mod</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S^{i}=(\sum _{j=1}^{5}(q_{j}^{i}K_{j}^{i}))+K_{6}^{i}{\bmod {p}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e7525c402fba177992ee096e4243abb799d14098" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:29.952ex; height:7.676ex;" alt="{\displaystyle S^{i}=(\sum _{j=1}^{5}(q_{j}^{i}K_{j}^{i}))+K_{6}^{i}{\bmod {p}}}"/></span> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt82" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"S = S^u \\parallel \\cdots \\parallel S^1"}}' id="mwwg"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle S=S^{u}\parallel \cdots \parallel S^{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo>=</mo> <msup> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>u</mi> </mrow> </msup> <mo>∥<!-- ∥ --></mo> <mo>⋯<!-- ⋯ --></mo> <mo>∥<!-- ∥ --></mo> <msup> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S=S^{u}\parallel \cdots \parallel S^{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ab455b0bc883228539a8d0302993ca8253767d66" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.497ex; height:3.176ex;" alt="{\displaystyle S=S^{u}\parallel \cdots \parallel S^{1}}"/></span> <i id="mwww">S</i> = <i id="mwxA">S</i> ⨁ RabbitNextbit(<i id="mwxQ">u</i>∙32) <b id="mwxg">return</b> S

Notation

From the pseudocode above, k denotes the key in the Rabbit Key Setup(K) which initializes Rabbit with the 128-bit key k. M denotes the message to be hashed and |M| denotes the length of the message in bits. ⁠${\displaystyle q_i}$⁠ denotes a message M that is divided into i blocks. For the given ⁠${\displaystyle 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 report the performance of Badger measured on a 1.0 GHz Pentium III and on a 1.7 GHz Pentium 4 processor. The speed-optimized versions were programmed in assembly language inlined in C and compiled using the Intel C++ 7.1 compiler.

The following table presents Badger's 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 stream cipher . "Setup" denotes the key setup, and "Fin." denotes finalization with IV-setup.

MMH (Multilinear Modular Hashing)

The name MMH stands for Multilinear-Modular-Hashing. Applications in Multimedia are for example to verify the integrity of an on-line multimedia title. The performance of MMH is based on the improved support of integer scalar products in modern microprocessors.

MMH uses single precision scalar products as its most basic operation. It consists of a (modified) inner product between the message and a 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 multilinear functions on ${\displaystyle F_p^k}$ for some positive integer k. The family MMH* of functions from ${\displaystyle F_p^k}$ to ${\displaystyle F_p}$ is defined as follows.

${\displaystyle {\mathrm{M}\mathrm{M}\mathrm{H}}^{\ast }=\{g_x:F_p^k\to F_p|x\in F_p^k\}}$

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

${\displaystyle g_x(m)=mxmodp=\sum _{i=1}^n{m}_i{x}_{i}modp}$

In the case of MAC, m is a message and x is a key where ${\displaystyle m=(m_1,\dots ,m_k)}$ and ${\displaystyle x=(x_1,\dots ,x_k),x_i,m_i\in F_p}$.

MMH* should satisfy the security requirements of a MAC, enabling say Ana and Bob to communicate in an authenticated way. They have a secret key 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 m' and Ana's message m will differ in at least one bit (e.g. ${\displaystyle m_1\ne m_1^{\prime }}$).

Assume that Charles knows that the function is of the form ${\displaystyle g_x(m)}$ and he knows Ana's message m but he does not know the key x then the probability that Charles can change the message or send his own message can be explained by the following theorem.

Theorem 1:The family MMH* is ∆-universal.

Proof:

Take ${\displaystyle a\in F_p}$, and let ${\displaystyle m,m^{\prime }}$ be two different messages. Assume without loss of generality that ${\displaystyle m_1\ne m_1^{\prime }}$. Then for any choice of ${\displaystyle x_2,x_3,\dots ,x_s}$, there is

${\displaystyle \begin{array}{cc}{Pr}_{x_1}[g_x(m)-g_x(m^{\prime })\equiv a\mathrm{mod}p]& ={Pr}_{x_1}[(m_1{x}_1+m_2{x}_2+\cdots +m_k{x}_k)-(m_1^{\prime }{x}_1+m_2^{\prime }{x}_2+\cdots +m_k^{\prime }{x}_k)\equiv a\mathrm{mod}p]\\ & ={Pr}_{x_1}[(m_1-m_1^{\prime })x_1+(m_2-m_2^{\prime })x_2+\cdots +(m_k-m_k^{\prime })x_k]\equiv a\mathrm{mod}p]\\ & ={Pr}_{x_1}[(m_1-m_1^{\prime })x_1+\sum _{k=2}^s(m_k-m_k^{\prime })x_k\equiv a\mathrm{mod}p]\\ & ={Pr}_{x_1}[(m_1-m_1^{\prime })x_1\equiv a-\sum _{k=2}^s(m_k-m_k^{\prime })x_k\mathrm{mod}p]\\ & =\frac{1}{p}\end{array}}$

To explain the theorem above, take ${\displaystyle F_p}$ for ${\displaystyle p}$ prime represent the field as ${\displaystyle F_p=\underset{p}{\underbrace{\{0,1,\dots ,p-1\}}}}$. If one takes an element in ${\displaystyle F_p}$, let say ${\displaystyle 0\in F_p}$ then the probability that ${\displaystyle x_1=0}$ is

${\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,\dots ,x_k)\in F_p^k}(g_x(m)\equiv g_x(m^{\prime })\mathrm{mod}p)}$

But,

${\displaystyle \begin{array}{cc}{Pr}_{(x_1,\dots ,x_k)\in F_p^k}(g_x(m)\equiv g_x(m^{\prime })\mathrm{mod}p)& =\sum _{(x_2,\dots ,x_k)\in F_p^{k-1}}{Pr}_{(x_2^{{}^{\prime }}\cdots ,x_k^{{}^{\prime }})\in F_p^{k-1}}(x_2=x_2^{{}^{\prime }},\dots ,x_k=x_k^{{}^{\prime }})\cdot {Pr}_{x_1\in F_p}(g_x(m)\equiv g_x(m^{\prime })\mathrm{mod}p)\\ & =\sum _{(x_2,\dots ,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{array}}$

From the proof above, ${\displaystyle \frac{1}{p}}$ is the collision probability of the attacker in 1 round, so on average p verification queries will suffice to get one message accepted. To reduce the collision probability, it is necessary to choose large p or to concatenate n such MACs using n independent keys so that the collision probability] becomes ${\displaystyle \frac{1}{p^n}}$. In this case the number of keys are increased by a factor of n and the output is also increased by n.

MMH*32

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

${\displaystyle {\mathrm{M}\mathrm{M}\mathrm{H}}_{32}^{\ast }}$ is defined as follows:

${\displaystyle {\mathrm{M}\mathrm{M}\mathrm{H}}_{32}^{\ast }=\left\{g_x({\left\{0,1\right\}}^{32}{)}^k\right\}\to F_p,}$

where ${\displaystyle {\left\{0,1\right\}}^{32}}$ means ${\displaystyle \left\{0,1,\dots ,2^{32}-1\right\}}$ (i.e., binary representation)

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

${\displaystyle \begin{array}{cc}{g}_x(m)& \stackrel{\underset{\mathrm{d}\mathrm{e}\mathrm{f}}{}}{=}m\cdot xmod(2^{32}+15)\\ & =\sum _{i=1}^k{m}_i\cdot x_{i}mod(2^{32}+15)\end{array}}$

where

${\displaystyle x=(x_1,\dots ,x_k),m=(m,\dots ,m_k)}$

By theorem 1, the collision probability is about ${\displaystyle ϵ=2^{-32}}$, and the family of ${\displaystyle {\mathrm{M}\mathrm{M}\mathrm{H}}_{32}^{\ast }}$ 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 several effects:

• Since the costly modular reduction over k is multiply and add operations increasing k should decrease the speed.
• Since the key x consist of k 32-bit integers increasing k will results in a longer key.
• The probability of breaking the system is ${\displaystyle 1/p}$ and ${\displaystyle p\approx 2^k}$ so increasing k makes the system harder to break.

Performance

Below are the timing results for various implementations of MMH 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