Message authentication

Message authentication codes provide message integrity by appending a checksum to the message which receiver on decryption calculates again and verify whether message was tampered or not. Provides 2 properties:

• Authentication: Message was really created by sender
• Integrity: Message was not tempered during transmission.

But any middle man can create a new message with a new MAC, how does receiver know whether it's sent by original sender or adversary?

Nope, as you study further, you discover that MAC is actually realised using a tag whose only requirement is that it can only be generated with a secret key.

how is MAC different from signatures?

• consists of following algorithms:
  • $\text{KeyGen}(1^n)\to k$
  • $\text{MAC}(k,m\in \mathcal{M})\to t$
  • ${\text{Vrfy}}_k(m,t)\to b$
• Canonical Verification: when receiver computes $\tilde{t}:={\text{Mac}}_k(m)$ and verifies that $\tilde{t}=t$.
• MAC’s, $\Pi :=(\text{KeyGen,Mac,Vrfy})$ security definition: adversary should be able to verify MAC of message that it doesn’t have, i.e. forgery of MAC happens when adversary can produce valid MAC tag.
  • ${\text{Mac-forge}}_{\mathcal{A},\Pi }(n)$: PPT adversary $\mathcal{A}$ has access to oracle ${\text{Mac}}_k(\cdot )$, and can request tag t for any message of its choice.
  • $\mathcal{O}$ maintains a set $\mathcal{Q}$ of messages $M\in \{m_0,m_1,\dots \}$ containing all previously queries messages.
  • $\mathcal{A}$ succeeds if it can produce forgery of MAC, i.e. produces valid $(m,t)$, where tag for $m$ wasn’t requested previously, and when $(m,t)$ is given to a third party, $\text{Vrfy}$ succeeds.
  • Mac which has no efficient adversary is said to be ==existentially unforgeable under an adaptive chosen-message attack==.
  • $\mathrm{Pr}[{\text{Mac-Forge}}_{\mathcal{A},\Pi (n)}=1]\le \text{negl}(n)$
• Strength of definition: for most scenarios, this definition of MAC seems too strong, because even though adversary can request tag for messages of its choice any number of times, it still can’t forge a new tag for unauthenticated message.

Examples

Browser Cookies: stored user side in browser to authenticate a user in a session. TCP handshake: calculated server side during second TCP syn+ack to authenticate the user.

• 2FA & TOTP: timed one-time passwords are an excellent example of real-world usage of MACs. user calculate mac $t:={\text{Mac}}_k(m\parallel T)$, sends $m,t$ to server, and server verifies with key, ${\text{Vrfy}}_k(m\parallel T)$.

• Replay attacks: Mac doesn’t provide replay attack prevention guarantees, i.e. adversary can send same (message, tag) and receiver won’t be able to detect whether this message has been sent previously or not.
  • This is done to ensure usability of MACs in different scenarios and should be handled by higher-level application.
• Strong security: $\mathcal{A}$ forges $t^{\prime }\ne t$ for MAC $(m,t)$ where $m\in \mathcal{Q}$.
  • Denote $\mathrm{Pr}[{\text{Mac-sforge}}_{\mathcal{A},\Pi }=1]\le \text{negl}(n)$. Now, $\mathcal{O}$ maintains tuple of $(m,t)$ in set $\mathcal{Q}$.
  • Prove: secure MAC with canonical verification is strongly secure.
• Timing attacks: side channel attacks which can determine value of mac using timing attacks on verification oracle.

Secure-MAC using PRF

• Construct a MAC using PRF where $t:={\text{Mac}}_k(m)=F_k(m)$, where $F_k$ is a PRF, and canonical verification happens using $t^{\prime }:={\text{Vrfy}}_k(m);t^{\prime }\stackrel{?}{=}t$.
• Prove: $\mathrm{Pr}[{\text{Mac-forge}}_{\mathcal{A},\Pi }(n)=1]-\mathrm{Pr}[Mac-forg{e}_{\mathcal{A},\Pi }=1]\le \text{negl}(n)$
  • To prove above construction is secure, create a Polynomial-time distinguisher $D$ that is given oracle access to $\mathcal{O}$, and needs to determine whether $\mathcal{O}$ is PRF or not.
  • $D$ simulates message authentication experiment for adversary $\mathcal{A}$ by answering $\text{Mac}$ queries and returning $t:=\mathcal{O}(m)$ to $\mathcal{A}$.
  • After all queries, $\mathcal{A}$ outputs $(m,t)$. $D$ queries $t^{\prime }:=\mathcal{O}(m)$, and obtain $t^{\prime }$.
  • If $t^{\prime }=t$ and $m\notin \mathcal{Q}$, $D$ outputs 1.

sequenceDiagram
loop Oracle queries
A->>+D: message: m_i
D->>+O: message: m_i
Note right of O: calculates $t=O(m)$
O->>-D: tag: t
D->>-A: tag: t
end
A->>D: (m,t)
D->>O: m
Note right of O: calculates $t'=O(m)$
O->>D: t'
Note over D: checks $t'=t$ and m was not sent before, output 1

• Now, when $\mathcal{O}$ is a PRF, then adversary’s view is equal to $\mathcal{A}$ in ${\text{Mac-forge}}_{\mathcal{A},\Pi }(n)$ experiment, thus, $\mathrm{Pr}[D^{F_k(\cdot )}(1^n)=1]=\mathrm{Pr}[{\text{Mac-forge}}_{\mathcal{A},\Pi }(n)=1]$.
• Similarly, when $\mathcal{O}$ is uniform random function: $\mathrm{Pr}[D^{f(\cdot )}(1^n)=1]=\mathrm{Pr}[{\text{Mac-forge}}_{\mathcal{A},\tilde{\Pi }}(n)=1]$
• Next prove that: $\mathrm{Pr}[{\text{Mac-forge}}_{\mathcal{A},\Pi }(n)=1]\le 2^{-n}+\text{negl}(n)$

MAC for arbitrary length messages

• Construct a simple mac for arbitrary length message by dividing $m=(m_1,m_2,\dots )$ and computing ${\text{Mac}}_k^{\prime }(r\parallel l\parallel i\parallel m_i)$.
• Construction: let ${\Pi }^{\prime }=({\text{Mac}}^{\prime },{\text{Vrfy}}^{\prime })$ be fixed length MAC of length $n$, then
  • $\text{Mac}$: On input of key $k\in \{0,1{\}}^n$ message $m\in \{0,1{\}}^{\ast }$, parse $m=(m_1,\dots ,m_d)$ of length $\frac{n}{4}$ and choose a uniform $r\in \{0,1{\}}^{n/4}$. Compute $\forall i\in [1,d];t_i\leftarrow {\mathsf{Mac}}^{\prime }(r\parallel l\parallel i\parallel m_i)$. Output $⟨r,t_1,\dots ,t_d⟩$.
  • $\text{Vrfy}$: On input key $k\in \{0,1{\}}^n$, a message $m\in \{0,1{\}}^{\ast }$ and tag $t$, output $\forall i\in [1,d];t_i={\text{Vrfy}}^{\prime }(r\parallel l\parallel i\parallel m_i)$.C
• Prove this is secure MAC.
  • Basic idea is to prove $\mathrm{Pr}[{\text{Mac-forge}}_{\mathcal{A},\Pi }=1]$ by proving two events:
    • $\text{repeat}$: $r$ is used for some other message during oracle queries
    • $\text{NewBlock}$: $\mathcal{A}$ tries to forge a block $r\parallel l\parallel i\parallel m_i$ which was authenticated by ${\text{Mac}}^{\prime }$ before during answering ${\mathcal{A}}^{\prime }s$ queries to oracle.
  • So, $\mathrm{Pr}[{\text{Mac-forge}}_{\mathcal{A},\Pi }]\le \mathrm{Pr}[\text{repeat}]+\mathrm{Pr}[\text{Mac-forge}\wedge \overline{\text{repeat}}\wedge \text{NewBlock}]+\mathrm{Pr}[\text{Mac-forge}\wedge \overline{\text{repeat}}\wedge \overline{\text{NewBlock}}]$.

CBC-MAC

• constructing a MAC using pseudorandom function $F_k$ for $k\in \{0,1{\}}^n$ and length function $l(n)>n$, and message length $l(n)\cdot n$.
  • $\text{Mac}$: parse m as $m_1,\dots ,m_l$ and $t_0=\{0{\}}^n$, then $t_i=F_k(t_{i-1}\oplus m_i)$.
  • $\text{Vrfy}$: output 1 if $t\stackrel{?}{=}{\text{Mac}}_k(m)$.
