[Cache Side-channel Attacks] Cache, Flush+Reload, Prime+Probe, Countermeasure

배경지식: Cache

 

Locality

: 프로그램이 실행되는 동안 주소 공간의 일부분만을 집중적으로 접근하는 경향

▶Temporal locality

: 최근에 access된 것은 곧 다시 access될 확률이 높다

- 따라서 최근에 접근된 데이터를 프로세서 가까이에 유지하면 성능 향상됨 

eg. 반복문 안에서는 동일한 명령어가 반복적으로 실행되기 때문에, 해당 명령어는 다시 접근될 확률이 높다.

▶Spatial locality

: 최근에 access된 것 가까이에 있는 것은 곧 access될 확률이 높다 

메모리의 연속적인 주소 공간이 자주 함께 사용되는 경우가 많기 때문
- 따라서 연속된 데이터 블록을 메모리의 상위 수준으로 옮기면 성능 향상됨

eg. 배열은 메모리에 연속적으로 저장되며, 배열의 요소들이 순차적으로 접근되는 경우가 많음

 

Cache 구조

 

▶First level (L1) is separate on-chip instruction and data caches placed where our instruction and data memories reside
◦ 16-64KB for each cache (desktop/server machine)
◦ Fast, power-hungry, not-so-dense, static RAM (SRAM)

▶Second level (L2) consists of another larger unified cache 
◦ Holds both instructions and data
◦ 256KB-4MB SRAM
◦ On or off-chip

 

▶Third level (L3) is yet another larger unified shared cache
◦ Works for multiple cores
◦ Off-Chip, Multichip package
◦ 12MB-24MB SRAM

 

 

Timing difference in cache

deltaA (cache miss) > deltaB (cache hit)

 

Cache memory in virtualization

 

 

 

Flush+Reload

 

step

Flush: Attacker는 cache의 target line을 flush한다.	비밀값에 따라, victim은 access하거나	Reload: Attacker는 다시 access한다.	Fast access time
	access 안함		Slow access time

 

code

 

Prerequisite

- Attacker와 Victim 간에 공유되는 메모리 페이지가 있어야 한다.

∵

Flush 단계: 공격자가 정확히 어떤 메모리 주소를 플러시할지를 알아야 하므로, victim과 해당 메모리 주소를 공유해야 함Reload 단계: 공격자가 victim과 동일한 메모리 주소를 접근할 수 있어야 함

 

Prime+Probe

 

step

Prime: Attacker는 자신의 메모리 주소 공간에서 주소의 하위 비트를 분석하여  cache의 동일한 특정 set에 map되는 주소들에 access함으로써 그 set을 전부 자신의 데이터로 채운다.	비밀값에 따라, victim은 access하거나	Probe: Attacker가 다시 access한다.	Slow access time
	access 안함		Fast access time

 

Prerequisite

- 공격자는 victim과 물리적 메모리를 공유할 필요는 없고, 동일한 캐시 세트를 공유하기만 하면 된다.

∵

캐시는 보통 set-associative으로 구성됨

: 물리적 메모리 주소는 그 주소의 특정 비트에 따라 캐시의 특정 세트에 매핑되므로,

특정 메모리 주소는 특정 캐시 세트에만 저장될 수 있고,

또한 여러 프로세스의 메모리 주소가 동일한 캐시 세트를 공유할 수도 있음 -> 공격자는 이 특성을 이용

 

flush+reload: 한 cache line을 다룸

prime+probe: 한 cache set을 다룸 -> 오래걸림 

 

 

Example

- Attack on ECDSA

 

- Attack on RSA

 

 

Countermeasure

 

Constant time programming

비밀값에 따라 memory access나 flow control이 달라지지 않도록 한다.

 

- if문이나 분기문이 없음 -> secret-dependent가 없음 -> safe 

 

Runtime detection

HW performance counter 활용