2
$\begingroup$

The Coursera cryptography 1 course says:

If you want to use MAC-then-encrypt mode then you should either use randomized-CTR or randomized-CBC. And if you use randomized-CTR then one-time-MAC is sufficient.

Here is the slide:

MAC-then-encrypt

I have two question regarding this:

  1. How we can use one-time-MAC without negotiating the different keys for each message?
  2. What is wrong with randomized-CBC that doesn't allow us to use with one-time-MAC?
$\endgroup$
2
$\begingroup$
  1. How can we use one-time-MAC without negotiating the different keys for each message?

If you use a universal hashing one-time MAC, and you encrypt it with CTR mode, effectively you are creating a Carter–Wegman–Shoup MAC:

  • Carter and Wegman showed[1] that if $r, s_0, s_1, \dots$ are independent uniform random and $H_r$ is a universal hash with bounded difference probability $\Pr[H_r(x) - H_r(y) = \delta] < \varepsilon$ for all $x \ne y$ and $\delta$, then the forgery probability for the authenticator $m_i \mapsto H_r(m_i) + s_i$ is bounded by $\varepsilon$.

  • Shoup suggested[2] deriving $s_i = E_k(i)$ for a block cipher $E$, which is essentially what you get with MAC-then-encrypt in CTR mode. Since $E_k$ is a permutation you run up against the birthday bound, of course, just like any use of a block cipher in CTR mode.

  1. What is wrong with randomized-CBC that doesn't allow us to use with one-time MAC?

Offhand, I am not sure! If the one-time MAC is a universal hash with bounded collision probability $\Pr[H_r(x) = H_r(y)] < \varepsilon$ for all $x \ne y$, then this intuitively sounds like it ought to be a secure construction, because $m \mapsto F_k(H_r(m))$ is a secure long-input, short-output PRF if $F_k$ is a secure short-input, short-output PRF and $H_r$ has bounded collision probability[3]. That's not exactly the scenario we have here, because there is not one fixed family $F_k$—if we encrypt $m \mathbin \| H_r(m)$, we get $$E_k(\mathit{iv} \oplus m) \mathbin\| E_k(E_k(\mathit{iv} \oplus m) \oplus H_r(m)),$$ so $m$ figures in twice, but it's pretty close, so intuitively it seems like this should be secure.

Of course, it's not clear that the mere security of a one-time MAC—a bound on forgery probability after a single attempt—implies any of this even with CTR: I'm assuming bounds on collision or difference probabilities, specifically. Maybe you could ask Dan Boneh what he meant.

There is also a danger of padding oracles with CBC in MAC-then-encrypt or MAC-and-encrypt, because CBC works on sequences of blocks rather than sequences of bits, which is why it is hard to get right: practical realizations like TLS and SSH had mistakes for years that leaked plaintexts via padding oracles.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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