Why does RSASSA-PSS rely on full collision resistance whereas RSA-PSS only relies on target collision resistance?

This is sort-of a reply to the top answer given to this question, which states that whereas RSA-PSS, defined in terms of $H(r \ || \ M)$, only relies on target collision resistance and is secure even if MD5 is used (or at least was at the time of writing that answer), RSASSA-PSS, defined in terms of $H(r \ || \ H(m))$ is totally broken, because it relies on full collision resistance, which has been broken for MD5.

I am looking for a more in depth explanation for this. In particular, I want to understand how performing this pre-hash means the signature relies on the full collision resistance. Ideally, I would like an answer that looks like a sketched security proof, showing that having access to an oracle that can produce hash collisions can allow me to break RSASSA-PSS but not RSA-PSS. I understand that that's not how the problem will end up looking, but that's the type of explanation that would really help me. Thanks!

In RSASSA-PSS signature verification, the message to verify is used only as input to EMSA-PSS-VERIFY. And then $M$ is only used to check it's length is small enough for hashing (step 1), and to compute $\mathrm{mHash}=\operatorname{Hash}(M)$ (step 2).

Using only this observation, we know we can turn any "oracle that can produce hash collisions" into a break the EUF-CMA property of RSASSA-PSS, as follows:

• use the collision-producing oracle to obtain a hash collision, that is two messages $M$ and $M'$ with $M\ne M'$, length small enough to be hashed, and $\operatorname{Hash}(M)=\operatorname{Hash}(M')$.
• in the EUF-CMA experiment
  • get and ignore the public key
  • submit $M$ for signature and obtain signature $S$
  • output $M'$ and $S$

This wins the EUF-CMA experiment, because $M'$ and $S$ will verify against the public key, because signature verification will do the same thing as it would do when it verifies $M$ and $S$ against the public key, except for how it obtains the same $\mathrm{mHash}$ at step 2 of EMSA-PSS-VERIFY.

Contrast this with RSA-PSS in the P1363a proposal. In the verification, message $M$ enters $G(“\operatorname{p1363-emsa-pss-make-w}”,seed,M)[wLen]$, where $G$ is a mask generation function, which will internally compute $\operatorname{Hash}(“\operatorname{p1363-emsa-pss-make-w}”\mathbin\|seed\mathbin\|M)$. To transpose the above attack, we needs messages $M$ and $M'$ with $$\operatorname{Hash}(“\operatorname{p1363-emsa-pss-make-w}”\mathbin\|seed\mathbin\|M)=\\\operatorname{Hash}(“\operatorname{p1363-emsa-pss-make-w}”\mathbin\|seed\mathbin\|M')\ \ \ $$ where $seed$ is "a fresh, random octet string, having 20 octets" generated at signature time, and thus not known to an attacker until they obtain the signature $S$. That requires different collision-producing oracle. That could be

1. one that produces two distinct messages $M$ and $M'$ such that for a sizable proportion of random $seed$, the above relation holds.
2. or one that produces a message $M$, then accepts $seed$ obtained from the signature of $M$, then with sizable probability produces a message $M'\ne M$ such that the above relation holds.

Neither of these two kinds of different collision-producing oracle is entirely unthinkable, but they are not the vanilla kind used in the first attack. And hashes as we have seen them failing collision (or chosen-prefix collision), MD5 and SHA-1 being prime examples, have not been attacked in the manner of 1 (which seems to require finding messages $M$ and $M'$ that absorb earlier state changes) or 2 (which seems akin to breaking second-preimage resistance).

If we consider the prefix $“\operatorname{p1363-emsa-pss-make-w}”\mathbin\|seed$ to be the key $K$ of a function $F_K(M)$, the property that the collision-producing oracle would need to break is target collision resistance as defined by Bellare and Rogaway in Collision Resistant Hashing: Towards Making UOWHFs Practical (in proceedings of Crypto 1997) .

There are good reasons for the change that was made in RSASSA-PSS. In particular, when signature is performed in a constrained security device like a Smart Card or HSM, the hashing can be conveniently offloaded to the host of the device.

I don't know any instance of successful attack on a deployed system using RSASSA-PSS, much less one using the collision property of the hash.