4
$\begingroup$

From an answer to the question RSA maximum bytes to encrypt, comparison to AES in terms of security? I learned that there is a theoretical limit of how much data can be safely encrypted with symmetric block ciphers (like AES for example) with the same key. The answer says that for a block size of n bits there are theoretical concerns when approaching 2^(n/2) encrypted blocks with the same key, and a comment suggests to use 2^(n/4) for a more defensive approach. For AES with its 16 bytes per block, both figures would be significantly more than any single AES key would ever encrypt in my application, so I needn't worry about that.

Nevertheless, even if this limitation bears no practical relevance for me and I have not understood why it exists, I still consider it "good to know" (e. g. because for other symmetric block ciphers with smaller block sizes, it might become relevant).

Hence I'm wondering: are there a similar hypothetical limitations for RSA? In other words: is there some kind of "maximum number of encryptions" I should do with the same RSA key, or is it truly infinite how many times I can encrypt something (in my case: varying 128-bit AES keys) with RSA (assuming the private key remains private forever and there's no attack found)?

Notes:

I haven't yet found anything about it, mainly because when something like this is asked, the answers tend to immediately focus on how much data can you encrypt at once, but they don't say anything about the maximum number of encryptions.

And finally, for completion's sake: I'll use RSA-2048+OAEP-SHA256, but the question is targeted towards RSA in general, for any padding algorithm, and if the answer varies by padding algorithm used, that'd be nice to know.

$\endgroup$
  • $\begingroup$ Public key cryptography is used for signature and key exchange. RSA is slow to encrypt something. For key exchange with RSA-KEM you have 2^2048 random key input for a KDF and that will maps to 2^128 for AES128 and 2^256 for AES-256. $\endgroup$ – kelalaka Apr 6 at 15:27
  • $\begingroup$ @kelalaka Yes, I know all of this, but how is the information on, say, performance relevant for my question on how often I can safely encrypt data with the same key? $\endgroup$ – LWChris Apr 6 at 16:12
4
$\begingroup$

Is there a maximum number of encryptions I should make with the same RSA key?

No, at least, none that can be practically performed.

For RSA, we assume that the adversary has the public key, and hence is able to generate his own plaintext/ciphertext pairs, and in fact, can do that a huge number of times, should he find that helpful.

Hence, if RSA becomes insecure if you encrypt, say, $2^{80}$ messages, then a large adversary can go ahead and encrypt that many messages himself (and thus obtain whatever weakness that was posited.

The fact that we believe that, say, 3k RSA cannot be broken with less than $O(2^{128})$ operations would therefore say that it's safe to encrypt $2^{128}$ messages (and you'll never ever need to encrypt that many).

| improve this answer | |
$\endgroup$
  • $\begingroup$ I agree with No only if we disregard padding and decryption, as I explain. That answer gives another good reason. $\endgroup$ – fgrieu Apr 6 at 22:20
  • 2
    $\begingroup$ "the adversary has the public key, and hence is able to generate his own plaintext/ciphertext pairs"... I feel stupid. This is so simple and obvious that I totally overlooked it. $\endgroup$ – LWChris Apr 7 at 11:18
2
$\begingroup$

is there some kind of "maximum number of encryptions" I should do with the same RSA (public) key.

Not one worth consideration for the textbook-RSA part of RSA, because the message space [0,N) is so large when the public modulus N is large enough to be secure against factorization.

However, even when not used for hybrid encryption with AES, RSA is typically used with some kind of padding that does create a limitation. In particular, when enciphering using RSAES-PKCS1-v1_5 at its maximum message capacity (11 bytes below the byte size of the modulus), the random padding is only 8 bytes, that is 64-bit, therefore when enciphering the same message 224 times (that is <17 millions) to the same public key, there is probability about 22×24-64-1 = 2-17 (that is >0.0007%, not quite negligible) that two ciphertexts are identical, which is detectable by an adversary, leaking that two identical messages have been sent. It is possible to construct use cases where that matters.

More modern RSA paddings (like RSAES-OAEP) typically use a random as wide as the hash, thus the limit is much higher and becomes practically immaterial.


There often are practical limits to the number of times it is safe to decipher or sign with the same RSA private key, due to side-channel attacks (timing, DPA) or (especially for decryption) padding-oracle attacks. But these are attacks against implementations, not against RSA itself. Their success or failure often depends more on the freedom the adversary has to submit queries, on how deeply s/he can observe, and on implementation/platform details, than on the number of attempts.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ So if I send the same plaintext over and over, usually the padding algorithm would ensure that each ciphertext looks totally different, but with the old algorithm and a short padding it's literally "running out of options" and since a bitwise identical ciphertext can only be decrypted to the bitwise identical plaintext, this is some information an adversary would gain (not what it is, but that it was sent at least twice). $\endgroup$ – LWChris Apr 14 at 14:52
  • $\begingroup$ Yes. In "running out of options" it is not kept track of the options previously used; it is relied on chance not to use twice the same option. Hence collision occurs per the birthday bound. As noted in the answer, this happens mostly when close to the maximum capacity of RSAES-PKCS1-v1_5, but this is precisely what happens when one enciphers sizable plaintext in some APIs that attempt to give the same interface for symmetric and asymmetric crypto. Java/BouncyCastle is an example of that dubious design philosophy, which is a common cause of security and reliability issues. $\endgroup$ – fgrieu Apr 14 at 16:00
2
$\begingroup$

If you encrypt n messages with the same key, then the cost of cracking the key is constant, but the reward grows with n.

If you could crack a key at a cost of 100,000,000 and cracking a message is worth 10,000, you won’t try. If I encrypt 100,000 messages like that, you will crack the key.

| improve this answer | |
$\endgroup$
  • $\begingroup$ This is an interesting aspect. It's not only about the number of messages, it's also about the worth of a single message... Thankfully not relevant in my case, I think, but still a point worth consideration. $\endgroup$ – LWChris Apr 7 at 11:22

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.