|
I'm working on problem 12.4 from Katz-Lindell. The problem is as follows:
|
|||||||||||
|
|
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 3, 5 or 7, this can be done with the encoding $enc$ in the question, by considering $r=2^t$ for some appropriate $t$, and extended to $r=v\cdot2^t$ for some small $v$. 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. |
||||
|
|
