article

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

Authors:

Xiong LiAuthors Info & Claims

Journal of Systems and Software, Volume 86, Issue 1

Pages 100 - 107

https://doi.org/10.1016/j.jss.2012.07.020

Published: 01 January 2013 Publication History

Abstract

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 d"p and d"q, 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.

References

[1]

A vulnerability in RSA implementations due to instruction cache analysis and its demonstration on OpenSSL. In: Malkin, T. (Ed.), CT-RSA 2008, LNCS, vol. 4964, Springer, Heidelberg. pp. 256-273.

[2]

Cheap hardware parallelism implies cheap security. In: 4th Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC 2007), IEEE Press, New York. pp. 80-91.

[3]

On the power of simple branch prediction analysis. In: Robert, D., Pierangela, S. (Eds.), ASIACCS 2007, ACM Press, New York. pp. 312-320.

[4]

Micro-architectural cryptanalysis. IEEE Security and Privacy. v5 i4. 62-64.

[5]

Predicting secret keys via branch prediction. In: Masayuki, A. (Ed.), CT-RSA 2007, LNCS, vol. 4377, Springer, Heidelberg. pp. 225-242.

[6]

New results on instruction cache attacks. In: Mangard, S. (Ed.), CHES 2010, LNCS, vol. 6225, Springer, Heidelberg. pp. 110-124.

[7]

Bernstein, D.J., 2004. Cache-Timing Attacks on AES. http://cr.yp.to/papers.html#cachetiming.

[8]

Cache-timing template attacks. In: Matsui, M. (Ed.), ASIACRYPT 2009, LNCS, vol. 5912, Springer, Heidelberg. pp. 667-684.

[9]

Remote timing attacks are practical. In: Proceedings of the 12th Usenix Security Symposium, 2003, pp. 1-14.

[10]

Brumley, B.B., Tuveri, N., 2011. Cache-Timing Attacks and Shared Contexts, COSADE 2011. http://cosade2011.cased.de/files/2011/cosade2011_talk22_paper.pdf.

[11]

Finding a small root of a bivariate integer equation: factoring with high bits known. In: Maurer, U. (Ed.), EUROCRYPT 1996, LNCS, vol. 1070, Springer, Heidelberg. pp. 178-189.

[12]

Correcting errors in RSA private keys. In: Rabin, T. (Ed.), CRYPTO 2010, LNCS, vol. 6223, Springer, Heidelberg. pp. 351-369.

[13]

Reconstructing RSA private keys from random key bits. In: Halevi, Shai, (Eds.), CRYPTO 2009, LNCS, vol. 5677, Springer, Heidelberg. pp. 1-17.

[14]

Side channel cryptanalysis of product Ci-phers. Journal of Computer Security. v8 i23. 141-158.

[15]

Timing attack on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (Ed.), CRYPTO 1996, pp. 104-113.

[16]

Handbook of Applied Cryptography. 1997. CRC Press, Boca Raton, AM.

[17]

Advances on access-driven cache attacks on AES. In: Biham, E. (Ed.), SAC 2006, LNCS, vol. 4356, Springer, Heidelberg. pp. 147-162.

[18]

OpenSSL, 2006. The Open Source Toolkit for SSL/TLS. http://www.openssl.org.

[19]

Cache attacks and countermeasures: the case of AES. In: Pointcheval, D. (Ed.), CT-RSA 2006, LNCS, vol. 3860, Springer, Heidelberg. pp. 1-20.

[20]

Percival, C., 2005. Cache Missing for Fun and Profit. http://www.daemonology.net/papers/cachemissing.pdf.

[21]

A Programmer's Perspective. 2nd ed. PEARSON Press.

Cited By

