Timeline for Proof that MAC and hash composition is insecure
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 10, 2023 at 21:54 | comment | added | Marc Ilunga | As said in the other answers, the PRF UHF composition is provably secure. Interestingly, however, it is not the case for the MAC UHF composition. | |
| May 15, 2018 at 5:11 | answer | added | fgrieu♦ | timeline score: 2 | |
| May 14, 2018 at 23:14 | vote | accept | Daniel | ||
| May 14, 2018 at 20:06 | comment | added | Squeamish Ossifrage | @Maeher Let $F$ be a random oracle. Does an oracle for $G\colon m \mapsto F(H_k(m))$ help to find a collision in $H_k$? A collision in $G$ implies either a collision in $F$, which happens with the same probability as a birthday coincidence since $F$ is uniform random, or a collision in $H_k$. | |
| May 14, 2018 at 15:39 | comment | added | Maeher | @SqueamishOssifrage That's not entirely correct. Standard definition of a UHF only requires that for any input pair the prob. of collision over a uniformly chosen key is bounded. However, here the order of quantification is wrong. First a key is fixed and then the inputs are chosen. This makes no difference in absence of an oracle, but presence of the oracle invalidates the security guarantee. Nevertheless, you may be correct that leakage from oracle (an efficient attacker, should only be able to test for collisions.) is not enough to efficiently construct collisions. | |
| May 14, 2018 at 15:03 | comment | added | Squeamish Ossifrage | @Maeher On the contrary: As long as the adversary doesn't know the UHF key, the UHF property is precisely that it's hard to find collisions because the probability of collision for any pair of messages is negligible. Note we don't get to see the possibly structured output of the UHF, only the output of the PRF. (Collision resistance is a different property with a different attack model: the adversary learns the key. For pseudorandomness, the adversary never learns the key, only the oracle to evaluate the PRF under the key.) | |
| May 14, 2018 at 2:02 | answer | added | Squeamish Ossifrage | timeline score: 6 | |
| May 13, 2018 at 18:33 | comment | added | Maeher | The thing to keep in mind is that once a key has been fixed for the UHF, there is no guarantee that it's hard to find collisions. This should be how to construct the counter example. | |
| May 13, 2018 at 18:27 | comment | added | Daniel | @fgrieu you are right, MACs are defined over a single key, my mistake. This MAC's key is a pair $(k_1, k_2)$, I updated the question. | |
| May 13, 2018 at 18:26 | history | edited | Daniel | CC BY-SA 4.0 |
added 2 characters in body
|
| May 13, 2018 at 16:33 | history | tweeted | twitter.com/StackCrypto/status/995703628911595521 | ||
| May 13, 2018 at 14:32 | comment | added | Daniel | yes, I'm trying to build a pair of secure functions (a PRF and a UHF) that, when composed, becomes insecure. | |
| May 13, 2018 at 14:31 | comment | added | Maarten Bodewes♦ | Yeah, I just removed that comment. OTOH, it seems like you're trying to find a collision for a hash with that definition? | |
| May 13, 2018 at 14:30 | comment | added | Daniel | an universal hash function is a family of hash functions from some domain to some codomain, so when you choose $H(k_1, m)$, you are choosing a function $H_{k_1}(m)$, and an attacker should have no more than negligible chance to find a pair of inputs that collides. | |
| May 13, 2018 at 10:54 | comment | added | fgrieu♦ | There's no statement about security of $H$. What is exactly the definition used for universal hash function? As an aside, MACs are defined for a single key, so is not it rather $S'(k_1\mathbin\|k_2, m) = F(k_2, H(k_1,m))$? | |
| May 13, 2018 at 4:05 | history | asked | Daniel | CC BY-SA 4.0 |