Skip to main content
Cryptography

Return to Question

edited tags
Link
Maarten Bodewes ♦
Maarten Bodewes ♦
  • 94.5k
  • 13
  • 165
  • 319
Tweeted twitter.com/StackCrypto/status/1231549382597730309
edited title
Source Link
Maarten Bodewes ♦
Maarten Bodewes ♦
  • 94.5k
  • 13
  • 165
  • 319

Insecure MacMAC built on pseudorandom function

this is a question about Katz-Lindell book, introduction to modern cryptography, 2nd edition, exercise 4.7, part c. enter image description here

For (a) and (b) it is clear that the Macs are insecure, but for (c) I am struggling to see why.

For me, when the attacker will present his pair $(m^*, \langle r^*,t^* \rangle)$, the MAC will sample uniformly its own $r$ (before applying the $\operatorname{Vrfyk}(.)$ algorithm), and will prepend $r$ to the computed $t$.

So no matter how the attacker will choose $m^*$ (even if the attacker chooses $m^*$ randomly), the MAC (assuming that it is a deterministic MAC using a canonical verification) will always sample a random $r$ from ${0,1}^n$, independently from the one $(r*)$$(r^*)$ that the attacker output to it, and the probability that $r=r^*$ will be negligible. So it is still secure MAC, the one presented in part (c).

Can someone correct me if I am wrong please?

Insecure Mac built on pseudorandom function

this is a question about Katz-Lindell book, introduction to modern cryptography, 2nd edition, exercise 4.7, part c. enter image description here

For (a) and (b) it is clear that the Macs are insecure, but for (c) I am struggling to see why.

For me, when the attacker will present his pair $(m^*, \langle r^*,t^* \rangle)$, the MAC will sample uniformly its own $r$ (before applying the $\operatorname{Vrfyk}(.)$ algorithm), and will prepend $r$ to the computed $t$.

So no matter how the attacker will choose $m^*$ (even if the attacker chooses $m^*$ randomly), the MAC (assuming that it is a deterministic MAC using a canonical verification) will always sample a random $r$ from ${0,1}^n$, independently from the one $(r*)$ that the attacker output to it, and the probability that $r=r^*$ will be negligible. So it is still secure MAC, the one presented in part (c).

Can someone correct me if I am wrong please?

Insecure MAC built on pseudorandom function

this is a question about Katz-Lindell book, introduction to modern cryptography, 2nd edition, exercise 4.7, part c. enter image description here

For (a) and (b) it is clear that the Macs are insecure, but for (c) I am struggling to see why.

For me, when the attacker will present his pair $(m^*, \langle r^*,t^* \rangle)$, the MAC will sample uniformly its own $r$ (before applying the $\operatorname{Vrfyk}(.)$ algorithm), and will prepend $r$ to the computed $t$.

So no matter how the attacker will choose $m^*$ (even if the attacker chooses $m^*$ randomly), the MAC (assuming that it is a deterministic MAC using a canonical verification) will always sample a random $r$ from ${0,1}^n$, independently from the one $(r^*)$ that the attacker output to it, and the probability that $r=r^*$ will be negligible. So it is still secure MAC, the one presented in part (c).

Can someone correct me if I am wrong please?

added 57 characters in body
Source Link
Maarten Bodewes ♦
Maarten Bodewes ♦
  • 94.5k
  • 13
  • 165
  • 319

this is a question about Katz-Lindell book, introduction to modern cryptography, 2nd edition, exercise 4.7, part c. enter image description here

For a(a) and b(b) it is clear that the Macs are insecure, but for c(c) I am struggling to see why. 

For me, when the attacker will present his pair (m*, <r*,t*>)$(m^*, \langle r^*,t^* \rangle)$, the MacMAC will sample uniformly its own r $r$ (before applying the Vrfyk(.)$\operatorname{Vrfyk}(.)$ algorithm), and will prepend r$r$ to the computed t$t$. 

So no matter how the attacker will choose m* $m^*$ (even if the attacker chooses m*$m^*$ randomly), the MacMAC (assuming that it is a deterministic MacMAC using a canonical verification) will always sample a random r$r$ from {0,1}power n${0,1}^n$, independently from the one (r*)$(r*)$ that the attacker output to it, and the probability that r=r*$r=r^*$ will be negligible. So it is still secure MacMAC, the one presented in part c(c). 

Can someone correct me if I am wrong please? Thank you

this is a question about Katz-Lindell book, introduction to modern cryptography, 2nd edition, exercise 4.7, part c. enter image description here

For a) and b) it is clear that the Macs are insecure, but for c) I am struggling to see why. For me, when the attacker will present his pair (m*, <r*,t*>), the Mac will sample uniformly its own r (before applying the Vrfyk(.) algorithm), and will prepend r to the computed t. So no matter how the attacker will choose m* (even if the attacker chooses m* randomly), the Mac (assuming that it is a deterministic Mac using a canonical verification) will always sample a random r from {0,1}power n, independently from the one (r*) that the attacker output to it, and the probability that r=r* will be negligible. So it is still secure Mac, the one presented in part c). Can someone correct me if I am wrong please? Thank you

this is a question about Katz-Lindell book, introduction to modern cryptography, 2nd edition, exercise 4.7, part c. enter image description here

For (a) and (b) it is clear that the Macs are insecure, but for (c) I am struggling to see why. 

For me, when the attacker will present his pair $(m^*, \langle r^*,t^* \rangle)$, the MAC will sample uniformly its own $r$ (before applying the $\operatorname{Vrfyk}(.)$ algorithm), and will prepend $r$ to the computed $t$. 

So no matter how the attacker will choose $m^*$ (even if the attacker chooses $m^*$ randomly), the MAC (assuming that it is a deterministic MAC using a canonical verification) will always sample a random $r$ from ${0,1}^n$, independently from the one $(r*)$ that the attacker output to it, and the probability that $r=r^*$ will be negligible. So it is still secure MAC, the one presented in part (c). 

Can someone correct me if I am wrong please?

Source Link
xplorer_tedger
xplorer_tedger
  • 31
  • 1