# Practical implications of the switching lemma and the counter mode security bound

I have some trouble with determining how many times a key can be safely used when using counter mode encryption.

If we, for example, split the IV into two parts, a message counter (nonce) and a block counter. Messages are always of the same length. We make sure that under the same key, the IV is never repeated, and we use AES128 for the block cipher.

The paper ‘A concrete security treatment of symmetric encryption’ tells me that the advantage of an attacker is at most half the security strength of the underlying PRF. Then with the switching lemma, the advantage of the underlying PRF can be bounded by the advantage of the underlying PRP (with AES-128 would be about $$2^{-128}$$) plus $$q^22^{-l-1}$$.

• Does this $$q^22^{-l-1}$$ just show that there is no attack that is better than this bound, or does it also give us an attack? And if so, what does that imply?

• Is $$q$$ the amount of queries that is allowed by the oracle and thus, assuming no other leaks, the total amount of cypher calls by my system? Or can the attacker create it’s own oracle like with a brute force attack on the key space?

• Is there no time complexity in that part of the formula?

Let’s say I take an advantage bound $$2^{-30}$$ (very improbable) then I can have $$2^{49}$$ cipher calls ($$1/2^{30} = q^22^{-128-1}$$). Any adversary that wants to gain a better advantage has to do an attack on the underlying permutation, something like $$2^{97}$$ key checks on AES-128 for example.

Does this $q^2 2^{−l−1}$ just show that there is no attack that is better than this bound, or does it also give us an attack? And if so, what does that imply?

1. The switching lemma is tight up to constant factors. If you make $q$ queries, then you can indeed distinguish between a PRF and PRP with probability at least $0.632 q^2 2^{-l-1}$. Here the 0.632 is $1 - 1/e$. More specifically, this is the probability that you will see a repeated output by a PRF (and obviously a repeated output from a PRP is impossible).

2. You can indeed attack the IND-CPA security of PRP+CTR with this advantage.

Suppose you ask for $q$ identical blocks to be encrypted. Assuming the IV+counter never repeats, it is not hard to see that there will be no repeated ciphertext blocks under a PRP.

Suppose you ask for $q$ uniformly distributed blocks to be encrypted. Then the ciphertext blocks will be uniformly distributed and therefore display duplicates with the above probability.

Is $q$ the amount of queries that is allowed by the oracle and thus, assuming no other leaks, the total amount of cypher calls by my system?

In this context, $q$ is the number of calls to the PRP that the attacker induces the honest party to make.

• With probability at least? The paper states $Adv_{PRF} \leq Adv_{PRP} + q^22^{-l-1}$, isn't it at most then? Jan 16 '18 at 8:59
• I have seen this attack before. I often see mention that in for example AES-GCM a single key can be used for encrypting a huge amount of data ($2^{32}$ invocations of up to $2^{31}$ blocks). This still gives a high advantage to the attacker under this attack. The information leaked under this attack doesn't seem like much, but that doesn't mean that there are no attacks that leak a lot more information that are only slightly slower right? Jan 16 '18 at 9:34
• The paper is proving a statement "for any adversary that makes q queries, its advantage is at most $Adv_{PRP} + q^2/2^{l+1}$". Of course some adversaries that make q queries have advantage 0. I described an adversary that makes q queries and has advantage at least $0.632 q^2 / 2^{l+1}$. Jan 17 '18 at 6:56
• @SapChicken I've seen that you haven't accepted any answers. If possible could you review the answers and accept them (using the V mark to the left) if the answers are sufficient for you? Jan 7 at 23:53