Skip to content

Hardware-Backed Heist: Extracting ECDSA Keys from Qualcomm's TrustZone

Qualcomm'un QSEE/Keymaster'ına karşı bir cache ve branch-predictor side channel'ı, signing sırasında ECDSA nonce bit'lerini leak eder ve hardware-backed keystore'dan 256-bit bir private key'in tam recovery'sine olanak tanır.

Mechanism

Bug class: bir TEE, untrusted world ile microarchitectural state paylaşır ve non-constant-time bir ECDSA kullanır

Android'in hardware-backed keystore'u, private key'leri TrustZone secure world'ünün (Qualcomm'un QSEE'si) içinde saklar, öyle ki rooted bir Android (normal world) kernel'i bile onları okuyamaz. Security boundary, TrustZone tarafından enforce edilen normal-world / secure-world ayrımıdır.

İki gerçek birleşerek onu kırar:

  1. Shared microarchitecture. TrustZone, L1 data cache'i veya branch target buffer'ı (BTB) partition etmez. Normal world ve secure world aynı cache set'leri ve predictor entry'leri üzerinde contend eder, böylece secure-world memory-access ve branch pattern'leri normal world'den gözlemlenebilir hâle gelir.
  2. Secret-dependent control flow. ECDSA signing routine'inin scalar multiplication'ı, per-signature nonce k'yı k'nın bit'lerine bağlı code path'leri ve table lookup'larıyla işler. Bu access pattern'lerini gözlemlemek, her nonce'un birkaç most/least-significant bit'ini leak eder.

Signature başına bir avuç nonce bit'i bile leak etmek, ECDSA key recovery'sini Hidden Number Problem (HNP)'e dönüştürür: birçok partially-known nonce üzerinde bir lattice reduction, long-term private key'i recover eder. İhlal edilen invariant "secret-dependent operasyonlar constant-time ve isolated olmalıdır"dır; ikisi de geçerli değildi.

Walkthrough

High-level recovery akışı (kavramsal)
  1. Normal world'den spy yap. Yüksek çözünürlüklü L1D cache üzerinde Prime+Probe yapan ve aynı anda BTB'yi probe eden, düşük gürültüyle yüksek temporal ve spatial hassasiyet elde eden unprivileged bir monitor çalıştır (public Cachegrab tooling'i bunu Cortex-A core'larında gösterir).
  2. Signing'i tetikle. Spy trace'lerini örneklerken, keystore'dan (Keymaster) seçilen mesajlar üzerinde ECDSA P-256 signature'ları üretmesini tekrar tekrar iste.
  3. Nonce bit'lerini extract et. Per-trace cache/branch aktivitesini scalar-multiplication yapısıyla correlate et, böylece her nonce k'nın az sayıda bit'ini çıkar.
  4. HNP'yi çöz. Birçok (signature, partial nonce) çifti verildiğinde, eşitsizlikler kur ve random subsample'lar üzerinde tekrarlı lattice (LLL/BKZ) reduction'ları çalıştır; doğru 256-bit private key birkaç denemeden sonra (dakika mertebesinde) ortaya çıkar.

Bir Nexus 5X (Snapdragon 808, Cortex-A57/A53) üzerinde gösterildi. CVE-2018-11976 olarak takip edilir.

Detection

  • On-device anomali: bir Keymaster signing servisi yüksek frekansta exercise edilirken, sıkı, tekrarlı cache-eviction / timing loop'ları (Prime+Probe pattern'i) yapan unprivileged bir process.
  • Telemetry: tek bir app'ten anormal hacimde keystore signing request'i; TEE ile birlikte pin'lenmiş bir core'da sürekli %100 CPU.
  • EDR/heuristic: cycle counter'lar üzerinden per-access latency'yi ölçen ve shared cache set'leri map'leyen native code — benign mobil app'lerde nadirdir.
  • Leak'in kendisi yalnızca timing'dir; tespit, spying workload'una ve anormal keystore call oranlarına odaklanır.

Mitigation

Qualcomm tarafından Nisan 2019 Android güvenlik güncellemesinde düzeltildi

Qualcomm'a 2018'de rapor edildi; müşteriler 1 Ekim 2018'de bilgilendirildi; patch Nisan 2019 Android güvenlik bülteninde CVE-2018-11976 altında yayımlandı.

  • Constant-time / blinded ECDSA: scalar multiplication'ı data-oblivious yap ve nonce/scalar blinding ekle, böylece gözlemlenen access pattern'leri artık k ile correlate olmasın. Bu, Qualcomm'un fix yönüydü.
  • Microarchitectural sharing'i azalt: world switch'lerde secure/normal world boundary'si boyunca shared cache ve predictor state'i flush'la/partition et.
  • Defense in depth: keystore signing'i rate-limit et ve bir attacker'ın toplayabileceği signature sayısını sınırlayan key-use policy'lerini tercih et (HNP birçok sample'a ihtiyaç duyar).

References