[September 10th 2024] Message authentication

[Exyss]

WARNING - The photos of this exam were badly taken (they are left below as reference). The full exercise requests have been reconstructed from students' memory, but they may still not be accurate.

• Consider the following MAC for messages of length $\ell = 2n-2$ using a pseudorandom function $F : \{0,1\}^{\lambda} \times \{0,1\}^n \to \{0,1\}^n$. On input a message $m = m_0 || m_1$ (with $| m_0 | = | m_1 | = n-1$) and key $k \in \{0,1\}^{\lambda}$, algorithm $\mathrm{Tag}(k,m)$ outputs $\mathrm{Tag}(k,m) = F(k, 0 || m_0) || F(k, 1 || m_1)$. Is this scheme secure? Prove your answer.
• Show how to build a MAC from the DDH assumption.

[cornflexxx]

1. The Tag is not ufcma :

• query $Tag_k(m_0||m_1) = \tau_0||\tau_1$
• query $Tag_k(m_2||m_3) = \tau_2||\tau_3$
• forge $(m^{\ast},\tau^{\ast}) = (m_0||m_3,\tau_0||\tau_3)$