7
$\begingroup$

The structure can be the following:

  • A signature (on the sha-256 of everything else).
  • RSA-encrypted random AES key (or none) and as much data as it fits into an RSA block.
  • AES-encrypted blocks with the rest of the data (or none at all).

The point is that an RSA block can hold a lot. Seems like a waste of space.

Is it worse than this?:

  • A signature (on the sha-256 of everything else)
  • RSA-encrypted random AES key
  • AES-encrypted blocks with the data
$\endgroup$
  • $\begingroup$ Welcome to crypto, Velkan. Hopefully my answer gets a bit more reviewing than it currently does. Maybe somebody else can answer as well. Unfortunately already answered questions sometimes get less attention. Wait a bit before accepting any answer. $\endgroup$ – Maarten Bodewes Dec 22 '16 at 12:03
  • $\begingroup$ @MaartenBodewes, have to implement before accepting. As for the software that I've got - the practical answer will probably be something with JWT/JWE (RFC7519, RFC7516) and without any weirdness. $\endgroup$ – Velkan Dec 22 '16 at 12:27
  • $\begingroup$ Using JSON web encryption is quite perpendicular with trying to save space - but you're the only one that can assess the situation, so. As long as accepting any answer doesn't rely on the JSON implementation; that would be weird. $\endgroup$ – Maarten Bodewes Dec 22 '16 at 12:41
  • $\begingroup$ IIUC, you are trying to use encrypt-then-sign with asymmetric crypto. Encrypt-then-sign ís reasonable with symmetric crypto. With asymmetric crypto, anyone can „steal“ the message, i.e., remove the signature and add own one. $\endgroup$ – v6ak Dec 22 '16 at 21:16
  • $\begingroup$ @v6ak, if he adds own signature then it would be the wrong signer. $\endgroup$ – Velkan Dec 23 '16 at 7:17
1
$\begingroup$

You can put in as much data into RSA as it can hold, bar the padding. The padding is required to keep RSA (provably) secure - presuming that RSA is secure itself of course.

So yes, what you are supposing is perfectly possible. It actually has a name: encryption with partial message recovery.

I found one paper that claimed that the security is may not be be provable secure, so beware that you're threading on largely uncovered ground here; there aren't any standardized schemes out there.


It may not be optimal to use current padding techniques as you would about double the randomness in the encryption scheme: once for the secure padding itself and once for the AES key. On the other hand, this is the best you can do with standardized functions libraries.

That said, the overhead of RSA-OAEP is only about 42 bytes, so for a 2048 bit RSA key and a 128 bit AES key (about the minimum key size) there would only be a static overhead of 42 + 16 = 58 bytes, leaving 256 - 58 = 198 bytes for the message itself.

If you require protection against active attacks that may alter the ciphertext you may need to include an authentication tag over the rest of the message, adding another 8 to 16 bytes for e.g. AES-GCM.


I'd propose a scheme such as this:

R = M | RSA-PSS-SHA256(Sk, M)
K = Rand(k)
r1 = s / 8 - 42 - k / 8
R1 = Sub(R, 0, r1)
R2 = Sub(R, r1)
C = RSA-OAEP(Pk, K | R1) | AES-GCM(K, R2)

Where:

  • M is the message
  • R is the signed message (using the sender's private key)
  • K is an AES key of length k bits
  • Rand is a cryptographically secure random number generator (or key generator operating in bits)
  • s is the receivers key length in bits
  • o is the OAEP overhead in bytes (using SHA-1 for the underlying MGF1)
  • r1 is the size of R1, r2 is the size of R2
  • R1 is the partial message encrypted using RSA-OAEP
  • R2 is the partial message encrypted using AES-GCM
  • Sub takes a substring of the given array and offset, and optional end offset
  • C is the resulting ciphertext, including the AES-GCM tag

The IV for AES-GCM can be left at 12 zero bytes (as the AES key gets regenerated each time anyway).


Notes:

  • if you use normal PKCS#1 signing that you leak information about the message that you encrypt. So you should use PSS padding or you should encrypt the signature as well. Above scheme uses a combination of both;
  • while you're at it you might want to look for RSA-PSS-R, which is a scheme for signatures giving message recovery, defined here and in IEEE P1363a;
  • to show a more efficient scheme, try this if you're academically inclined - it also includes a proof of security;
  • it is also possible to use RSA-PKCS#1 and AES-CBCbut beware that those are not IND_CCA secure and that you should not allow padding oracle attacks.
$\endgroup$
  • $\begingroup$ Anything missing from my answer, Velcan? $\endgroup$ – Maarten Bodewes Feb 2 '17 at 13:42

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.