Message authentication code

In almost all situations the damage that modified message can do is far greater than the damage of leaking the plaintext. Therefore, you should always combine encryption with authentication.

A secure MAC must have exis­tential unforgeability under an adaptive chosen-message attack.

Let $F:\mathcal K\times \mathcal X \rightarrow \mathcal Y$ be a PRF. Then if we set $I=(S,V)$ such that $S(k,m)=F(k,m)$ and $V(k,m,t)=yes$ iff $F(k,m)=t$, then for all PPT-adversary $A$ that attacks $I$, there is a PPT-adversary $B$ that attacks $F$ and $$Adv_{MAC}[A,I]\le Adv_{PRF}[B,F] + \frac{1}{|\mathcal Y|}.$$It follows that if $F$ is secure, then the derived MAC is secure given that $|\mathcal Y|$ is large, say $|\mathcal Y|=2^{20}.$

ECBC-MAC	Encrypted CBC-MAC
NMAC	Nested MAC
CMAC	Cipher-based MAC	Do not need dummy block
PMAC	Parallel MAC	Can be done in parallel and incrementally
One-time MAC	Analogy to OTP	Faster than PRF-based MACs and has perfect security
CW-MAC		Converting a one-time MAC to a many-time MAC
HMAC	MAC with Hash	Use $h(K\oplus a || h(K \oplus b || m))$ with secure hash $h$ where $a$ and $b$ are specified constants

ECBC-MAC
Key	$(k, k_1)$
Padding	"10...0" with possibly a dummy block
Tag	CBC-MAC(k,m)$=F(k,F(k,...F(F(k,m_1)\oplus m_2) \oplus m_3)...)\oplus m_n$ ECBC-MAC$(k,k_1,m)=F(k_1, $CBC-MAC$(k,m))$

• Note that it is a bad idea to padding with 0's. If the length of $m$ is not a multiple of the block size, then padding with 0's yields $pad(m)=pad(m||0)$, and thus an attacker that obtains a tag on $m$ also obtains a tag on $m||0$.
• If we remove the last encryption then we get CBC-MAC, which is encryption in CBC mode with zero IV. CBC-MAC is not secure for variable-length messages: One can first query a tag $t=F(k,m)$ for a one-block message $m$, and then forge a tag $t'=F(k, m')=t$ for message $m'=m||m\oplus t$. However, CBC-MAC is secure for fixed-length messages.

PMAC
Key	$(k, k_1)$
Padding	Similar to CMAC
Tag	$F(k_1, (m_1 \oplus P(k,1)) \oplus ... \oplus (m_n \oplus P(k,n)))$

• PMAC is provably reducible in security to the underlying block cipher $F$.
• $P(k,n)$ enforces order on the blocks; otherwise the blocks may be swapped. 
• PMAC can be done incrementally; if we want to change the $i$th block then we just compute $t'=F(k_1, t)$
• When each key is used at most once, PMAC is secure against all adversaries.
• $P$ are fast and faster than PRF-based MACs.

NMAC
Key	$(k, k_1)$
Padding	"10...0" with possibly a dummy block
Tag	$F(k,F(F(...F(F(k_1,m_1), m_2)...))$