Research Statement
With the advent of e-commerce and electronic transactions, the need for development of secured systems has grown tremendously.
However history has taught us that designing strong cryptographic algorithms is just the beginning. Although the internal
algorithms are robust against conventional cryptanalysis, implementations of the ciphers may leak valuable secret information
through covert channels commonly referred to as side channels. Cache-attacks are a class of side-channel attacks that affect
all systems that use cache memories. These attacks glean secret information from the cache access patterns. The cache patterns
are manifested through the power consumed and the time required for an encryption. This research work aims at understanding
cache-attacks with the aim of defending against the attack.
Cache-attacks affect every system that uses cache memories. Unlike other forms of side channel attacks, cache-attacks do not always require a close proximity to the encrypting device. In 2009, Crosby, Wallach, and Riedi showed that it is possible to gather timing information about encryptions from any computer connected on the Internet. Thus any computer on the Internet can be compromised by this form of attack. Due to this threat, microprocessor manufactures like Intel have recently added dedicated instructions to prevent cache attacks. However these instructions are only useful for the Advanced Encryption Standard (AES). All remaining ciphers in use today are still vulnerable to being attacked by leakages through the cache.
Current defense strategies are mostly in the implementation of the cipher. These strategies are either infeasible in practice or have an enormous computation time overhead making the cipher unsuitable for most applications. Further there is also no measure of the level of security provided against such counter-measures. Thus it is possible that a countermeasure for one attack would open a vent for another. Alternate strategies require an over hauling of the cache architecture. In 2007, Lee and Wang found that cache interference was the root cause and proposed two designs: a partition locked cache (PLcache) and random permutation cache (RPcache). However incorporating these new cache designs on existing systems is not feasible. Formal models have been developed to counter side-channel attacks. Also, a few provably side-channel resistant ciphers have been proposed. However these proposals are often complex and does not lead to efficient design implementations. In some cases it has also been found to be still vulnerable. This shows that there is a significant gap between the theory developed and the practical world.
The research explores cache attacks with the aim of developing systems which are secure against this deadly attack. First the power of cache-attacks is established by minimizing the attack time and expanding the configurations in which cache-attacks are possible. Minimizing the attack time would require more optimized attacks. One technique is to combine classical cryptanalytic techniques with cache attacks. A cache attack enhanced with differential cryptanalytic techniques can reduce the complexity of an attack on the block cipher CLEFIA from 2^40 to 2^14. In order to determine the kinds of ciphers susceptible to such attacks, ciphers with small table implementations were targeted. A profiled cache timing attack on CLEFIA implemented with small tables requires around 226 encryptions and accurately obtains the secret key 85% of the time. The attack time is less than 5 minutes.
The next part of the research is to pin-point the main causes of cache attack. That is the features in the cache memory and cipher structure most susceptible to cache attacks are identified. It was found that in AES; only the first two rounds are vulnerable. Thus only the first two rounds need to be protected. Similarly, it was found that cache features such as prefetching, parallelization, pipelining, and out-of-order execution lead to attacks.
Cache-attacks would subsequently be formally modeled in order to quantify the amount of information leaked through the cache memory. These models would be used to develop a metric, which could be used to quantify the security of a cipher and its implementation. This would aid in quantifying the security offered by counter-measures and help a naive programmer who is ignorant of the leakages in cache memory.
Cache-attacks affect every system that uses cache memories. Unlike other forms of side channel attacks, cache-attacks do not always require a close proximity to the encrypting device. In 2009, Crosby, Wallach, and Riedi showed that it is possible to gather timing information about encryptions from any computer connected on the Internet. Thus any computer on the Internet can be compromised by this form of attack. Due to this threat, microprocessor manufactures like Intel have recently added dedicated instructions to prevent cache attacks. However these instructions are only useful for the Advanced Encryption Standard (AES). All remaining ciphers in use today are still vulnerable to being attacked by leakages through the cache.
Current defense strategies are mostly in the implementation of the cipher. These strategies are either infeasible in practice or have an enormous computation time overhead making the cipher unsuitable for most applications. Further there is also no measure of the level of security provided against such counter-measures. Thus it is possible that a countermeasure for one attack would open a vent for another. Alternate strategies require an over hauling of the cache architecture. In 2007, Lee and Wang found that cache interference was the root cause and proposed two designs: a partition locked cache (PLcache) and random permutation cache (RPcache). However incorporating these new cache designs on existing systems is not feasible. Formal models have been developed to counter side-channel attacks. Also, a few provably side-channel resistant ciphers have been proposed. However these proposals are often complex and does not lead to efficient design implementations. In some cases it has also been found to be still vulnerable. This shows that there is a significant gap between the theory developed and the practical world.
The research explores cache attacks with the aim of developing systems which are secure against this deadly attack. First the power of cache-attacks is established by minimizing the attack time and expanding the configurations in which cache-attacks are possible. Minimizing the attack time would require more optimized attacks. One technique is to combine classical cryptanalytic techniques with cache attacks. A cache attack enhanced with differential cryptanalytic techniques can reduce the complexity of an attack on the block cipher CLEFIA from 2^40 to 2^14. In order to determine the kinds of ciphers susceptible to such attacks, ciphers with small table implementations were targeted. A profiled cache timing attack on CLEFIA implemented with small tables requires around 226 encryptions and accurately obtains the secret key 85% of the time. The attack time is less than 5 minutes.
The next part of the research is to pin-point the main causes of cache attack. That is the features in the cache memory and cipher structure most susceptible to cache attacks are identified. It was found that in AES; only the first two rounds are vulnerable. Thus only the first two rounds need to be protected. Similarly, it was found that cache features such as prefetching, parallelization, pipelining, and out-of-order execution lead to attacks.
Cache-attacks would subsequently be formally modeled in order to quantify the amount of information leaked through the cache memory. These models would be used to develop a metric, which could be used to quantify the security of a cipher and its implementation. This would aid in quantifying the security offered by counter-measures and help a naive programmer who is ignorant of the leakages in cache memory.
References
[1] D. J. Bernstein. Cache-timing attacks on AES, Technical report, 2005.
[2] D. A. Osvik, A. Shamir, and E. Tromer, Cache attacks and countermeasures: The case of AES In D. Pointcheval, editor, CT-RSA, volume 3860 of Lecture Notes in Computer Science, pages 1-20. Springer, 2006.
[3] Sony Corporation, The 128-bit Blockcipher CLEFIA : Algorithm Specification, 2007.
[4] T. Ristenpart, E. Tromer, H. Shacham, S. Savage, Hey, You, Get Off of My Cloud! Exploring Information Leakage in Third-Party Compute Clouds, proc. ACM Conference on Computer and Communications Security (CCS) 2009, 199-212, ACM, 2009.
[5] S. A. Crosby, D. S. Wallach, and R. H. Ried, Opportunities and Limits of Remote Timing Attacks, ACM Transactions on Information and System Security, Vol. 12, No. 3, Article 17, Pub. date: January 2009.
[6] S. Gueron, Intel® Advanced Encryption Standard (AES) Instructions Set (Rev : 3.0), 2010.
[7] J. Kelsey, B. Schneier, D. Wagner, and C. Hall, Side Channel Cryptanalysis of Product Ciphers, J. Comput. Secur., 8(2,3):141¿158, 2000.
[8] P. Kocher, J. Jaffe, B. Jun, Introduction to Differential Power Analysis and Related Attacks, 1998, http://www.cryptography.com
[9] S. Mangard, N. Pramstaller, E. Oswald, Successfully Attacking Masked AES hardware Implementations", CHES 2005, (LNCS 3659)
[10] K. Tiri, D. Hwang, A. Hodjat, B. C. Lai, S. Yang, P. Schaumont, I. Verbauwhede, Prototype IC with WDDL and Differential Routing - DPA Resistance Assessment, CHES 2005, (LNCS 3659)
[11] N. Pramstaller, E. Oswald, S. Mangard, F. K. Gürkaynak and S. Häne, A Masked AES ASIC Implementation, Austrochip 2004, 2004
[12] M. Alam, S. Ghosh, M.J. Mohan, D. Mukhopadhyay, D.R. Chowdhury, and I.S. Gupta, Effect of glitches against masked AES S-box implementation and countermeasure, IET Information Security, 3(1), 34-44 (2009)
[13] S. Micali and L. Reyzin, Physically observable cryptography, TCC, LNCS Springer, 2004.
[14] F.X. Standaert, O. Pereira, Y. Yu, J. J. Quisquater, M. Yung, and E. Oswald, Leakage Resilient Cryptography in Practice, Cryptology ePrint Archive, Report 2009/341, 2009. http://eprint.iacr.org/.