Verificare a dovezii: fals pentru un MAC

Mă uit la MAC definit după cum urmează: $$\text{Mac}_k(m)=\langle r,f_k(r\oplus m)\rangle $$ Unde $r$ este aleasă uniform la întâmplare (de fiecare dată) și $f_k$ este un PRF. Vrfy este cel canonic. Încerc să infirm faptul că este sigur (definiția sigură de mai jos).

Jocul Mac-Forge este definit aici:

Si deasemenea:

Acum, falsificarea va funcționa după cum urmează: atacatorul alege două mesaje $m_1,m_2$ cu $m_1\neq m_2$. Apoi sună oracolul cu ambele mesaje (separat) și se întoarce $(m_1,t_1),(m_2,t_2)$. Apoi, se întoarce: $$(r_1\oplus r_2\oplus m_1, \langle r_2, t_1\rangle) $$ Această etichetă este valabilă dacă nu $r_1\oplus r_2\oplus m_1$ egală $m_1$ sau $m_2$. Primul caz se întâmplă când $r_1\oplus r_2=0^n$ ceea ce se întâmplă cu probabilitate $1/2^n$. Al doilea caz se întâmplă cu probabilitate $1/2^n$ pentru același motiv. Folosind uniunea legată: $$\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 }}$$ Asa de: $$\Pr[\text{Mac-forge}_{\mathcal{A},\pi}(n)=1]> 1-\frac{1}{2^{n-1}}$$ ceea ce nu este de neglijat.