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?

  • If you would allow secure padding and then this might not have been a dupe. – Maarten Bodewes Jun 13 at 11:58
  • yes in fact I forgot to specify the padding part (I considered that implicit but better clarify I was not talking of textboox RSA) so I edited the question. anyway, I clearly stated from that start that m < N, so not a dupe. – Kzar Jun 14 at 13:31
  • The question now boils down to: For short-enough messages, why can't we put the message where there is the message's hash in RSA signature paddings like RSASSA-PKCS1-v1_5 or RSASSA-PSS?. None of the answers in Why hash the message before signing it with RSA seems to quite fit. – fgrieu Jun 14 at 16:50
up vote 2 down vote accepted

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: we can obtain the signature of one message from the signature of three chosen ones, which is a break.

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.

  • so essentially it is the "randomness" of the hash that ensures the security of the signing by encoding with private key. I'm not so sure about the role of "one-wayness" if the message has anyway to respect some rules in order to be valid. the validity rules would remove the possibility to forge a message using only maths. but it would nonetheless be easier to (randomly) find a suitable message, than a matching hash. – Kzar Jun 15 at 17:46
  • @kzar: The hash makes (a sizable portion of) what's submitted to $x\mapsto x^d\bmod N$ "random", that is (in the context) with no special math property. Another way to consider this is that the transformation of message to hash is one-way: we can easily go from message to hash, but can't go from a desired hash value to a message hashing to that; and that's what prevents forgeries of the kind I illustrate. – fgrieu Jun 15 at 20:27

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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