Score:1

Proof check: Forgery for a MAC

ke flag

I'm looking at the MAC defined as follows: $$\text{Mac}_k(m)=\langle r,f_k(r\oplus m)\rangle $$ where $r$ is uniformly chosen at random (each time) and $f_k$ is a PRF. Vrfy is the canonical one. I'm trying to refute that it is secure (secure definition below).

The Mac-Forge game is defined here: enter image description here

and also: enter image description here

Now, the forgery will work as follows: the attacker picks two messages $m_1,m_2$ with $m_1\neq m_2$. He then calls the oracle with both messages (separately) and gets back $(m_1,t_1),(m_2,t_2)$. Then, he returns: $$(r_1\oplus r_2\oplus m_1, \langle r_2, t_1\rangle) $$ This tag is valid unless $r_1\oplus r_2\oplus m_1$ equals $m_1$ or $m_2$. The first case happens when $r_1\oplus r_2=0^n$ which happens with probability $1/2^n$. The second case happens with probability $1/2^n$ for the same reason. Using the union bound: $$\Pr[r_1\oplus r_2 = 0^n \vee r_1\oplus r_2 = m_1\oplus m_2]\le \frac{2}{2^n}=\frac{1}{2^{n-1}}$$ So: $$\Pr[\text{Mac-forge}_{\mathcal{A},\pi}(n)=1]> 1-\frac{1}{2^{n-1}}$$ which is not negligible.

us flag
What is your question?
yankovs avatar
ke flag
Does it make sense? is there something that I'm missing? I'm trying to apply these definitions for the first time.
Daniel S avatar
ru flag
Welcome to crypto SE. It makes sense, but lacks ambition. You've shown that the scheme is EUF-CMA insecure, but there are even weaker security definitions that it fails to meet.
kelalaka avatar
in flag
[UF-KMA](https://crypto.stackexchange.com/q/44188/18298) +1 for the try.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.