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

  • Welcome back! Agenda  Introduction-timelines and how to apply

    Welcome back! Agenda Introduction-timelines and how to apply

    Schulich School of Education CLE/Year 4 Practicum Opportunities2018-19Costa Rica, A144France, H109Kenya (Me To We), H112Trois Pistoles, H110. Application: myinternational.nipissingu.ca
  • Parallel Physical Design for Computer Aided Design

    Parallel Physical Design for Computer Aided Design

    Use trace buffer technology. Trace buffer is embedded inside a Circuit-under-Debug (CUD) Trigger an event in the CUD. Real-time capture values of a few selected flipflops which are stored in on-chip buffers
  • What is the Philosophy of Language?

    What is the Philosophy of Language?

    Indeterminacy of Resemblance. In both the man-on-the-hill case and the twin case, what we have is one representation that exactly resembles two distinct things (man going up vs. man going down, twin #1 vs. twin #2).
  • PG CONNECTION, 2016.01.16 SNK Series PI-Spring Triple deck

    PG CONNECTION, 2016.01.16 SNK Series PI-Spring Triple deck

    Value proposition. SNK PI-Spring Triple Deck - ZK2.5-T… January 16, 2017. Slide . 3 decks in a compact Terminal Block. Rotating top marker holder which does not need to be removed during the wiring for a better circuit identification
  • Microsoft brand template - SourceForge

    Microsoft brand template - SourceForge

    This Microsoft PowerPoint template and usage guidelines has been created for presentations when Microsoft is the lead brand. Internal group identity, and product brand templates are also available on MediaBank. Please be sure to use the correct content to fit...
  • Hegel's Epistemograph, Classification, and Spivak's ...

    Hegel's Epistemograph, Classification, and Spivak's ...

    Part of mainstream education involves learning to ignore this absolutely, with a sanctioned ignorance." Spivak, 1999, p. 2. If we do, we will never be able to understand more than the mainstream with the result being ignorance and injustice.
  • Interwar Romania - WordPress.com

    Interwar Romania - WordPress.com

    The Romanian Jewries: Transylvania & Banat. Before: Hungary. yiddish, orthodox x neolog. Urban middle class: „Hungarians of Mosaic faith" strong antisemitism. N Transylvania (Maramures) more of E type (towns, yiddish, hasidism) Satmar (Satu- Mare) Sighet
  • Input and Output in C - vitscse

    Input and Output in C - vitscse

    I/O in C Lecture 6 Engineering H192 Lecture 06 Winter 2005 Input/Output in C C has no built-in statements for input or output. A library of functions is supplied to perform these operations.