Why ISO/IEC 9796 (signature with message recovery) instead of just encrypt the short message with private key?

Question

I've had a look at “Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures” and read the very good answer https://crypto.stackexchange.com/a/17846/59673 and I understand that signature and encryption are usually different algorithms. For clarity, here I am just talking of RSA.

For long messages usually a hash is computed, padded, and then encrypted with the private key, and sent along with the message. The receiver can decrypt the signature with the public key and compare with the hash (re)computed on the message (and verify the padding integrity).

For short messages ( m < N ), what I (still) do not understand is the need of complex algorithms like ISO/IEC 9796.

Given that encryption is not the important factor but only verification is needed, the sender could encrypt the whole message with the private key (like it is normally done for the hash). The receiver decrypts the message with the public key, gets the message and implicitly verifies the sender.

Obviously textbook RSA would be subject to existential forgery (which wouldn't be a problem with formatted messages) and maybe to multiplicative forgeries. So one has to add padding, like in standard RSA.

If there are security issues on this mechanism, for what I understand they are exactly the same than for standard signature. So the only downside is that without the public key the receiver cannot get the message.

EDIT: I'va also read the answers to Why hash the message before signing it with RSA? but as stated, I am asking in case of m < N.

So, are there more reasons not to encrypt the original message + some padding?

Answer 1

I'll be taking the question as: when signing short-enough messages, why don't we simply put the message where there is the message's hash in RSA signature padding like RSASSA-PKCS1-v1_5 or RSASSA-PSS of PKCS1v2.2?

Usual RSA deterministic signature as appendix goes $M\mapsto M\mathbin\|((P(H(M)))^d\bmod N)$ where $M\mapsto P(H(M))$ is a one-way function from the message space to $[0,N)$, built from a reversible injection $P$, and a hash $H$ for the one-wayness. The proposal is to change this to $M\mapsto (P(M))^d\bmod N$. That removes the one-wayness.

We don't have a constructive argument that's secure, and it should be reason enough not to do this. Worse, the gone one-wayness had a security role: preventing turning arithmetic properties of $x\mapsto x^d\bmod N$ into attack, by preventing going from $x$ with suitable arithmetic properties and in the right subset of $[0,N)$, to message $M$ with $P(H(M))=x$ allowing exploitation of said properties.

For some padding shemes, that removal of the one-wayness is enough to allow attack. Consider RSASSA-PKCS1-v1_5 thus modified: we can obtain the signature of one message from the signature of three chosen ones, which is a break. That's detailed below.

With the modification, the signature of $m$-byte message $M$ using private key $(N,d)$ with $n$-bit $N$ is, assimilating bistrings to integers per big-endian convention $$\begin{align} \mathcal S(M)&=(\mathtt{00\,01\,FF\dots FF\,00\,XX\dots XX}\mathbin\|M)^d\bmod N\\ &=(R\cdot2^{8m}+M)^d\bmod N\end{align}$$ with some fixed public integer $R\lesssim2^{193}$, when $m=\left\lceil\displaystyle\frac n8\right\rceil-26$. For example, consider message $M$ of $m=230$ bytes signed with $n=2048$-bit (256-byte) RSA key.

Now, if we find 4 distinct $m$-byte messages $M_0$, $M_1$, $M_2$, $M_3$ with $$(R\,2^{8m}+M_0)\,(R\,2^{8m}+M_1)=(R\,2^{8m}+M_2)\,(R\,2^{8m}+M_3)\tag{1}\label{eq1}$$ then it follows that $\mathcal S(M_0)\,\mathcal S(M_1)\equiv\mathcal S(M_2)\,\mathcal S(M_3)\pmod N$, and thus $$\mathcal S(M_0)=\mathcal S(M_1)^{-1}\,\mathcal S(M_2)\,\mathcal S(M_3)\bmod N$$ which is easy to compute from $N$ and the signatures $\mathcal S(M_1)$, $\mathcal S(M_2)$, $\mathcal S(M_3)$.

We can take $$\begin{align} M_0&=R\,((2^{4m+i}+a)\,(2^{4m-i}+b)-2^{8m})\\ M_1&=R\,((2^{4m+i}+c)\,(2^{4m-i}+d)-2^{8m})\\ M_2&=R\,((2^{4m+i}+a)\,(2^{4m-i}+d)-2^{8m})\\\ M_3&=R\,((2^{4m+i}+c)\,(2^{4m-i}+b)-2^{8m})\\ \end{align}$$ which insure $\eqref{eq1}$ holds; and suitably small $i$, $|a|$, $|b|$, $|c|$, $|d|$ so that $0\le M_j<2^{8m}$. For example, $i=0$, $a=b=1$, $c=2$, $d=3$ will do.

Using that large class of messages, we can easily obtain $s$ bogus signatures from $s+3$ signatures of chosen messages. Or/and, since there's considerable freedom in the choice of the messages, we can force some application-imposed bytestring into some section of the messages, bringing that theoretical attack closer to practice. There are further classes of messages allowing other attacks.