1Encryption: E(m) = m^e mod n
2Decryption: D(c) = c^d mod n
34---
51. 공개키 (e,n), 개인키 (d,n)
62. 공격자가 알고 있는 정보 : c, e, n
73. 공격자가 암호문을 해독하기 위해 알고 싶은 정보 : d
83-1. d를 알기 위해 필요한 정보 : φ(n)
93-2. φ(n)을 알기 위해 필요한 정보 : p, q
104. 결론 : n = p * q 에서 p, q를 분리하는 것은 매우 어려움
Square-and-Multiply
bit = 0 : square → reduce
bit = 1 : square → reduce → multiply → reduce
multiply 코드의 cache line 접근 여부로 비트 추측 가능
3. Flush + Reload Technique
3.1 기본 프로토콜
11) Flush: 특정 cache line을 모든 캐시에서 제거
22) Wait: victim 실행 대기
33) Reload: 접근 시간 측정
빠름 → victim 접근
느림 → victim 접근 없음
3.2 Wait Period Trade-off
wait 증가 → miss 감소
wait 증가 → 시간 해상도(granularity) 감소
해결책
루프 내부처럼 자주 실행되는 코드 타겟
빈도로 패턴 복원
3.3 False Positive
실제 접근 없는데 접근한 것처럼 보이는 현상
원인 :
speculative execution
data prefetching
→ 분석 단계에서 필터링 필요
3.4 핵심 명령어
1rdtsc ; 타임스탬프 카운터
2clflush ; 특정 cache line을 전체 캐시에서 제거
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 공격 시나리오
Same-OS
spy가 victim 실행 파일을 mmap
동일 물리 페이지 공유
Cross-VM
spy가 victim 실행 파일의 복사본을 mmap
메모리 디듀플리케이션으로 물리 페이지 공유
LLC는 물리 주소 기반 → ASLR 영향 거의 없음
4.2 Trace 구현
Time slot: 2,500 CPU cycles
각 슬롯에서 :
square
multiply
reduce
각각 대표 cache line 1개 probe
함수 초반부는 speculative execution 때문에 회피
4.3 Bit Pattern 해석
패턴
의미
square → reduce
0
square → reduce → multiply → reduce
1
단일 슬롯은 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 접근 패턴을 추적
💡
AES S-box 접근이란 ?
암호 연산 중에 비밀키에 따라 S-box 테이블의 특정 메모리 위치를 읽는 행위
“어느 위치를 읽었는지”가 캐시를 통해 새어 나간다
캐시 사이드 채널을 사용
같은 코어 전제
LLC는 활용하지 않음
이 논문이 확장한 점
shared LLC를 이용 → cross-core 공격 가능
동기화 방식 : cpuid → fence
명령 스트림 동기화를 위해 cpuid 사용, 한번 실행하는 데 1000+ cycles
mfence/lfence 같은 fence instruction 사용 → 약 3배의 해상도 향상
Zhang et al.
가상화 환경을 타겟으로 함
다른 VM에서 실행 중인 GnuPG의 ElGamal 개인키 추출
Xen 하이퍼바이저 스케줄러 취약점에 의존
한계
해상도가 낮음
짧은 키는 못잡음(4096 bit modulus 사용)
노이즈가 심해서 필터링 필수, 6시간 연속 복호화
Weiß et al.
Bernstein 공격을 변형한 가상 환경에서의 캐시 타이밍 공격
L4 마이크로 커널 환경에서 도메인 간 통신 시간이 매우 짧다는 특수성을 이용
특성 커널 구조에 의존, 일반적인 VM/클라우드 환경에 바로 적용되긴 어려움
7. Conclusion
7.1 의의
멀티 코어 경계
→ victim과 attacker가 서로 다른 CPU 코어여도 가능
가상머신 경계
→ 서로 다른 VM 이어도 가능
7.2 GnuPG
이메일 암호화, 파일 암호화, 통신 암호화 등에 쓰이는 표준급 암호 소프트웨어
→ 취약한 GnuPG 버전이 돌아가는 시스템 멀티테넌트 환경이나 신뢰할 수 없는 코드가 함께 실행되는 환경에서는 안전하지 않다.
7.3 else
다른 암호 공격
RSA, ElGamal 외에도 구현이 비트 의존적인 모든 암호 알고리즘
일반 소프트웨어 감시
네트워크 처리 코드
키보드 드라이버
→ 비밀이 메모리 접근 패턴에 영향을 주는 코드라면, 암호가 아니어도 공격 대상이 된다.
9. 기타
9.1 mmap vs read
💡
mmap 이란 ?
파일이나 익명 메모리를 프로세스 주소 공간에 직접 매핑하는 시스템 콜.
mmap() : 파일의 페이지 자체를 주소 공간에 매핑, 같은 파일을 mmap하면 → 같은 물리 페이지
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
56slot k 결과 =[square=1, multiply=0, reduce=1]
probe 세 개를 굳이 해야 하는 이유
1# current2probe A:
3 mfence
4 rdtsc
5 load A
6 rdtsc
7 clflush A
89probe B:
10 mfence
11 rdtsc
12 load B
13 rdtsc
14 clflush B
1516probe C:
17 mfence
18 rdtsc
19 load C
20 rdtsc
21 clflush C
2223# what if ?24probe A B C:
25 mfence
26 rdtsc
27 load A B C
28 rdtsc
29 clflush A B C
3031```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 까지만 알고 정밀도가 낮음