Cross-VM Side Channels and Their Use in Private Key Extraction

Cross-VM Side Channels and Their Use in Private Key Extraction

Cross-VM Side Channels and Their Use to Extract Private Keys Yinqian Zhang (UNC-Chapel Hill) Ari Juels (RSA Labs) Michael K. Reiter (UNC-Chapel Hill) Thomas Ristenpart (U Wisconsin-Madison) Motivation Security Isolation by Virtualization VM VM Crypto Keys Attacker

Victim Virtualization Layer Computer Hardware Access-Driven Cache Timing Channel VM VM Crypto Keys Attacker Side Channels Victim

Virtualization (Xen) An open problem: Are cryptographic side channel attacks possible in virtualization environment? Related Work Publication Percival 2005 Osvik et al. 2006 Neve et al. 2006 Aciicmez 2007 Aciicmez et al. 2010 Bangerter 2011 MultiCore

Virtualization w/o SMT Target RSA AES AES RSA DSA AES Related Work Publication Percival 2005

Osvik et al. 2006 Neve et al. 2006 Aciicmez 2007 Ristenpart el al. 2009 Aciicmez et al. 2010 Bangerter 2011 MultiCore Virtualization w/o SMT Target RSA AES

AES RSA load DSA AES Related Work Publication Percival 2005 Osvik et al. 2006 Neve et al. 2006 Aciicmez 2007 Ristenpart el al. 2009 Aciicmez et al. 2010 Bangerter 2011 Our work

MultiCore Virtualization w/o SMT Target RSA AES AES RSA load DSA AES ElGamal

Outline Stage 1 Stage 2 Cross-VM Vectors of cache Side Channel measurements Probing Cache Pattern Classification Sequences of SVMclassified labels Noise Reduction

Stage 3 Fragments of code path Code-Path Reassembly Stage 4 Digress: Prime-Probe Protocol PRIME PRIME-PROBE Interval PROBE Time

4-way set associative L1 I-Cache Cache Set Cross-VM Side Channel Probing VM VM Attacker Victim Virtualization (Xen) L1

L1 L1 L1 I-Cache I-Cache I-Cache I-Cache Challenge: Observation Granularity VM/VCPU VM/VCPU Attacker Victim L1 I-Cache 30ms

30ms W/ SMT: tiny primeprobe intervals W/o SMT: gaming schedulers Time Ideally Time Short intervals Use Interrupts to preempt the victim: Timer interrupts? Network interrupts? HPET interrupts?

Inter-Processor interrupts (IPI)! Inter-Processor Interrupts Attacker VM For( ; ; ) { send_IPI(); Delay(); } VM/VCPU Attacker VCPU IPI VCPU

Victim Virtualization (Xen) CPU core CPU core Cross-VM Side Channel Probing Time 2.5 s 2.5 s 2.5 s

Outline Stage 1 Stage 2 Cross-VM Vectors of cache Side Channel measurements Probing Cache Pattern Classification Sequences of SVMclassified labels Noise Reduction

Stage 3 Fragments of code path Code-Path Reassembly Stage 4 Square-and-Multiply (libgcrypt) /* y = xe mod N , from libgcrypt*/ Modular Exponentiation (x, e, N): ei = 1 SRMR let en e1 be the bits of e ei = 0 SR y1 for ei in {en e1}

y Square(y) (S) y Reduce(y, N) (R) if ei = 1 then y Multi(y, x) (M) y Reduce(y, N) (R) Cache Pattern Classification Key observation: Footprints of different functions are distinct in the I-Cache ! Square(): cache set 1, 3, , 59 Multi(): cache set 2, 5, , 60, 61 Reduce(): cache set 2, 3, 4, , 58

Square() Classification Multi() Reduce() Support Vector Machine Noise: hypervisor context switch Square() SVM Multi() Reduce() Read more on SVM training

Support Vector Machine SVM SS SRS RRR R S RMM R MM Outline Stage 1 Stage 2 Cross-VM Vectors of cache

Side Channel measurements Probing Cache Pattern Classification Sequences of SVMclassified labels Noise Reduction Stage 3 Fragments of code path Code-Path Reassembly

Stage 4 Noise Reduction SSRSRRSRMRMR Square Reduce Multi requires robust automated error correction Hidden Markov Model S R

M Square Reduce Multi Unkn Hidden Markov Model SSRS RRSR MRMR S R

M Square Reduce Multi Unkn Hidden Markov Model low confidence Eliminate Non-Crypto Computation

SVM SRRRRRRMRRS MM Eliminate Non-Crypto Computation SRRRRRRMRRS MM S R M Square Reduce

Multi Unkn Eliminate Non-Crypto Computation Key Observations S:M Ratio should be roughly 2:1 for long enough sequences! MM signals an error (never two sequential multiply operations) Start Decryption VCPU Victim

Key Extraction Unkn Unkn Unkn Square Reduce Square Reduce Multi

Reduce VCPU Attacker Virtualization (Xen) L1 L1 L1 L1 I-Cache I-Cache I-Cache I-Cache Multi-Core Processors 0100011...

Another VCPU Victim VCPU Attacker VCPU IPI VCPU Dom0 VCPU L1 L1

L1 L1 I-Cache I-Cache I-Cache I-Cache Multi-Core Processors ..#####... Victim VCPU Dom0 VCPU Another VCPU IPI

VCPU Attacker VCPU L1 L1 L1 L1 I-Cache I-Cache I-Cache I-Cache Multi-Core Processors ##10100... Another VCPU Dom0

VCPU IPI VCPU Victim VCPU Attacker VCPU L1 L1 L1 L1 I-Cache I-Cache I-Cache I-Cache From an Attackers Perspective

#####1001111010#### #0111101011######## ####110101101#####0 1101110############ ###########........ Outline Stage 1 Stage 2 Cross-VM Vectors of cache Side Channel measurements Probing

Cache Pattern Classification Sequences of SVMclassified labels Noise Reduction Stage 3 Fragments of code path Code-Path Reassembly Stage 4 Code-Path Reassembly

1001110010 0111101111 110101101 11101110 DNA ASSEMBLY No error bit! 100111*01*1101110 Outline Stage 1 Stage 2 Cross-VM

Vectors of cache Side Channel measurements Probing Cache Pattern Classification Sequences of SVMclassified labels Noise Reduction Stage 3 Fragments of code path Code-Path

Reassembly Stage 4 Evaluation Intel Yorkfield processor 4 cores, 32KB L1 instruction cache Xen + linux + GnuPG + libgcrypt Xen 4.0 Ubuntu 10.04, kernel version 2.6.32.16 Victim runs GnuPG v.2.0.19 (latest) libgcrypt 1.5.0 (latest) ElGamal, 4096 bits Results Work-Conserving Scheduler 300,000,000 prime-probe results (6 hours)

Over 300 key fragments Brute force the key in ~9800 guesses Non-Work-Conserving Scheduler 1,900,000,000 prime-probe results (45 hours) Over 300 key fragments Brute force the key in ~6600 guesses Conclusion A combination of techniques IPI + SVM + HMM + Sequence Assembly Demonstrate a cross-VM access-driven cachebased side-channel attack Multi-core processors without SMT Sufficient fidelity to exfiltrate cryptographic keys Thank You

Questions? Please contact: [email protected]

Recently Viewed Presentations

  • Object-Oriented Programming: Polymorphism

    Object-Oriented Programming: Polymorphism

    Object-Oriented programming. What is a class. What is an object. Static data and why the main method is static. What are fields. What are methods. What is a constructor. Method overloading. Encapsulation. Inheritance. Polymorphism. Abstract classes. Interfaces
  • The Protista Kingdom

    The Protista Kingdom

    Algae and Land Plants. Charophyceans - closest algal relatives of land plants. Four key traits that strongly suggest a relationship. Rose-shaped complexes for cellulose synthesis. Synthesize the cellulose microfibrils of the cell wall. Peroxisome enzymes. Enzymes that help minimize the...
  • New Lab Request Form

    New Lab Request Form

    Rollover fields for further clarification. Spell check available. Space for up to ten individuals - each appears separately. ... Individuals listed at the top of the form will appear in this section. Once the type of individual is selected (suspect,...
  • 1 SIS Global Reach and Capabilities Company Overview

    1 SIS Global Reach and Capabilities Company Overview

    1984. 1986. 1990. 2012. SIS publishes one of the first books on China's Generation Y. Ruth Stanat publishes The Intelligent Corporation, a book that expounded on effective strategic planning and building the intelligent corporate intranet.
  • Welcome to Introduction to Bioinformatics Wednesday, 16 October

    Welcome to Introduction to Bioinformatics Wednesday, 16 October

    * Trypanosoma brucei Causative agent of sleeping sickness Life Cycle Central Nervous System Death Trypanosoma brucei Dependence on glycolysis Entry of glucose Phosphorylation Breakdown to triose phosphates Conversion to pyruvate Release of pyruvate Arsenate (AsO4 = Asi) Competitive with Pi...
  • Preparing for the 8th Grade Science CRT Exam:

    Preparing for the 8th Grade Science CRT Exam:

    DOK1. The question requires recall and there is nothing to "figure out" The student either knows the answer or they donot. DOK2. The student needs to applyinformation
  • The Crusades

    The Crusades

    Feudal Lords Knights Peasants The First Crusade (1096-1099) Peasant army Untrained Lacked military equipment Many killed by Muslim Turks Knights Succeeded in capturing Jerusalem Second Crusade (1147-1149) After victory many Christians went back home. The Turks eventually took back much...
  • How to Grow Great Tomatoes - University Of Maryland

    How to Grow Great Tomatoes - University Of Maryland

    HGIC video about tomatoes and pruning: ... If anything, the Mg cations could compete with Ca cations for uptake by plant roots making blossom-end rot even worse…. Tomato varieties recommended by University of Maryland Extension ... San Remo, Super Italian,...