[side-channel] FLUSH+RELOAD: a High Resolution, Low Noise, L3 Cache Side-Channel Attack

1. Introduction

Flush+Reload는 cross-core, cross-VM 환경에서도 동작하는 고해상도 캐시 사이드채널 공격이다.

기존 캐시 공격과 달리 공격자(spy)와 피해자(victim)가 같은 CPU 코어에서 실행될 필요가 없다는 점이 핵심적인 차별점이다.

1.1 핵심 특징

• Cross-core attack

  → 공격자와 피해자가 서로 다른 CPU 코어에서 실행 가능

• Cross-VM attack

  → 서로 다른 가상머신(VM) 간에도 공격 가능

1.2 주요 장점

2. Preliminaries

2.1 Page Sharing

페이지 공유는 두 가지 목적을 가진다.

Page Sharing 방식

Copy-on-Write (CoW)

• 공유 페이지는 읽기 전용

• write 발생 시:

CoW는 내용 변경은 막지만 캐시 접근 패턴까지 숨기지는 못한다

2.2 Cache Architecture

기본 개념

• Cache line: 캐시에 저장되는 최소 단위 (보통 64 bytes)

• Cache set: 여러 개의 cache line을 담는 단위

• Cache associativity: 한 cache set이 담을 수 있는 line 개수
  • L1, L2: 8-way
  • L3 (LLC): 12-way

Cache hierarchy

CPU에 가까울수록 빠르고, 메모리에 가까울수록 느림

LLC의 특징

LLC는 inclusive cache

• L1, L2에 있는 데이터는 반드시 LLC에도 존재

• LLC에서 eviction → L1, L2에서도 제거

• clflush로 전체 캐시 계층 제어 가능

→ Flush+Reload 공격의 핵심 전제

2.3 Cache Side-Channel Protocols

공격의 기본 아이디어는 다음과 같다.

기존 접근 방식

2.4 Prior Works와 LLC의 한계

기존 공격들이 L1 캐시에 집중했던 이유:

• victim 실행을 중단시키는 공격 구조 (scheduler 공격)

• L1 캐시는 코어 전용 → 타이밍 정밀

LLC 공격이 어려웠던 이유:

• 캐시 크기가 커서 동기화가 어려움

• 가상 메모리로 인해 주소 → 캐시 매핑이 불투명

• 결과적으로 LLC 채널은 bandwidth가 낮음

→ Flush+Reload는 page sharing + clflush로 해결

2.5 RSA Background

RSA는 대표적인 공개키 암호 시스템이다.

Key Generation

• 두 소수 선택: p, q

• n = p × q

• 오일러 파이 함수: φ(n) = (p-1)(q-1)

• 공개 지수 e 선택 (GnuPG: 65537)

• 개인 지수 d ≡ e⁻¹ (mod φ(n))

암호화 / 복호화

Square-and-Multiply

• bit = 0 : square → reduce

• bit = 1 : square → reduce → multiply → reduce

multiply 코드의 cache line 접근 여부로 비트 추측 가능

3. Flush + Reload Technique

3.1 기본 프로토콜

• 빠름 → victim 접근

• 느림 → victim 접근 없음

3.2 Wait Period Trade-off

• wait 증가 → miss 감소

• wait 증가 → 시간 해상도(granularity) 감소

해결책

• 루프 내부처럼 자주 실행되는 코드 타겟

• 빈도로 패턴 복원

3.3 False Positive

• 실제 접근 없는데 접근한 것처럼 보이는 현상

• 원인 :
  • speculative execution
  • data prefetching

→ 분석 단계에서 필터링 필요

3.4 핵심 명령어

3.5 Hypervisor Noise

• L1 hit: 33 ~ 43 cycles

• Memory miss: ~230 cycles

• Threshold: ~120 cycles

• KVM 환경: 6000+ cycles outlier 발생

