Research on Cache Timing Attack Against RSA with Sliding Window Exponentiation Algorithm

Research on Cache Timing Attack Against RSA with Sliding Window Exponentiation Algorithm

Caisen Chen (Ministry of Science Research, Academy of Armored Forces Engineering, Beijing, China), Yangxia Xiang (Department of Information Engineering, Academy of Armored Forces Engineering, Beijing, China), Yuqin DengLiu (Department of Information Engineering, Academy of Armored Forces Engineering, Beijing, China) and Zeyun Zhou (Ministry of Science Research, Academy of Armored Forces Engineering, Beijing, China)
DOI: 10.4018/IJITN.2016040108
OnDemand PDF Download:


The vulnerabilities of the RSA cryptographic algorithm are analyzed, and it is not securely implemented. As the simultaneous multithreading could enable multiple execution threads to share the execution resources of a superscalar between the chipper process and the spy process, the shared access to memory caches provides an easily used high bandwidth covert channel between threads, allowing that a malicious thread can monitor the execution of another thread. This paper targets at RSA algorithm which is implemented with sliding window exponentiation algorithm via OpenSSL, the attacker can monitor the cryptographic thread by executing a spy thread, recording the timing characteristic during the RSA decryption when reading the Cache. The attacker can recover the original key via analyzing these timing measurements. Finally, the authors provide some countermeasures of how this attack could be mitigated or eliminated entirely.
Article Preview

1. Introduction

Cache-based side channel attacks have been known for more than a decade. In such attacks, the attacker forces contention on cache sets the victim uses, in order to identify victim activity in these cache sets. Cryptographic devices leak “side-channel” information such as timing and power consumption information that is easily measurable, radiation of various levels, and more. Side channel attacks exploit this “side-channel” information to derive confidential information, particularly secret keys used in cryptographic systems. Recently, there are newly developed software-based side channel attacks which exploit architectural features of modern commodity processors such as caches and branch predictors. These attacks do not require physical access to target or direct access to the memory space of cipher process and are conducted through legitimate software operations. As a result, they pose serious threats to modern computer systems (Aciicmez, & Mez, 2007).

One form of interference through shared pages results from the shared use of the processor cache. When a process accesses a shared page in memory, the contents of the accessed memory location is cached. Gullasch et al. (2011) describes a side channel attack technique that utilizes this cache behavior to extract information on access to shared memory pages. The limiting factor of all existing attacks is that sophisticated knowledge about the attacked algorithm or software is necessary, i.e., access to the source code or even modification of the source code (Brumley, B. B., & Hakala, R. M., 2009) is required in order to identify vulnerable memory accesses or the execution of specific code fragments manually.

In this paper, we focus on side-channel cryptanalysis of cryptosystems on commodity computer platforms. Especially, we analyze one of the CPU components--Cache, from side-channel point of view. We show that the functionalities of cache create very serious security risks in software systems, especially in software based cryptosystems.

RSA is a public key cryptosystem which is developed by Rivest, Shamir and Adleman (1983). The main computation in RSA decryption is the modular exponentiation.

(1) where C is the message of ciphertext, d is the private key that is a secret, and N is the public modules which is known to anyone, is a product of two large primes p and q. There are some different methods to compute an exponentiation, such as binary Square-and-Multiply Exponentiation Algorithm, Chinese Remainder Theorem (CRT), and Sliding Window Exponentiation (SWE) Algorithm and so on (Gruss, D., Spreitzer, R., & Mangard, S., 2015), (Du, S., Li, Z., Zhang, B., & Lin, D., 2015).

In this paper, we mainly consider the effect of Cache timing attack on the RSA algorithm implemented using SWE. The cache accesses should be visible in the timing during the RSA decryption. This paper proposes a new cryptanalysis method on RSA via analyzing the cache timing data.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing