% Last modified: Fri Dec 19 15:55:30 EST 2003 \documentclass[11pt]{llncs} \def\ss{\smallskip} \def\makeitbig{% \setlength{\textwidth}{15.9cm}% \setlength{\oddsidemargin}{.01cm}% \setlength{\evensidemargin}{.01cm}% \setlength{\textheight}{21.5cm}% \setlength{\topmargin}{.25cm}% \setlength{\headheight}{.7cm}% \leftmargini 20pt \leftmarginii 20pt% \leftmarginiii 20pt \leftmarginiv 20pt% \leftmarginv 12pt \leftmarginvi 12pt% \pagestyle{myheadings}}% \usepackage{epsfig} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \newcommand{\algo}[1]{\mbox{\tt #1}} \newcommand{\event}[1]{\mbox{\tt #1}} \newcommand{\hex}{_{\mbox{{\small {\tt 16}}}}} \newcommand{\mlm}[1]{\multicolumn{2}{l}{#1}&&&&&&&} \newcommand{\pkcs}{PKCS\#1 v1.5} \def\bbbZ{\mbox{\sf Z\kern-0.4em Z}} \newcommand{\negl}{\mbox{\tt negl}} \newcommand{\var}{\mbox{Var}} \newcommand{\E}{\mbox{E}} \newcommand{\PSS}{\algo{PSS}} \newcommand{\jacobi}[2]{\left(\frac{#1}{#2} \right)} \newcommand{\iso}{{\sc iso/iec} 9796-1} \newcommand{\iss}{{\sc iso/iec} 9796-2} %\usepackage{communication} \makeitbig %\addtolength{\textwidth}{+1cm} \title{Index Calculation Attacks on RSA Signature and Encryption} \author{Jean-S\'{e}bastien Coron \inst{1} \and Yvo Desmedt \inst{2} \and David Naccache \inst{1} \and \\ Andrew Odlyzko\inst{3} \and Julien P. Stern \inst{4} } \institute{Gemplus Card International\\ \email{$\{$jean-sebastien.coron,david.naccache$\}$@gemplus.com} \and Florida State University\\ \email{desmedt@cs.fsu.edu} \and University of Minnesota\\ \email{odlyzko@umn.edu} \and Cryptolog International\\ \email{julien@cryptolog.com} } \begin{document} \maketitle \begin{abstract} At Crypto '85, Desmedt and Odlyzko described a chosen-ciphertext attack against plain RSA encryption. The technique can also be applied to RSA signatures and enables an existential forgery under a chosen-message attack. The potential of this attack remained untapped until a twitch in the technique made it effective against two very popular RSA signature standards, namely \iso\ and \iss. Following these attacks \iso\ was withdrawn and \iss\ amended. In this paper, we explain in detail Desmedt and Odlyzko's attack as well as its application to the cryptanalysis of \iss. \end{abstract} \section{Introduction} RSA was invented in 1977 by Rivest, Shamir and Adleman \cite{rsa}, and is now the most widely used public-key cryptosytem. RSA can be used for both encryption and signature. A chosen-ciphertext attack against plain RSA encryption was described at Crypto '85 by Desmedt and Odlyzko \cite{desmedt}. In the plain RSA encryption scheme, a message $m$ is simply encrypted as~: $$c=m^e \mod N$$ where $N$ is the RSA modulus and $e$ is the public exponent. Informally, during a chosen-ciphertext attack, an attacker may obtain the decryption of any ciphertext of his choice; the attacker's goal being to decrypt (or to recover some information about) some given ciphertext. However, Desmedt and Odlyzko's attack did not seem to threaten real-world RSA encryption standards, because in practice, the message $m$ is generally encoded as $\mu(m)$ before being encrypted~: $$ c=\mu(m)^e \mod N$$ where $\mu$ is some (probabilistic) algorithm. As noted in \cite{surv}, Desmedt and Odlyzko's attack can also be applied to RSA signatures. Recall that the RSA signature of a message $m$ is defined as: $$ s=\mu(m)^d \mod N$$ where $\mu(m)$ is an encoding function and $d$ the private exponent. As we will see below, Desmedt and Odlyzko's attack on RSA signatures only applies if the encoding function $\mu(m)$ produces integers much smaller than $N$. In this case, one obtains an existential forgery under a chosen-message attack. In this setting, the attacker can ask for the signature of any message of his choice, and his goal is to forge the signature for some (possibly meaningless) message which was not signed before. At Crypto '99 \cite{coron99}, Coron, Naccache and Stern published an attack against the \iss\ RSA signature standard \cite{iso2} and a slight variant of the \iso\ signature standard \cite{iso1}. Both attacks were an adaptation of Desmedt and Odlyzko's attack, which could not be applied directly since for both standards $\mu(m)$ happened to be as big as $N$. Shortly after, the attack was extended to the real \iso\ standard by Coppersmith, Halevi and Jutla \cite{copiso}. Following this final blow \iso\ was withdrawn and \iss\ amended. This paper is organized as follows: we first recall the definition of the RSA cryptosystem. Then we describe Desmedt and Odlyzko's attack against plain RSA encryption, and eventually its application to the cryptanalysis of the \iss\ standard. \section{The RSA cryptosystem} The first instance of public-key encryption and digital signatures was invented in 1977 by Rivest, Shamir and Adleman \cite{rsa}: \begin{definition}[The RSA Primitive] The RSA primitive is a family of trapdoor permutations, specified by: \begin{itemize} \item The RSA generator $\cal RSA$, which on input $1^k$, randomly selects two distinct $k/2$-bit primes $p$ and $q$ and computes the modulus $N=p \times q$. It randomly picks an encryption exponent $e \in {\mathbb Z}^{*}_{\phi(N)}$, computes the corresponding decryption exponent $d=e^{-1} \bmod \phi(N)$ and returns $(N,e,d)$; \item The function $f: {\mathbb Z}_N^* \rightarrow {\mathbb Z}_N^*$ defined by $f(x)=x^e \bmod N$; \item The inverse function $f^{-1}: {\mathbb Z}_N^* \rightarrow {\mathbb Z}_N^*$ defined by $ f^{-1}(y)=y^d \bmod N$. \end{itemize} \end{definition} \subsection{The RSA Encryption Scheme} The standard practice for encrypting a message $m$ with RSA is to first apply an encoding scheme $\mu$ and raise $\mu(m)$ to the public exponent $e$. The algorithm $\mu$ is generally chosen to be probabilistic. The ciphertext $c$ is then $$c=\mu(m)^e \bmod N\enspace.$$ where $(N,e)$ is the public-key. Decryption simply consists in using the private key $d$ to compute~: $$\mu(m)=c^e \bmod N\enspace.$$ and recover $m$ from $\mu(m)$. \subsection{The RSA Signature Scheme} As previously, the public-key is $(N,e)$ and the private key is $d$. The RSA signature scheme is specified by an encoding function $\mu$, which takes as input a message $m$ and returns an integer modulo $N$, denoted $\mu(m)$. The signature of a message $m$ is then: $$s=\mu(m)^d \mod N$$ The signature $s$ is verified by checking that~: $$\mu(m) \stackrel{?}{=} s^e \mod N$$ \section{Attack on RSA Encryption} \label{desattack} In \cite{desmedt}, Desmedt and Odlyzko describe a chosen-ciphertext attack against plain RSA encryption. Recall that for plain RSA encryption, a message $m$ is directly encrypted as $c=m^e \mod N$. The attack's setting is the following~: \begin{enumerate} \item The attacker receives the public-key $(N,e)$. \label{recpk} \item The attacker can ask for the decryption of any ciphertext of his choice, {\sl i.e.} he submits $x$ and receives $m=x^d \mod N$ for any $x$ of his choice. The number of decryption queries is unlimited. \label{decora} \item Upon receiving a challenge ciphertext $c$, the attacker's ability to make decryption queries ceases. The attacker must now output $c^d \mod N$. \label{decrypt} \end{enumerate} Desmedt and Odlyzko's attack works as follows. After receiving the public-key (step \ref{recpk}), we ask for the decryption $x^d \mod N$ of all integers $x\in S=S_1\cup S_2$, where: $$ S_1=\{p:~~~ p\leq L_N[\alpha], p\mbox{~is prime}\} $$ $$ S_2=\{\lfloor \sqrt{N}\rfloor+1,\lfloor \sqrt{N}\rfloor+2,\ldots,\lfloor \sqrt{N}\rfloor+\lfloor L_N[\alpha]\rfloor\} $$ where $\alpha >0$ is some fixed parameter and the function $L_N[\alpha]$ is defined as~: $$ L_N[\alpha]=\exp\big(\alpha \cdot \sqrt{\log N \log \log N}\big)$$ %To avoid detection by simple screening programs, we choose a %random $y_x$ for each $x$ and obtain $(x y_x^e)^d\equiv x^d y_x %\mod N$ from the decrypting algorithm, which then allows to obtain %$x^d \mod N$.\ss Once we have obtained $x^d \mod N$ for all $x\in S$ (step \ref{decora}), we receive the challenge ciphertext $c$. We must now output $c^d \mod N$, without using the decrypting facility anymore (step \ref{decrypt}). The basic idea is to find a representation: \begin{equation} \label{twotwo} c= y^e \prod_{x\in S} x^{a_x} \mod N \end{equation} for some integers $a_x$ and $y$, since then~: $$ c^d = y \prod_{x\in S}(x^d)^{a_x} \mod N $$ where $y$ and all the $x^d$ are known. To obtain the representation (\ref{twotwo}), we proceed in two steps. In the first step we find some integer $y$ and primes $q_i \leq L_N[2\alpha]$ such that: \begin{equation} \label{two3} c= y^e \prod_{i=1}^h q_i \mod N \end{equation} To obtain the representation (\ref{two3}), we chose a random $y$, compute~: $$ b= c \cdot y^{-e} \mod N $$ and check whether $b$ factors into primes $q\leq L_N[2\alpha]$. We use the following theorem \cite{canfield} to estimate the average number of $y$ values before such factorization is obtained. \begin{theorem} \label{theosmooth} Let $x$ be an integer and let $L_x[\beta]=\exp\big(\beta \cdot \sqrt{\log x \log \log x}\big)$. Let $z$ be an integer randomly distributed between zero and $x^\gamma$ for some $\gamma>0$. Then for large $x$, the probability that all the prime factors of $z$ are lesser than $L_x[\beta]$ is given by~: $$L_x \left[-\frac{\gamma}{2\beta}+o(1)\right]$$ \end{theorem} Taking $\gamma=1$ and $\beta=2\alpha$, it appears that we need to generate on average $L_N[1/(4\alpha)+o(1)]$ values of $y$ before such a factorization is obtained. Moreover, for each $y$, it takes $L_N[o(1)]$ bit operations to test whether such a factorization exists, using Lenstra's elliptic curve factorization algorithm \cite{ecm}. Therefore this stage is expected to take time $L_N[1/(4\alpha)+o(1)]$. Although Lenstra's algorithm is asymptotically faster, it may be more efficient in practice to use trial division, for small enough prime factors. Once a factorization of the form (\ref{two3}) is obtained, we proceed to the second step, in which we represent each of the at most $O(\log(N))=L_N[o(1)]$ primes $q=q_i \leq L_N[2\alpha]$ in the form: \begin{equation} \label{two4} q= \prod_{x\in S} x^{u_x} \mod N \end{equation} where only $O(\log N)$ of the $u_x$ are non-zero (possibly negative). Once such a representation is obtained for each $q$, we quickly obtain (\ref{twotwo}). To see how to represent a prime $q\leq L_N[2\alpha]$ in the form (\ref{two4}), let~: \begin{equation} \label{defm} m=\left\lfloor\frac{\sqrt{N}}{q} \right\rfloor \end{equation} and determine those integers among~: $$ m+1,m+2,\ldots,m+\lfloor L_N[\beta]\rfloor $$ that are divisible solely by primes $p\leq L_N[\alpha]$, for some $\beta >0$. Using the previous theorem, we expect to find $L_N[\beta-1/(4\alpha)+o(1)]$ such integers, and finding them will take $L_N[\beta+o(1)]$ bit operations if we employ Lenstra's factorization algorithm. We next consider two cases. If $\alpha\geq\frac{1}{2}$, we take $\beta=\frac{1}{4\alpha}+\delta$ for any $\delta>0$. We then have $L_N[\delta+o(1)]$ integers $m+j$, $1\leq j\leq L_N[\beta]$, all of whose prime factors are $\leq L_N[\alpha]$. For each such integer and any $i$ such that $1\leq i\leq L_N[1/(4\alpha)] \leq L_N[\alpha]$, we write~: \begin{equation} \label{two6} q(m+j)(k+i)= t \mod N \end{equation} where $k=\lfloor \sqrt{N} \rfloor$. Using equation (\ref{defm}) and the corresponding bounds for $q$, $j$ and $i$, we obtain that~: $$t \mod N\leq N^{\frac{1}{2}+o(1)}$$ Therefore, if the integers $t$ factor like random integers of the same size, we will find $L_N[\delta+o(1)]$ integers $t$ that factor into primes $\leq L_N[\alpha]$, and any single one will yield a factorization of the form (\ref{two4}), which gives the desired result. Since the testing of each $t$ takes $L_N[o(1)]$ bit operations, this stage requires $L_N[\beta+o(1)]$ bit operations, and since this holds for all $\delta>0$, we conclude that for $\alpha\geq\frac{1}{2}$, this stage can be carried out in $L_N[1/(4\alpha)+o(1)]$ bit operations. It remains to consider the case $\alpha<\frac{1}{2}$. Here we take $\beta=\frac{1}{2\alpha}-\alpha+\delta$. We expect to find $L_N[\beta-1/(4\alpha)+o(1)]=L_N[1/(4\alpha)-\alpha+\delta+o(1)]$ values of $m+j$, $1\leq j\leq L_N[\beta]$, which factor into primes $\leq L_N[\alpha]$, and it takes $L_N[\beta+o(1)]$ bit operations to find them. For each one and for $1\leq i\leq L_N[\alpha]$, we test whether the $t$ defined by (\ref{two6}) is composed of primes $\leq L_N[\alpha]$. We expect to find $L_N[\delta+o(1)]$ of them. Letting $\delta \rightarrow 0$, we obtain that this case takes $L_N[1/(2\alpha)-\alpha+o(1)]$ bit operations. We thus conclude that if the attacker can obtain decryptions of $L_N[\alpha]$ chosen ciphertexts he will be able to decrypt any individual ciphertext in $L_N[1/(4\alpha)+o(1)]$ bit operations for $\alpha \geq \frac{1}{2}$ and in $L_N[1/(2\alpha)-\alpha+o(1)]$ bit operations for $0<\alpha \leq \frac{1}{2}$. For $\alpha = \frac{1}{2}$ both steps require $L_N[1/2+o(1)]$ operations. Therefore, Desmedt and Odlyzko's attack is asymptotically faster than the quadratic-sieve factorization algorithm \cite{quadratic}, which requires $L_N[1+o(1)]$ steps to recover the factorization of $N$. However, the attack is asymptotically slower than the general number field sieve algorithm \cite{nf} which appeared later, whose complexity to factor $N$ is given by~: $$ \exp\left((c+o(1))(\log N)^{1/3} (\log \log N)^{2/3}\right)$$ for some constant $c \simeq 1.9$. Given that in practice RSA encryption schemes use an encoding function $\mu(m)$, the attack did not appear directly applicable to real-world standards. The situation nonetheless proved very different for RSA signature schemes, as explained in the next sections. \section{Attack on RSA Signatures} \label{dosig} The previously described attack against RSA encryption can be easily adapted to RSA signatures to provide an existential forgery under a chosen-message attack, as shown in \cite{surv}. The outline of such a scenario is the following~: \begin{enumerate} \item Select a bound $y$ and let $S=(p_1,\ldots,p_\ell)$ be the list of primes smaller than $y$. \ss \item \label{dofind} Find at least $\ell+1$ messages $m_i$ such that each $\mu(m_i)$ is the product of primes in $S$. \ss \item \label{linsolve} Express one $\mu(m_j)$ as a multiplicative combination of the other $\mu(m_i)$, by solving a linear system given by the exponent vectors of the $\mu(m_i)$ with respect to the primes in $S$. \ss \item \label{doforge} Ask for the signature of the $m_i$ for $i\neq j$ and forge the signature of $m_j$.\ss \end{enumerate} The attack's complexity depends on the cardinality of~$S$ and on the difficulty of finding at step (\ref{dofind}) enough $\mu(m_i)$ values which are the product of primes in $S$. Generally, the attack would apply only when $\mu(m)$ is small; otherwise, the probability that $\mu(m)$ has only small prime factors is too small.\ss In the following, we describe the attack in more detail. First, we assume that $e$ is a prime integer. We let $\tau$ be the number of messages $m_i$ obtained at step (\ref{dofind}). We say that an integer is $B$-smooth if all its prime factors are smaller than $B$. The integers $\mu(m_i)$ obtained at step (\ref{dofind}) are therefore $y$-smooth and we can write for all messages $m_i$, $1 \leq i \leq \tau$: \begin{equation} \label{eqmui} \mu(m_i)=\prod_{j=1}^{\ell} p_j^{v_{i,j}} \end{equation} Step (\ref{linsolve}) works as follows~: to each $\mu(m_i)$ we associate the $\ell$-dimensional vector of the exponents modulo $e$~: $$ \vec{V_i}=(v_{i,1}\mbox{~mod~} e,\ldots,v_{i,\ell}\mbox{~mod~} e)$$ The set of all $\ell$-dimensional vectors modulo $e$ forms a linear space of dimension $\ell$. Therefore, if $\tau \geq \ell+1$, one can express one vector, say $\vec{V_\tau}$, as a linear combination of the others modulo $e$, using Gaussian elimination: \begin{equation} \label{lincomb} \vec{V}_{\tau}=\sum\limits_{i=1}^{\tau-1} \beta_i \vec{V}_i+\vec{\Gamma} \cdot e \end{equation} for some $\vec{\Gamma}=(\gamma_1,\ldots,\gamma_\ell)$. Denoting \begin{equation} \label{defdelta} \delta=\prod\limits_{j=1}^{\ell} p_j^{\gamma_j} \end{equation} one obtains from (\ref{eqmui}) and (\ref{lincomb}) that $\mu(m_{\tau})$ is a multiplicative combination of the other $\mu(m_i)$: \begin{equation} \label{multcomb} \mu(m_{\tau})=\delta^e \cdot \prod\limits_{i=1}^{\tau-1} \mu(m_{i})^{\beta_i} \end{equation} Then, at step (\ref{doforge}), the attacker will ask for the signature of the $\tau-1$ first messages $m_i$ and forge the signature of $m_\tau$ using: \begin{equation} \label{eqforgeRSA} \mu(m_{\tau})^d=\delta \cdot \prod\limits_{i=1}^{\tau-1} \left(\mu(m_{i})^d\right)^{\beta_i} \mod N \end{equation} The attack's complexity depends on $\ell$ and on the probability that the integers $\mu(m_i)$ are $y$-smooth. We define $\psi(x,y)=\#\{v \leq x \mbox{, such that $v$ is $y$-smooth}\}$. It is known \cite{rho3} that, for large $x$, the ratio $\psi(x,\sqrt[t]{x})/x$ is equivalent to Dickman's function defined by~: $$\rho(t)=\left\{ \begin{array}{cl} 1 & \mbox{~~if~~} 0 \leq t \leq 1\\ \\ {\displaystyle \rho(n) - \int_{n}^{t}\frac{\rho(v-1)}{v}dv} & \mbox{~~if~~} n \leq t \leq n+1\\ \end{array} \right. $$ $\rho(t)$ is thus an approximation of the probability that a $u$-bit number is $2^{u/t}$-smooth; table \ref{tdickman} gives the numerical value of $\rho(t)$ (on a logarithmic scale) for $1 \leq t \leq 10$. \begin{table} \[ \begin{array}{|c||c|c|c|c|c|c|c|c|c|c|} \hline t & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ \hline \log_2 \rho(t) & ~~0~~ & -1.7 & -4.4 & -7.7 & -11.5 & -15.6 & -20.1 & -24.9 & -29.9 & -35.1 \\ \hline \end{array} \] \caption{The value of Dickman's function.} \label{tdickman} \end{table} In the following, we provide an asymptotic analysis of the algorithm's complexity, based on the assumption that the integers $\mu(m)$ are uniformly distributed between zero and some given bound $x$. Letting $\beta$ be a constant and letting: $$y=L_x[\beta]=\exp\big(\beta \cdot \sqrt{\log x \log \log x}\big)$$ one obtains from theorem \ref{theosmooth} that, for large $x$, the probability that an integer uniformly distributed between one and $x$ is $L_x[\beta]$-smooth is: $$\frac{\psi(x,y)}{x}=L_x \left[-\frac{1}{2\beta}+o(1)\right]$$ Therefore, we have to generate on the average $L_x[1/(2 \beta)+o(1)]$ integers $\mu(m)$ before we can find one which is $y$-smooth. \smallskip Using the ECM factorization algorithm \cite{ecm}, a prime factor $p$ of an integer $n$ can be found in time $L_p[\sqrt{2}+o(1)]$. A $y$-smooth integer can thus be factored in time $L_y[\sqrt{2}+o(1)]=L_x[o(1)]$. The complexity of finding a random integer in $[0,x]$ which is $y$-smooth using the ECM is thus $L_x\left[1/(2 \beta)+o(1)\right]$. Moreover, the number $\tau$ of integers which are necessary to find a vector which is a linear combination of the others is $\ell+1 \leq y$. Therefore, one must solve a system with $r=L_x[\beta+o(1)]$ equations in $r=L_x[\beta+o(1)]$ unknowns. Using Lanzos' iterative algorithm \cite{lanczos}, the time required to solve such system is ${\cal O}(r^2)$ and space is roughly ${\cal O}(r)$. \smallskip To summarize, the time required to obtain the $L_x[\beta+o(1)]$ equations is asymptotically $L_x \left[\beta+1/(2\beta)+o(1) \right]$ and the system is solved in time $L_x[2 \beta +o(1)]$. The total complexity is minimized by taking $\beta=1/\sqrt{2}$. We obtain a time complexity of~: $$ L_x[\sqrt{2}+o(1)]$$ and a space complexity of~: $$ L_x\left[\frac{\sqrt{2}}{2}+o(1)\right]$$ where $x$ is a bound on $\mu(m)$. This complexity is sub-exponential in the size of the integers $\mu(m)$. Therefore, without any modification, the attack will be practical only if $\mu(m)$ is small. In particular, when $\mu(m)$ is about the size of $N$, the attack's complexity is worse than factoring~$N$. Note that the attack can easily be extended to any exponent $e$, and also to Rabin signatures (see \cite{coron99}). In table \ref{compcoron}, we give the values of the functions $L_x[\sqrt{2}]$ et $L_x[\sqrt{2}/2]$ corresponding to the attack's time complexity and space complexities, as a function of the size $|x|$ of the integer $\mu(m_i)$. This table should be handled with care: being just an approximation of the attack's practical complexity, the attack may demand more time in practice. The table suggests that the attack can be practical when the size of $\mu(m)$ is smaller than $128$ bits, but the attack becomes quickly impractical for larger values of $|x|$. \smallskip \begin{table} \begin{center} \begin{tabular}{|c|c|c|c|c|}\hline ~~$|x|$~~&~$\log_2 \mbox{\bf time}$ &~~$\log_2 \mbox{\bf space}$~~\\\hline 64 & 26 & 13 \\\hline % 96 & 34 & 17 \\\hline 99 & 35 & 18 \\\hline 119 & 39 & 20 \\\hline % 128 & 41 & 20 \\\hline 139 & 43 & 22 \\\hline 144 & 44 & 22 \\\hline 176 & 49 & 25 \\\hline 200 & 53 & 27 \\\hline 256 & 62 & 31 \\\hline 368 & 77 & 39 \\\hline \end{tabular} \end{center} \caption{The Attack's Complexity.} \label{compcoron} \end{table} \section{The Security of \iss~ Signatures} \iss~ \cite{iso2} is an encoding standard allowing total or partial message recovery. The standard uses a hash-function $\mbox{HASH}$ during the message formatting process. Let us denote by $k_h$ the output size of the hash function. Hash-functions of different sizes are acceptable. Section 5, note 4 of \cite{iso2} recommended (before the standard's correction by ISO following the attack described in this paper) $64 \leq k_h \leq 80$ for total message recovery and $128 \leq k_h \leq 160$ for partial message recovery. For \iss~, the encoding function $\mu(m)$ has the same size as $N$. Therefore, Desmedt and Odlyzko's attack can not apply directly here. Our technique will consist in generating messages $m_i$ such that a linear combination $t_i$ of $\mu(m_i)$ and $N$ is much smaller than $N$. Then, the attack will be applied to the integers $t_i$ instead of $\mu(m_i)$. \subsection{Partial Message Recovery} For simplicity, assume that $k$ (the size of the modulus $N$), $k_h$ and the size of $m$ are all multiples of eight and that the hash function is known to both parties. The message $m$ is separated into two parts $m=m[1]\|m[2]$ where $m[1]$ consists of the $k-k_h-16$ most significant bits of $m$ and $m[2]$ of all the remaining bits of $m$. The padding function is~: $$\mu(m)=\mbox{{\tt 6A}}\hex \| m[1]\| \mbox{HASH}(m)\|\mbox{\tt BC}\hex$$ and $m[2]$ is transmitted in clear. Dividing $(\mbox{{\tt 6A}}\hex+1) \cdot 2^{k}$ by $N$ we obtain~: $$ (\mbox{{\tt 6A}}\hex+1)\cdot 2^k=i \cdot N+r \mbox{~~with~~} 0 \leq r< N < 2^k$$ Defining $N'=i\cdot N$ we get~: $$ N'=\mbox{{\tt 6A}}\hex \cdot 2^k+(2^k-r)$$ Therefore, we can write $N'$ as~: $$N'=\mbox{{\tt 6A}}\hex \| N'[1] \| N'[0]$$ where the $N'[1]$ block is $k-k_h-16$ bits long, the same bit-size as $m[1]$. Then, one can take $m[1]=N'[1]$, and letting~: $$t=2^8 \cdot \mu(m)-i \cdot N$$ we obtain that~: \begin{eqnarray*} t &= & (\mbox{{\tt 6A}}\hex \| m[1]\| \mbox{HASH}(m)\|\mbox{\tt BC00}\hex)-(\mbox{{\tt 6A}}\hex \| N'[1] \| N'[0]) \\ t& = & (\mbox{HASH}(m)\|\mbox{\tt BC00}\hex)-N'[0] \end{eqnarray*} where the size of $t$ is less than $k_h+16$ bits. The attacker modifies $m[2]$ (and therefore $\mbox{HASH}(m)$) until he finds sufficiently many integers $t$ which are the product of small primes. Then since $t=2^8 \cdot \mu(m) \mod N$, one can apply Desmedt and Odlyzko attack's described in section \ref{dosig} to the integers $t$ (the factor $2^8$ can be added to the set $\cal S$). The attack's complexity is independent of the size of $N$; it only depends on the hash size $k_h$. From table \ref{compcoron}, we derive table \ref{attacfull} expressing the attack's complexity, as a function of the hash size. For example, for $k_h=128$, the size of $t$ is $144$ bits and from table \ref{compcoron}, we obtain that time complexity is roughly $2^{44}$. Again, recall that this is only an estimate, and that practical complexity may be much higher. Nevertheless the table suggests that the attack may be practical for $k_h=128$, but will be more demanding for $k_h=160$. Note that the following complexities are much smaller than the complexities obtained in \cite{coron99}. This is due to the fact that we have obtained a smaller complexity in section \ref{dosig}. \begin{table} \begin{center} \begin{tabular}{|c|c|c|}\hline ~~$k_h$~~&~~$\log_2\mbox{\bf time}$~~&~~$\log_2\mbox{\bf space}$~~\\\hline 128 & 44 & 22 \\\hline 160 & 49 & 25 \\\hline \end{tabular} \end{center} \caption{Attack's Complexity with Partial Message Recovery} \label{attacfull} \end{table} \subsection{Full Message Recovery} Assuming again that the hash function is known to both parties, that $k$ and $k_h$ are multiples of eight and that the size of $m$ is $k-k_h-16$, the encoding function $\mu$ is then defined as~: $$\mu(m)=\mbox{{\tt 4A}}\hex \| m \| \mbox{HASH}(m) \| \mbox{\tt BC}\hex$$ Let us separate $m=m[1] \| m[0]$ into two parts where $m[0]$ consists of the $\Delta$ least significant bits of $m$ and $m[1]$ of all the remaining bits of $m$ and compute, as in the previous case, an integer $i$ such that~: $$N'=i \cdot N=\mbox{{\tt 4A}}\hex \| N'[1] \| N'[0]$$ where $N'[0]$ is $(k_h+\Delta+16)$-bit long and $N'[1] \| N'[0]$ is $k$-bit long. Setting $m[1]=N'[1]$ we get~: $$ t=2^8 \cdot \mu(m)-N'=(m[0] \| \mbox{HASH}(m) \| \mbox{\tt BC00}\hex)-N'[0]$$ where the size of $t$ is less than $k_h+\Delta+16$ bits. The attacker will thus modify $m[0]$ (and therefore $\mbox{HASH}(m))$ as needed and conclude the attack as in the partial recovery case. As shown in section \ref{dosig}, the number of $t$-values necessary to forge a signature is roughly $L_x[\sqrt{2}+o(1)]$, where $x$ is a bound on $t$. Therefore, the parameter $\Delta$ must be tuned so that $2^\Delta \simeq L_x[\sqrt{2}]$. From table \ref{compcoron}, we obtain the attack complexities summarized in table \ref{tf}, as a function of the hash size. For example, for $k_h=64$, we take $\Delta=39$ bits and the size of $t$ is then $64+39+16=119$ bits and table \ref{compcoron} shows that the time complexity is roughly $2^{39}$. This shows that the attack may be practical for $k_h=64$. This actually led ISO to edit a revision of the \iss\ standard. \begin{table}[h] \begin{center} \begin{tabular}{|c|c|c|c|c|}\hline ~~$k_h$~~&~~$\Delta$~~&~~$\log_2\mbox{\bf time}$~~&~~$\log_2\mbox{\bf space}$~~\\\hline 64 & 39 & 39 & 20 \\\hline 80 & 43 & 43 & 22 \\\hline 128 & 53 & 53 & 27 \\\hline \end{tabular} \end{center} \caption{Attack Complexity with Full Message Recovery} \label{tf} \end{table} \section{Conclusion} In this paper we explained in detail Desmedt and Odlyzko's attack and illustrated its potential by exhibiting a design flaw in the \iss\ signature standard. The publication of this attack drove ISO to correct and re-edit \iss. A more elaborate variant (not described in this paper) \cite{copiso,coron99} led to the complete withdrawal of another signature standard, the \iso\ standard. \begin{thebibliography}{30} \bibitem{canfield} E. R. Canfield, P. Erd¨os and C. Pomerance, {\sl On a Problem of Oppenheim Concerning 'Factorisation Numerorum'}, J. Number Th. 17, 1-28, 1983. \smallskip \bibitem{copiso} D. Coppersmith, S. Halevi and C. Jutla, {\sl {ISO 9796-1} and the new forgery strategy}, Research contribution to P1363, 1999, available at {\tt http://grouper.ieee.org/groups/1363/contrib.html}. \smallskip \bibitem{coron99} J.S. Coron, D. Naccache and J.P. Stern, {\sl On the security of RSA Padding}, Proceedings of Crypto '99, LNCS vol. 1666, Springer-Verlag, 1999, pp. 1-18. \smallskip \bibitem{desmedt} Y.~Desmedt and A.~Odlyzko. {\sl A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes}, Proceedings of Crypto '85, LNCS 218, pp. 516--522. \smallskip \bibitem{rho3} K.~Dickman, {\sl On the frequency of numbers containing prime factors of a certain relative magnitude}, Arkiv f\"or matematik, astronomi och fysik, vol. 22A, no. 10, pp. 1--14, 1930. \smallskip \bibitem{iso1} ISO/IEC 9796, {\sl Information technology - Security techniques - Digital signature scheme giving message recovery, Part 1~: Mechanisms using redundancy}, 1999. \smallskip \bibitem{iso2} ISO/IEC 9796-2, {\sl Information technology - Security techniques - Digital signature scheme giving message recovery, Part 2~: Mechanisms using a hash-function}, 1997. \smallskip \bibitem{lanczos} C.~Lanczos, {\sl An iterative method for the solution of the eigenvalue problem of linear differential and integral operator}, J. Res. Nat. Bur. Standards, 1950, vol. 45, pp. 255--282. \smallskip \bibitem{nf} A.K.~Lenstra and H. W. Jr. Lenstra, {\sl The Development of the Number Field Sieve}, Berlin: Springer-Verlag, 1993. \smallskip \bibitem{ecm} H.~Lenstra, Jr., {\sl Factoring integers with elliptic curves}, Ann. of Math. (2) 126 (1987) pp. 649-673. \smallskip \bibitem{surv} J.-F.~Misarsky, {\sl How (not) to design RSA signature schemes}, Public-key cryptography, Springer-Verlag, Lectures notes in computer science 1431, pp. 14--28, 1998. \smallskip \bibitem{quadratic} C.~Pomerance, {\sl The Quadratic Sieve Factoring Algorithm}, In Advances in Cryptology, Proceedings of Eurocrypt '84. Springer-Verlag, pp. 169-182, 1985. \smallskip %\bibitem{pommerance} %C.~Pomerance, {\sl Analysis and comparison of some integer %factoring algorithms}, pp. 89--139 in Computational Methods in %Number Theory: Part 1, H.W. Lenstra, Jr., and R. Tijdeman ed. %Math. Centre Tract 154, Math. Centre Amsterdam, 1982. %\smallskip \bibitem{rsa} R.~Rivest, A.~Shamir and L.~Adleman, {\sl A method for obtaining digital signatures and public key cryptosystems}, CACM 21, 1978. \smallskip \end{thebibliography} \end{document}