Why does PSS produce an EM message that's almost as long as the modulus?

Question

I try to understand the reasons behind the design of PSS scheme for RSA. Why is the length of the EM message (that is, the result of PSS transformation just before signing) equals approximately to the size of the modulus? Why PSS does not use a last call to a hash function (for instance SHA-256) so as to reduce the size of the resulting element before performing the exponentiation?

Answer 1

Why PSS does not use a last call to a hash function (for instance SHA-256) so as to reduce the size of the resulting element before performing the exponentiation?

There's a radical reason why: it would no longer be possible to verify the signature, because hashing is irreversible, and prevents PSS verification to work. The present section of this answer deals exclusively with that issue.

In normal RSASSA-PSS, the signing of $M$ use a random $\mathit{salt}$ to produce the padded message $\mathit{EM}$ as follows

It is then applied to $\mathit{EM}$ the RSA private-key function $x\mapsto x^d\bmod N$, yielding the signature (for simplification I ignore conversions between octet strings and integers).

Verification procedure is

1. Apply the RSA public key function $x\mapsto x^e\bmod N$ to the signature, yielding $\mathit{EM}$.
2. Check a few bit(s) of $\mathit{EM}$ on the left (not in the drawing), and the bc octet on the right.
3. Extract $H$ from $\mathit{EM}$.
4. Apply MGF to $H$.
5. By inverting the two arrows marked with a pink dot, compute $\mathit{DB}$.
6. Check $\text{padding}_2$ is all-zero in $\mathit{DB}$
7. Extract $\mathit{salt}$ from $\mathit{DB}$.
8. Compute the hash of the alleged message $M$ (expected to match the true $M$), yielding alleged $\mathit{mHash}$.
9. Form the alleged $M'$ from the alleged $\mathit{mHash}$ and extracted $\mathit{salt}$.
10. Hash that alleged $M'$, yielding the alleged $H$.
11. Check that the alleged $H$ is equal to the $H$ extracted from $\mathit{EM}$.

If $\mathit{EM}$ had been further hashed as proposed in the question, that verification procedure could not take place, because the verifier does not initially know $\mathit{salt}$, and can thus not compute $\mathit{EM}$ in the forward direction then hash it!

This reasoning also applies to hashing de-randomized RSASSA-PSS, because the verifier does not hold the private key (or other secret material) used by the signer to deterministically produce $\mathit{salt}$.

---

Why does PSS produce an EM message that's almost as long as the modulus?

A signature of the form $(\operatorname{SHA-256}(\mathit{EM})^d\bmod N\,)\mathbin\|salt$ (as suggested in comment) would be verifiable. However, the small width of $\operatorname{SHA-256}$ compared to that for the public modulus $N$ would cause a security issue:

• The scheme would be insecure at least for some common parameters (as illustrated for small RSA public exponent $e$ in that other answer, with reference to Poncho's attack)
• Security would not be demonstrably reducible to the RSA problem, as proven (but not explained) by the previous fact. The underlying issue is essentially that the RSA problem is to efficiently invert the public-key function $x\mapsto x^e\bmod N$ for random $x$ with $0\le x<N$, but breaking the signature scheme using 256-bit padding only requires inverting the public-key function $x\mapsto x^e\bmod N$ for random $x$ with $0\le x<N$ and $x^e\bmod N\,<2^{256}$. The last inequality reduces the space of $x$ by a large factor (for $\log_2(N)\approx2048$, the size of the set of candidate $x$ is reduced by a factor of $2^{\approx1792}$).

With $\mathit{salt}$ chosen randomly by the signer, or as a deterministic secret function of the message, I see no attack working with large $e$. However if $\mathit{salt}$ was fixed or a public function of the message (in which case $\mathit{salt}$ needs not be appended), there is an existential forgery under chosen message attack (that is allowing to obtain a message/signature pair by asking for signature of other messages to a signing oracle). That attack is essentially the signature version of Y. Desmedt and A. M. Odlyzko: A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, in proceedings of Crypto 1985. A modern re-exposition is in section 3 of Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi and Ralf-Philipp Weinmann: Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures in proceedings of Crypto 2009 then Journal of Cryptology, 2016.

Answer 2

To prove that, for a generic hash function, forging PSS signatures is not much easier than computing arbitrary $e^\mathit{th}$ roots modulo a large composite of unknown factorization, we need to grant the attacker, who is trying to compute $e^\mathit{th}$ roots, oracle access to a forger for a signature scheme that uses the entire set of residue classes $\mathbb Z/n\mathbb Z$. That way, any attack enabling forgery also implies way to solve the RSA problem at only slightly more computational cost than forgery.

If we granted the attacker access to a much more limited signature scheme that only revealed $e^\mathit{th}$ roots of a very small subset of possible residue classes, then an attack on that would not necessarily imply an easy way to solve the RSA problem.

And there are pitfalls with signature schemes involving subsets of the residue classes: e.g., if a signature on a message $m$ is defined to be an integer $s$ with $s^3 \equiv H(m) \pmod n,$ you may be tempted to test the similar-looking criterion $(s^3 \bmod n) \equiv H(m) \pmod{2^{256}}.$ Although $e = 3$ is a good sensible choice for near-fastest verification in a well-designed signature scheme (only $e = 2$ with Rabin–Williams will beat it), this modified criterion gives the adversary leeway to find a cube root by varying the higher-order bits of $s$ until they get an integer perfect cube whose low 256 bits happen to coincide with $H(m)$ for some chosen $m$. Our friend poncho here sketched a similar attack on a variation on this theme several years ago.

This doesn't mean that a variant of RSA-PSS using a short hash would be insecure: only that we don't have confidence it can't be much easier than solving the RSA problem in general. Compare, for example, Rabin–Williams, which can't be much easier than factoring the modulus—but we don't discard RSA-PSS simply because we haven't shown a reduction of the RSA problem to factorization. For a similar example, see my proposed not-quite reduction of RSAP-KEM to factorization.

That said, having the security reduction helps cryptanalysts to focus their attention on a small number of problems—the RSA problem, factorization—for a large number of cryptosystems, instead of having to divide it among potentially much easier problems for each cryptosystem like RSASSA-PKCS1-v1_5, of which naive implementations may be vulnerable to the low-exponent attack I described above. The security reduction guarantees that there isn't any much easier attack on the specific cryptosystem, so the cryptanalyst's attention might as well be focused on the general problem.