5 of 10
Polish
fgrieu
  • 117k
  • 10
  • 252
  • 490

The usual methods of RSA signature with message recovery (that is, embedding a part of the message in the signature, known as the revoverable message) are those in ISO/IEC 9796-2:2010 (partial preview). There are three:

  • Scheme 1; it is an ad-hoc scheme that essentially concatenates the recoverable message, the hash of the whole message, and a little fixed data (about two bytes when there's more to the message than the recoverable part), forming the padded message; to which the raw RSA private function is then applied. This scheme is insecure if the adversary can obtain the signature of many chosen messages, see 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; or full PDF

  • Scheme 2; in addition to hashing, it uses salting and an unbalanced two-rounds Feistel construct using a Mask Generation Function, so that the input of the raw RSA private function is indistinguishable from random (except for about two bytes, and without knowledge of the salt assumed random). It aims at demonstrable security similar to (and by the same means as) the Probabilistic Signature Scheme introduced in version 2 of PKCS#1, and pioneered by Mihir Bellare and Phillip Rogaway: The exact security of digital signatures - how to sign with RSA and Rabin, in proceedings of Eurocrypt 1996; or better PDF.

  • Scheme 3; that's precisely scheme 2 with no salt. It is deterministic (when the size of the recoverable portion of the message is fixed), and has the same message embedding capacity as scheme 1. It has the demonstrable security of Full Domain Hash; see Jean-Sébastien Coron, On the Exact Security of Full Domain Hash, in proceedings of Crypto 2000, or better PDF.


I'll assume the rest of the question asks how to attack the trivial RSA signature scheme giving message recovery where the signature of message $M$ is defined as $\mathcal S(M)=(M\|M)^d\bmod N$, for $M$ of $m$ bits with $m$ fixed, positive, multiple of $8$ (message consists of $m/8$ octets), and such that $2^{2m}<N$; and the verification procedure recovers $M$ from $\mathcal S(M)$, as $M=(\mathcal S(M)^e\bmod N)\bmod 2^m$, then checks that $\big\lfloor(S(M)^e\bmod N)/2^m\big\rfloor=M$. Bitstrings are assimilated to integers using big-endian conventions.

One attack goes:

  • Chose 4 positive integers/messages less than $2^m$ such that $M_0\cdot M_1$=$M_2\cdot M_3$, $M_0\ne M_1$, $M_0\ne M_2$, $M_0\ne M_3$; for example $M_0=1$, $M_1=4$, $M_2=M_3=2$; or perhaps, if messages are constrained to be two ASCII lowercase letters, $M_0=6561_\mathtt h$, $M_1=7970_\mathtt h$, $M_1=6E72_\mathtt h$, $M_3=6F78_\mathtt h$.
  • Notice that $(M_0\|M_0)\cdot(M_1\|M_1)=(M_2\|M_2)\cdot(M_3\|M_3)$, hence $\mathcal S(M_0)\cdot\mathcal S(M_1)\equiv\mathcal S(M_2)\cdot\mathcal S(M_3)\pmod N$.
  • Obtain the signatures of the messages $M_1$, $M_2$ and $M_3$ (by three, or sometime two queries to a signature oracle) and compute the signature of message $M_0$ as $\mathcal S(M_0)=\mathcal S(M_1)^{-1}\cdot\mathcal S(M_2)\cdot\mathcal S(M_3)\bmod N$.
fgrieu
  • 117k
  • 10
  • 252
  • 490