Badger is a message authentication code (MAC) based on the idea of universal hashing and was developed[when?]
by Boesgaard, Scavenius, Pedersen, Christensen, and Zenner.
[1] 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
[2] 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.
The Badger MAC processes a message of length up to
bits and returns an authentication tag of length
According to the security needs, user can choose the value of
, that is the number of parallel hash trees in Badger.
On the other hand, a stronger family can be reduced to a weaker one, as long as a performance gain can be reached.
The proof for Theorem 2 was described in [1] The ENH-family is constructed based on the universal hash family NH (which is also used in UMAC): Where '
-AU function family ENH, which will be the basic building block of the badger MAC: where all arguments are 32-bits long and the output has 64-bits.
Badger is constructed using the strongly universality hash family and can be described as where an
-ASU function family F is used to guarantee the strong universality of the overall construction.
The maximum input size of the function family H* is
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
Pseudo-code of the finalization phase 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.
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 following table presents Badger's properties for various restricted message lengths.
denotes the amount of memory required to store the internal state including key material and the inner state of the Rabbit stream cipher .
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
The construction of MMH works in the finite field
for some positive integer k. The family MMH* of functions from
MMH* should satisfy the security requirements of a MAC, enabling say Ana and Bob to communicate in an authenticated way.
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
In this case the number of keys are increased by a factor of n and the output is also increased by n. Halevi and Krawczyk[4] construct a variant called
This idea is adopted from the suggestion by Carter and Wegman to use the primes
The value of k that describes the length of the message and key vectors has several effects: Below are the timing results for various implementations of MMH[4] in 1997, designed by Halevi and Krawczyk.