• Prove this is a secure Mac.

Mac from difference-universal function

Let $h:{\mathcal{K}}_n\times {\mathcal{M}}_n\to {\mathcal{T}}_n$ be a keyed function where $k\in {\mathcal{K}}_n$ and message $m\in {\mathcal{M}}_n$ and output $t\in {\mathcal{T}}_n$, where ${\mathcal{T}}_n$ is a group. For $h$ to be $\epsilon -$difference universal function, take $m,m^{\prime }\in {\mathcal{M}}_n$ and any $\text{Updelta}\in {\mathcal{T}}_n$ such that $\mathrm{Pr}[h_k(m)-h_k(m^{\prime })=\text{Updelta}]\le \epsilon (n)$, where $\epsilon (n)\ge \frac{1}{|{\mathcal{T}}_n|}$.

Let’s construct a MAC from DUF, take $h$ to be $\epsilon -$DUF and $F$ to be a PRF, then following is a strongly secure MAC for messages in ${\mathcal{M}}_n$:

• $\text{Gen}$: output key $k_h\in {\mathcal{K}}_n$ and $k_F\in \{0,1{\}}^n$.
• $\text{Mac}$: for key, $m\in {\mathcal{M}}_n$, choose uniform $r\in \{0,1{\}}^n$, output $t=⟨r,h_{k_h}(m)+F_{k_F}(r)⟩$
• $\text{Vrfy}$: for key, $m\in {\mathcal{M}}_n$, parse $t=(r,s)$, output 1 if $s\stackrel{?}{=}{h}_{k_h}(m)+F_{k_F}(r)$

Prove that above construction is strongly secure MAC, $\mathrm{Pr}[{\text{Mac-sforge}}_{\mathcal{A},\Pi }=1]-\mathrm{Pr}[{\text{Mac-sforge}}_{\mathcal{A},\tilde{\Pi }}]\le \text{negl}(n)$

• take two events required to model the security:
  • $\text{repeat}$: $r$ is not repeated by $\mathcal{O}$ in any of the oracle queries by $\mathcal{A}$.
  • $\text{new-r}$: $\mathcal{A}$ outputs $⟨m,(r,s)⟩$ where $r$ was not used in any of the previous oracle query.
• study for uniform function first, i.e. $\mathrm{Pr}[{\text{Mac-sforge}}_{\mathcal{A},\tilde{\Pi }}]=\mathrm{Pr}[\text{repeat}]+\mathrm{Pr}[\text{Mac}=1\wedge \text{new-r}]+\mathrm{Pr}[\text{Mac}=1\wedge \overline{\text{repeat}}\wedge \overline{\text{new-r}}]$.
  • probability of repeat is $\frac{q(n{)}^2}{2^{n+1}}$
  • Probability of new-r is $\frac{1}{|{\mathcal{T}}_n|}$ because $f$ is a uniform function is $\mathcal{A}$‘s view.
  • prob of neither repeat, nor r-new is $\le \epsilon (n)$ by taking two distinct $(r,s),(r,s_i)$, where $m_i$ was ith oracle query and their $r^{\prime }s$ match (because new-r doesn’t occur) and equating their $s$
• a common DUF is taking a finite field $F_q$, $k_h$ to be a point in $F$, and $m\in F[X{]}^{<l}$ is a polynomial of degree < l (constant) in $F$. Now, $h_k(m)=m(k)$, i.e. evaluation of $m$ on $k$. This is $\frac{l}{|F|}$-DUF.

GMAC

TODO

Poly1305

TODO

Information-Theoretic MACs

• until now all MAC constructions are computational secure, i.e. efficient adversary that runs in polynomial time, and thus, we need a security parameter $n$ that is used to model the asymptotic behaviour of both the construction and the adversary.
• Now, we look at conditions that are required to create MAC that are secure for unbounded adversary, i.e. Information Theoretic MAC
• Max probability that we can reach for an unbounded adversary to correctly output a tag that works is $\max \left(\frac{1}{|\mathcal{K}|},\frac{1}{|\mathcal{T}|}\right)$, and only restriction on adversary is number of times it can access the oracle.
• Construct a one-time MAC:
  • A gives $m^{\prime }$ and gets $t^{\prime }={\text{Mac}}_k(m^{\prime })$
  • A outputs $(m,t)$, output 1 if ${\text{Vrfy}}_k(m,t)=1$ and $m\ne m^{\prime }$.
