Score:9

Does this RSA decryption scheme make sense?

sv flag

A custom file format has a header encrypted with a 2048-bit RSA public key. I need to decrypt it using a 2048-bit RSA private key. The header has 48 bytes, and according to the scheme I got for the task, after decryption I should get a 48 bytes of "plaintext" payload.

However, this scheme does not make any sense to me. It is my understanding that if we encrypt something using a 2048-bit RSA key, we will inevitably get a 256 ciphertext. Am I wrong in my assumption? Is there a way to RSA-decrypt a 48 byte ciphertext with a 2048-bit private key and get a 48 byte plaintext out of it?

I have tried using -raw mode with openssl like this, and it produces a 256-byte long plaintext message:

openssl rsautl -decrypt -in ./header.bin -out ./header-out.bin -inkey ./privkey.pem -raw

enter image description here

P. S. After discussion with the client and going through the encryption source code, we've figured out that the documentation had it wrong. In reality, header is not 48 bytes but variable length, and the first 2 bytes of the file contain the header length.

cn flag
I'd guess it's a copy-paste mistake in the docs, where they copied the 48B header size to the "RSA block" item and forgot to adjust it.
Score:10
ar flag

You're right, normal RSA does not (and cannot) work like that. Most likely, your client either:

  1. is using RSA with an absurdly low (and insecure) key size,
  2. is not actually using RSA at all, or
  3. has provided you with incorrect documentation regarding the encrypted header size.

All of those seem plausible. I would suggest telling your client that the documentation they have provided appears inconsistent, and asking them to supply you with working code that can either read (and decrypt) or write (and encrypt) files in their format. That should hopefully be sufficient for you to figure out what the heck is actually going on.

(Note that it's quite possible that your client doesn't know either, if they didn't write the software themselves. It's quite possible that they believe the documentation to be correct, and lack the crypto expertise to know better.)


Ps. There is, technically, at least one more thing that they could be doing: they could be using (truncated) RSA decryption as a PRF. That is, they could be generating a random 48-byte header, feeding it (padded e.g. with zeroes) to 2048-bit RSA decryption as ciphertext, and truncating the resulting 2048-bit pseudorandom plaintext back to 48 bytes.

Is that secure? Maybe. It's definitely not a normal way of using RSA, but I can't immediately think of an obvious attack against it. And at least I can't think of any other halfway secure way to use 2048-bit RSA to map 48-byte strings to 48-byte strings.

Of course, the obvious problem is that, in order to do that, the encryption code would also need access to the private RSA key — which makes using RSA pointless, since any symmetric-key PRF would work just as well. But at least they could technically claim that they were "using RSA." And honestly it wouldn't be anywhere near the craziest thing ever found in do-it-yourself encryption schemes.

Maksym Shcherban avatar
sv flag
It's most likely option 3, because I have access to the private key, and have confirmed that it is indeed 2048 RSA private key. They also have a desktop app that can decode the files given the private key, so it is working somehow. If we get along with the project, and if it doesn't break any NDAs, I will try to not forget and update my question and ping you. Once again, big thanks to everybody for the answers, you are most helpful.
pabouk - Ukraine stay strong avatar
gb flag
I am not sure what did you mean in the PS section. Did you mean to use RSA as a pseudorandom number generator whose output will be used as a key for XOR encryption?
Maksym Shcherban avatar
sv flag
Ping :) I've added P.S. to the post.
Score:6
us flag

You can encrypt and decrypt arbitrary size of plaintext & ciphertext with RSA without using padding. This method is called as "Textbook RSA." However, it is definitely insecure. Different padding methods are used in current systems in order to make the output size equals to the size of the RSA modulus "$n$".

So in your case, 48-byte plaintext is padded according to some padding format and 2048-bit output is obtained inevitably. openssl may be use PKCS#1 as default format, I'm not sure. If you want to encrypt 48-byte plaintext and obtain it as 48-byte after decryption of corresponding ciphertext, you should use Textbook RSA.

fgrieu avatar
ng flag
Even in textbook RSA with the minimal $e=3$ and 2048-bit public modulus $n$, encrypting 48 bytes would yield an about-144-byte cryptogram, larger than in the question (and that would be entirely insecure, to the point that decryption does not need $n$).
Maksym Shcherban avatar
sv flag
Thank you for your answer. I do not want to encrypt anything. The context is, we have received a request from a client who wants to build an app working with files stored in custom format. The scheme in my question is from a document provided by the client describing this file format. They claim that's how it works (48 bytes ciphertext -> RSA decrypt with 2048 bit key -> 48 byte plaintext), which did not look very credible to me, it seems some relevant piece of information is missing.
Score:4
ng flag

if we encrypt something using a 2048-bit RSA key, we will inevitably get a 256 (bytes) ciphertext.

Yes, except it's possible to save a few bits, and there are commonly used tricks to save one bit (with the benefit of allowing subsequent textbook RSA signature with a second RSA modulus of the same size).

In this 1-bit-saving trick, a message to encipher $M$ is padded into an integer $m$ (adding randomness and redundancy) in such a way that $m<n/2$ (as in the EME-OAEP padding of RSAES-OAEP) and/or $m$ is even. Then textbook RSA is applied, giving $c\gets m\bmod n$. The actual ciphertext if $\tilde c\gets\min(c,n-c)$, which is one bit less than $n$. On decryption it's computed $\tilde m\gets\tilde c^d\bmod n$, then $m$ is either $\tilde m$ or $n-\tilde m$ whichever matches the $m<n/2$ and/or $m$ even criteria. Then $M$ is extracted from $m$ as usual.

It's possible to save more bits, but AFAIK all the techniques that do have expected computational cost that grows exponentially with the number of bits saved past the first one.

Is there a way to RSA-decrypt a 48 byte ciphertext with a 2048-bit private key.

No. It's not possible to save that much space in an RSA cryptogram.

Maksym Shcherban avatar
sv flag
Thank you for the detailed explanation.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.