Hybrid encryption with RSA and AES versus spliting into multiple RSA messages?

Question

I've done research about this subject, but I can't find the answer I'm looking for.

The problem is that the string I want to send doesn't fit into the RSA key that the client have, and during encryption getting ValueError: Plaintext is too long.

The proposed solution is to do hybrid encryption by generating a secret key, sending the secret key encrypted with the clients public key, and then send the rest of the data encrypted using AES and the secret key.

I understand the performance is much better in this manner, but for me this feels like opening an extra door to the data. Even though no one would ever find my service interesting enough to try to decrypt the RSA or AES data. But now I have to trust and support two(!) algorithms for the client applications.

Everyone only seems to be speaking good about the hybrid solution, and I understand that it would be the best solution for anything with a lot of traffic going on. Since it's probably about serving users as fast as possible and its not good to waste resources on encrypting/decrypting data.

But theoretically the data is open to two attacks, either by brute-forcing the RSA and get the secret key to decrypt the AES, or directly by brute-forcing the AES. But then again, using 2048-bit RSA and 256-bit AES wouldn't be possible to brute-force any of them any time soon.

So the 256-bit AES must be harder than the 2048-bit RSA, else the data is now less secure somehow, but since AES is 'thousands of times' faster than RSA this doesn't feels true.

Guessing a 32-byte AES password seems easier than guessing the much longer private key.

How secure are they (AES-256 vs RSA-2048) relatively to each other?

The idea I have is that I split my message into chunks, and encrypts each one of them using RSA, then concatenate them into one packet, and the client can then read each encrypted chunk and decrypt them and then concatenate them back to the original message.

Other than it's slower than a hybrid method, Is there anything wrong with this approach?

How much slower it would be to use RSA in this way relatively to AES? For a 512B string and a 2kB string? Or if the speed is constant, the answer expressed in MB/s

PS: Now you don't need to bother and fight about the protocol, which I happened to explain earlier. I just thought the background would help you to answer the question easier, but instead more comments and downvotes on the wrongs in the protocol than the real questions.

Answer 1

There is a lot of things to discuss in your question, but I'll focus on one specific line:

Guessing a 32-byte AES password seems easier than guessing the much longer private key.

AES does not use passwords, it uses keys. These keys should be generated by a secure random number generator if used within a hybrid encryption scheme. As there are no known attacks on full AES when used as a block cipher, brute forcing the AES key is comparable to guessing a 128, 192 or 256 bit number. That's $2^{127}$, $2^{191}$ or $2^{255}$ guesses on average.

RSA's key size is not directly related to its security margin. An RSA 2048 key in your example is equated with 112 bit security by NIST and about 104 bit by ECRYPT-II (2012 predictions). So RSA 2048 is significantly less secure and much slower than any form of AES. Note that RSA encryption also requires access to a secure random number generator to generate the padding.

All in all, both RSA with a key size of 2048 bits and AES-128 are pretty secure. There is a lot of reason to expect that other parts of the system are much more vulnerable to attack. This is especially true if communication is performed without integrity/authenticity provided by a signature or other authentication tag. Once your message has integrity and authenticity protection you need to take care of side channel attacks and attacks on physical security, bugs in software (updates) etc. etc. etc.

Please use a standardized form of hybrid encryption and quickly move on to secure other parts of your system.

Answer 2

The question has several aspects:

• it asked (initially) about any security issue in breaking a piece of data into separately RSA-encrypted chunks;
• it asks what's the weak link in the security chain when doing hybrid encryption with a 256-bit AES key transfered enciphered using 2048-bit RSA;
• it asks how much slower 2048-bit RSA would be for bulk encryption, compared to AES-256;
• it (formerly) outlined a protocol where a public key is RSA-enciphered (causing the Plaintext is too long error); that protocol turned out to be unsafe not protect the confidentiality of data enciphered with that public key, basically because that public key was sent enciphered, rather than signed.

On the first aspect: if the goal of encryption is limited to protecting the confidentiality of some data (which is the only goal assigned to encryption in its modern definition), and RSA encryption is done properly (that is, with random padding), then there is no security issue, only performance and message size issues.

However the protocol formerly outlined used RSA encryption for other purposes than encryption. So maybe breaking the encrypted material into chunks worsens things; like, multiple cryptograms can be reordered by an adversary.

---

When doing hybrid encryption with 2048-bit RSA used to transfer a 256-bit AES key, the weak link is, from an academic point of view, the 2048-bit RSA key. According to the multiple sources considered by this well-respected website on key length, 2048-bit RSA is somwhat less secure than a block cipher with a 128-bit key, which itself is (theoretically) $2^{128}$ times less secure than a block cipher with a 256-bit key. Two levels of explanations to that:

• Qualitative: in RSA, an adversary is given a lot of information about the key (the whole public modulus); whereas in AES, the key is assumed secret, being exposed to the adversary only through the complex layers of the cipher.
• Quantitative: factoring $N$ is known to require less than $\exp\Big(\big(\sqrt[3]{\frac{64}{9}}+o(1)\big)\cdot(\ln N)^{\frac1 3}\cdot(\ln\ln N)^{\frac2 3}\Big)$ operations, and plugging $N\approx2^{2048}$ into that, ignoring the $o(1)$ term, gives less than $2^{117}$.

But reality is, the true weak link (beyond using a bad protocol) is the ability to keep undisclosed the secret material involved (e.g. the secret AES key and the private RSA key). Many things conspire to make this hard, both for RSA and AES, including implementation goofs, side channels, and NSA-planted backdoors.

---

How much slower RSA-2048 is compared to AES-256 depends on many things:

• Is the cost of key generation to be considered? That is the case in the protocol formerly described, where a 2048-bit RSA key is generated for each user connection, and used only a few times per session, unquestionably making RSA key generation the performance bottleneck: generating an RSA key is much slower than using it, and can be like $2^{20\pm12}$ times more costly than AES-256 key generation or encryption (methods used for RSA key generation vary widely, and what we should include on the AES-256 side is unclear).
• What is the hardware? If there is hardware for AES, but not for RSA, which is common on many modern CPUs, AES-256 encipher and decipher bulk data like $2^{20\pm 8}$ times faster than bulk RSA can. Even with hardware for RSA but not AES, like on this Smart Card with ARM Cortex M3 CPU, RSA is slower than AES is.
• What is the software? Poorly written software can slow anything without limit. It is very common that two deployed implementations of a cryptographic algorithm differ in performance by a factor of $2^4$ on the same hardware.
• Are we considering RSA encryption or decryption, and in the former case what's the public exponent? With $e=3$ and simple implementations, RSA-2048 decryption is $2^{10\pm1}$ times slower than encryption is; make that $2^{7\pm1}$ for $e=65537$.
• The size of what's encrypted: AES's speed advantage is least when the data enciphered exactly fits the capacity of the RSA encryption scheme.

---

On the last aspect (now no longer part of the question):

• Whatever exactly the protocol outlined was and aimed at, it was bound to be vulnerable to a Man-in-the-Middle attack during the "upload" of the "uniquely already known (user) public key"; a sure sign is that the client starts without any credential.
• The protocol included an explicit step of encrypting something designated as "public key" (see end of step 4 in the protocol); this is a tale-tale sign of a design error.
• Even if that "public key" was not made public, the confidentiality of commands normally sent enciphered by the user using that key (in step 5 of the protocol) was not ensured, for an adversary could inject another public key to be used instead.
• In some most common uses of RSA for signature, an unknown public key is easy to infer from a few signatures; keeping that public key confidential during its transfer does not prevent its later disclosure when and if it is used for signatures (as alluded in comments but not in the former description of the protocol).