10
$\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$

migrated from security.stackexchange.com Dec 6 '16 at 7:45

This question came from our site for information security professionals.

  • $\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 '16 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 '16 at 9:52
  • $\begingroup$ @SEJPM The only problem with RSA-KEM that is that I find it impractical to use a modulus-long random. I find it more practical to use a random number of length k - 1 where k is the size of the size of the modulus in bytes. RSA is usually defined on bytes (i.e. including the internal I2OSP) in crypto libraries and generating a very large random number up to a certain size is cumbersome as well. Yeah, I've "heard of it" :P $\endgroup$ – Maarten Bodewes Dec 6 '16 at 10:12
15
$\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.

$\endgroup$
  • 2
    $\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 '17 at 14:20
  • 2
    $\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 of course, regardless iof 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 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy