Article Preview
Top1. 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.