Badger is a message authentication code (MAC) based on the idea of universal hashing and was developed by Boesgaard, Scavenius, Pedersen, Christensen, and Zenner. It is constructed by strengthening the ∆-universal hash family MMH using an ϵ-almost strongly universal (ASU) hash function family after the application of ENH (see below), where the value of ϵ is 1 / ( 2 32 − 5 ) {\displaystyle 1/(2^{32}-5)} . Since Badger is a MAC function based on the universal hash function approach, the conditions needed for the security of Badger are the same as those for other universal hash functions such as UMAC.
Introduction The Badger MAC processes a message of length up to 2 64 − 1 {\displaystyle 2^{64}-1} bits and returns an authentication tag of length u ⋅ 32 {\displaystyle u\cdot 32} bits, where 1 ≤ u ≤ 5 {\displaystyle 1\leq u\leq 5} . According to the security needs, user can choose the value of u {\displaystyle u} , that is the number of parallel hash trees 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 2 64 {\displaystyle 2^{64}} . The key setup has to be run only once per key in order to run the Badger algorithm under a given key, since 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 in the following. Theorem 2 Let H △ {\displaystyle H^{\triangle }} be an ϵ-AΔU hash family from a set A to a set B. Consider a message ( m , m b ) ∈ A × B {\displaystyle (m,m_{b})\in A\times B} . Then the family H consisting of the functions h ( m , m b ) = H △ ( m ) + m b {\displaystyle h(m,m_{b})=H^{\triangle }(m)+m_{b}} is ϵ-AU. If m ≠ m ′ {\displaystyle m\neq m'} , then the probability that
h ( m , m b ) = h ( m ′ , m b ′ ) {\displaystyle h(m,m_{b})=h(m',m'_{b})} is at most ϵ, since H △ {\displaystyle H^{\triangle }} is an ϵ-A∆U family. If m = m ′ {\displaystyle m=m'} but m b ≠ m b ′ {\displaystyle m_{b}\neq m_{b}'} , 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):
N H K ( M ) = ∑ i = 1 ℓ 2 ( k ( 2 i − 1 ) + w m ( 2 i − 1 ) ) × ( k 2 i + w m 2 i ) mod 2 2 w {\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}}
… excerpt ends here. Continue reading the full article.
