9
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 31, 2023 at 13:23

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$ Mar 30, 2023 at 23:56
  • $\begingroup$ 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? $\endgroup$ Mar 31, 2023 at 12:23
  • $\begingroup$ Ping :) I've added P.S. to the post. $\endgroup$ Apr 28, 2023 at 21:12
6
$\begingroup$

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.

$\endgroup$
2
  • 5
    $\begingroup$ 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$). $\endgroup$
    – fgrieu
    Mar 30, 2023 at 11:59
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 30, 2023 at 12:11
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for the detailed explanation. $\endgroup$ Mar 30, 2023 at 12:04

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.