# Demonstrating the insecurity of an RSA signature encoding scheme

I'm working on problem 12.4 from Katz-Lindell. The problem is as follows:

Given a public encoding function $\newcommand{\enc}{\operatorname{enc}}\enc$ and a textbook RSA signature scheme where signing occurs by finding $\enc(m)$ and raising it to the private key $d \bmod N$, how can we demonstrate the scheme's insecurity for $\enc(m) = 0||m||0^{L/10}$, where $L = |N|$ and $|m| = 9L/10 - 1$ and m is not the message of all zeroes?

-
Okay, and where do you need help here? – Paŭlo Ebermann Dec 9 '11 at 21:52
I need to know how to find a forgery on an m not in Q, where Q is the set of queries to the adversary's signing oracle. Is there something dead simple that I'm missing about this? – pg1989 Dec 9 '11 at 21:56
Have a look at the corresponding verifying scheme. Can you find a number, which, when taken to the power $e$ (the public exponent), gives something in this encoding? (This depends on the public key, but assume it it something like $3$.) – Paŭlo Ebermann Dec 9 '11 at 22:08
Well, here's a hint: remember that for textbook RSA $enc(X) \cdot enc(Y) = enc( X \cdot Y) \mod N$ -- how can we find two messages $X$ and $Y$ such that $X \cdot Y \mod N$ is also a valid message? – poncho Dec 9 '11 at 22:10
@pg1989: Presumably that should go "and $m$ is not ...". $\;\;$ – Ricky Demer Dec 9 '11 at 22:20

An RSA signature scheme with public key $(n,e)$, private exponent $d$, and encoding function $enc$ (including but not limited to the question's $enc$), signs message $m$ as $$Sign(m) = enc(m)^d\bmod n$$

Such scheme is insecure if an adversary can figure out $k>0$ distinct messages $m_i$, and integers $u_i$, $r$, $s$ verifying $$s^e \cdot enc(m_0) \cdot \prod_{0\lt i\lt k} enc(m_i)^{u_i} \equiv r^e \pmod n$$ because this implies (by raising to the power $d$) $$Sign(m_0) \equiv r \cdot s^{-1} \cdot\prod_{0\lt i\lt k}Sign(m_i)^{-u_i} \pmod n$$ which allows computing the signature of $m_0$ (if $k\gt 1$, it is also necessary that the attacker obtain the signatures of the other messages $m_i$; that becomes an existential forgery, or chosen-message attack). Although dated, Jean-Francois Misarsky's How (Not) to Design RSA Signature Schemes is an interesting and relatively easy reading on that topic.

In fact, every known attack on an RSA signature scheme is either of the above kind (with more or less involved computations to exhibit $m_i$, $u_i$, $r$, $s$); or amounts to factorization of $n$ (which includes anything recovering $d$, perhaps by side-channel attack); or is some implementation error, perhaps widespread.

In order to mount an attack of the above kind, a relation of the form $enc(m_0)=r^e$ is ideal. It gives the signature of $m_0$ without any consideration on $n$ or known signature. When $e$ is low enough, this can be done with the encoding $enc$ in the question, by considering $r=2^t$ for some appropriate $t$. That's because by definition (and assimilating bit strings to integers using big-endian convention), $enc(m)=m\cdot2^{L/10}$ with $L/10$ an integer; hence $enc(m_0)=r^e$ with $r=2^t$ holds if and only if $m_0$ has a single bit set and $\log_2(m_0)+L/10=e\cdot t$; for all $m$ that $enc$ aims at handling, $\log_2(m)<9L/10$, hence $enc(m_0)=r^e$ can hold only if $e\cdot t<L$; there are no solutions for $e\ge L$, and about $9L\over10e$ solutions for small $e$; the lower $e$, the more solutions. When we extend that with $r=v\cdot2^t$ for odd $v$, the trend for more solutions for low $e$ remains, with no solution when $e\ge L$.

Similarly, $enc(m_0) = r^e\cdot enc(m_1)$ gives the signature of one message from the signature of the other, without any consideration on $n$. This can be done with the encoding $enc$ in the question, for a wider choice of $e$.

Similarly, $enc(m_0) \cdot enc(m_1) = enc(m_2) \cdot enc(m_3)$ gives the signature of one message from the signature of the other three, for any public key $(n,e)$. With the encoding $enc$ in the question, there is ample choice (the equation simplifies to $m_0\cdot m_1=m_2\cdot m_3$, and all messages which left bit is 0 or which integer representation is composite are vulnerable). The ISO/IEC 9796:1991 signature encoding scheme (section 11.3.5 of the Handbook of Applied Cryptography), now withdrawn, turned out to be vulnerable to that, of course if the adversary can obtain the signature of three chosen messages, and is content with the signature of the fourth.

Even the hash-based ISO/IEC 9796-2:1997 (now known as ISO/IEC 9796-2:2010 scheme 1), still in wide use, is vulnerable if the adversary can obtain the signature of many weird chosen messages and is content with the signature of another, which fortunately is seldom the case in practice.

Some require $e>2^{16}$ (FIPS 186-3 appendix B3.1, RGS Annex B1 section 2.2.1.1, and I have seen suggestions for much wider random $e$), because some attacks on weak encoding schemes or implementations of RSA signature/encryption have been easiest for $e=3$ or other small $e$, as is the case for the scheme in the question. I will not condone a course of action that will lead us to loose the main appeal of RSA (or Rabin) signature schemes: fast and simple verification with modest hardware.

-
A bit of an old post, but I'm stuck with the same problem. Reading the solution, I wonder why we can have that $Enc(m_0)=r^e$ only for $e$ is $3,5$ or $7$? – verdict Mar 17 at 0:13
@verdict: my statement was wrong (though on the right tracks); I've revised it, and give a justification. – fgrieu Mar 17 at 6:18