Further Cryptanalysis of a Provably Secure CRT-RSA Algorithm

At CCS 2003, a new fault immune CRT-RSA signature algorithm, namely BOS scheme was proposed by Bl¨omer, Otto, and Seifert. Unfortunately, one year later, Wagner presented a practical fault attack on the BOS scheme. How- ever, Wagner\´s attack itself contains a flaw in the most re- alistic "random fault model". Though it has been fixed by Liu et al. at DASC 2006, it is still of interest to see other possible and efficient attacks against the BOS scheme. Re- cently, Ming Li et al. proposed an efficient fault attack on the BOS scheme which targets the secret key dp and some related messages. In this paper, a new fault attack on the BOS scheme is presented. Our attack is similar to but dif- ferent from Li et al.\´s attack and is still more efficient than Wagner\´s attack. To completely break the security of the BOS scheme, the adversaries first induce a permanent fault on the secret RSA key dp or dq and then run the BOS scheme to obtain four faulty RSA signatures. Lastly, the adversaries can obtain the factorization of the RSA modulus by using the Greatest Common Divisor algorithm.