Implementation Guidance for the PKCS #1 RSA Cryptography Specification

7.1. General recommendations

It's especially important to make sure that all values that are secret to the attacker are stored in memory buffers that have sizes determined by the public modulus.¶

For example, the private exponenents should be stored in memory buffers that have sizes determined by the public modulus value, not the numerical values of the exponents themselves.¶

Similarly, the size of the output buffer for multiplication should always be equal to the sum of buffer sizes of multiplicands. The output size of the modular reduction operation should similarly be equal to the size of the modulus and not depend on bit size of the output.¶

7.2. Montgomery ladder

For the modular exponentiation algorithm to be side-channel free every step of the calculation MUST NOT depend on the bits of the exponent. In particular, use of simple square and multiply algorithm will leak information about bits of the exponent through lack of multiplication operation in individual exponentiation steps.¶

The recommended workaround against it, is the use of the Montgomery ladder construction.¶

While that approach ensures that both the square and multiply operations are performed, the fact that the results of them are placed in different memory locations based on bits of the secret exponent will provide enough information for an attacker to recover the bits of the exponent. To counteract it, the implementation should ensure that both memory locations are accessed and updated on every step.¶

7.3. Montgomery reduction in multiplication

As multiplication operations quickly make the intermediate values in modular exponentiation large, performing a modular reduction after every multiplication or squaring operation is a common optimisation.¶

To further optimise the modular reduction, the Montgomery modular multiplication is used for performing the combined multiply-and-reduce operation. The last step of that operation is conditional on the value of the output. A side-channel free implementation should perfom the subtraction in all cases and then copy the result or the first operand of the subtraction based on sign of the result of the subtraction.¶

10.1. IRPRF

For the calculation of the random message for implicit rejection we define a Pseudo-Random Function (PRF) as follows:¶

IRPRF( KDK, label, length )¶

Input:¶

KDK the key derivation key¶

label a label making the output unique for a given KDK¶

length requested length of output in octets¶

Output: derived key, an octet string¶

Steps:¶

1. If KDK is not 32 octets long, or if length is larger than 8192 return error and stop.¶

2. The returned value is created by concatenation of subsequent calls to a SHA-256 HMAC function with the KDK as the HMAC key and following octet string as the message:¶

     P_i = I || label || bitLength
   

   ¶
3. Where the I is an iterator value encoded as two octet long big endian integer, label is the passed in label, and bitLength is the length times 8 (to represent number of bits of output) encoded as two octet big endian integer. The iterator is initialised to 0 on first call, and then incremented by 1 for every subsequent HMAC call.¶
4. The HMAC is iterated until the concatenated output is shorter than length¶
5. The output is the length left-most octets of the concatenated HMAC output¶

10.2. Implicit rejection

For implementations that cannot remove support for the PKCS #1 v1.5 padding nor provide a usage-specific API, it's possible to implement an implicit rejection algorithm as a protection measure. It should be noted that implementing it is hard, thus it's RECOMMENDED instead to disable support for PKCS #1 v1.5 padding instead.¶

To implement implicit rejection, the RSAES-PKCS1-V1_5-DECRYPT from section 7.2.2 of RFC 8017 needs to be implemented as follows:¶

1. Length checking: If the length of the ciphertext C is not k octets (or if k < 11), output "decryption error" and stop.¶

2. RSA decryption:¶

   1. Convert the ciphertext C to an integer ciphertext representative c:¶

        c = OS2IP (C).
      

      ¶

   2. Apply the RSADP decryption primitive to the RSA private key (n, d) and the ciphertext representative c to produce an integer message representative m:¶

        m = RSADP ((n, d), c).
      

      ¶

      Note: the RSADP MUST be constant-time with respect of message m.¶

      If RSADP outputs "ciphertext representative out of range" (meaning that c >= n), output "decryption error" and stop.¶

   3. Convert the message representative m to an encoded message EM of length k octets:¶

        EM = I2OSP (m, k).
      

      ¶

      Note: I2OSP MUST be constant-time with respect of m.¶

3. Derivation of alternative message¶

   1. Derive the Key Derivation Key (KDK)¶

      1. Convert the private expoent d to a string of length k octets:¶

           D = I2OSP (d, k).
         

         ¶

      2. Hash the private exponent using the SHA-256 algorithm:¶

           DH = SHA256 (D).
         

         ¶

         Note: This value MAY be cached between the decryption operations, but MUST be considered private-key equivalent.¶

      3. Use the DH as the SHA-256 HMAC key and the provided ciphertext C as the message. If the ciphertext C is not k octets long, it MUST be left padded with octets of value zero.¶

           KDK = HMAC (DH, C, SHA256).
         

         ¶

   2. Create the candidate lengths and the random message¶

      1. Use the IRPRF with key KDK, "length" as six octet label encoded with UTF-8, to generate 256 octet output. Interpret this output as 128 two octet long big-endian numbers.¶

           CL = IRPRF (KDK, "length", 256).
         

         ¶

      2. Use the IRPRF with key KDK, "message" as a seven octet label encoded with UTF-8 to generate k octet long output to be used as the alternative message:¶

           AM = IRPRF (KDK, "message", k).
         

         ¶

   3. Select the alternative length for the alternative message.¶

      Note: this must be performed in side-channel free way.¶

      1. Iterate over the 128 candidate CL lengths. For each zero out high order bits so that they have the same bit length as the maximum valid message size (k - 11).¶
      2. Select the last length that's not larger than k - 11, use 0 if none are. Save it as AL.¶

4. EME-PKCS1-v1_5 decoding: Separate the encoded message EM into an octet string PS consisting of nonzero octets and a message M as¶

     EM = 0x00 || 0x02 || PS || 0x00 || M.
   

   ¶

   If the first octet of EM does not have hexadecimal value 0x00, if the second octet of EM does not have hexadecimal value 0x02, if there is no octet with hexadecimal value 0x00 to separate PS from M, or if the length of PS is less than 8 octets, the check variable must remember if any of those checks failed. Irrespective of the check variable value, the code should also return length of message M: L. If there is no octet with hexadecimal value 0x00 to separate PS from M, then L should equal 0.¶

   Note: All those checks MUST be performed irrespective if previous checks failed or not. A common technique for that is to have a check variable that is OR-ed with the results of subsequent checks.¶

5. Decision which message to return: in case the check variable is set, the code should return the last AL octets of AM, in case the check variable is unset the code should return the last L octets of EM.¶

   Note: The decision which length to use MUST be performed in side-channel free manner. While the length of the returned message is not considered sensitive, the read memory location is. As such, when returning message M both EM and AM memory locations MUST be read.¶

14.1. Normative References

[RFC8017]

Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2", RFC 8017, DOI 10.17487/RFC8017, November 2016, <https://www.rfc-editor.org/info/rfc8017>.

14.2. Informative References

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/info/rfc2119>.