1
$\begingroup$

UMAC uses a key to choose a random hash function from a family of universal hash functions. The value of the hash function is always encrypted using yet another key, and the resulting ciphertext becomes the MAC code.

  • What would go wrong if I skipped the encryption step?
  • In case I have to skip the encryption step (but I can choose different universal hash function than UHASH), what properties would be required from the universal hash function to make the scheme secure?
$\endgroup$
1
  • 1
    $\begingroup$ In case you "have to skip the encryption step", the property which "would be required from the $\hspace{.44 in}$ universal hash function to make the scheme secure" is that the universal hash family be a secure MAC. $\hspace{.29 in}$ $\endgroup$
    – user991
    Commented Jun 14, 2015 at 1:21

1 Answer 1

2
$\begingroup$

What would go wrong if I skipped the encryption step?

It's be easy for someone getting some message/UHASH pairs get enough information about the key to produce further message/UHASH pairs himself. If he receives enough pairs (and it wouldn't take that much), he can fully recover the entire key (and then generate a UHASH for any message of his choosing).

To take a simple example, suppose the attacker receives the UHASH for two messages that differ in a single block. If we call the data from the block that differs from one message $(A, B)$, the UHASH for the first message is $(k_1 - A) \cdot (k_2 - B) + M$ (where $M$ is the contribution from the rest of the message, and $k_1, k_2$ is the UHASH keying data for that block); if the data from the second message is $(C, D)$, then the UHASH for that second message is $(k_1 - C) \cdot (k_2 - D) + M$ (with $M$ being the same, as we assumed that the rest of the message is the same).

If we substract these two, the attacker can recover the value $(k_1 - A) \cdot (k_2 - B) - (k_1 - C) \cdot (k_2 - D) = AB+CD - (B+D)k_1 - (A+C)k_2$

He has a nontrivial probability of being able to recover $k_1, k_2$ just from this; if not, a third message that differs in only this block will make the recovery unique.

This observation is not difficult to extend to sets of messages that differ in multiple blocks.

In case I have to skip the encryption step, what properties would be required from the universal hash function to make the scheme secure?

I can't add much to what Ricky Demer has already said; if you need a function that can be used as a MAC, it needs to have the security properties of a MAC

$\endgroup$
1
  • $\begingroup$ Just to supplement this answer, the $(k_1 - A) \cdot (k_2 - B) + M$ seems to come from the NH hash family construction (page 19). $\endgroup$
    – Paya
    Commented Jun 18, 2015 at 16:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.