Improvement of trace-driven I-Cache timing attack on the RSA algorithm

• Published in: The Journal of systems and software 2013-01, Vol.86 (1), p.100-107
• Main Authors: Chen, CaiSen, Wang, Tao, Kou, YingZhan, Chen, XiaoCen, Li, Xiong
• Format: Article
• Language: English
• Subjects: Algorithms; Cache; Computer programs; Cryptography; Decisions; Error correction & detection; Error detection; Feasibility; Instruction cache timing attacks; Public Key Infrastructure; RSA cryptographic algorithm; Side-channel attacks; Software; Spying; Studies; Time measurements; Trace-driven
• ISSN: 0164-1212; 1873-1228
• DOI: 10.1016/j.jss.2012.07.020

► We build a trace-driven I-Cache timing attack model on the RSA algorithm via spying on the whole instruction cache. ► An improvement can recover more bits of exponent than the former and further reduce the search space of the key. ► The full private key can be recovered from the scattered known bits which were recovered by I-Cache timing attack. ► An error detection mechanism is proposed to detect some erroneous decisions of the operation sequences. The previous I-Cache timing attacks on the RSA algorithm which exploit the instruction path of a cipher are mostly proof-of-concept, and it is harder to put them into practice than D-Cache timing attacks. We propose a trace-driven timing attack model on the RSA algorithm via spying on the whole I-Cache, instead of the partial instruction cache to which the multiplication function mapped, by analyzing the complications in the previous I-Cache timing attack on the RSA algorithm. Then, an improved analysis algorithm of the exponent using the characteristic of the window size in SWE algorithm is provided, which could further reduce the search space of the key bits than the former. We further demonstrate how to recover the private key d from the scattered known bits of dp and dq, through demonstrating some conclusions and validating it by experimentation. In addition, an error detection mechanism to detect some erroneous decisions of the operation sequences is provided to reduce the number of the erroneous recovered bits, and improve the precision of decision. We implement an I-Cache timing attack on RSA of OpenSSL in a practical environment, the experimental results show that the feasibility and effectiveness of I-Cache timing attack can be improved.