Fiolhais LSousa L(2023)Transient-Execution Attacks: A Computer Architect PerspectiveACM Computing Surveys10.1145/360361956:3(1-38)Online publication date: 6-Oct-2023
https://dl.acm.org/doi/10.1145/3603619
Sun YZhang HWang XWang M(2021)Bit-level color image encryption algorithm based on coarse-grained logistic map and fractional chaosMultimedia Tools and Applications10.1007/s11042-020-10373-y80:8(12155-12173)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1007/s11042-020-10373-y
Montasari RHosseinian-Far AHill RMontaseri FSharma MShabbir S(2018)Are Timing-Based Side-Channel Attacks Feasible in Shared, Modern Computing Hardware?International Journal of Organizational and Collective Intelligence10.4018/IJOCI.20180401038:2(32-59)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.4018/IJOCI.2018040103
Show More Cited By

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

Recommendations

Improving timing attack on RSA-CRT via error detection and correction strategy

In timing attack, a class of side channel attack, the attacker attempts to break a cryptographic algorithm by timing the operations of a specific system. Several studies on different types of timing attacks have been published, but they are either ...
A cross-platform cache timing attack framework via deep learning
DATE '22: Proceedings of the 2022 Conference & Exhibition on Design, Automation & Test in Europe

While deep learning methods have been adopted in power side-channel analysis, they have not been applied to cache timing attacks due to the limited dimension of cache timing data. This paper proposes a persistent cache monitor based on cache line ...
Architecting against Software Cache-Based Side-Channel Attacks

Using cache-like architectural components including data caches, instruction caches, or branch target buffers as a side channel, software cache-based side-channel attacks are able to derive secret keys used in cryptographic operations through legitimate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Systems and Software

Journal of Systems and Software Volume 86, Issue 1

January, 2013

247 pages

ISSN:0164-1212

Issue’s Table of Contents

Copyright © © 2012.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 January 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fiolhais LSousa L(2023)Transient-Execution Attacks: A Computer Architect PerspectiveACM Computing Surveys10.1145/360361956:3(1-38)Online publication date: 6-Oct-2023
https://dl.acm.org/doi/10.1145/3603619
Sun YZhang HWang XWang M(2021)Bit-level color image encryption algorithm based on coarse-grained logistic map and fractional chaosMultimedia Tools and Applications10.1007/s11042-020-10373-y80:8(12155-12173)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1007/s11042-020-10373-y
Montasari RHosseinian-Far AHill RMontaseri FSharma MShabbir S(2018)Are Timing-Based Side-Channel Attacks Feasible in Shared, Modern Computing Hardware?International Journal of Organizational and Collective Intelligence10.4018/IJOCI.20180401038:2(32-59)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.4018/IJOCI.2018040103
Maisuradze GRossow CLie DMannan MBackes MWang X(2018)ret2specProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security10.1145/3243734.3243761(2109-2122)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1145/3243734.3243761
Salman SElsadany A(2018)On the bifurcation of Marottos map and its application in image encryptionJournal of Computational and Applied Mathematics10.1016/j.cam.2017.07.010328:C(177-196)Online publication date: 15-Jan-2018
https://dl.acm.org/doi/10.1016/j.cam.2017.07.010
Liu LMiao S(2018)A new simple one-dimensional chaotic map and its application for image encryptionMultimedia Tools and Applications10.1007/s11042-017-5594-977:16(21445-21462)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1007/s11042-017-5594-9
Biswas AGhosal DNagaraja S(2017)A Survey of Timing Channels and CountermeasuresACM Computing Surveys10.1145/302387250:1(1-39)Online publication date: 10-Mar-2017
https://dl.acm.org/doi/10.1145/3023872
Liu LMiao S(2017)An image encryption algorithm based on Baker map with varying parameterMultimedia Tools and Applications10.1007/s11042-016-3925-x76:15(16511-16527)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s11042-016-3925-x
Gruss DSpreitzer RMangard S(2015)Cache template attacksProceedings of the 24th USENIX Conference on Security Symposium10.5555/2831143.2831200(897-912)Online publication date: 12-Aug-2015
https://dl.acm.org/doi/10.5555/2831143.2831200
Yarom YFalkner KFu K(2014)FLUSH+RELOADProceedings of the 23rd USENIX conference on Security Symposium10.5555/2671225.2671271(719-732)Online publication date: 20-Aug-2014
https://dl.acm.org/doi/10.5555/2671225.2671271
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents