How to show the PRF in 4.8(b) is not secure?

LJCOUC

2/18/23, 4:48 AM

Let F be a PRF defined over $F:\{0, 1\}^n \times \{0, 1\}^n \to Y$.

We say that $F$ is XOR-malleable if $F(k, x \oplus c) = F(k, x) \oplus c$ for all $k, x, c \in \{0, 1\}^n$.
We say that $F$ is key XOR-malleable if $F(k \oplus c, x) = F(k, x) \oplus c$ for all $k, x, c \in \{0, 1\}^n$.

Clearly an XOR-malleable PRF cannot be secure: malleability lets an attacker distinguish the PRF from a random function.Show that the same holds for a key XOR-malleable PRF.

Remark: In contrast, we note that there are secure PRFs where $F(k_1\oplus k_2, x) = F(k_1, x)\oplus F(k_2, x)$.

I don't know how to construct an attacker to determine that this is an insecure PRF. My confusion is that this topic has changed the key, but for the attacker, the key is not assignable, so I am very confused. I have discussed with others for a long time without results, so I come here for advice. Thank you very much!

205

0 + 0

xor

pseudo-random-function

Manish Adhikari

2/18/23, 9:53 AM

Hint! The attacker cannot control the challengers key, yes, but can calculate $F(k',x)$ for any key $k'$ of her choice. Advisable to keep it simple like $0^n$

LJCOUC

2/18/23, 12:56 PM

I'm very sorry. I haven't been in contact with cryptography for a long time, so I don't understand many problems. For 4.8 (a), I let x = C = 1n, get a property of F, and then construct two experiments. The attacker can distinguish the two experiments with an indistinguishable advantage, so this is an unsafe PRF. But I don't know what is the connection between (a) and (b)?

LJCOUC

2/18/23, 12:59 PM

Do you mean that an attacker can calculate F(k ', x)? Does 0n mean K 'or x?

Manish Adhikari

2/18/23, 3:20 PM

The attack is not on $k'$ but it can be used to recover the key used $k$ in b). Try editing the question by showing your work and then maybe it will be open for answering. Of course we won't do your homework for you.

LJCOUC

2/19/23, 2:45 AM

Thank you very much. I think I may have some ideas now. If I can do it or have any confusion, I will come here again for advice! Because this is the first time I use this website, there are many things I can't do well. Thank you for your understanding and tolerance!