Suppose, we have a secure PRF $F$. Then can there be a MAC Scheme $I=(Sign, Verify)$ using F such that $I$ is insecure, but I is secure under the restriction that all the queries for MAC challenges are different?
7
-
1$\begingroup$ "under the restriction that all the queries for MAC challenges are different" that doesn't do much, unless the MAC algorithm does not just depend on the message; you'd otherwise get the same value back each time, which doesn't give the adversary any advantage. Either I'm not getting it or the description of the MAC algorithm lacks detail. $\endgroup$– Maarten Bodewes ♦Sep 28 at 9:46
-
$\begingroup$ yeah, we have to create such a MAC, where it makes a difference. And obviously, it must be randomized otherwise it won't make any difference. $\endgroup$– John_cenaSep 28 at 10:30
-
$\begingroup$ So most probably, we will first get different tags for the same message,m and then we should be able to create a new tag from the tags we have for the given message $\endgroup$– John_cenaSep 28 at 10:40
-
$\begingroup$ So if you'd have a semi-random value that you can influence somehow and identical messages then you can possibly use that to create an insecure MAC. But that's just my intuition. $\endgroup$– Maarten Bodewes ♦Sep 28 at 10:54
-
$\begingroup$ can you explain a bit more about the construction $\endgroup$– John_cenaSep 28 at 10:57
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
2
Let's leave aside that something like this would still not be considered secure from a cryptographic point of view, since we generally assume an arbitrary (usually probabilistic polynomial-time) attacker.
I assume that the question is asked in the sense that an adaptation of the MAC scheme is sought, which is safe under the given assumption. Let's assume we got $KeyGen$ $k \leftarrow \{0,1\}^n$ with $n$ being the security parameter. Assume $t \leftarrow MAC(k, m) = F(k, m)$ for some message $m \in \{0,1\}^*$. And Assume $b \leftarrow Vrfy(k,m,t)$ with $b\in\{0,1\}$, where 1 is valid and 0 is invalid. This is, given your assumption, secure, if for all queries, all messages are different. But assuming an arbitrary adversary, this is not secure. Thus, we now want to make it secure.
The idea for that is a nonce (number used only once) or a random value (which has a negligible collision probability). Using this we could build $t \leftarrow MAC_r(k,m,r)$ with $r \leftarrow \\\$ \{0,1\}^*$ or $t \leftarrow MAC_n(k,m,n)$, where $n$ is e.g. a counter.
I hope this helps, because honestly I don't quite understand your question completely.
Note: I assume you can proof the security of the previous construction using a reduction proof, reducing the security of $MAC_r(k,m,r)$ or $MAC_n(k,m,n)$ to the assumed security of $MAC$.
-
$\begingroup$ We know the definition of original MAC Security, that we can query polynomially many $x$ and the challenger will return $MAC(k,x)$ where $MAC$ may be random or deterministic. And the adversary will after all the queries return a pair $m,c$ and win if Verify(k,m,c)=1. We will say that the MAC is secure if the advantage of any polynomial time adversary is negligible. Now we define a slightly weaker definition of MAC Security where all the setup remains, the same as it is but differs only in queries. Now we can not query the same $x$ more than once. $\endgroup$ Sep 28 at 14:37
-
$\begingroup$ Now we want to find a $MAC$ from a PRF $F$ such that MAC is weakly secure but not secure under the original security definition.Is this clear now? $\endgroup$ Sep 28 at 14:39
$\begingroup$
$\endgroup$
One example would work as follows at a high level: The MAC scheme is built from the PRF $F$, and another probabilistic MAC scheme $M$ and a counter $c$.
For MACing a message $m$: Compute a key $k_M \xleftarrow{$} F(m)$, then send output the mac $\tau = (k_M^{c,m}, M.\textrm{sign}(k_M, m))$ and increase the counter $c$. $K_M^{c,m}$ refers to the the first or second half of $F(m)$ depending on the parity of $c$. Other levels of leakage may also be considered.
As for security, as long as a given message is queried only once, then the adversary only gets half of the key of the "inner" MAC.
I would conjecture that in such a setting, the advantage of the adversary against $I$ is upper bounded by a PRF advantage on $F$, a MAC advantage on $M$ and term of the form $\frac{1}{2^{n/2}}$ for the probability of guessing the second half. (I didn't actually work through this rigorously).