• $\mathrm{Pr}[{\text{Mac-forge}}_{\mathcal{A},\Pi }^{\text{1-time}}]\le \epsilon$
• Strongly universal functions (SUF): or also called pairwise independent functions. Function $h:\mathcal{K}\times \mathcal{M}\to \mathcal{T}$, where $m,m^{\prime }\in \mathcal{M}$ and $t,t^{\prime }\in \mathcal{T}$, such that $\mathrm{Pr}[h_k(m)=t\wedge h_k(m^{\prime })=t^{\prime }]=\frac{1}{|\mathcal{T}{|}^2}$.
• Construct MAC using SUF: simply output $t:={\text{Mac}}_k(m)$, and output 1 if $\text{Vrfy}(m,t):=t^{\prime };t\stackrel{?}{=}{t}^{\prime }$.
• Prove above construction is $\frac{1}{|\mathcal{T}|}$ secure MAC.
• A simple example of SUF is $h_{a,b}(m)=a\cdot m+b\mathrm{mod}p$
• One-time MAC from DUF: can be constructed as simply taking $k\in \mathcal{K}$ and $r\in \mathcal{T}$ and $\text{Mac}(m)=h_k(m)+r$.

Mac using hash functions

Let $H^s=(\text{Gen},H)$ be a arbitrary length hash function

Hash-and-MAC: $t\leftarrow {\text{Mac}}_{K_m}(H^s(m))$, and verify using ${\text{Vrfy}}_{K_m}(H^s(m),t)\stackrel{?}{=}1$.

• This can be proven as secure MAC by modelling two adversaries, i.e. $\mathrm{Pr}[{\text{Mac-forge}}_{{\mathcal{A}}^{\prime },{\Pi }^{\prime }}=1]=\mathrm{Pr}[{\text{Mac-forge}}_{{\mathcal{A}}^{\prime },{\Pi }^{\prime }}\wedge \text{coll}]+\mathrm{Pr}[{\text{Mac-forge}}_{{\mathcal{A}}^{\prime },{\Pi }^{\prime }}\wedge \overline{\text{coll}}]$. Now, prove that both terms are negligible.
  • first can be proven secure by formulating a reduction proof on collision resistance property of $H^s$ with adversary $\mathcal{A}$ that attacks ${\Pi }^{\prime }$ and $\mathcal{C}$ attacking $H^s$.
  • second is secure using secure MAC

HMAC: $\text{Mac(m)}:t\leftarrow H^s((k\oplus \text{opad})\Vert H^s((k\oplus \text{ipad})\Vert m))$, and verified using $\text{Vrfy}(m,t):H^s((k\oplus \text{opad})\Vert H^s((k\oplus \text{ipad})\Vert m))\stackrel{?}{=}t$.

• can be seen as Hash-and-MAC approach where inner pad is used to hash mac to $n^{\prime }$ length string $\hat{m}$
• and $\hat{m}$ again hashed with outer pad to create a tag $t$.
• and $k_{in},k_{out}$ are generated using a pseudorandom generator

one question that arises is why ipad and opad is needed at all? why can't you just use $k$ to generate a pseudorandom string of $k_{in}\Vert k_{out}$?

This is because $|k|$ is typically less than $n^{\prime }$, and IV is concatenated with $k_{in}\oplus \text{ipad}$ to increase key length. Moreover, $k_{in},k_{out}$ need to be uniform, thus, a PRG is used to decrease key length to $|k|$ and derive two pseudorandom keys from that.

Questions

• 4.1: adversary’s success remains same, and canonical verification MAC will always satisfy this.
• 4.2: can i use a MAC that doesn’t use canonical verification? so just use vrfy oracle to determine a pair (m,t) and then output that pair.
• 4.3: if secure MAC uses canonical verification that it’s easy to see that its also strongly secure because adversary won’t be able to forge a tag with substantial probability.
• 4.4:

References

• Intro to Modern Cryptography: Chapter 4
• A graduate course in applied cryptography by Dan Boneh, Victor Shoup: Chapter 6
• Understanding Cryptography: Chapter 12
• Joy of Cryptography: Chapter 10