7
$\begingroup$

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!

$\endgroup$

2 Answers 2

3
$\begingroup$

An RSA PSS signature of either type provides assurance both that a message and a salt were sent that hash to a particular value (essentially either $H(r||m)$ or $H(r||H(m))$) AND that the value of the salt used was $r$.

This means that I can swap out messages if the messages do not change the hash value, but I cannot swap out salt values due to the second piece of assurance. Now note that $H(m)=H(m')\Rightarrow H(r||H(m))=H(r||H(m'))$ but $H(m)=H(m')\not\Rightarrow H(r||m)=H(r||m')$.

Now, suppose that I can generically produce collisions in $H$ and let $H(m)=H(m')$ be one such collision. If I as an adversary with CMA (chosen message attack) powers can induce a signer to sign message $m$ using RSASSA-PSS then I have an existential forgery by taking the signature and appending it to the message $m'$. The assurance of the signature tells the verifier that the salt $r$ was used, but the assurance that to the verifier that the appended message that hashes with $r$ to the value $H(r||H(m))$ does not prevent verification because that value is also equal to $H(r||H(m'))$.

Producing messages where $H(m)=H(m')$ does not help in RSA-PSS because it is still very likely that $H(r||m)\neq H(r||m')$. The adversary can produce collision such that $H(r||m)=H(r'||m')$, but trying to use a signature for $m$ as a signature for $m'$ will not work because the verification process will tell the verifier that the salt $r$ has been used and not the salt $r'$. Even if they can predict the value of $r$ that a signer will use, an adversary would have to produce a targeted collision such that $H(r||m)=H(r||m')$ to make a signature that can be transferred from $m$ to $m'$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, this is a great answer, too. $\endgroup$
    – whatf0xx
    Commented Feb 28, 2023 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.