VM exit, page fault, EPT 관리, 스케줄링 개입 때문 → outlier 제거 필요

4. Attacking GnuPG

4.1 공격 시나리오

LLC는 물리 주소 기반 → ASLR 영향 거의 없음

4.2 Trace 구현

• Time slot: 2,500 CPU cycles

• 각 슬롯에서 :
  • square
  • multiply
  • reduce

    각각 대표 cache line 1개 probe

• 함수 초반부는 speculative execution 때문에 회피

4.3 Bit Pattern 해석

단일 슬롯은 noisy → 연속 슬롯의 패턴으로 판단

4.4 Observation 결과

• 1,000개의 서명 관찰

• spy와 victim 비동기 실행

• error 0개 확률 ≈ 33%

환경별 결과:

• HP > Dell (CPU 마이크로아키텍처 차이)

• Same-OS > Cross-VM (가상화 오버헤드)

에러가 많으면 brute-force 불가 예: 20 bits error → 2²⁰

4.5 Search Space 감소 (CRT-RSA)

• RSA는 CRT 최적화 사용

• d_p 또는 d_q 중 하나만 정확해도 키 복구 가능

• 에러가 적은 CRT 컴포넌트 선택

4.6 Recovery 전략

• 기존 연구 : 27% ~ 70% 비트로 키 복구 가능

• Flush+Reload : 90% 이상 관측 (위치 불확실)

해결

• 여러 서명 결과 병합

• 에러 위치가 서로 다를 확률 활용

4.7 Limitations

• spy와 victim은 같은 physical CPU 필요

• 실환경에서는 다른 프로세스 노이즈 존재

• 병렬 GnuPG 인스턴스 구분 불가

• 최소 time slot ≈ 2,200 cycles

  → 짧은 키에서는 해상도 부족

5. Mitigation Techniques

• Flush Reload 공격에는 네가지 요소가 필요 :
  • data flow from sensitive data to memory access patterns
  • memory sharing between the spy and the victim
  • accurate, high resolution time measurements
  • unfettered use of the clflush instruction

• clfulsh 의 사용처 :
  • enhance memory coherence
  • control the use of the cache for improving program performance
  • clflush 가 있는 이유 : 캐시 저장에서 오류가 발생할 상황을 대비해서(프로세서가 캐시를 불러올 적에 old cache를 불러오는 상황 등)

• 해결책 제안 : clflush instruction의 권한을 제한
  • 쓰기 권한 있는 페이지에만 clflush 허용
  • os가 허용한 영역에만 flush 가능하게 페이지 속성(PAT)으로 통제

• ARM 아키텍처 : cache line 지우기가 있지만, 특권 모드에서만 가능 → 상대적으로 Flush Reload 공격에 대해 안전

• AMD
  • Intel inclusive LLC: L1/L2에 있으면 LLC(L3)에도 복사본이 있음 → LLC에서 지우면 아래도 같이 영향
  • non-inclusive: L1에만 있고 LLC에 꼭 있을 필요가 없음 → LLC를 flush해도 다른 코어 L1에 남아있으면, victim이 L1에서 그냥 읽어버려서 spy가 LLC에 로드된 흔적을 못 잡음

• HW based countermeasures cannot provide immediate solution → SW based solutions are required

• preventing page sharing → it will increase memory requirements

• partial solution :

• software diversification : VM마다 바이너리(또는 페이지 내용)를 미묘하게 다르게 만들어서 동일성을 깸
  • ASLR : 주소만 다르게
  • Diversification : 내용(바이트) 자체를 다르게

• high resolution clock :
  • 타이머의 해상도를 낮추거나, 노이즈를 추가하는 방법으로 방어 → 공격자가 다른 방식으로 고품질 clock 생성 가능

GnuPG ver 1.4.14

• mitigate the attack using the square-and-multiply-always algorithm

