# The security of an encrypt-and-MAC

I would like to know what is the security of an encrypt-and-MAC with different keys for each transaction

For example: the one-time-pad with $k_1$ and the HMAC with $k_2$

$$C = M \oplus k_1\\ MAC = HMAC(k_2,M)$$

The ciphertext is $C||MAC$. The two keys $k_1$ and $k_2$ change for each transaction (for each $M$).

-
Very closely related: crypto.stackexchange.com/questions/202/… –  hunter Aug 29 '13 at 14:41
@hunter: related to that other question, but different since keys are not reused, and thus with a different answer. This is fine in theory, but utterly impractical as anything involving the One-Time-Pad, and anything assuming not reusing a MAC key (here k2) without a definition of how new keys are established. –  fgrieu Aug 29 '13 at 17:12
@fgrieu : $\;\;\;$ This needs HMAC to be a secure privacy-preserving MAC. $\:$ (I'm aware that that would follow from certain properties of the compression function, but it's a stronger assumption than HMAC just being a secure MAC.) $\:$ A better option is to use an unconditionally secure MAC in the encrypt-then-MAC approach. –  Ricky Demer Aug 29 '13 at 18:11
Does not respond to my question: in the construction above (my example), and about the security of plaintext (is it affected by the encrypt-and-MAC ?). I know that the latter can (only) provide the integrity of plaintext contrarily to the encrypt-then-MAC. Roughly speaking, Can we said that in the example above the confidentiality and integrity of "data" are provided (Of course, with considering the keys updates) –  zof Aug 29 '13 at 19:28
This seems very similar to this recent question. The only real difference I can see is that the other question explicitly specifies that k1 = RC4(k2). –  Ilmari Karonen Aug 29 '13 at 22:00

## 1 Answer

The answer to this question follows directly from the answers to Should we MAC-then-encrypt or encrypt-then-MAC? and the comment thread here. In short: Your scheme is computationally secure (IND-CCA2 and INT-CTXT) assuming that HMAC is a computationally secure privacy-preserving MAC; but your scheme is wildly impractical, as fgrieu explains, so it is not very interesting from a practical perspective. In addition, this is far from the best possible construction.

If you want advice on what construction to use, I suggest you ask a new question specifying your requirements and let folks suggest a construction. In practice standard schemes for authenticated encryption should suffice for almost all real-world situations.

-
Concerning the impracticability, can you be more precise!? –  zof Aug 29 '13 at 20:31
It's not necessarily that impractical: you can derive the unique encryption and MAC keys from a master key and some nonce (e.g. a message number) using a KDF. Sure, changing the key for each message is probably slightly slower than using the same key for all of them, but then, if you're using HMAC you're presumably not aiming to squeeze every last bit of performance from your hardware anyway. (If you are, consider using a universal hashing based MAC instead.) –  Ilmari Karonen Aug 29 '13 at 20:50
@zof, a one-time pad is impractical, for all the standard reasons (use search to find more discussion of this). See also the comment by fgrieu. (Ilmari, if you are deriving per-message keys from a master key using some computationally secure method, then it is not fair to call what you've got a one-time pad any longer.) –  D.W. Aug 29 '13 at 21:09
His construction will in fact satisfy INT-CTXT, since the one-time pad has the property that different ciphertexts decrypt to different plaintexts. $\:$ Also, "is a computationally secure privacy-preserving MAC" implies "is a computationally secure MAC". $\;\;\;$ –  Ricky Demer Aug 29 '13 at 21:35
@RickyDemer, you are right (on both points). I mis-read your statement. Sorry about that. Thank you for your comments. –  D.W. Aug 30 '13 at 0:09