Highly Efficient Algorithms for AES Key Retrieval in Cache Access Attacks
Authors:
- C. AshokkumarCAC. Ashokkumar
- Ravi Prakash GiriRGRavi Prakash Giri
- Bernard MenezesBMBernard Menezes
- 1 March 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 261-275
Abstract
Leakage of information between two processes sharing the same processor cache has been exploited in many novel approaches targeting various cryptographic algorithms. The software implementation of AES is an specially attractive target since it makes extensive use of cache-resident table lookups. We consider two attack scenarios where either the plaintext or ciphertext is known. We employ a multi-threaded spy process and ensure that each time slice provided to the victim (running AES) is small enough so that it makes a very limited number of table accesses. We design and implement a suite of algorithms to deduce the 128-bit AES key using as input the set of (unordered) cache line numbers captured by the spy threads in an access-driven cache-based side channel attack. Our algorithms are expressed using simple relational algebraic operations and run in under a minute. Above all, our attack is highly efficient - we demonstrate recovery of the full AES key given only about 6 - 7 blocks of plaintext or ciphertext (theoretically even a single block would suffice). This is a substantial improvement over previous cache-based side channel attacks that require between 100 and a million encryptions. Moreover, our attack supports varying cache hit/miss observation granularities, does not need frequent interruptions of the victim and will work even if the victim makes up to 60 cache accesses before being interrupted. Finally, we develop analytic models to estimate the number of encryptions/decryptions required as a function of access granularity and compare model results with those obtained from our experiments.Keywords
This publication has 23 references indexed in Scilit:
- Wait a Minute! A fast, Cross-VM Attack on AES2014
- An Approach for Isolating the Sources of Information Leakage Exploited in Cache-Based Side-Channel Attacks2013
- Cross-VM side channels and their use to extract private keys2012
- Pinpointing Cache Timing Attacks on AES2010
- Hardware-software integrated approaches to defend against software cache-based side channel attacks2009
- An Analytical Model for Time-Driven Cache AttacksLecture Notes in Computer Science, 2007
- Cache-Collision Timing Attacks Against AES2006
- Lattice scheduling and covert channels2003
- Side channel cryptanalysis of product ciphersJournal of Computer Security, 2000
- On the estimation of join result sizesLecture Notes in Computer Science, 1994