• the algorithm executes square and the multiply steps for each bit, but ignores the result of the multiply step for bits of value 0 → 코드 실행 패턴(어떤 함수/라인이 실행되는지)이 비트에 따라 달라지지 않게 만듦

• when introducing instructions with no effect → 컴파일러가 지워버릴 수 있음(최적화) → 다시 사이드 채널 공격 가능 그러나 GnuPG fix 에서는 optimiser cannot know that added addition(함수 호출 부분) does not have side-effects → 유지

• 여전히 ‘비트에 따라 달라지는 코드 섹션’ 존재(이론적으로 악용 가능) → 그럼에도 Flush + Reload 로는 관찰이 불가능 한 이유 :

• this fix does not protect against other forms of side-channel attack
  • the code is likely to be vulnerable to Branch Prediction Analysis
  • as access patterns to data depend on the values of exponent bits, the code is likely to be vulnerable to Prime+Probe attacks → 이러한 공격은 constant time exponentiation 으로 방어 가능
  • constant time exponentiation : 함수와 메모리 주소 접근이 고정되어있고 exponent bits에 의존하지 않음

• NaCl : constant-time 암호 라이브러리

• OpenSSL RSA : 엄밀히 constant time 이 아닐 수 있지만, Flush+Reload 가 겨냥한 메모리 라인 접근 패턴은 비밀 비트에 의존하지 않음 → Flush Reload 공격에는 안전함

• constant time 이 안전할 순 있지만, overhead도 있기에 암호 쪽에선 이상적 / 일반 sw, system에서는 페이지 공유 정책, clflush 제약, dedup 끄기 같은 시스템 차원 해결책도 필요

6. Related work

• page sharing → exposes guests to information leakage 이걸 이용하여 :
  • covert channel(은닉 채널) 만들기
  • OS fingerprinting(상대 VM의 OS 종류 추정)
  • 다른 VM에서 어떤 앱/데이터가 존재하는지 탐지 등과 같은 공격들이 제안됨

• 이러한 공격들이 공통 원리 : Copy-on-Write(COW)
  • 페이지가 공유된 상태에서 누군가 쓰기(write)를 하면 : 그 순간 페이지 복사(copy) 발생, 복사 과정은 눈에 띄게 느림
  • 공격자 : 이 페이지에 write 했을때 느려진다 → 이 페이지는 다른 VM이랑 공유되고 있다 라고 추론

• 한계 : page de-duplication 자체가 느린 과정, COW 로 인한 지연도 드문 이벤트 → 해상도가 매우 낮음

Gullasch et al.

• AES 구현에서 S-box 접근 패턴을 추적

• 캐시 사이드 채널을 사용

• 같은 코어 전제

• LLC는 활용하지 않음

이 논문이 확장한 점

Zhang et al.

• 가상화 환경을 타겟으로 함

• 다른 VM에서 실행 중인 GnuPG의 ElGamal 개인키 추출

• Xen 하이퍼바이저 스케줄러 취약점에 의존

한계

• 해상도가 낮음

• 짧은 키는 못잡음(4096 bit modulus 사용)

• 노이즈가 심해서 필터링 필수, 6시간 연속 복호화

Weiß et al.

• Bernstein 공격을 변형한 가상 환경에서의 캐시 타이밍 공격

• L4 마이크로 커널 환경에서 도메인 간 통신 시간이 매우 짧다는 특수성을 이용

• 특성 커널 구조에 의존, 일반적인 VM/클라우드 환경에 바로 적용되긴 어려움

7. Conclusion

7.1 의의

7.2 GnuPG

• 이메일 암호화, 파일 암호화, 통신 암호화 등에 쓰이는 표준급 암호 소프트웨어 → 취약한 GnuPG 버전이 돌아가는 시스템 멀티테넌트 환경이나 신뢰할 수 없는 코드가 함께 실행되는 환경에서는 안전하지 않다.

7.3 else

• 다른 암호 공격
  • RSA, ElGamal 외에도 구현이 비트 의존적인 모든 암호 알고리즘

