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?

  • $\begingroup$ key recovery attacks on block ciphers generally require large amounts of plaintext-ciphertext pairs, wheras with a public key system, many attacks can be started with only the publication of the public key $\endgroup$ Commented Dec 23, 2015 at 6:17
  • $\begingroup$ You rotate your public / private keys primarily because if you don't things may go very bad. A single leaked private key usually has a much larger impact on security than some 5 minutes symmetric TLS session key. If you loose your private PGP key for example every message you received can be decrypted. While the same is true in principle for symmetric crypto re-keying them is possible much more often. $\endgroup$
    – SEJPM
    Commented Dec 23, 2015 at 20:01

1 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.

  • $\begingroup$ CBC would require the block cipher be a PRP since invertiblity is a requirement for this mode. You seem to imply that a proof of the CBC theorem relies on results around the birthday problem, would you have a reference to the actual proof. As @Ritchie Frame implies the situation is fundamentally different for RSA-OAEP since the attacker holds the encrypting key and is in some sense her own encrypting oracle, able to produce an unlimited number of cipher texts... A system like this could not require a bound be placed on the number of encryptions under a public given key... $\endgroup$ Commented Dec 26, 2015 at 19:16
  • $\begingroup$ @RohitKhera, for CBC proof follows from the fact that at the birthday bound you leak the XOR of some random plaintext blocks. I can't off hand tell you where to go for a proof, but Katz and Lindell's Introduction to Modern Cryptography has the equivalent for CBC-MAC. $\endgroup$
    – otus
    Commented Dec 27, 2015 at 8:58
  • $\begingroup$ @RohitKhera, with RSA-OAEP the numbers are larger. The attacker could go through every possible encryption of "Hello World" to see if that is the encrypted string but that is slower than just finding the decryption exponent (which breaks all ciphertexts). $\endgroup$
    – otus
    Commented Dec 27, 2015 at 9:01
  • $\begingroup$ Where can I find the Bonds for RSA-OAEP? $\endgroup$
    – DaWNFoRCe
    Commented Aug 12, 2019 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.