Mitigating Conflict-Based Attacks in Modern Systems
C
E
A
S
E
R
:
M
i
t
i
g
a
t
i
n
g
C
o
n
f
l
i
c
t
-
B
a
s
e
d
A
t
t
a
c
k
s
v
i
a
E
n
c
r
y
p
t
e
d
-
A
d
d
r
e
s
s
a
n
d
R
e
m
a
p
p
i
n
g
M
o
i
n
u
d
d
i
n
Q
u
r
e
s
h
i
MICRO-2018
B
a
c
k
g
r
o
u
n
d
:
R
e
s
o
u
r
c
e
S
h
a
r
i
n
g
B
LLC
CORE
CORE
Modern systems share LLC for improving resource utilization
Sharing the LLC allows system to dynamically allocate LLC capacity
C
o
n
f
l
i
c
t
-
B
a
s
e
d
C
a
c
h
e
A
t
t
a
c
k
s
B
LLC
CORE
(Spy)
CORE
(Victim)
A
B
V
Co-running spy can infer access pattern of victim by causing cache conflicts
Conflicts leak access pattern, used to infer secret [AES
–
Bernstein’05]
Miss for B
Victim
Accessed Set
P
r
i
o
r
S
o
l
u
t
i
o
n
s
Way Partitioning
NoMo [TACO’12], CATalyst [HPCA’16]
O
u
r
G
o
a
l
Protect the LLC from conflict-based attacks, while incurring
1.
Negligible storage overhead
1.
Negligible performance overhead
1.
No OS support
1.
No restriction on capacity sharing
1.
Localized Implementation
O
u
t
l
i
n
e
Why?
CEASE
CEASER
Effective?
C
E
A
S
E
:
C
a
c
h
e
u
s
i
n
g
E
n
c
r
y
p
t
e
d
A
d
d
r
e
s
s
S
p
a
c
e
Insight: Don
’
t memorize the random mapping, compute it
LLC
xCAFE0000
Physical Line
Address (
PLA
)
Encrypt
Key
(ELA)
0xa17b20cf
CEASE
Localized change (ELA visible only within the cache)
Cache operations (access, coherence, prefetch) all remain unchanged
R
a
n
d
o
m
i
z
a
t
i
o
n
v
i
a
E
n
c
r
y
p
t
i
o
n
Lines that mapped to the same set, get scattered to different sets
LLC
Mapping depends on the key, different machines have different keys
E
n
c
r
y
p
t
i
o
n
:
N
e
e
d
F
a
s
t
,
S
m
a
l
l
-
W
i
d
t
h
C
i
p
h
e
r
Block
Cipher
B
B
PlainText
CipherText
Small-width Ciphers deemed insecure:
•
Brute-force attack on key
•
Memorize all input-output pairs
PLA is ~40 bits
(up-to 64TB memory)
Insight: ELA not visible to attacker (okay to use 40-bit block cipher)
L
o
w
-
L
a
t
e
n
c
y
B
l
o
c
k
C
i
p
h
e
r
(
L
L
B
C
)
LLBC incurs a delay of 24 XOR gates (approximately 2-cycle latency)
Four-Stage Feistel-Network (with Substitution-Permutation Network)
*inspired by DES and BlowFish Encryption
O
u
t
l
i
n
e
Why?
CEASE
CEASER
Effective?
L
e
t
’
s
B
r
e
a
k
C
E
A
S
E
…
LLC
E
Attacker can break CEASE within 22 seconds (8MB LLC)
[Liu et al. S&P, 2015]
Form pattern such that
cache has a conflict miss
Removed line NOT
in conflicting set
Removed line MAPS
to conflicting set
C
E
A
S
E
R
:
C
E
A
S
E
w
i
t
h
R
e
m
a
p
p
i
n
g
CEASER uses gradual remapping to periodically change the keys
Split time into Epoch of N accesses (change Key every Epoch)
CACHE
Key
Key
Key
EPOCH
time
C
E
A
S
E
R
:
C
E
A
S
E
w
i
t
h
R
e
m
a
p
p
i
n
g
Remap-Rate of 1 %
Remap W-way set after (100*W) accesses
Access=0
Epoch=0
Access=200
Epoch=0
B0
A1
B1
A0
X0
X1
Access=400
Epoch=0
Access=600
Epoch=0
Y0
Y1
Access=800
Epoch=0
Z0
Z1
Access=0
Epoch=1
Cache Access: If (Set[CurrKey] < Sptr) Use NextKey
CEASER with gradual remap needs negligible hardware (one bit per line)
O
u
t
l
i
n
e
Why?
CEASE
CEASER
Effective?
S
e
c
u
r
i
t
y
A
n
a
l
y
s
i
s
CEASER can tolerate years of attack (Even with remap-rate of 1%)
Time to learn “Eviction Set” for one set (vulnerability removed after remap, <1ms)
Limits impact on missrate,
energy, accesses to ~1%
P
e
r
f
o
r
m
a
n
c
e
a
n
d
S
t
o
r
a
g
e
O
v
e
r
h
e
a
d
s
CEASER incurs negligible slowdown (~1% ) and storage overheads (24 bytes)
8 cores with 8MB LLC 16-way
(34 workloads, SPEC + Graph)
S
u
m
m
a
r
y
Cache
Line Address
Encrypt
Change Key, Periodically
Need practical solution to protect LLC from conflict-based attacks
Appealing for Industrial Adoption
W
h
a
t
A
b
o
u
t
F
l
u
s
h
-
B
a
s
e
d
A
t
t
a
c
k
s
?
Flush-Based Attack: Use
clflush
to evict shared line, wait, and test
Partitioning
Randomization
D
i
f
f
u
s
i
o
n
P
r
o
p
e
r
t
i
e
s
o
f
L
L
B
C
Diffusion: Single bit change in input causes lots of bits to change in output
Proposed LLBC has close-to-ideal diffusion properties
D
e
t
e
r
m
i
n
i
n
g
S
e
t
I
n
d
e
x
Cache index function determines the line to set mapping
Proprietary index functions can be learned [Liu et al., S&P 2015]
Breaking one machine gives information for ALL other machines
B
Line Address
CEASER presents a solution to protect Last-Level Cache (LLC) from conflict-based cache attacks using encrypted address space and remapping techniques. By avoiding traditional table-based randomization and instead employing encryption for cache mapping, CEASER aims to provide enhanced security with negligible storage and performance overhead, no OS support requirement, and unrestricted capacity sharing.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CEASER: Mitigating Conflict-Based Attacks via Encrypted-Address and Remapping MICRO-2018 Moinuddin Qureshi
Background: Resource Sharing Modern systems share LLC for improving resource utilization B LLC CORE CORE Sharing the LLC allows system to dynamically allocate LLC capacity
Conflict-Based Cache Attacks Co-running spy can infer access pattern of victim by causing cache conflicts B B V A Miss for B Victim Accessed Set LLC CORE (Spy) CORE (Victim) Conflicts leak access pattern, used to infer secret [AES Bernstein 05]
Prior Solutions Table-Based Randomization Way Partitioning NoMo [TACO 12], CATalyst [HPCA 16] RPCache[ISCA 07], NewCache[MICRO 08] Mapping Table (MT) Mapping Table large for LLC (MBs) Inefficient use of cache space OS support needed to protect Table Not scalable to many core
Our Goal Protect the LLC from conflict-based attacks, while incurring 1. Negligible storage overhead 1. Negligible performance overhead 1. No OS support 1. No restriction on capacity sharing 1. Localized Implementation
Outline Why? CEASE CEASER Effective?
CEASE: Cache using Encrypted Address Space Insight: Don t memorize the random mapping, compute it Key Key xCAFE0000 Decrypt Encrypt Physical Line Address (PLA) Dirty Evict ELA 0xa17b20cf (ELA) LLC CEASE Localized change (ELA visible only within the cache) Cache operations (access, coherence, prefetch) all remain unchanged
Randomization via Encryption Lines that mapped to the same set, get scattered to different sets Key Key A B A B A Encrypt Encrypt B LLC LLC LLC CEASE CEASE Mapping depends on the key, different machines have different keys
Encryption: Need Fast, Small-Width Cipher B B Block Cipher PlainText CipherText PLA is ~40 bits (up-to 64TB memory) Larger tag (80+ bits) Small-width Ciphers deemed insecure: Brute-force attack on key Memorize all input-output pairs Latency of 10+ cycles Insight: ELA not visible to attacker (okay to use 40-bit block cipher)
Low-Latency Block Cipher (LLBC) Four-Stage Feistel-Network (with Substitution-Permutation Network) *inspired by DES and BlowFish Encryption LLBC incurs a delay of 24 XOR gates (approximately 2-cycle latency)
Outline Why? CEASE CEASER Effective?
Lets Break CEASE [Liu et al. S&P, 2015] Form pattern such that cache has a conflict miss D Remove one line from pattern & check conflict B C A E LLC Yes No Conflict Miss? Removed line MAPS to conflicting set Removed line NOT in conflicting set Attacker can break CEASE within 22 seconds (8MB LLC)
CEASER: CEASE with Remapping Split time into Epoch of N accesses (change Key every Epoch) Key Key Key CACHE BULK time EPOCH CurrKey CurrKey CurrKey NextKey NextKey NextKey GRADUAL CEASER uses gradual remapping to periodically change the keys
CEASER: CEASE with Remapping Remap-Rate of 1 % Remap W-way set after (100*W) accesses X1 A1 A0 B0 SetPtr CurrKey CurrKey NextKey NextKey B1 X0 Access=0 Epoch=0 Epoch=0 Epoch=0 Epoch=0 Epoch=0 Epoch=1 Access=200 Access=400 Access=600 Access=800 Access=0 Y1 Y0 Z0 Z1 Cache Access: If (Set[CurrKey] < Sptr) Use NextKey CEASER with gradual remap needs negligible hardware (one bit per line)
Outline Why? CEASE CEASER Effective?
Security Analysis Time to learn Eviction Set for one set (vulnerability removed after remap, <1ms) Remap-Rate 8MB LLC 1 MB LLC-Bank 1% (default) 100+ years 100+ years 0.5% 100+ years 21 years 0.1% 0.05% 100+ years 37 years 5 hours 5 minutes No-Remap (CEASE) 22 seconds Limits impact on missrate, energy, accesses to ~1% 0.4 seconds CEASER can tolerate years of attack (Even with remap-rate of 1%)
Performance and Storage Overheads 8 cores with 8MB LLC 16-way (34 workloads, SPEC + Graph) CEASE CEASER Norm Performance (%) 100 Structures 80-bit key (2 LLBC) SPtr Cost 20 bytes 2 bytes 99 98 97 Access Counter 2 bytes 96 Total 24 bytes 95 Rate-34 Mix-100 ALL-134 CEASER incurs negligible slowdown (~1% ) and storage overheads (24 bytes)
Summary Need practical solution to protect LLC from conflict-based attacks Robust to attacks (years) Key1 Key2 Negligible slowdown (~ 1%) Encrypt Line Address Negligible storage (24 bytes) Localized change (within cache) Cache No OS support needed Change Key, Periodically Appealing for Industrial Adoption
What About Flush-Based Attacks? Flush-Based Attack: Use clflush to evict shared line, wait, and test Partitioning Randomization Restriction SHARP [ISCA 17] Compatible with CEASER Line Duplication NewCache [MICRO 17]
Diffusion Properties of LLBC Diffusion: Single bit change in input causes lots of bits to change in output Proposed LLBC has close-to-ideal diffusion properties
Determining Set Index Cache index function determines the line to set mapping ? Proprietary Function B B Line Address Line Address Proprietary index functions can be learned [Liu et al., S&P 2015] Breaking one machine gives information for ALL other machines
