1
$\begingroup$

I understand that RSASSA-PSS is not deterministic. But I see that in message encoding, MGF and SHA functions are deterministic. So even if I keep default salt length, it produces different signature.

Where is the randomness introduced?

$\endgroup$
  • 1
    $\begingroup$ Just extend the name: Probabilistic Signature Scheme $\endgroup$ – kelalaka Sep 5 '19 at 15:11
4
$\begingroup$

You aren't using the same salt.

The randomness is introduced with the salt: it is generated randomly. The input to the MGF is calculated from the hash and the salt. Thus, if you sign the same message twice, you get different signatures, because the salt is different each time. For the details, see PKCS#1 (RFC 8017) §9.1.1.

There are only two ways to use the same salt with any sane implementation of RSA-PSS.

  • If you choose a salt length of 0, then the salt is always the same, and PSS becomes deterministic.
  • If you can set the state of the RNG, using the same message with the same RNG state will result in the same signature.

Otherwise, if the salt length is $n$, there are $2^{8n}$ possible salts, and the probability that two given signatures would use the same salt is $2^{-8n}$, which is negligible (unless $n$ is very small, but in practice it isn't).

The default salt length is the length of the hash in most implementations. More precisely, most implementations use the maximum possible salt length, which is usually the hash length but can be shorter when using a large hash with a small key (the salt plus the hash plus two bytes must fit in the key size in bytes, so a 1024-bit key with SHA-512 only leaves room for a 30-byte salt). The general rationale is that if you wanted your signature to be deterministic, you'd use PKCS#1v1.5; and if you're going to use a salt, the cost of making it longer is negligible, so you might as well make it maximum-length.

On why you'd want a signature algorithm to be non-deterministic, see Why use randomness in digital signature algorithms? (which mostly covers RSA-PSS). On the salt length in RSA-PSS, see RSA-PSS salt size

| improve this answer | |
$\endgroup$
  • $\begingroup$ Maybe even more explicitly state that the salt length doesn't determine the salt value. Yes, that seems to go without saying, but here we are... Also note that implementations of RSA-PSS are likely to retrieve the default secure RNG, although some implementations (Java's JCA) do allow you to set another RNG. $\endgroup$ – Maarten Bodewes Sep 5 '19 at 19:17

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.