• 일반 소프트웨어 감시
  • 네트워크 처리 코드
  • 키보드 드라이버

→ 비밀이 메모리 접근 패턴에 영향을 주는 코드라면, 암호가 아니어도 공격 대상이 된다.

9. 기타

9.1 mmap vs read

9.2 Slot

• “slot 하나에서 필요한 probe 3개의 총합이 약 2,200 cycles”
  • probe 1개가 하는 일 1. mfence / lfence 2. rdtsc 3. memory load 4. rdtsc 5. clflush ≈ 700~ 750cycles
  • slot 하나의 내부 구조 : 3 bit vector

    1slot k: 2 probe(square_line) → hit / miss 3 probe(multiply_line) → hit / miss 4 probe(reduce_line) → hit / miss 5 6slot k 결과 = [square=1, multiply=0, reduce=1]

  • probe 세 개를 굳이 해야 하는 이유

    1# current 2probe A: 3 mfence 4 rdtsc 5 load A 6 rdtsc 7 clflush A 8 9probe B: 10 mfence 11 rdtsc 12 load B 13 rdtsc 14 clflush B 15 16probe C: 17 mfence 18 rdtsc 19 load C 20 rdtsc 21 clflush C 22 23# what if ? 24probe A B C: 25 mfence 26 rdtsc 27 load A B C 28 rdtsc 29 clflush A B C 30 31``` 323배의 해상도를 얻을 수 있나? 33-> timestamp(A) 가 아니라 timestamp(A+B+C)가 구해져, 어느것이 캐시 히트인지 알 수 없음 34-> RSA 복호화 불가능 35```

9.3 COW(Copy-on-Write) 기반 공격

• VM / OS의 메모리 중복 제거 (page deduplication)

• 같은 페이지를 공유 중일 때, 누군가 write를 하면 → page fault + 복사(copy) → 이때의 지연 시간을 바탕으로 상대가 그 페이지를 쓰는지 추론

• 해상도가 낮고, 암호키 직접 복구는 어려움. 존재 여부 탐지용으로 주로 쓰임

9.4 Bernstein attack (cache timing)

• AES 전체 실행 시간으로 판단

• 입력을 바꿔가며 이 입력에서 암호화가 느리다 → 특정 S-box 접근이 있었음을 통계로 추론

• 원격 가능, 그러나 노이즈 크고 느림

9.5 Prime + Probe

• 캐시의 set 단위 충돌

• attacker가 cache set을 prime → victim 실행 → attacker가 다시 접근(probe) → 느리면 : victim이 해당 set을 사용

• 공유 메모리 필요 없고 VM 간 사용 가능하지만, 어느 cache set 까지만 알고 정밀도가 낮음

• 참고 : https://hyoung-2y.tistory.com/30

9.6 ⭐Flush + Reload⭐

• clflush + 공유된 read-only 페이지, LLC 사용

• 특정 코드/테이블 주소를 flush → victim 실행 → reload 시간 측정 → 빠르다 : victim 접근함 / 느리다 : 접근 안함

• cache line 단위(64gb), cross-core, cross-VM 가능하고 노이즈 적음

• RSA exponent bit 복구 가능

0. 단어 정리

복기 !

• 이 논문의 contribution ?
  • cross-core, cross-vm 간에도 공격 캐시 공격 가능

• Flush + Reload technique ?
  • 캐시 비우고 → victim 실행 여부에 따라 hit / miss 판단

• details ?
  • square → reduce (→ multiply → reduce) ↔ bit = 0 / 1
  • 루프 위주로

• limitations ?
  • 어쨌든 spy + victim 같은 cpu여야 하고, 다른 프로세스의 노이즈 존재, 최소 타임 slot (2200 cycles) 필요 ; 짧은 키 복구는 힘듦, 병렬 GnuPG 인스턴스 처리 불가(?)

• mitigation techniques ?