I want to combine encryption and MAC.

For encryption I use AES-256 with CBC and PKCS5Padding. For MAC I use HmacSHA512.

I use the Encrypt-then-Mac approach (calculate MAC over the ciphertext and deliver it with the ciphertext)

The algorithm should be able to process streamed data, and if I calculate the MAC once over the whole ciphertext, there are two possibilities:

  • Prepend the mac to the ciphertext:

    This is a very bad idea, because the encryption part has to encrypt the whole text before it can output the mac. Therefore it's not streamable. On decryption, we have to process the whole ciphertext before knowing if is compromised (also not fully streamable).

  • Append the mac to the ciphertext:

    Better idea, but the decryption part can only check the MAC in the end. Before that, it did output many bytes that could have been changed by an attacker, or it has to wait until it sees the MAC (not streamable again).

So I need a solution which divides the ciphertext into parts and then calculates a MAC for each part. Because the ciphertext shouldn't be much larger than the plaintext, I choose a MAC block size that is greater than the encryption block size (for example 4 kB).

I want to use a pattern like (with $c_X$ = part X of the ciphertext, $m_i$ = part X of the MAC):

$$ m_1 || IV || c_1 || m_2 || c_2 || m_3 || c_3 || \dots $$

The calculation of the first MAC is clear ($k$ being the MAC key):

$$ m_1 = MAC(k, IV || c_1) $$

But then we meet problems. If we just use

$$ m_X = MAC(k, c_X), $$

this wouldn't be secure. An attacker could change the blocks in order, he could duplicate or remove whole blocks, and so on.

So I thought about an idea similar to CBC mode in encryption:

$$ m_X = MAC(k, m_{X-1} || c_X) $$

Is this now secure? And is there a difference to this one?

$$ m_X = MAC(k, c_1 || ... || c_X) $$


migrated from stackoverflow.com Jun 2 '12 at 3:35

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ I'm pretty sure this scheme is secure $\endgroup$ – CodesInChaos Jun 2 '12 at 0:26
  • 1
    $\begingroup$ What is possible is a BEAST style attack on the implicit IVs you're using. But only if an attacker can control part of the plaintext. $\endgroup$ – CodesInChaos Jun 2 '12 at 0:28
  • $\begingroup$ Welcome to Cryptography Stack Exchange. Your question was migrated here because of being not directly related to software development (the topic of Stack Overflow), and being fully on-topic here. Please register your account here, too, to be able to comment and accept an answer. $\endgroup$ – Paŭlo Ebermann Jun 2 '12 at 11:00
  • $\begingroup$ The IV for the encryption is chosen randomly and prepended to the ciphertext. I just mentioned it above to make clear, that the first mac includes it. This should avoid BEAST style attacks - correct? $\endgroup$ – Heinzi Jun 2 '12 at 11:56
  • $\begingroup$ Not saying anything about your question (it is an interesting one), but is there a reason not to use an established protocol like TLS? This will manage authenticated encryption and break down the stream into message blocks (where the blocks can be of varying size) for you. $\endgroup$ – Paŭlo Ebermann Jun 2 '12 at 11:57

It looks like your protocol is secure for integrity purposes, i.e. the receiver will only accept a stream if it is the same as the one sent by the sender (assuming the MAC is not broken).

But if your possible attack scenarios contain a (partial) chosen plaintext attack, the use of CBC makes it weak against the BEAST-like attack against the confidentiality part, mentioned in the comment by CodeInChaos.

For CBC to be secure against chosen-plaintext attacks of the BEAST-style, it is important that each block's "effective initialization vector" (i.e. the previous block or the IV for the first block) is sent not earlier than the content of the block is fixed. If you send your stream in MAC-block pieces (i.e. $m_i || c_i$) and you send one such full piece before the (plaintext of) the first block of the next piece is known, an attacker which can both observe the ciphertext and chose this block of plaintext can use this to verify guesses about other parts of the ciphertext.

In your context of file encryption, quite likely the full file is already fixed when you start encrypting it, thus this attack is not possible. But make sure you document this limitation when creating your program. Alternatively, use other modes like CTR instead of CBC, which are not weak against chosen plaintext attacks.

  • $\begingroup$ CTR would also make it easier to allow for certain optimizations, e.g. using multithreading to encrypt. It's not done to optimize pre-maturely, but keeping it in mind when designing the protocol should be fine. Of course, with e.g. GCM you could also use a stream cipher + authentication. $\endgroup$ – Maarten Bodewes Jun 3 '12 at 16:05

One weakness with your format is that if you don't read the file from the beginning, but seek to the middle, it's open to reordering attacks. I'd use a scheme like

$HMAC(IV_0 || i || IV_i || data_i) $

The inclusion of $IV_0$ tries to guard against attacks mixing the contents of multiple files.

  • $\begingroup$ 1) Why do you add $$IV_i$$ 2) Would $$m_x = HMAC(k,m_{x-1} || i || data_i) $$ provide the same security? Including the mac of the last block should prevent file mixing. $\endgroup$ – Heinzi Jun 11 '12 at 9:23
  • 1
    $\begingroup$ If you don't include $ IV_i $, random read access becomes much harder, since you still need to verify the IV somehow. Else the attacker can modify the IV, allowing him to modify your first plaintext block without you noticing. This assumes that the last block of the previous part serves as IV for the current part. If you use a different method for deriving the IV, this might not be necessary. $\endgroup$ – CodesInChaos Jun 11 '12 at 9:31
  • $\begingroup$ Ah you're right. I exchanged CBC by CTR to avoid the BEAST attack. So it would be enough to include $IV_0$ into $m_0$ as described in the question above? Thinking about it I even think that including the block number isn't necessary with CTR mode, because the block number affects the IV. Is this correct? Could I just use the approach of my question with CTR mode and the reordering attack you discovered is prohibited? $\endgroup$ – Heinzi Jun 11 '12 at 13:14
  • $\begingroup$ With CTR mode, you don't need to include $IV_i$, but you still need to include the block number. Else the reordering is still possible, and will result in corrupted plaintext. At least if you use a encrypt then MAC mode. $\endgroup$ – CodesInChaos Jun 11 '12 at 13:30
  • $\begingroup$ I thought it would be enough, because the attacker can't change $IV_i$ for intermediate blocks in CTR mode. But it would be enough to change $m_{x-1}$ to let the algorithm accept the reordered block $data_x$. Didn't see that. So summarizing I have two possibilities: $$m_0=HMAC(IV_0||data_0)$$ $$m_i=HMAC(i||m_{i-1}||data_i)$$ or $$\forall i: m_i=(IV_0||i||data_i)$$Both approaches should provide the same security. Is this correct? $\endgroup$ – Heinzi Jun 11 '12 at 16:19

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.