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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Note that besides a direct answer, OAEP is often used within a hybrid encryption scheme where a random (data) key is encrypted, which in turn encrypts a ciphertext. In that sense OAEP can easily be converted into something that can handle almost infinite amount of data while still only adding a constant overhead (of at least the key size). $\endgroup$
    – Maarten Bodewes ♦
    Dec 6, 2016 at 8:49
  • 1
    $\begingroup$ @MaartenBodewes funfact (you probably already know but others don't): You don't need OAEP if you do hybrid encryption. Just RSA-encrypt a modulus-long random value and use the hash of it as the key. This is provably as hard as the RSA problem or breaking the used symmetric crypto. $\endgroup$
    – SEJPM
    Dec 6, 2016 at 9:52

1 Answer 1

Reset to default
33
$\begingroup$

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.

Improve this answer
$\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 that you have read and understand our privacy policy and code of conduct.