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

tagwhose only requirement is that it can only be generated with a secret key.

how is MAC different from signatures?

- consists of following algorithms:
- $KeyGen(1_{n})→k$
- $MAC(k,m∈M)→t$
- $Vrfy_{k}(m,t)→b$

- Canonical Verification: when receiver computes $t~:=Mac_{k}(m)$ and verifies that $t~=t$.
- MAC’s, $Π:=(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.- $Mac-forge_{A,Π}(n)$: PPT adversary $A$ has access to oracle $Mac_{k}(⋅)$, and can request tag t for any message of its choice.
- $O$ maintains a set $Q$ of messages $M∈{m_{0},m_{1},…}$ containing all previously queries messages.
- $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, $Vrfy$ succeeds.
- Mac which has no efficient adversary is said to be ==
==.**existentially unforgeable under an adaptive chosen-message attack** - $Pr[Mac-Forge_{A,Π(n)}=1]≤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:=Mac_{k}(m∥T)$, sends $m,t$ to server, and server verifies with key, $Vrfy_{k}(m∥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: $A$ forges $t_{′}=t$ for MAC $(m,t)$ where $m∈Q$.
- Denote $Pr[Mac-sforge_{A,Π}=1]≤negl(n)$. Now, $O$ maintains tuple of $(m,t)$ in set $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:=Mac_{k}(m)=F_{k}(m)$, where $F_{k}$ is a PRF, and canonical verification happens using $t_{′}:=Vrfy_{k}(m);t_{′}?t$.
- Prove: $Pr[Mac-forge_{A,Π}(n)=1]−Pr[Mac−forge_{A,Π}=1]≤negl(n)$
- To prove above construction is secure, create a Polynomial-time distinguisher $D$ that is given oracle access to $O$, and needs to determine whether $O$ is PRF or not.
- $D$ simulates message authentication experiment for adversary $A$ by answering $Mac$ queries and returning $t:=O(m)$ to $A$.
- After all queries, $A$ outputs $(m,t)$. $D$ queries $t_{′}:=O(m)$, and obtain $t_{′}$.
- If $t_{′}=t$ and $m∈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 $O$ is a PRF, then adversary’s view is equal to $A$ in $Mac-forge_{A,Π}(n)$ experiment, thus, $Pr[D_{F_{k}(⋅)}(1_{n})=1]=Pr[Mac-forge_{A,Π}(n)=1]$.
- Similarly, when $O$ is uniform random function: $Pr[D_{f(⋅)}(1_{n})=1]=Pr[Mac-forge_{A,Π}(n)=1]$
- Next prove that: $Pr[Mac-forge_{A,Π}(n)=1]≤2_{−n}+negl(n)$

## MAC for arbitrary length messages

- Construct a simple mac for arbitrary length message by dividing $m=(m_{1},m_{2},…)$ and computing $Mac_{k}(r∥l∥i∥m_{i})$.
- Construction: let $Π_{′}=(Mac_{′},Vrfy_{′})$ be fixed length MAC of length $n$, then
- $Mac$: On input of key $k∈{0,1}_{n}$ message $m∈{0,1}_{∗}$, parse $m=(m_{1},…,m_{d})$ of length $4n $ and choose a uniform $r∈{0,1}_{n/4}$. Compute $∀i∈[1,d];t_{i}←Mac_{′}(r∥l∥i∥m_{i})$. Output $⟨r,t_{1},…,t_{d}⟩$.
- $Vrfy$: On input key $k∈{0,1}_{n}$, a message $m∈{0,1}_{∗}$ and tag $t$, output $∀i∈[1,d];t_{i}=Vrfy_{′}(r∥l∥i∥m_{i})$.C

**Prove**this is secure MAC.- Basic idea is to prove $Pr[Mac-forge_{A,Π}=1]$ by proving two events:
- $repeat$: $r$ is used for some other message during oracle queries
- $NewBlock$: $A$ tries to forge a block $r∥l∥i∥m_{i}$ which was authenticated by $Mac_{′}$ before during answering $A_{′}s$ queries to oracle.

- So, $Pr[Mac-forge_{A,Π}]≤Pr[repeat]+Pr[Mac-forge∧repeat ∧NewBlock]+Pr[Mac-forge∧repeat ∧NewBlock]$.

- Basic idea is to prove $Pr[Mac-forge_{A,Π}=1]$ by proving two events:

### CBC-MAC

- constructing a MAC using pseudorandom function $F_{k}$ for $k∈{0,1}_{n}$ and length function $l(n)>n$, and message length $l(n)⋅n$.
- $Mac$: parse m as $m_{1},…,m_{l}$ and $t_{0}={0}_{n}$, then $t_{i}=F_{k}(t_{i−1}⊕m_{i})$.
- $Vrfy$: output 1 if $t?Mac_{k}(m)$.

- Prove this is a secure Mac.

## Mac from difference-universal function

Let $h:K_{n}×M_{n}→T_{n}$ be a keyed function where $k∈K_{n}$ and message $m∈M_{n}$ and output $t∈T_{n}$, where $T_{n}$ is a group. For $h$ to be $ε−$difference universal function, take $m,m_{′}∈M_{n}$ and any $\Updelta∈T_{n}$ such that $Pr[h_{k}(m)−h_{k}(m_{′})=\Updelta]≤ε(n)$, where $ε(n)≥∣T_{n}∣1 $.

Let’s construct a MAC from DUF, take $h$ to be $ε−$DUF and $F$ to be a PRF, then following is a strongly secure MAC for messages in $M_{n}$:

- $Gen$: output key $k_{h}∈K_{n}$ and $k_{F}∈{0,1}_{n}$.
- $Mac$: for key, $m∈M_{n}$, choose uniform $r∈{0,1}_{n}$, output $t=⟨r,h_{k_{h}}(m)+F_{k_{F}}(r)⟩$
- $Vrfy$: for key, $m∈M_{n}$, parse $t=(r,s)$, output 1 if $s?h_{k_{h}}(m)+F_{k_{F}}(r)$

Prove that above construction is strongly secure MAC, $Pr[Mac-sforge_{A,Π}=1]−Pr[Mac-sforge_{A,Π}]≤negl(n)$

- take two events required to model the security:
- $repeat$: $r$ is not repeated by $O$ in any of the oracle queries by $A$.
- $new-r$: $A$ outputs $⟨m,(r,s)⟩$ where $r$ was not used in any of the previous oracle query.

- study for uniform function first, i.e. $Pr[Mac-sforge_{A,Π}]=Pr[repeat]+Pr[Mac=1∧new-r]+Pr[Mac=1∧repeat ∧new-r]$.
- probability of repeat is $2_{n+1}q(n)_{2} $
- Probability of new-r is $∣T_{n}∣1 $ because $f$ is a uniform function is $A$‘s view.
- prob of neither repeat, nor r-new is $≤ε(n)$ by taking two distinct $(r,s),(r,s_{i})$, where $m_{i}$ was ith oracle query and their $r_{′}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∈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 $∣F∣l $-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(∣K∣1 ,∣T∣1 )$, and only restriction on adversary is number of times it can access the oracle.
- Construct a
**one-time MAC**:- A gives $m_{′}$ and gets $t_{′}=Mac_{k}(m_{′})$
- A outputs $(m,t)$, output 1 if $Vrfy_{k}(m,t)=1$ and $m=m_{′}$.

- $Pr[Mac-forge_{A,Π}]≤ε$
**Strongly universal functions (SUF)**: or also called pairwise independent functions. Function $h:K×M→T$, where $m,m_{′}∈M$ and $t,t_{′}∈T$, such that $Pr[h_{k}(m)=t∧h_{k}(m_{′})=t_{′}]=∣T∣_{2}1 $.- Construct
**MAC using SUF**: simply output $t:=Mac_{k}(m)$, and output 1 if $Vrfy(m,t):=t_{′};t?t_{′}$. - Prove above construction is $∣T∣1 $ secure MAC.
- A simple example of SUF is $h_{a,b}(m)=a⋅m+bmodp$
- One-time MAC from DUF: can be constructed as simply taking $k∈K$ and $r∈T$ and $Mac(m)=h_{k}(m)+r$.

## Mac using hash functions

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

Hash-and-MAC: $t←Mac_{K_{m}}(H_{s}(m))$, and verify using $Vrfy_{K_{m}}(H_{s}(m),t)?1$.

- This can be proven as secure MAC by modelling two adversaries, i.e. $Pr[Mac-forge_{A_{′},Π_{′}}=1]=Pr[Mac-forge_{A_{′},Π_{′}}∧coll]+Pr[Mac-forge_{A_{′},Π_{′}}∧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 $A$ that attacks $Π_{′}$ and $C$ attacking $H_{s}$.
- second is secure using secure MAC

HMAC: $Mac(m):t←H_{s}((k⊕opad)∥H_{s}((k⊕ipad)∥m))$, and verified using $Vrfy(m,t):H_{s}((k⊕opad)∥H_{s}((k⊕ipad)∥m))?t$.

- can be seen as Hash-and-MAC approach where inner pad is used to hash mac to $n_{′}$ length string $m^$
- and $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}∥k_{out}$?

This is because $∣k∣$ is typically less than $n_{′}$, and IV is concatenated with $k_{in}⊕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: