# Forgery attack against Textbook RSA with simple redundancy

I know how to forge vanilla Textbook RSA message signatures (easy).

I've learnt that by adding a good redundancy to the message, it cannot be forged anymore.

How can one add redundancy so that the message could be recovered from the signature (RSA with message recovery), and cannot be forged (meaning the redundancy function is "good")?

For example, a redundancy function which adds a 00...0 sequence in the beginning
of the message is considered not secure because it's easy to forge. (How?)

• There's example of that in the HAC (PDF).
– SEJPM
Jun 19 '16 at 20:03
• @SEJPM: yes; that's ISO/IEC 9796:1991 (better known as ISO/IEC 9796-1, even though it never officially was approved under that name). It is withdrawn, and insecure : a forged signature can be obtained from the signature of 1 or 3 chosen messages, depending on parameters.
– fgrieu
Jun 19 '16 at 20:54

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.

Noticing that left-padding a message $M$ with zero bits leaves its value unchanged when bitstrings are assimilated to integers using big-endian conventions (as customary), the last paragraph 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^d\bmod N$ (just as in vanilla Textbook RSA message signature), restricted to $M$ of (perhaps: at most) $m$ bits with $m$ fixed, positive, and such that $m\ll \log_2N$;
• the verification procedure recovers $M$ from $\mathcal S(M)$, as $M=\mathcal S(M)^e\bmod N$, then checks that $M<2^m$ (that is, checks the padding consists of zero bits).

Another way to look at this is: vanilla Textbook RSA message signature, with the message omitted (as it can be recovered from the signature), and restricted to be exactly (or at most) $m$ bits.

Just as in vanilla Textbook RSA message signature, it is easy to make an existential forgery out of nothing, in the sense that the message consisting of $m$ bits at zero has signature $0$, and the message consisting of $m-1$ bits at zero followed by a single bit at one has signature $1$. Also, if the public exponent $e$ is small, for any positive integer $S$ less than $2^{m/e}$, $S$ is the signature of message $M=S^e$.

Just as in vanilla Textbook RSA message signature, it is easy to make a forgery for a large fraction of valid messages $M$ one wishes to obtain a signature for, when having access to a signing oracle (that is, mean to obtain signature of any desired valid message, except for the messages subject to forgery). One method is to try to factor $M$ into $M_0\cdot M_1$ for $1<M_0\le M_1$, which is possible for a large fractions of messages $M$ (including all even $M\ge4$, and more generally all $M$ divisible by a small prime and larger than this prime). It holds that $\mathcal S(M_0)\cdot\mathcal S(M_1)\bmod N=\mathcal S(M)$, and that allows computing the signature of $M$ from that of $M_0$ and $M_1$.

Note: a former version of the present answer explained how to forge a slightly less vulnerable trivial RSA signature scheme giving message recovery, which (it turned out) did not match that intended in the question.

• Thanks! And one last thing: regarding the last paragraph... how 00...0m is forgeable? Jun 20 '16 at 16:11
• in the Textbook RSA you have no padding... I talked about messages without pad Jun 22 '16 at 20:38
• can you please explain how to forge 00...0m messages? Jun 24 '16 at 9:48
• @Jjang: I have assumed that the last paragraph of the question considers left-padding the message with "00...0m" (where "m" is the message), rather than with "00...0" as stated, since (when using the usual big-endian convention) doing the later is indistinguishable from "vanilla Textbook RSA message signature", which (according to the question) you "know how to forge". If that was a correct guess of what the question is about, please fix the question.
– fgrieu
Jun 24 '16 at 15:52
• What's the difference between "padding message with 00...0m where m is the message" and what I wrote (a redundancy function which adds a 00...0 sequence in the beginning of the message) which results in 00...0m? Jun 24 '16 at 16:25