Contrasting Key Rotation Requirements : Asymmetric vs. Symmetric Ciphers

Question

I'm trying to contrast key rotation requirements for asymmetric and symmetric ciphers.

In the case of symmetric ciphers, we have the results such as the so called "CBC Theorem" (stated on pg. 24 of https://crypto.stanford.edu/~dabo/cs255/lectures/PRP-PRF.pdf) The CBC Theorem states that for a "q - query" CPA attacker attempting to break semantic security of AES-128-CBC, the attacker's advantage is less than $1/2^{32}$ only if $q^{2}L^{2} / \left\lVert X \right\rVert$, the "error" term in the CBC theorem, is less than $1/2^{32}$, i.e. given that $\left\lVert X \right\rVert = 2^{128}$ for AES-128, we can encrypt $2^{48}$ AES-128 blocks after which we need to switch the key in order to keep the attacker’s advantage below $1/2^{32}$

I have not seen a proof of theorem, but I'm guessing such results arise from basing the security of block cipher modes purely on their behavior as pseudo random functions.

Probabilistic asymmetric encryption schemes such as RSAES-OAEP, ECIES etc., on the other hand, employ the assumption of pseudo randomness in addition to an assumption around (computational) hardness of some number theoretic or algebraic problem, such as hardness of EC/DLP, factoring or short vector problems etc.

Does the fact that asymmetric schemes are based on such dual assumptions (pseudo randomness + factoring etc.) mitigate or extend the horizon for key rotation in such schemes after a certain number of encryptions under the same key, beyond what is implied by relying purely on pseudorandomness as is the case for AES-128-CBC under the CBC theorem? Is there an asymmetric analog for the CBC theorem that quantifies the advantage conferred to an adversary after some number of encryptions under the same key?

Answer 1

I have not seen a proof of theorem, but I'm guessing such results arise from basing the security of block cipher modes purely on their behavior as pseudo random functions.

Another factor is that block ciphers are not pseudorandom functions (PRF), but pseudorandom permutations (PRP). That means that as you get close to the birthday bound you do not see the collisions that you would expect from a PRF. This is significant with some modes of encryption.

However, yes, even with a PRF if you have collisions in the input to the function you start to lose security, so that puts a bound on things.

In the case of CBC mode the theorem concerns the probability that two ciphertext blocks are equal (and thus the inputs). This happens with significant probability as you get to the birthday bound. From such a collision the attacker finds that $p_i \oplus p_j = c_{i-1} \oplus c_{j-1}$, the right side of which they know.

---

Or is there an analog for the CBC theorem that necessitates rotation of asymmetric encryption keys after some critical number of encryptions under the same key?

Yes, there are analogs.

If you are talking about pure asymmetric encryption like padded RSA, there is a chance that the random padding collides with an earlier one and you leak plaintext equality. E.g. if you encrypt the same plaintext twice with RSA-OAEP and have parameters such that there is $x$ bits of randomness, the probability of the randomness colliding and getting two equal ciphertexts is $2^{-x}$, in which case an attacker knows they must be the same plaintext.

If you use hybrid encryption, there is similarly a probability that the random symmetric keys used are equal, which would encrypt the same plaintext to the same symmetric ciphertext, again leaking equality.

(These are not the best attacks on RSA, just an example that bounds exist.)

---

Does that mean that you must rotate keys? Not really. The actual bounds for secure RSA sizes and padding algorithms are large enough that you will not hit them. A limited signing key lifetime may be a good idea for other reasons - in case you lose the key and in case better attacks come along - but you are not practically limited in the data you can encrypt or sign.