Cache Timing Attack on AES
This paper by Sarani Bhattacharya, Chester Rebeiro, and Debdeep Mukhopadhyay from the Dept. of Computer Science and Engineering at IIT Kharagpur, India, delves into the intricacies of a Cache Timing Attack on AES. The study explores the vulnerabilities of AES to such attacks, shedding light on potential threats and security implications. The research provides valuable insights for enhancing cryptographic protocols and safeguarding sensitive information.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Cache Timing Attack on AES Sarani Bhattacharya, Chester Rebeiro, and Debdeep Mukhopadhyay Dept. of Computer Science and Engineering Indian Institute of Technology, Kharagpur, India sarani.bhattacharya,chester,debdeep@cse.iitkgp.ernet.in 5 February 2014 SAG, DRDO
Proposed Work Milestone 1 Cache Attacks on AES block cipher Milestone 2 Differential Cache attacks on Clefia Milestone 3 Analysis of micro-architectural components in the processor.
Cryptographic Communication Kb Ka plaintext plaintext Encrypt Decrypt ciphertext A generic use of crypto
Cryptographic Threat Model Message Message E D Communication Channel Ka Kb leaked Information Bob Alice Side Channels in the real world Through which a cryptographic module leaks information to its environment unintentionally Mallory Assumptions Only Alice Knows Ka Only Bob Knows Kb Mallory has access to E, D and the Communication Channel but does not know the decryption key Kb
Side Channel Sources Threat Model & Security Goal Key dependent Variations computation time Cryptographic Algorithms Traditionally we have handled only Protocols Software Human User Hardware Power consumption EM Radiations Test Methodologies Behavior under faults E/D It is impossible to design a totally secure system with humans in it K Deployment & Usage Real World System
What is Cache? Slow! Fast! Figure from [1]
Cache Memory Leaks Information Microprocessor Cache Memory Main Memory If there is a Cache Hit Access time is less Power Consumption is less If there is a Cache Miss Access time is more Power Consumption is more
Cache Attacks : The Principle P0 P1 K0 K1 XOR XOR Sbox Sbox Power and Time for the second access depends on the previous sbox access. If cache hit : K P K P = = 0 0 1 1 K K P P 0 1 0 1 K K Since we know P0 and P1, we can determine but we need to differentiate between a cache hit and miss. 0 1
Classes of Cache Attacks Three ways to identify cache behavior Cache Timing Attacks Cache Access Attacks Cache Trace Attacks
Cache Access Attacks : Osviks Attack Uses a spy program to determine cache behavior Cache Memory Part of the cache memory occupied by tables Cache Miss Microprocessor Cache Hit AES Spy Memory
Cache Trace Attacks The Power Profile of the system gives away cache behavior. Without Cache Miss With Cache Miss
Causes of Cache Timing Attacks 1. Number of Cache Misses (For Large Tables) : The number of cache misses that occur during the entire encryption. 2. Micro-architecture effects (For Small Tables) : The number of cache misses that occur in each round. This is affected by the micro-architectural features in the cache.
Cache Memories Low cost solution to bridge the performance gap between processor and memory It has been in use since 1960s and is present in all computing platforms More than 100x performance gains with cache memory 14
Cache CacheLeaks Memories Leak Information Cache Hits Cache Misses Oscilloscope Waveforms Power Consumptions of 4 accesses to the S-Box But the correspondence is not so obvious for the complete cipher.
Cache Attacks : The Principle P0 P1 K0 K1 XOR XOR Sbox Sbox Power and Time for the second access depends on the previous sbox access. If cache hit : K P K P = = 0 0 1 1 K K P P 0 1 0 1 Since we know P0 and P1, we can determine K0 xor K1 Reduce the key space from 22n to 2n+ 16
Differential Cache Attacks On a Cache hit Reduces the key space from 22n to 2n+ In order to reduce the key space further, we take another plaintext, resulting in a hit. The corresponding cache hit equation is: 17
Differential Cache Attacks (contd.) Combining these equations we have the following differential equation: The uncertainty of the key now depends on the differential property of the S-Box. Thus, if favg is the number of keys on an average that would satisfy the above equation, then the key space is reduced to: N=2 favg 18
A Differential Cache Attack on CLEFIA CLEFIA is a block cipher used by Sony for Digital Rights Management Authorized Library of CLEFIA (with secret key) Application Software
Differential Cache Attack on CLEFIA F0 F1 128 bit block cipher from Sony. Generalized Feistel Structure Number of rounds : 18 Whitening Keys added at the beginning and end. Attacking Clefia requires finding any set of 4 round keys. RK0, RK1, RK2, RK3 20
Observations in CLEFIA F0 F1 Matrices M0 and M1in the F functions does not attain complete diffusion (is not diffusion optimal). If 5 MSBs of the output of each S-Box are known, then 3 bits of F0 and 2 bits of F1 are computable. For a differential pair, the CLEFIA S-Boxes cause 60% in S0 and 50% in S1 input output differentials to be invalid. For a valid input output differential, on an average 1.28 actual values are possible for S0, while it is 1.007 for S1. 21
Differential Cache Attack CLEFIA The na ve cache trace attack on CLEFIA requires 240 encryptions Using Differential Trace Attack, CLEFIA can be broken in less than 214 encryptions This may not be the optimal attack, but it brings us closer. 22
Attack Steps First determine RK0 and RK1 Then determine (RK0+WK0) and (RK1+WK1) Use this information to determine RK4 and RK5 Finally, the key expansion algorithm to compute 57 bits of RK2|RK3.
Feistel Ciphers with SP round function Diffusion layer Key addition Substitution layer Is being considered as a good structure for ciphers Adopted in CLEFIA, CAMELLIA, SMS4, E2
Complete Differential Attack on CLEFIA
Determining RK0 and RK1 Choose plaintexts P and Q to obtain cache hits in the first and second rounds. This would give the difference equations The complexity of finding these relations is 27.
Determining WK0+RK2 and WK1+RK3 Choose plaintexts P and Q to get cache hits in the third round. This would give the relations The complexity of finding these relations is 211
Experimental Setup Test Platform: Xilinx XC2VP30 FPGA on the SASEBO side channel attack evaluation board. 300 MHz PowerPC-405 core 16 kB two way set associative data cache. 32 kB of the FPGAs block RAM configured as the processor memory. CLEFIA s reference code from SONY was run on PowerPC (http://www.sony.net/clefia) 21/12/2010 Registration Seminar 28
Power Profiles for two first round access patterns 20 MMHHHHHM MMHHHHHH 15 Power Consumption (mV) 10 5 0 -5 -10 -15 -20 5 10 15 20 25 30 35 40 Time ( microseconds) The difference is not so obvious as for the single S-Box seen earlier. However correlation analysis seems to pick up the small difference. 21/12/2010 Registration Seminar 29
Classification of Hit Miss Patterns This helps us to classify the Hit Miss patterns based on their power consumption: for example the first round has 64 Hit Miss patterns. We were able to create 64 different power profiles, corresponding to each Hit Miss pattern This classification helps to identify an unknown Hit Miss pattern from an observed power profile
Correlation Analysis with no. of measurements 1.001 1 Correlation Value 0.999 0.998 0.997 0.996 1 2 4 8 16 32 64 128 256 Number of Measurements The power profiles for the same Hit Miss patterns show a strong correlation: It increases from 0.997 to 1 with the number of measurements (as shown above) For two different patterns it is around 0.8 21/12/2010 Registration Seminar 31
Differential Cache Attack with Timing as Side-Channel
Differential Trace Attack On a Cache hit Reduces the key space from 22n to 2n+ In order to reduce the key space further, we change x0 by a small displacement dx0 This small displacement gets converted to a random change due to the s-boxes in the F function. We then restore cache hits by changing y
Differential Trace Attack contd. So we now have the input difference (dx0 ) and the output difference of the F function (dy = y y ) From the input difference dx0 we can determine all possible output differences of the s-box : (d0, 0, 0 ..,0). Apply the transformation : (d0, 0, 0 ..,0). M to get (dz0, dz1, , dzn). For the correct differential dz0 = dy0 , dz1 = dy1 . We thus can obtain the input and output differential for the s-box to get key candidates. dy0 dy1 dy2 dz0 d0 dx0 S1 dz1 0 0 S2 M dz2 0 0 S3
Obtaining the key from here dx dy We know dx and the corresponding dy
Differential Cache Attacks (Step 1 : the collision setup) Keep x constant and vary y until all s-box accesses in the second round are cache hits The following equation holds y k = ) 0 ( i ) 0 ( ) 1 ( i ( , ) x F x k k i i i
Differential Cache Attacks (Step 2 : the disturbance) Change x0 to (x0 ^ dx0) where dx0 is a small displacement Some of the cache hits in the second round get lost
Differential Cache Attacks (Step 3 : the restoration) Change y again to restore cache hits in the second round (All bytes of y may need to be changed in order to restore cache hits) We can obtain the differences in y : dy0, dy1, dy2, dy3
Assuming Collision is Set, We Can find the Keys
Determining ??2 ??0 and ??3 ??1 To determine the values of these intermediate rounds we need to distinguish a desirable and an undesirable Cache Hit. We proposed two Methods to distinguish, that Elimination method and Probabilistic Method. Elimination is deterministic but cannot be used always.
Determining ??2 ??0 and ??3 ??1(Contd )
Determining ??2 ??0 and ??3 ??1(Contd )
Finally We determine ??4,??5 To determine ??4,??5 we use round 3, 4 , F0 tale access, plain text ?8,?9, ?10, ?11 difference with ?12,?13, ?14, ?15. The undesirable collisions occurring with F1 are taken removed by probabilistic method. Total no of encryptions required to correctly determine the keys are
Current Countermeasures are Adhoc! Software Hardware Cache Memory Remove Cache Memory Non deterministic access ordering Randomized cache policies Increase cache line size Dynamic Partitioning cache Processor Enforce fixed time/instruction Disable cache sharing New instructions to lock table into cache Dedicated crypto-processor Adding Noise Random Skews Dummy operations Permutation Controlling Cache Misses Cache Warming Small Tables Without sboxes Constant Time Compensation loop Intel AES-NI
References Daniel J.Bernstein , Cache-timing attacks on AES , Department of Mathematics, Statistics, and Computer Science,The University of Illinois at Chicago. C.Rebeiro, D.Mukhopadhyay, J.Takahashi and T.Fukunaga, ''Cache Timing Attacks on CLEFIA'', INDOCRYPT 2009 Chester Rebeiro, Mainack Mandal, Debdeep Mukhopadhyay, Pinpointing Cache Timing Attacks on AES , VLSID 2010. C.Rebeiro and D.Mukhopadhyay, ''Cryptanalysis of CLEFIA using Differential Methods with Cache Trace Patterns'', CT-RSA 2011 C. Rebeiro, R. Poddar, A. Datta, and D. Mukhopadhyay, ''An Enhanced Differential Cache Attack on CLEFIA for Large Cache Lines'', INDOCRYPT 2011
