Why did OAEP change from PKCS#1 v2.0 and v2.1?

Question

In PKCS#1 v2.1 the OAEP output is prepending with a null byte. Quoting RFC 3447,

  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 PKCS#1 v2.0 (as defined in RFC 2437):

   11. Let EM = maskedSeed || maskedDB.

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

Answer 1

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.