3
$\begingroup$

As you may know, PKCS#1 defines two different padding in it's v1.5 : one for signature and one for encryption. Here they are :

enter image description here

The middle part is refered as PS in the standard.

There is only one thing bothering me : why does PS differ between signature and encryption ? I can't see any reason ti fixe PS to a '0xFF' string for both padding.

$\endgroup$
  • $\begingroup$ To deterministically distinguish between signature and encryption padding ? $\endgroup$ – Ruggero Jul 30 '18 at 9:54
  • $\begingroup$ @Ruggero The second byte is enough to distinguish between signature and encryption (01 for signature, 02 for encryption) $\endgroup$ – Faulst Jul 30 '18 at 10:57
  • $\begingroup$ "Why"'s are always hard but in this case I think it will be something like: "because signature generation doesn't require non-deterministic behavior and it is nice when a random number generator isn't required to implement an algorithm." Note that the bytes are not just non-zero: they need to be random in the range [1,256). $\endgroup$ – Maarten Bodewes Jul 30 '18 at 11:40
  • $\begingroup$ @MaartenBodewes I hadn't though about the need of a non-deterministic behavior for RSA encryption. It seems like a very reasonable reason, thanks ! $\endgroup$ – Faulst Jul 30 '18 at 12:30
  • $\begingroup$ The description above seems to have been made for the unpadding scheme, which doesn't need to test the randomness of the non-zero bytes. So it doesn't mention the RNG. $\endgroup$ – Maarten Bodewes Jul 30 '18 at 12:33
3
$\begingroup$

The 01 and 02 valued bytes before the PS are used for domain separation; each scheme has it's own unique value that way.


For a generic cipher it is required that the method is non-deterministic. The reason is simple: otherwise you would be able to identify which messages are identical, as they would result in identical ciphertext:

$$E_{pk}(p) = E_{pk}(p') \iff p = p'$$

In other words: repetition of the ciphertext shows to an adversary that the plaintext is identical as well; absence of identical ciphertext likewise shows that no plaintext messages were repeated. So obviously this does not result in a cipher that is resilient against chosen plaintext attacks.


Non-determinism is not a strict requirement for digital signatures, even though many of such schemes are indeed non-deterministic. Examples of non-deterministic schemes are ECDSA and RSA-PSS. The latter has been defined in version 2.1 of the PKCS#1 standard referenced in the question.

The submission to the IEEE 1363 workgroup called "PSS: Provably Secure Encoding Method for Digital Signatures" shows that a random seed can be used to tighten the security proof for PSS and that it allows for weaker assumptions on the security of the mask generation function that is used within PSS. But it also states that PSS remains provable secure (assuming the RSA cryptosystem is secure) even if the random number generator fails or if the seed is provided by an adversary.


In the end random number generation is not required for signature generation. The fact that an RSA signature can be generated without relying on a cryptographically secure random number generator is certainly an advantage; it will speed up computation and it doesn't rely on a resource that may need to block until entropy becomes available.

$\endgroup$
  • $\begingroup$ Nit: PKCS1 added SSA-PSS in 2.1, but ES-OAEP in 2.0. $\endgroup$ – dave_thompson_085 Aug 1 '18 at 0:49
  • $\begingroup$ D'oh, I just read the PSS proposal where that is stated, thanks. Off-by 0.1 error is common among developers. $\endgroup$ – Maarten Bodewes Aug 1 '18 at 1:26
  • 2
    $\begingroup$ This answer correct, but it is missing one important point. It is actually NOT secure to have random values in PKCS#1V1.5 padded signatures, otherwise signatures could be forged via bleichenbacher's e=3 attack. See blog.filippo.io/… to see what happens when signature verification implementations forget to assert that those bytes are actually 0xFF. $\endgroup$ – swolfe Sep 17 '18 at 23:39
  • $\begingroup$ @swolfe That's good enough to merit a separate answer in my opinion. Cutting my own throat here :P Otherwise, feel free to edit it in. $\endgroup$ – Maarten Bodewes Sep 17 '18 at 23:58
  • $\begingroup$ @maarten Yeah, your probably right. I turned my comment into a separate answer. cheers! $\endgroup$ – swolfe Sep 18 '18 at 0:31
4
$\begingroup$

Maarten Bodewes answer is correct, but it is missing one important point.

It is actually NOT secure to have randomness in PKCS#1V1.5 padded signatures, otherwise signatures could be forged via bleichenbacher's e=3 attack.

Take a look at https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/ to see what happens when signature verification implementations forget to assert that those bytes are actually 0xFF.

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