22
$\begingroup$

OAEP is an important technique used to strengthen RSA. However, using OAEP (or any technique that adds randomness) reduces the size of plaintexts that can be encrypted.

Assume for instance that OAEP is using a 160-bit seed and a hash function that produces a 256-bit value. In that case, how large a plaintext can be handled when RSA is used with 2048-bit key?

$\endgroup$
1
  • 1
    $\begingroup$ You don't need OAEP if you do hybrid encryption. Just use RSA-KEM: RSA-encrypt a modulus-long random value and use a key derivation function or hash to derive a symmetric key used to encrypt the message itself. $\endgroup$
    – SEJPM
    Dec 6, 2016 at 9:52

1 Answer 1

34
$\begingroup$

Important note: usually OAEP is only used to encrypt a random symmetric key, which is then used to encrypt a plaintext message; this is called a hybrid cryptosystem. Repeated use of OAEP would require more bytes and would increase the processing overhead as well. Basically a 32 byte / 256 bit symmetric key will always fit, and would allow a message of (almost) any size to be encrypted.


The input length of OAEP is directly specified in the standard:

M        message to be encrypted, an octet string of length mLen,
         where mLen <= k - 2hLen - 2

or simply mLen = k - 2 * hLen - 2 if we want to calculate the maximum message size.

Where:

  • k - length in octets of the RSA modulus n
  • hLen - output length in octets of hash function Hash
  • mLen - length in octets of a message M

The key size of RSA is defined as the number of bits within the unsigned modulus representation. So the key size is identical to the modulus size in bits.


So to complete the calculation we have to include k = ceil(kLenBits / 8) where kLenBits is the key size in bits. This can be rewritten as k = (kLenBits + 7) / 8 for integer-only calculations. However, since kLenBits is commonly limited to multiples by eight k = kLenBits / 8 usually suffices.

The same goes for hLen which is practically always the hash output in bits - say hLenBits divided by 8. From here on all calculations will be in octets / bytes.

To calculate the maximum payload of RSA OAEP we then substitute the nLen and hLen by their respective calculations (and <= by = because we're looking for the maximum):

mLen = k - 2 * hLen - 2

becomes

mLen = kLenBits / 8 - 2 * hLenBits / 8 - 2 

If we observe this we see that the amount of overhead only depends on the hashlength: 2 * hLenBits / 8 - 2. This makes it easy to write out the possibilities for SHA-1, SHA-2 and SHA-3:

\begin{array} {|l|c|c|} \hline \text{HASH} & \text{OVERHEAD} & \text{RSA 1024} & \text{RSA 2048} & \text{RSA 3072} & \text{RSA 4096} \\ \hline \operatorname{SHA-1} & 42 & 86 & 214 & 342 & 470 \\ \hline \operatorname{SHA-224} & 58 & 70 & 198 & 326 & 454 \\ \hline \operatorname{SHA-256} & 66 & 62 & 190 & 318 & 446 \\ \hline \operatorname{SHA-384} & 98 & 30 & 158 & 286 & 414 \\ \hline \operatorname{SHA-512} & 130 & \text{N/A} & 126 & 254 & 382 \\ \hline \end{array}

note that SHA-1 has an output size of 160 (or hLen = 20 in PKCS#1). Probably better to simply include the calculation in your source code if the function to calculate the maximum input size is missing from your crypto library. Of course you want to avoid 1024 bit RSA; I've added it just for when backwards compatibility is required.


Great so now we can finally fill in the numbers as kLenBits = 2048 and hLenBits = 256:

mLen = 2048 / 8 - 2 * 256 / 8 - 2 = 256 - 64 - 2 = 190

so the message has a maximum size of 190 bytes.

$\endgroup$
2
  • 3
    $\begingroup$ For PKCS#1 v1.5 padding for encryption the overhead is simply 11 bytes (three bytes static values and 8 bytes filled with random numbers 1..255). $\endgroup$
    – Maarten Bodewes
    Mar 30, 2017 at 14:20
  • 3
    $\begingroup$ But it is no longer recommendable to use PKCS#1 v1.5 encryption padding with minimum overhead: with only 64-bit randomness, it is borderline feasible to test a guess of plaintext by brute force. And regardless of overhead, we know no security reduction of PKCS#1 v1.5 encryption padding, and it is harder to implement its decryption in a way that resist padding oracle attacks, than it is with RSAES-OAEP. $\endgroup$
    – fgrieu
    Feb 28, 2019 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.