Cryptanalysis of a provably secure CRT-RSA algorithm

ABSTRACT

We study a countermeasure proposed to protect Chinese remainder theorem (CRT) computations for RSA against fault attacks. The scheme was claimed to be provably secure. However, we demonstrate that the proposal is in fact insecure: it can be broken with a simple and practical fault attack. We conclude that the proposed countermeasure is not safe for use in its present form.

REFERENCES

• 1: R. Anderson, M. Kuhn, "Tamper resistance---a cautionary note," 2nd USENIX Workshop on Electronic Commerce, pp.1--11, 1996.
• 2: Ross J. Anderson , Markus G. Kuhn, Low Cost Attacks on Tamper Resistant Devices, Proceedings of the 5th International Workshop on Security Protocols, p.125-136, April 07-09, 1997
• 3: H. Bar-El, H. Choukri, D. Naccache, M. Tunstall, C. Whelan, "The sorcerer's apprentice guide to fault attacks," Workshop on Fault Detection and Tolerance in Cryptography, June 2004.
• 4: Johannes Blömer , Martin Otto , Jean-Pierre Seifert, A new CRT-RSA algorithm secure against bellcore attacks, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948151]
• 5: D. Boneh, R.A. DeMillo, R.J. Lipton, "On the importance of checking cryptographic protocols for fault," EUROCRYPT'97, Springer-Verlag, LNCS 1233, pp.37--51, 1997.
• 6: M. Joye, A.K. Lenstra, J.-J. Quisquater, "Chinese remaindering based cryptosystems in the presence of faults," Journal of Cryptology, vol. 12, no. 4, pp.241--245, 1999.
• 7: A.K. Lenstra, "Memo on RSA signature generation in the presence of faults," Sept. 1996.
• 8: Sung-Ming Yen , Marc Joye, Checking Before Output May Not Be Enough Against Fault-Based Cryptanalysis, IEEE Transactions on Computers, v.49 n.9, p.967-970, September 2000 [doi>10.1109/12.869328 ]
• 9: Sung-Ming Yen , Seungjoo Kim , Seongan Lim , SangJae Moon, RSA Speedup with Residue Number System Immune against Hardware Fault Cryptanalysis, Proceedings of the 4th International Conference Seoul on Information Security and Cryptology, p.397-413, December 06-07, 2001

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Security

Keywords:
RSA, chinese remainder theorem, cryptanalysis, fault attacks