Conclusions

The soundness of protocols can be verified by formal methods and thanks to the experience of the designer of good and bad practice. However this is not enough, flaws can be found in a well-designed protocol. Protocols must also be carefully implemented. Usually, programmers use some tricks in order to speed up the computations. In this paper, we illustrate this topic by showing how some secret information might be recovered if the right-to-left square-and-multiply algorithm was used to perform modular exponentiations. This proves once more that security and efficiency are two natural but conflicting goals in cryptography. Note that our attack does not apply to the left-to-right square-and-multiply algorithm. Therefore, the formal definition of correctness for cryptographic protocols must take into account the implementation (hardware and software).

The second warning of this paper is that the protocols must be faults resistant, or at least must provide for how to react in the case of faults. The correctness verification cannot always be achieved by doing calculations twice as proposed in [3]. Our cycling attack can pass through this test. The verification must be done by another (proved secure) way. For example, the Lenstra's attack (see Fig. 2) can be avoided as follows [14]. We use the same notations as in Section 1 (Introduction). Bob first chooses a (small) random number r relatively prime to $n_{\!B}$.Then he computes $m_{rp}=c^{d_{\!B}\bmod{\phi(rp)}} \bmod{rp}$ and $m_{rq}=c^{d_{\!B}\bmod{\phi(rq)}} \bmod{rq}$. If $m_{rp} \equiv m_{rq} \pmod{r}$, then the computations are assumed correct and $m=\mathop{\mathrm{CRT}}(m_{rp} \bmod{p},m_{rq} \bmod{q})$.