Our attack

Let $s=\sum_{i=0}^{t-1}s_i 2^i$ be the secret key to be discovered. We suppose that exponentiations are achieved by the right-to-left square-and-multiply algorithm (Fig. 3). The attack supposes that the register containing the value of y has some permanently damaged known bits, always `0' or `1'. Let $\mathcal{C}$and $\mathcal{I}$ denote the subsets of correct and incorrect (i.e. damaged) bits of register y , respectively. So, any value $\hat{y}$stored in register y can be written as

$$\hat{y}=\sum_{j\in\mathcal{C}}\hat{y}_j 2^j + \sum_{j\in\mathcal{I}}\hat{y}_j 2^j.$$

From Eq. (1), the faulty signature corresponding to message m is given by

$$\hat{S}=\mathop{\widehat{\EuScript{S}}}(m) = \mathop{\widehat{\... ...)}) = \prod_{i=0}^{t-1}\left(\hat{y}^{(i)}\right)^{s_i} \bmod{n}.$$

Let $f: \mathcal{C}\to\mathcal{C}$ be the function that maps the correct bits of $\hat{y}^{(i)}$ to the correct bits of $\hat{y}^{(i+1)}$. Since $\mathcal{C}$ is finite, the sequence must eventually cycle. The length $\mu$ of the tail and the length $\lambda$ of the cycle can efficiently be computed by the Floyd's algorithm [9, exercise 6 on p. 7]. This algorithm is also known as the kangaroos' method . It has the advantage of minimizing the storage requirements.

Two kangaroos $K_1$ and $K_2$ cover the sequence generated by f . Kangaroo $K_1$ progresses in bounds of 1 unit and kangaroo $K_2$ in bounds of 2 units. Since the sequence cycles, the two kangaroos will meet. If they meet after k bounds, then $\hat{y}^{(k)}=\hat{y}^{(2k)}$. Once k has been found, it suffices to generate $\hat{y}^{(j)}$ and $\hat{y}^{(k+j)}$ for $j\geq 0$.Then, $\mu$ is the smallest integer j such that $\hat{y}^{(k+j)}=\hat{y}^{(j)}$.

Proof.Since $\hat{y}^{(k)}=\hat{y}^{(2k)}$, it follows that (2k-k) is a multiple of $\lambda$. Moreover since $\hat{y}^{(\lambda+\mu)}=\hat{y}^{(\mu)}$, $\mu$ is the smallest integer j such that $\hat{y}^{(k+j)}=\hat{y}^{(j)}$.

length $\lambda$ of the cycle is the smallest integer j such that $\hat{y}^{(k+j)}=\hat{y}^{(k)}$. Putting all together, we obtain the Floyd's algorithm (see Fig. 5).

   Figure 5: Kangaroos' method.

To recover the bits of the secret exponent s , the pirate Carol proceeds as follows. She first chooses a random message m . Then, by the kangaroos' method, she computes the tail's length $\mu$ and the cycle's length $\lambda$ of the sequence generated by the $\hat{y}^{(i)}$. If the sequence does not cycle, she chooses another message m and reiterates the process. The first bit of s is $s_0=1$ since s must be odd. To find the next $(\mu-1)$ bits $s_1,\ldots,s_{\mu-1}$, Carol asks to Alice to sign some $\hat{y}^{(i)}$ and successively evaluates

 $$\hat{\sigma}_j:=\frac{\mathop{\widehat{\EuScript{S}}}(\hat{y}^... ... -j\bmod{\lambda})})}\bmod{n}\quad \mbox{for $j=1,\ldots,\mu-1$}.$$

If $\hat{\sigma}_j \equiv \hat{\sigma}_{j-1} \pmod{n}$ then $s_j=0$;otherwise $s_j=1$.

Proof.Assume that Carol already computed $\hat{\sigma}_1,\ldots,\hat{\sigma}_{k-1}$ and therefore knows $s_0,s_1, \ldots,s_{k-1}$. Then, she computes

$$\hat{\sigma}_k \equiv \frac{\mathop{\widehat{\EuScript{S}}}... ...y}^{(\mu-1+\lambda-k\bmod{\lambda}+i)}\Bigr)^{s_i}} \pmod{n}.$$

Suppose that $i\gt k$. Then letting i=k+1+j with $j\geq 0$, we have

$$\hat{y}^{(\mu-1-k+i)}\equiv \hat{y}^{(\mu+j)} \pmod{n}$$

and

$$\begin{eqnarray*} \hat{y}^{(\mu-1+\lambda-k\bmod{\lambda}+i)} &\equiv& \hat{y}^... ...oor k/\lambda\rfloor))}\\ &\equiv& \hat{y}^{(\mu+j)}\! \pmod{n}.\end{eqnarray*}$$

So,

$$\hat{\sigma}_k \equiv \prod_{i=0}^{k}\frac{\left(\hat{y}^{(\... ...}^{(\mu -1)}}{\hat{y}^{(\mu-1+\lambda)}}\right)^{s_k} \pmod{n}.$$

There is no general recipe to find the remaining bits of s . If the length $\mu$ of the tail is short, Carol may choose another random message m to find the $\mu$ first bits of s . The next bits have to be found by exhaustive search. However, this search can be speeded up by noting that the unknown bits have to fulfill some algebraic relations. For example, the bits $s_{\mu},\ldots,s_{t-1}$ must satisfy the following relations:

 $$\left(\prod_{i=0}^{\lambda-1}\hat{y}^{(\mu+i)}\right)^{\sum_{j... ...mbda-1}\hat{y}^{(\mu+i)} \right)^{\sum_{j=0}^{\mu-1}s_j}}\pmod{n}$$

and

 $$\prod_{i=0}^{\lambda-1}\left(\frac{\hat{y}^{(\mu+i)}}{\hat{y}^... ...ft(\frac{\hat{y}^{(j)}}{\hat{y}^{(j+1)}} \right)^{s_j}} \pmod{n}.$$

Proof.

$$\begin{eqnarray*} \prod_{i=0}^{\lambda-1}\mathop{\widehat{\EuScript{S}}}(\hat{y}... ...a-1}\hat{y}^{(\mu+i)} \right)^{\sum_{j=\mu}^{t-1}s_j}\pmod{n}. \end{eqnarray*}$$

$$\begin{eqnarray*} \frac{\mathop{\widehat{\EuScript{S}}}(\hat{y}^{(0)})}{\mathop{... ...{0\leq j\leq t-1 -\mu}{j\bmod\lambda=i}}{s_{j+\mu}}} \pmod{n}. \end{eqnarray*}$$

Note that if $\lambda=2$, then Eq. (6) simplifies to

$$\left(\frac{\hat{y}^{(\mu)}}{\hat{y}^{(\mu+1)}} \right)^{\sum_... ...ft(\frac{\hat{y}^{(j)}}{\hat{y}^{(j+1)}} \right)^{s_j}} \pmod{n}.$$

Similar relations can be exhibited if $\lambda$ is a power of 2.