9
$\begingroup$

In PKCS1 v2.1 the OAEP output is prepending with a null byte. Quoting RFC3447,

  i. Concatenate a single octet with hexadecimal value 0x00,
     maskedSeed, and maskedDB to form an encoded message EM of
     length k octets as

        EM = 0x00 || maskedSeed || maskedDB.

In PKCS1 v2.0 (as defined in RFC2437):

   11. Let EM = maskedSeed || maskedDB.

So in PKCS1 v2.1 you prepend a null byte and in PKCS1 v2.0 you don't. What technical difference does that change (and possibly others) create between the two versions of the standard?

$\endgroup$
  • 4
    $\begingroup$ I do not know why that editorial change was made (hence I can't answer), but it does not change the value that is ultimately passed to the RSA exponentiation primitive: notice that zeroes on the left of a bytestring converted to integer by big-endian convention (as in PKCS#1) do not change the resulting number. $\endgroup$ – fgrieu Sep 16 '16 at 17:43
  • 3
    $\begingroup$ It was explained in the previous rfc - tools.ietf.org/html/rfc2313#section-8.1 : The leading 00 octet ensures that the encryption block, converted to an integer, is less than the modulus.. I agree the question should be reopened. $\endgroup$ – kludg Sep 17 '16 at 9:36
  • 3
    $\begingroup$ @kludg A leading zero octet doesn't automatically make the encoded integer less than the modulus. The important change was actually from Let dbMask = MGF(seed, emLen-hLen) to Let dbMask = MGF(seed, k - hLen - 1) $\endgroup$ – Artjom B. Sep 17 '16 at 10:16
  • 1
    $\begingroup$ The leading 00 does not change the value of the encoded integer. If after adding the 00, the byte-string remains with no more bits than in the modulus, then the encoded integer is less than the modulus. In my opinion, what maters to the question (and what I do not rule out) is if other changes (like definition of dbMask, or the length change caused by the leading 00) modify the value of the encoded integer between the two RFCs (assuming identical random to form the encoded integers). $\endgroup$ – fgrieu Sep 18 '16 at 6:26
  • 1
    $\begingroup$ @ArtjomB: that's not really a change; emlen in 2.0 is computed as k -- 1, so 2.0 makes both db and dbmask and thus maskeddb length k-1-hlen while 2.1 makes them k-hlen-1. +@fgrieu: And seed, seedmask, maskedseed are all hlen, so the total is k-1 (whitened and probably nonzero) octets in 2.0, or k octets with the first zero in 2.1 -- no difference after OS2I. $\endgroup$ – dave_thompson_085 Sep 18 '16 at 10:46
5
$\begingroup$

The answer is relatively simple, but I'll expand on the details of the changes from PKCS#1 2.0 to 2.1 in two additional sections below this answer.

On the padding with the zero valued byte

The I2OSP function - used during decryption - converts an integer to a statically sized, unsigned, big endian octet string or byte array. This function will always generate a number of $k$ octets as it is used, automatically left-padding with zeros. The OS2IP function is the reverse function.

However, as it is defined for PKCS#1 v2.0 / OAEP encoding, it will always operate over an octet string of $k - 1$ bytes. This isn't nicely symmetrical, and it doesn't clearly communicate to the reader that the top eight bits of the resulting number should always be set to zero. The result of the OS2IP function for $X_{k-1} || X_{k-2}... || X_0$ and $00 || X_{k-1} || X_{k-2}... || X_0$ are identical, because the big endian number is unsigned; even if the most significant bit is set, it doesn't get interpreted as the sign bit for a two complement number.

When implementing it in a language such as Java, the new description does make it clear that you can simply make sure that the encoding starts with 00 and then convert to a number using a converter that expects a signed value. In general it is also better to always operate on numbers with a known encoded size.

On the padding size

This section explains why the padding with the zero byte is required at all.

In PKCS#1 v2.0 the encoding operation for the encryption operation in 7.1.1 is mentioned in its own section 9.1.1.1 (not 9.1.1.2, I'll notify the author of the bug). In 2.1 it seems that this created too much complexity and the encoding operation has been integrated into the description of RSA OAEP encryption in section 7.1.1.

It is a requirement for the padding is to create an octet string (or byte array) that can fit into an integer of size $kLen-7$ or $kLen-8$ bits where $kLen$ is the key size in bits (not mentioned in RFC 2437). RSA signature generation already uses a padding of $kLen-7$ bits so RSA encryption uses a padding that is $kLen-8$ bits. The reason why the padding must be smaller than the key size in octets is because RSA is defined for any key size, including a key size of, for instance, $kLen=1025$ bits. In that case the size of the octet strings will be $k=129$ bytes rather than $k=128$ bytes.

However, the integer calculations are still using a 1025 bit modulus. If one of the first 7 bits of the first bit would be set then the input of the calculation would be higher than the modulus, so the modular operation with the private exponent would not result in the same octet string.

Note that because of these kind of complexities many RSA implementations only handle key sizes or an 8 bit or 32 bit increment. It is strongly recommended to use a key size of 1024 bits or (preferably) higher with a key size of the form $2^x$ (e.g. $2048$) or $2^x + x^{x-1}$ (e.g. $2048 + 1024 = 3072$).

On the encoding function

This section explains another difference between 2.0 and 2.1: the use of a separate encoding function.

There was also a comment by Artjom B about the size of $dbMask$. The size of $dbMask$ is not different for the different descriptions of the encoding scheme. So this section should be seen as a supplement to the answer.

RSA signature generation already uses a padding of $kLen-7$ bits so RSA encryption uses a padding that is $kLen-8$ bits. This means that the result of the encoding must be an octet string of one octet less as the key size / modulus size in octets. This is why the encoding function is called using $k-1$:

EM = EME-OAEP-ENCODE (M, P, k-1)

and if you look carefully then you'll see that $emLen = k-1$ in the algorithms of EME-OAEP-ENCODE, for instance the message length should be $emLen-1-2hLen$.

Now in PKCS#1 v2.1 the EME-OAEP-ENCODE is missing; it has been integrated in the description of OAEP encryption itself. This has the disadvantage that other encryption schemes (for instance those based on ElGamal encryption) cannot directly reference the encoding operation within the standard. That is however not a main objective for a standard that describes RSA. On the other hand the standard is more clear because it doesn't need to mention $emLen$ at all; it can directly reference $k$, possibly avoiding off-by-one errors in implementations. Furthermore, it simplifies reading the description of OAEP, as readers do not have to switch back and forth between 7.1.1 and 9.1.1.1.

$\endgroup$

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.