# What information about the ciphertext can an attacker discern if a key is used too many times?

Suppose that I use Blowfish or XTEA (both secure block ciphers with 64-bit block size) in CTR mode.

In these cases, I need to change the key after $2^{16}$ blocks to avoid leaking information with probability less than $2^{-32}$.

However, suppose that I make a mistake and use the key to encrypt a $2^{33}$-block ($2^{36}$ byte) plaintext. What information can an attacker, knowing only the ciphertext, discern about the plaintext?

• Pretty much nothing. In a known plaintext scenario he would be able confirm that you're using a PRP though as there are no collisions in the keystream.
– SEJPM
Feb 25 '16 at 13:08

However, the situation is very different if you encrypt many plaintext. This is because if there is a collision on the input, then the attacker will be able to get the XOR of the plaintexts (in which case it learns everything). Thus, this reduces to the question of whether or not a random counter repeats. If you are sending many small messages, then there is a good chance that this will happen, so this is disastrous. If you are sending two messages, each of length $2^{32}$ blocks and you use a fully random CTR, then the question becomes what the probability is that the counters used in the two messages will "overlap". This is equivalent to the question of what the probability is that the two messages are of distance at least $2^{32}$ apart. This is actually very easy to compute for 2 messages: fix the first counter $CTR_1$ and then note that the next counter can be anywhere except for in the range of $CTR_1-2^{32}$ and $CTR_2+2^{32}$ (where addition is modulo $2^{64}$). This probability is easily computed at $2^{31}$. However, it is important to be aware that the probability degrades fast when you have more messages.
For the above reason, a better strategy for CTR mode is to break the counter up into two parts: the first part is chosen at random, and the second part is then what is incremented. This is often what is done for AES with the first part being 96 bits and the second part being 32 bits. This means that you can only encrypt message of length $2^{32}$ at maximum (otherwise, you break them into two and use a new counter). However, with a 64-bit block you still get very weak bounds. However, if you KNOW that you are encrypting only a few very long messages, then you can do something like this. If you KNOW that you are encrypting many short messages then you are in trouble.