# Which padding is used for sha256WithRSAEncryption (1.2.840.113549.1.1.11), deterministic or random?

Questions

1. Is the only way to know which padding was used is to know the context of how sha256WithRSAEncryption was used (that PS is 0xFF when signing, and random non-zero when encrypting)?
2. Is there an explicit documentation stating that, or is a broad understanding of RFC 8017 the only way?

Background

While analyzing some code producing a CMS I reviewed RFC 5652 section 5.3 in particular digestAlgorithm, signatureAlgorithm, and signature. I have as an example 2.16.840.1.101.3.4.2.1 sha-256 (NIST Algorithm), 1.2.840.113549.1.1.11 sha256WithRSAEncryption (PKCS #1), and

00000000  64 f4 82 71 ac 8d 6a ab  51 85 69 59 f3 d7 ab 2b  |d..q..j.Q.iY...+|
00000010  ea 95 0b 11 fe 9a 46 fa  73 a4 c7 41 4f 13 79 82  |......F.s..AO.y.|
00000020  0e 34 52 02 23 b4 13 b2  7b ae 56 d8 3a 4a cc 96  |.4R.#...{.V.:J..|
00000030  27 ee b8 62 2a ae 83 2f  08 ef 3b d0 8a 17 e4 63  |'..b*../..;....c|
00000040  ca 49 04 48 05 e9 7d ac  d5 58 50 28 5e 16 37 08  |.I.H..}..XP(^.7.|
00000050  db e8 e6 a7 5b c4 0f b2  d2 42 cf c6 99 16 f2 26  |....[....B.....&|
00000060  90 f8 03 51 a7 7c e2 3f  87 a6 ef d2 ca 40 e6 61  |...Q.|.?.....@.a|
00000070  74 4d 64 7d 07 f8 01 42  c3 8f 3a fa 53 b6 30 b5  |tMd}...B..:.S.0.|
00000080  60 c4 94 54 60 7d 3c a0  fd 19 45 d3 d5 55 f8 e6  |..T}<...E..U..|
00000090  36 d8 55 06 84 c0 6f 57  a7 32 cd 71 f9 35 ab b3  |6.U...oW.2.q.5..|
000000a0  a2 20 7a 46 99 73 66 21  0b 50 7b 0c 43 59 6b b6  |. zF.sf!.P{.CYk.|
000000b0  b5 94 e3 b0 92 22 58 4f  a4 6b 3a 16 f2 81 11 b5  |....."XO.k:.....|
000000c0  e0 7b 41 9a 4b ab 38 39  53 6e 9f 53 b0 b7 c4 95  |.{A.K.89Sn.S....|
000000d0  cf 68 3d 48 30 9c a7 71  a8 df 62 5d e5 16 7c 6d  |.h=H0..q..b]..|m|
000000e0  88 cd eb 07 56 53 66 53  a7 78 f9 80 27 39 b2 74  |....VSfS.x..'9.t|
000000f0  58 08 15 e5 98 e3 dd 8f  fe 25 89 c1 85 1b a5 4e  |X........%.....N|


sha256WithRSAEncryption has an authoritative definition in RFC 8017 section A.2.4 RSASSA-PKCS1-v1_5. It further refers to EMSA-PKCS1-V1_5-ENCODE, which is defined in section 9.2 having the same name. Section 9.2. step 4 says

Generate an octet string PS consisting of emLen - tLen - 3 octets with hexadecimal value 0xff. The length of PS will be at least 8 octets.

whereas section 7.2. RSAES-PKCS1-v1_5 says

Generate an octet string PS of length k - mLen - 3 consisting of pseudo-randomly generated nonzero octets. The length of PS will be at least eight octets.

for encryption operations.

The signature decrypts as:

00000000  00 01 ff ff ff ff ff ff  ff ff ff ff ff ff ff ff  |................|
00000010  ff ff ff ff ff ff ff ff  ff ff ff ff ff ff ff ff  |................|
00000020  ff ff ff ff ff ff ff ff  ff ff ff ff ff ff ff ff  |................|
00000030  ff ff ff ff ff ff ff ff  ff ff ff ff ff ff ff ff  |................|
00000040  ff ff ff ff ff ff ff ff  ff ff ff ff ff ff ff ff  |................|
00000050  ff ff ff ff ff ff ff ff  ff ff ff ff ff ff ff ff  |................|
00000060  ff ff ff ff ff ff ff ff  ff ff ff ff ff ff ff ff  |................|
00000070  ff ff ff ff ff ff ff ff  ff ff ff ff ff ff ff ff  |................|
00000080  ff ff ff ff ff ff ff ff  ff ff ff ff ff ff ff ff  |................|
00000090  ff ff ff ff ff ff ff ff  ff ff ff ff ff ff ff ff  |................|
000000a0  ff ff ff ff ff ff ff ff  ff ff ff ff ff ff ff ff  |................|
000000b0  ff ff ff ff ff ff ff ff  ff ff ff ff ff ff ff ff  |................|
000000c0  ff ff ff ff ff ff ff ff  ff ff ff ff 00 30 31 30  |.............010|
000000d0  0d 06 09 60 86 48 01 65  03 04 02 01 05 00 04 20  |....H.e....... |
000000e0  88 b1 44 7c ac 6b 76 4f  fc 4c 35 76 12 a0 99 f2  |..D|.kvO.L5v....|
000000f0  a5 b4 dc 12 9a 00 cf 05  87 78 81 5c 93 97 b7 07  |.........x.\....|


and should be read as 0x00 || 0x01 || PS || 0x00 || T, where T is:

SEQUENCE (2 elem)
SEQUENCE (2 elem)
OBJECT IDENTIFIER 2.16.840.1.101.3.4.2.1 sha-256 (NIST Algorithm)
NULL
OCTET STRING (32 byte) 88B1447CAC6B764FFC4C357612A099F2A5B4DC129A00CF058778815C9397B707


Notes

-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAuoe/0wkWa917Qyss+OAE
4hZktETDUOtilbjxH8DdYL+lbyc7SduwMTDS4XpPa3uRrQHlrRV9/1tmAOfVC7jG
O+1aEfHSPCWxmpN5AHQF7r1ePEbyR/MB2CzX3lJmNbskCSgxmol78SRkkuZkGxmU
mgqNxOu74LrZta9EAQEHquCigZxzSTU7exLfpH2wq/QhTCmm3DP3d9BhDgzdz7B5
/FGAh3lp5WBeaUyfz8LLDtaXKUZ3zBYvG83gbbGYjqobQN8GWOu8BgyXAePrtroh
UXgRNRCNeSdm923YM1tu1y0K67sYAYtCt6MUjjNWvciqm11hlqNnSFxe9/ZHmXOC
2QIDAQAB
-----END PUBLIC KEY-----


It uses deterministic padding, i.e. padding with FF octets, finalized by a single 00 valued byte. So it is indeed RSASSA-PKCS1-v1_5 which uses EMSA-PKCS1-V1_5-ENCODE. Don't be fooled by the reference to RSA encryption in the OID for sha256WithRSAEncryption. That simply points to the modular exponentiation - in this case with the private key.

PKCS#1 versions up to 1.5 treated modular exponentiation as "encryption with the private key". That was changed in PKCS#1 v2.0 and subsequent versions where they have deliberately pointed out that the signature primitives RSASP1 and RSASV1 are different from the encryption primitives RSAEP and RSADP even though they are all based on modular exponentiation.

Unfortunately, the PKCS#1 v1.5 signature scheme and OID's predate that, so that makes it seem that the signature schemes have something to do with encryption or the padding used for encryption. They don't, other than that they obviously share many properties.

Do note that the configuration of the signature scheme should be known beforehand. So the properties should not be derived from the signature itself (after modular exponentiation). And no signature scheme should use padding designed for - and only specified for - encryption.

• Indeed: sha256WithRSAEncryption` is not about RSA encryption. It is about RSA signature, deterministic and ad-hoc (but still secure as far as we know). – fgrieu Jan 2 '20 at 8:26
• "...the PKCS#1 v1.5 signature scheme and OID's predate..." that is the crux of the answer. It was what I assumed. – Jason Pyeron Jan 3 '20 at 4:45