7
$\begingroup$

What is the Limit on Maximum Number of Blocks to be Encrypted under One Key in CBC and CTR Mode? What happens if the limit is crossed and more number of blocks are encrypted?

$\endgroup$
  • 1
    $\begingroup$ Do you really mean minimum or actually maximum? $\endgroup$ – mat Sep 14 '17 at 9:16
  • 1
    $\begingroup$ actually Maximum, not minimum. correctly pointed out :) $\endgroup$ – khan Sep 14 '17 at 9:27
3
$\begingroup$

CTR mode. There's a generic birthday attack on CTR mode of a block cipher.

The idea of CTR mode is to use a PRF, or pseudorandom function family, $F_k\colon \{0,1\}^\iota \to \{0,1\}^n$ to approximate a one-time pad with a short key $k$: $$c = m \oplus (F_k(0) \mathbin\| F_k(1) \mathbin\| F_k(2) \mathbin\| \cdots \mathbin\| F_k(\ell - 1)),$$ where $\ell$ is the length in $n$-bit blocks of the message $m$ (ignoring details of partial blocks).

If instead of a PRF we have a PRP, a pseudorandom permutation family or $n$-bit block cipher, $E_k\colon \{0,1\}^n \to \{0,1\}^n$, we can use that to approximate a PRF. But a PRP, being a family of permutations, has the property that in the sequence of blocks $E_k(0), E_k(1), \dots, E_k(\ell - 1)$, as long as $\ell < 2^n$, there are no repeated blocks. In a uniform random sequence of blocks, we would expect to see a collision when $\ell \approx \sqrt{2^n} = 2^{n/2}$, by the birthday paradox.

When $n = 128$ as in AES, this procedure—check for a repeated block—enables an attacker to distinguish a very long but not unimaginably long CTR mode pad from a very long uniform random pad with nonnegligible probability.

CBC mode. In CBC mode, the $i^\mathit{th}$ ciphertext block is $c_i = E_k(m_i \oplus c_{i-1})$, with $c_{-1}$ being the initialization vector. If the adversary notices that $c_i = c_j$ then they can infer $$m_i \oplus c_{i-1} = m_j \oplus c_{j-1}$$ from which they learn $$m_i \oplus m_j = c_{i-1} \oplus c_{j-1}.$$ Turning this into a distinguisher and calculating how the birthday bound is relevant here is left as an exercise for the reader who has had more breakfast so far this morning than I have.

Recommendations. Because of these birthday attacks, cryptographers usually sternly advise against using AES-CTR or AES-CBC for more than a few exabytes of data, or, to be conservative, a few hundred terabytes. (It doesn't matter whether that's for a lot of short messages or a few long messages.) 64-bit block ciphers like 3DES fare even worse, to the point that they can be broken in practice.

When $n = 256$ as in Threefish-256, these attacks are irrelevant: the birthday bound is around $2^{128}$ blocks of data, which you will never see. When it's a PRF with $n = 512$, as in Salsa20 or ChaCha, it's even less relevant—although if you pick per-message nonces at random, the birthday bound once again becomes relevant because those nonces are only 64 bits and there is a nonnegligible chance of a security-destroying collision in the nonce, which is why the extended-nonce variants XSalsa20 and XChaCha exist and why some cryptographers and standardizers are considering nonce-misuse-resistant AEAD schemes. In sum, the birthday paradox is a versatile tool!

$\endgroup$
  • 2
    $\begingroup$ As a co-author of Threefish, thanks for mentioning it and as an example of a cipher with a 256-bit block size, yes, you end up being able to mostly ignore birthday-bounds attacks. If you're actually going to use Threefish, it's better to use Threefish-512 because it's faster, more secure, and birthday bounds is completely irrelevant with that 512-bit block. Even better would be the 1024 one. In any of theses a reasonable KDF can expand a shorter key (like a 128-bit key) out to the needed size. $\endgroup$ – Jon Callas Sep 19 '17 at 22:28
1
$\begingroup$

Initially the question asked if there is a minimum. However, there isn't any. Actually, encrypting zero bytes is completely secure if you don't count the size of the message. This is a theoretical conundrum of course, as there is only one message with zero width, you know the message if you get zero bits of ciphertext for CTR mode.

For CTR the maximum is related to counter repetition and the amount of plaintext that should be encrypted by the underlying block cipher. If both are large enough, then for a 128 bit block cipher you could encrypt $2^{128}$ blocks of plaintext. That's next to no limit at all. However in real life CTR is used for multiple messages. In that case the counter must be split between a message specific part and a block specific part, while maintaining uniqueness of the counter. This could reduce the amount of blocks per message to about $2^{64}$ for a 128 bit block cipher.

For CBC the question is more complicated. In principle there is no specific end to the amount of blocks that can be encrypted. However, after a while it is possible that the input of the block cipher starts to repeat. The output of the block cipher is used as vector (XOR'ed with the plaintext). The output of the block cipher is indistinguishable from random for fresh plaintext blocks. That mean that the input to the next block cipher calculation is indistinguishable from random as well. However, due to the birthday problem, you would expect a repetition of some block in about $2^{64}$ block encrypts with a certainty of 0.5. This could for instance leak information that the vector and plaintext are identical to a previous encrypt, leaking some info about the plaintext. $2^{64}$ is given as absolute maximum for CBC to be secure.

However, I'd stop at $2^{48} \cdot 16$ for CBC mode to be on the safe side for a 128 bit block cipher. That's still about 4 PiB or 4.5 PB (petabytes) - let me know when you reach that limit. If you're overly worried you can always switch to CTR or a 256 bit block cipher in which case the limits will go out of any bound.


Things like side channel attacks on the implementation of the block cipher or authentication tag calculations may pose different limits. These are just theoretical limits. Besides that, you should design for key change.

$\endgroup$
  • $\begingroup$ in CBC, why would you stop at 2^48 blocks? how to calculate this number(2^48)? $\endgroup$ – khan Sep 14 '17 at 10:36
  • $\begingroup$ Basically there is a $0.5$ chance to repeat a ciphertext block after $2^{64}$. That chance is too large, having a $1 \over 2^{16}$ would be more acceptable, at least in my opinion. But note that the amount of info leaked is - in all likelyhood - smaller than with CTR on repetition. And with these kind of numbers it is possible to bring down the max. without obvious disadvantages. $\endgroup$ – Maarten Bodewes Sep 14 '17 at 13:32
0
$\begingroup$

CTR Mode

That depends on how you actually increment the counter, since it is crucial that you do not repeat a counter. Most implementation I am aware of (including GCM, which is actually CTR for the encrypytion) uses a fixed high part and a running counter (starting with 0) in the lower 32 bits. This would give you a maximum message size of $2^{32}$ blocks (or $2^{36}$ byte for a 128-bit block cipher like AES, which are 64 GiB). If you encrypt more blocks without changing the key or the nonce, you will have a repeating counter which will enable an opponent to read the plaintext of all blocks encrypted with a repeating counter.

CBC Mode

I am not aware of any limitations here, maybe someone else can correct me. The official NIST specification of CBC mode does not list an limitations.

$\endgroup$
  • $\begingroup$ There is limitation of 2^48 blocks on CBC and 2^64 on CTR mode for it to be CPA secure. But how i it, i want to know that :) $\endgroup$ – khan Sep 14 '17 at 11:39

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.