Cryptology ePrint Archive: Report 2017/896

Design, Implementation and Performance Analysis of Highly Efficient Algorithms for AES Key Retrieval in Access-driven Cache-based Side Channel Attacks

Ashokkumar C and M. Bhargav Sri Venkatesh and Ravi Prakash Giri and Bernard Menezes

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 especially 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

Category / Keywords: secret-key cryptography / AES, access-driven, cache attacks, side channel, table lookup

Original Publication (with major differences): Security and Privacy (EuroS&P), 2016 IEEE European Symposium on
DOI:
10.1109/EuroSP.2016.29

Date: received 12 Sep 2017, last revised 18 Sep 2017

Contact author: ashokkumar at cse iitb ac in

Available format(s): PDF | BibTeX Citation

Version: 20170918:130700 (All versions of this report)

Short URL: ia.cr/2017/896

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]