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

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?

• That's not just PSS; the whole idea of RSA padding modes is to expand the message/hash to the size of the modulus (or at least about the same size). I'll leave it to the more mathematical inclined to explain the precise attacks possible though. – Maarten Bodewes Sep 13 '17 at 21:00

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.

• Thank you for your answer. Why is it not possible to produce a variant of PSS where tha salt is provided along with the signature? – Dingo13 Sep 14 '17 at 7:31
• If the random element is provided, it could be hashed with the message. – Dingo13 Sep 14 '17 at 7:44

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.

• There is a generic attack against RSA padding $M\to P(M)=\text{SHA-256}(F(M))$ that is not restricted to small $e$: we find messages $M_j$ such that $P(M_j)$ are smooth (except perhaps two large primes), and use the techniques in the attack that found Squeamish Ossifrage as the Magic Words in order to form a multiplicative relation modulo $N$ between some of the $P(M_j)$. That leads to an existential forgery. However, as explained in my answer, in order for $M\to P(M)$ to work at all as RSA padding, $M\to F(M)$ much be a public function! – fgrieu Sep 14 '17 at 7:04
• @fgrieu If $F$ is public and we hash $F(M)$, this means that we could provide the random salt with the signature, that is a triplet $(M,salt,signature)$. – Dingo13 Sep 14 '17 at 8:08
• @Dingo13: Yes, that allows verification. But the insufficient width of SHA-256 becomes the next serious issue, for at least the reason in the answer; and then some that I explain in the above comment (cryptically, but the intended audience was the author of the answer), and now at the end of my answer. – fgrieu Sep 14 '17 at 8:31
• @fgrieu Finally, I have not completely understood your first comment. Could you explain what is the function $F$? Could you also give examples of multiplicative relations between the smoothed $P(M_j)$? Is this outlined problem related to the small output size of SHA-256? Or we could find multiplicative relations even for large hash ouput size? Thank you again. – Dingo13 Sep 18 '17 at 14:56
• @Dingo13: here, the function $F$ is such that $F(M)$ is $M$ after RSASSA-PSS padding with salt fixed or salt a public function of $M$ (it seems is this what this answer assumes). For the rest of the attack, see the last reference in my answer. Feasibility depends decisively on the width of the hash, since it conditions the proportion of smooth-enough $P(M)$. The attack is appreciably but not decisively easier for low $e$. It is essentially independent of the width of $N$. – fgrieu Sep 18 '17 at 15:23