|
|
| Line 1: |
Line 1: |
| {{cleanup|reason=too much (specific) content, split up appropriately|date=March 2011}}
| | I'm a 48 years old, married and work at the high school (Chinese Studies).<br>In my spare time I try to learn English. I've been there and look forward to returning anytime soon. I love to read, preferably on my kindle. I like to watch How I Met Your Mother and How I Met Your Mother as well as docus about anything technological. I like People watching.<br><br>my blog post - [http://tinyurl.com/ner2edt Louis Vuitton Bags online] |
| | |
| In [[cryptography]], to guarantee the integrity of a message, one can use either [[public key]] [[digital signatures]] or use a [[Message Authentication Code]] (MAC). A MAC is one of the possible [[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 <math> m </math>. They share a secret key <math> k </math>. When A sends a message to B then A calculates the MAC as a function of the message and the key <math> MAC = C_k(m) </math>. The message and the key are sent to B. Then B uses the same secret key <math> k </math> and calculates the MAC on the received message. The received MAC is compared to the new MAC. When it matches then the message is authentic because only the receiver and the sender know the secret key.
| |
| | |
| ==Introduction==
| |
| Carter and Wegman<ref name=WC81>{{ Cite web |title=New hash functions and their use in authentication and set equality |year=1981 | last1 = Carter | first1 = Larry |authorlink1=Larry Carter |last2 = Wegman | first2 = Mark N |authorlink2= Mark N Wegman |url=http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WJ0-4B55KFD-1M&_user=10&_coverDate=06%2F30%2F1981&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1618778289&_rerunOrigin=scholar.google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=782364a1012dd3c9f2ebd8aff12a2647&searchtype=a}}</ref> introduced [[universal hashing]] to construct a [[message authentication code]]s (MACs). [[Universal hashing]] is used to build secure message authentication schemes where the opponent’s ability to fake messages is bounded by the [[collision (computer science)|collision]] probability of the hash family. Proposals such as [[UMAC]], CRC32, BOB, [[Poly1305-AES]], and IPSX deal with implementation of [[universal hashing]] as a tool for achieving fast and secure message [[authentication]]. This page discusses MMH<ref name=HK97>{{ Cite web |title=MMH:Software Message Authentication in the Gbit/second rates |year=1997 |first1=Shai |last1=Halevi |authorlink1=Shai Halevi |first2=Hugo |last2=Krawczyk |authorlink2=Hugo Krawczyk |url=http://www.springerlink.com/content/l650p46118v0188g/}}</ref> and Badger.<ref name=BS05>{{Cite web |title= Badger- A fast and provably secure MAC |year=2005 |first1=Martin |last1=Boesgaard |authorlink1=Martin Boesgaard |first2=Ove |last2=Scavenius |authorlink2=Ove Scavenius |first3=Thomas |last3=Pedersen |author3-link=Thomas Pedersen |first4=Thomas |last4=Christensen |author4-link=Thomas Christensen |first5=Eric |last5=Zenner |author5-link=Eric Zenner |url=http://www.erikzenner.name/docs/2005_badger.pdf}}</ref>
| |
| | |
| == Universal hash function families<ref name=HK97/><ref name=BS05/>==
| |
| [[Universal hashing]] was first introduced by Carter and Wegman in 1979 and was studied further by Sarwate, Wegman and Carter and Stinson.<ref name=S03>{{ Cite web |title= Universal hashing and authentication code |year=2003 | first1=Douglas R. |last1 = Stinson |authorlink1=D.R Stinson |url=http://www.cacr.math.uwaterloo.ca/~dstinson/papers/hashingdcc.ps}}</ref> [[Universal hashing]] has many important applications in theoretical [[computer science]] and was used by Wegman and Carter in the construction of [[message authentication codes]] (MACs) in.<ref name=WC81 /> [[Universal hashing]] can be defined as a mapping from a finite set ''A'' with size ''a'' to a finite set ''B'' with size ''b''.<ref name=NP99>{{Cite web |title=Software Performance of Universal Hash Functions |year=1999 |first1=Wim |last1=Nevelsteen |authorlink1=Wim Nevelsteen |first2=Bart |last2=Preneel |authorlink2=Bart Preneel |url=https://www.cosic.esat.kuleuven.be/publications/article-73.pdf}}</ref>
| |
| | |
| The following sections define properties a universal hash function should satisfy.
| |
| | |
| ===ϵ-almost ∆-universal (ϵ-A∆U)===
| |
| Let <math>(B,+)</math> be an [[Abelian group]]. A family ''H'' of hash functions that maps from a set ''A'' to ''B'' is said to be ϵ-almost ∆-universal (ϵ-A∆U) w.r.t. <math>(B,+)</math>, if for any distinct elements <math>a, a' \in A </math> and for all <math>\delta \in B </math>:
| |
| | |
| : <math>{\Pr}_{h \in H}[h(a)-h(a')=\delta] \le \epsilon </math>
| |
| | |
| ''H'' is ∆-universal (∆U) if <math> \epsilon = \frac {1}{\left\vert B \right\vert}</math>.
| |
| | |
| ===ϵ-almost universal family or (ϵ-AU) family===
| |
| An ϵ-almost universal family or (ϵ-AU) family is one type of family in the [[universal hash function]]. This property is defined as follows:
| |
| | |
| Let ϵ be any positive real number. An ϵ-almost universal (ϵ-AU) family ''H'' of hash functions mapping from a set ''A'' to ''B'' is a family of functions from ''A'' to ''B'', such that for any distinct elements <math>a, a' \in A </math>:
| |
| | |
| : <math>{\Pr}_{h \in H}[h(a)=h(a')] \le \epsilon </math>
| |
| | |
| ''H'' is universal (U) if <math>\epsilon = \frac {1}{\left\vert B \right\vert}</math>.
| |
| | |
| The definition above states that the probability of a [[collision (computer science)|collision]] is at most ϵ for any two distinct inputs.
| |
| | |
| ===ϵ-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 defined as follows:
| |
| | |
| Let ϵ be any positive real number. An ϵ-almost strongly-universal (ϵ-ASU) family H of Hash functions maps from a set ''A'' to ''B'' is a family of functions from ''A'' to ''B'', such that for any distinct elements <math> a, a'\in A </math> and all <math> b, b'\in B</math>:
| |
| | |
| : <math>{\Pr}_{h \in H}[h(a)=b] = \frac {1}{\left\vert B \right\vert} </math>
| |
| | |
| and
| |
| : <math>{\Pr}_{h \in H}[h(a)=b, h(a')=b'] = \frac {\epsilon}{\left\vert B \right\vert} </math>
| |
| | |
| ''H'' is strongly universal (SU) if <math>\epsilon = \frac {1}{\left\vert B \right\vert}</math>.
| |
| | |
| The first condition states that the probability that a given input ''a'' is mapped to a given output ''b'' equals <math>\frac {1}{\left\vert B \right\vert}</math>. The second condition implies that if ''a'' is mapped to ''b'', then the conditional probability that <math>a'</math> with <math> a \ne a'</math> is mapped to <math>b'</math> is upper bounded by ϵ.
| |
| | |
| ==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 product]]s 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 [[modular arithmetic|modulo]] a [[prime]] <math>p</math>. The construction of MMH works in the [[finite field]] <math>F_p</math> for some prime integer <math>p</math>.
| |
| | |
| ===MMH*===
| |
| MMH* involves a construction of a family of [[hash functions]] consisting of [[multilinear]] functions on <math>F_p^k</math> for some positive integer <math>k</math>. The family MMH* of functions from <math>F_p^k</math> to <math>F_p</math> is defined as follows.
| |
| | |
| : <math> \mathrm{MMH}^* = \{ g_x : F_p^k \rightarrow F_p | x \in F_p^k \} \, </math>
| |
| | |
| where ''x, m'' are vectors, and the functions <math>g_x</math> are defined as follows.
| |
| :<math>\!g_x(m)</math> = <math> m x\mod p </math> = <math> \sum_{i=1}^n m_i\,x_i\mod p</math>
| |
| | |
| In the case of MAC, <math>m</math> is a message and <math> x </math> is a key where <math> m = (m_1,\ldots,m_k) </math> and <math>x = (x_1,\ldots,x_k), x_i, m_i \in \!F_p</math>.
| |
| | |
| 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 <math>x</math>. 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 <math>m'</math> and Ana's message <math>m</math> will differ in at least one bit (e.g. <math> m_1 \ne m'_1 </math>).
| |
| | |
| Assume that Charles knows that the function is of the form <math> g_x (m) </math> and he knows Ana's message <math> m </math> 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<ref name=HK97/>''':The family MMH* is ∆-universal.
| |
| | |
| Proof:
| |
| | |
| Take <math>a\in F_p</math>, and let <math> m , m'</math> be two different messages. Assume [[without loss of generality]] that <math> m_1 \ne m'_1 </math>. Then for any choice of <math> x_2,x_3,\ldots,x_s </math>, there is
| |
| : <math>
| |
| \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}
| |
| </math>
| |
| | |
| To explain the theorem above, take <math> F_p </math> for <math> p </math> prime represent the field as <math> F_p = \underbrace{\big\{ 0,1,\ldots,p-1 \big\}}_p </math>. If one takes an element in <math> F_p </math>, let say <math> 0\in F_p</math> then the probability that <math> x_1=0</math> is
| |
| | |
| :<math> {\Pr}_{x_1 \in \!{F_p}}(x_1=0)= \frac {1}{p} </math>
| |
| | |
| So, what one actually needs to compute is
| |
| :<math> {\Pr}_{(x_1,\ldots,x_k)\in \!{F_p^k}} (g_x(m)\equiv g_x(m')\mod p) </math>
| |
| | |
| But,
| |
| :<math>
| |
| \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{align}
| |
| </math>
| |
| | |
| From the proof above, <math>\frac{1}{p}</math> is the [[collision (computer science)|collision]] [[probability]] of the attacker in 1 round, so on average <math>p</math> verification queries will suffice to get one message accepted. To reduce the [[collision]] [[probability]], it is necessary to choose large ''p'' or to concatenate <math>n</math> such MACs using <math>n</math> independent keys so that the [[collision]] [[probability]] becomes <math>\frac{1}{p^n}</math>. In this case the number of keys are increased by a factor of <math>n</math> and the output is also increased by <math>n</math>.
| |
| | |
| ===<math>MMH_{32}^*</math>===
| |
| Halevi and Krawczyk<ref name=HK97/> construct a variant called <math>MMH^*_{32}</math>. The construction works with 32-bit [[integers]] and with the [[prime]] [[integer]] <math>p=2^{32}+15</math>. Actually the [[prime]] ''p'' can be chosen to be any prime which satisfies <math>2^{32}<p<2^{32}+2^{16}</math>. This idea is adopted from the suggestion by Carter and Wegman to use the primes <math>2^{16}+1</math> or <math>2^{31}-1</math>.
| |
| | |
| : <math>\mathrm{MMH}^*_{32}</math> is defined as follows:
| |
| | |
| : <math>MMH^*_{32}=\big\{g_x (\big\{0,1\big\}^{32} )^k \big\} \to F_p, </math>
| |
| | |
| where <math>\big\{0,1\big\}^{32}</math> means <math>\big\{0, 1, \ldots, 2^{32}-1\big\}</math> (i.e., binary representation)
| |
| | |
| The functions <math>g_x</math> are defined as follows.
| |
| | |
| : <math>
| |
| \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}
| |
| </math>
| |
| | |
| where
| |
| | |
| : <math> x= (x_1,\ldots,x_k )</math>, <math>m=(m,\ldots,m_k )</math>
| |
| | |
| By theorem 1, the [[collision]] [[probability]] is about ϵ = <math>2^{-32}</math>, and the family of <math>MMH^*_{32}</math> can be defined as ϵ-almost ∆ Universal with ϵ = <math>2^{-32}</math>.
| |
| | |
| ===The value of ''k''===
| |
| The value of ''k'' that describes the length of the message and key [[Tuple|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 <math>1/p</math> and <math>p\approx 2^k</math> so increasing ''k'' makes the system harder to break.
| |
| | |
| ===Performance===
| |
| Below are the timing results for various implementations of MMH<ref name=HK97/> in 1997, designed by Halevi and Krawczyk.
| |
| * A 150 MHz [[PowerPC]] 604 RISC machine running AIX
| |
| {| class="wikitable"
| |
| |-
| |
| ! 150 MHz [[PowerPC]] 604
| |
| ! Message in Memory
| |
| ! Message in Cache
| |
| |-
| |
| | 64-bit
| |
| | 390 Mbit/second
| |
| | 417 Mbit/second
| |
| |-
| |
| | 32-bit output
| |
| | 597 Mbit/second
| |
| | 820 Mbit/second
| |
| |}
| |
| | |
| * A 150 MHz Pentium-Pro machine running [[Windows NT]]
| |
| {| class="wikitable"
| |
| |-
| |
| ! 150 MHz PowerPC 604
| |
| ! Message in Memory
| |
| ! Message in Cache
| |
| |-
| |
| | 64-bit
| |
| | 296 Mbit/second
| |
| | 356 Mbit/second
| |
| |-
| |
| | 32-bit output
| |
| | 556 Mbit/second
| |
| | 813 Mbit/second
| |
| |}
| |
| | |
| * A 200 MHz Pentium-Pro machine running [[Linux]]
| |
| {| class="wikitable"
| |
| |-
| |
| ! 150 MHz PowerPC 604
| |
| ! Message in Memory
| |
| ! Message in Cache
| |
| |-
| |
| | 64-bit
| |
| | 380 Mbit/second
| |
| | 500 Mbit/second
| |
| |-
| |
| | 32-bit output
| |
| | 645 Mbit/second
| |
| | 1080 Mbit/second
| |
| |}
| |
| | |
| ==Badger==
| |
| Badger is a [[Message Authentication Code]] (MAC) based on the idea of [[universal hashing]] and was developed by Boesgaard, Christensen, and Zenner.<ref name=BS05/> 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 <math>1/(2^{32}-5)</math>.<ref name=SV05>{{Cite web |title=Evaluation of Badger |year=2005 |first1=Stefan |last1=Lucks |authorlink1=Stefan Luck |first2=Vincent |last2=Rijmen |authorlink2=Vincent Rijmen |url=http://www.cryptico.com/Files/Filer/Badger_Security_Report.pdf}}</ref> 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 <math>2^{64}-1</math> bits and returns an [[authentication]] [[Tag (metadata)|tag]] of length <math>u\cdot32</math> bits, where <math>1\le u \le 5 </math>. According to the [[security]] needs, user can choose the value of <math>u</math>, that is the number of parallel [[hash tree]]s 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 <math>2^{64}</math>.<ref name=B>{{Cite web |title=Badger Message Authentication Code,Algorithm Specification |year=2005 |url=http://www.cryptico.com/Files/Filer/WP_Badger_Specification.pdf}}</ref>
| |
| | |
| 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<ref name=BS05/>'''
| |
| | |
| Let <math>H^\triangle</math> be an ϵ-AΔU hash family from a set ''A'' to a set ''B''. Consider a message <math>(m, m_b) \in A \times B </math>. Then the family ''H'' consisting of the functions <math>h(m,m_b) = H^\triangle (m) + m_b </math> is ϵ-AU.
| |
| | |
| If <math> m \ne m'</math>, then the [[probability]] that
| |
| <math>h(m,m_b) =h(m',m'_b)</math> is at most ϵ,
| |
| since <math>H^\triangle</math> is an ϵ-A∆U family. If <math> m = m'</math> but <math> m_b\ne m_b'</math>, then the [[probability]] is trivially 0.
| |
| The proof for Theorem 2 was described in <ref name=BS05/>
| |
| | |
| The ENH-family is constructed based on the [[universal hash]] family NH (which is also used in [[UMAC]]):
| |
| | |
| : <math>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} </math>
| |
| | |
| Where ‘<math>+_w</math>’ means ‘addition modulo <math>2^w</math>’, and <math>m_i,k_i \in \big\{0,\ldots, 2^w-1\big\}</math>. It is a <math>2^{-w}</math>-A∆U hash family.
| |
| | |
| '''Lemma 1<ref name=BS05/>'''
| |
| | |
| The following version of NH is <math>2^{-w}</math>-A∆U:
| |
| | |
| : <math>NH_K (M)=(k_1 +_w m_1 )\times(k_2 +_w m_2 ) \mod 2^{2w}</math>
| |
| | |
| Choosing w=32 and applying Theorem 1, one can obtain the <math>2^{-32}</math>-AU function family ENH, which will be the basic building block of the badger MAC:
| |
| | |
| : <math>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</math>
| |
| | |
| 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
| |
| | |
| : <math>\mathcal{H}=H^* \times F,</math><ref name=BS05/>
| |
| | |
| where an <math>\epsilon_{H^*}</math>-AU universal function family ''H*'' is used to hash messages of any size onto a fixed size and an <math>\epsilon_{F}</math>-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 <math>2^{64}-1</math> 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 <math>2^{-32}</math> to <math>2^{-26.14}</math>. To construct the strongly universal function family ''F'', the ∆-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'''<ref name=B/>
| |
| In this phase, the data is hashed to a 64-bit string. A core function <math>h</math> : <math>\big\{0,1\big\}^{64}\times \big\{0,1\big\}^{128} \to \big\{0,1\big\}^{64}</math> is used in this processing phase, that hashes a 128-bit string <math> m_2 \parallel m_1</math> to a 64-bit string <math> h( k, m_2, m_1 )</math> as follows:
| |
|
| |
| : <math> h(k, m_2, m_1 )= (L(m_1 ) +_{32} L(k) )\cdot(U(m_1 ) +_{32} U(k) ) +_{64} m_2 \, </math>
| |
| | |
| for any ''n'', <math>+_n</math> means addition modulo <math>2^n</math>. 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 processed by using this function. Denote level_key [j][i] by <math>k_j^i</math>.
| |
| | |
| Pseudo-code of the processing phase is as follow.
| |
| | |
| <pre>
| |
| 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 )
| |
| </pre>
| |
| | |
| '''Finalize''' phase<ref name=B/>
| |
| In this phase, the 64-string resulting from the processing phase is transformed into the desired MAC tag. This finalization phase uses the [[Rabbit (cipher)|Rabbit]] [[stream cipher]] and uses both key setup and IV setup by taking the finalization key final_key[j][i] as <math>k_j^i</math>.
| |
| | |
| Pseudo-code of the finalization phase
| |
| | |
| <pre>
| |
| 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
| |
| </pre>
| |
| | |
| 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. 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 report the performance of Badger measured on a 1.0 GHz [[Pentium III]] and on a 1.7 GHz [[Pentium 4]] processor.<ref name=BS05/> 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 (cipher)|Rabbit]] [[stream cipher]] . “Setup” denotes the key setup, and “Fin.” denotes finalization with IV-setup.
| |
| | |
| {| class="wikitable"
| |
| |-
| |
| ! Max. Message Size
| |
| ! Forgery Bound
| |
| ! Memory Reg.
| |
| !Setup Pentium III
| |
| !Fin. Pentium III
| |
| !Setup Pentium III
| |
| !Fin. Pentium III
| |
| |-
| |
| | <math>2^{11}</math> bytes (e.g.IPsec)
| |
| | <math>2^{-57.7}</math>
| |
| | 400 bytes
| |
| | 1133 cycles
| |
| | 409 cycles
| |
| | 1774 cycles
| |
| | 776 cycles
| |
| |-
| |
| | <math>2^{15}</math> bytes (e.g.TLS)
| |
| | <math>2^{-56.6}</math>
| |
| | 528 bytes
| |
| | 1370 cycles
| |
| | 421 cycles
| |
| | 2100 cycles
| |
| | 778 cycles
| |
| |-
| |
| | <math>2^{32}</math> bytes
| |
| | <math>2^{-54.2}</math>
| |
| | 1072 bytes
| |
| | 2376 cycles
| |
| | 421 cycles
| |
| | 3488 cycles
| |
| | 778 cycles
| |
| |-
| |
| | <math>2^{61}-1</math> bytes
| |
| | <math>2^{-52.2}</math>
| |
| | 2000 bytes
| |
| | 4093 cycles
| |
| | 433 cycles
| |
| | 5854 cycles
| |
| | 800 cycles
| |
| |}
| |
| | |
| ==See also==
| |
| * [[UMAC]]
| |
| * [[VMAC]]
| |
| * [[Poly1305-AES]]
| |
| | |
| ==References==
| |
| {{Reflist}}
| |
| | |
| ==External links==
| |
| *[http://www.cryptico.com/ Cryptico re-thinking encryption]
| |
| | |
| [[Category:Message authentication codes]]
| |