Improved Encryption Technique for Phase Change Memory (PCM)
D
E
U
C
E
:
W
R
I
T
E
-
E
F
F
I
C
I
E
N
T
E
N
C
R
Y
P
T
I
O
N
F
O
R
P
C
M
March 16
th
2015
ASPLOS-XX Istanbul, Turkey
Vinson Young
Prashant Nair
Moinuddin Qureshi
•
Insight: re-encrypt only modified words
•
DEUCE: write-efficient encryption scheme
•
Result: bit flips reduced 50%
23% (
27% speedup)
•
PCM more
vulnerable to attacks
stolen module
•
Secure PCM with encryption
•
Problem:
Encryption increases bit flips
12%
50%
•
Goal: Encrypt PCM without causing 4x bit flips
•
Bit flips expensive
in Phase Change Memory (PCM)
–
Affects Lifetime, Power, and Performance
–
PCM system optimized to reduce bit flips (~12%)
E
X
E
C
U
T
I
V
E
S
U
M
M
A
R
Y
2
P
C
M
A
S
M
A
I
N
M
E
M
O
R
Y
Phase Change Memory (PCM)
–
Improved scaling + density
–
Non-volatile (no refresh)
Key Challenge
–
Writes: Limited endurance (10-100 million writes)
–
Writes: Slow and limited throughput
–
Writes: Power-hungry
3
PCM systems are designed to reduce writes
Invert if too many bit flips
Write only flipped bits
Flip-N-Write
T
Y
P
I
C
A
L
W
R
I
T
E
O
P
T
I
M
I
Z
A
T
I
O
N
S
I
N
P
C
M
Data-Comparison-Write
4
Cache
Comparison
Write
Cache
Flip-N-Write
Optimizations reduce bit-flips per write to 10-12%
Non-volatility: Power savings Security
More vulnerable to stolen-memory attack
S
E
C
U
R
I
T
Y
V
U
L
N
E
R
A
B
I
L
I
T
Y
O
F
P
C
M
5
S
t
o
l
e
n
m
e
m
o
r
y
a
t
t
a
c
k
B
u
s
s
n
o
o
p
i
n
g
a
t
t
a
c
k
a
l
s
o
p
o
s
s
i
b
l
e
We want to protect PCM from both
“stolen memory attack” and “bus snooping attack”
E
N
C
R
Y
P
T
I
O
N
O
N
P
C
M
Protect PCM using memory encryption
Encryption causes 50% bit flips on each write
1 bit flip in line
50% bit flips in encrypted line
6
Cache
Encrypted
PCM
Encryption causes 50% bit flips
Write-intensive
A
v
a
l
a
n
c
h
e
E
f
f
e
c
t
E
N
C
R
Y
P
T
I
O
N
O
N
P
C
M
C
O
S
T
L
Y
7
Encryption increases bit flips from 12% to 50% (4x!)
4x
G
O
A
L
:
W
R
I
T
E
-
E
F
F
I
C
I
E
N
T
E
N
C
R
Y
P
T
I
O
N
G
o
a
l
:
H
o
w
d
o
w
e
i
m
p
l
e
m
e
n
t
m
e
m
o
r
y
e
n
c
r
y
p
t
i
o
n
,
w
i
t
h
o
u
t
i
n
c
r
e
a
s
i
n
g
b
i
t
f
l
i
p
s
b
y
4
x
?
8
O
U
T
L
I
N
E
•
Introduction to PCM and encryption
•
Background on Counter-mode Encryption
•
DEUCE
•
Results
•
Summary
9
Pad-based Decryption
Direct Decryption
Encrypted Data
W
H
Y
P
A
D
-
B
A
S
E
D
E
N
C
R
Y
P
T
I
O
N
?
10
10
AES
Key
Data
Pad
Encrypted Data
AES
Key
Data
Pad-based decryption has low-latency
AES
AES in
critical path!
XOR in
critical
path
PCM
PCM
Cache
Cache
+
Z
E
R
O
E
S
P
A
D
N
E
E
D
F
O
R
U
N
I
Q
U
E
P
A
D
S
(0000)
⊕
Pad = Pad
Attack! Insecure if pad learned
11
11
Z
E
R
O
E
S
P
A
D
P
A
D
Secure pad encryption cannot re-use pads
+
P
A
D
E
N
C
R
Y
P
T
E
D
P
A
D
D
A
T
A
E
N
C
R
Y
P
T
E
D
Different pad per line address
Different pad per write to same line
per-line counter
P
A
D
-
c
t
r
3
+
+
+
L
i
n
e
1
P
A
D
1
L
i
n
e
2
P
A
D
2
L
i
n
e
1
T
i
m
e
3
L
i
n
e
1
T
i
m
e
2
C
O
U
N
T
E
R
-
M
O
D
E
E
N
C
R
Y
P
T
I
O
N
12
12
L
i
n
e
1
E
N
C
R
Y
P
T
1
L
i
n
e
2
P
A
D
2
E
N
C
R
Y
P
T
2
L
i
n
e
1
T
i
m
e
1
E
N
C
R
Y
P
T
1
E
N
C
R
Y
P
T
2
P
A
D
1
P
A
D
-
c
t
r
2
P
A
D
-
c
t
r
1
Pad changes every write
50% bit flips every write
Secured!
O
U
T
L
I
N
E
•
Introduction to PCM and encryption
•
Background on Counter-mode Encryption
•
DEUCE
•
Results
•
Summary
13
13
What if we re-encrypt only modified words?
I
N
S
I
G
H
T
1
Reduce bit flips by re-encrypting only modified words
Re-encrypted
Cache
Encrypted
PCM
Re-encrypted
Remains encrypted
14
14
Naïve implementation needs per-word counters/pads
Reduce storage overhead by using only
two counters
I
N
S
I
G
H
T
2
:
E
F
F
I
C
I
E
N
T
I
M
P
L
E
M
E
N
T
A
T
I
O
N
15
15
Encrypted
PCM
Encrypted
PCM
Do efficient partial re-encryption with only two counters
Expensive!
Each line has two counters:
•
Leading counter (
LeadCTR
): incremented every write
•
Trailing counter (
TrailCTR
): updated every N writes (
Epoch
)
“Modified” bit per word to choose between counters
D
E
U
C
E
:
D
U
A
L
C
O
U
N
T
E
R
E
N
C
R
Y
P
T
I
O
N
16
16
Epoch Start
D
E
U
C
E
:
O
P
E
R
A
T
I
O
N
On a write
LeadCTR++
Re-encrypt words
modified since Epoch
Set “modified” bits
TrailCTR=LeadCTR
Re-encrypt ALL words
Reset “modified” bits
Between Epoch
17
17
DEUCE re-encrypts only words modified since Epoch
D
E
U
C
E
:
E
X
A
M
P
L
E
(
E
P
O
C
H
=
4
W
R
I
T
E
S
)
ALL
W0
W7
W0
W4
W7
W0
W4
W7
ALL
W2
W4
Encrypted
Words
LCTR
TCTR
0
0
1
0
2
0
3
0
4
4
5
4
W0,W7
W4
W7
W2,W4
0
1
2
3
4
5
Modified Words
in Write
Get TrailCTR by masking 2 LSB off LeadCTR
DEUCE needs only one
physical counter per line
X
18
18
DEUCE does partial re-encryption between Epochs
Encrypted Line
D
E
U
C
E
:
H
O
W
T
O
D
E
C
R
Y
P
T
?
DEUCE generates two pads with LCTR and TCTR
Which pad to use decided by the “Modified” bits
Decrypted Line
Pad - LCTR
Pad - TCTR
A
E
S
A
E
S
Line
counter
Mask
4 LSB
LCTR
TCTR
1
0
0
1
1
0
0
0
Combined
19
19
O
U
T
L
I
N
E
•
Introduction to PCM and encryption
•
Background on Counter-mode Encryption
•
DEUCE
•
Results
•
Summary
20
20
M
E
T
H
O
D
O
L
O
G
Y
21
21
Shared L4
Cache
Phase Change
Memory
CPU
M
E
T
H
O
D
O
L
O
G
Y
22
22
Shared L4
Cache
Phase Change
Memory
CPU
Phase Change Memory [Samsung ISSCC’12]
4 ranks, each 8GB
32GB total
Read latency 75ns
Write latency 150ns (per 128-bit write slot)
M
E
T
H
O
D
O
L
O
G
Y
23
23
Shared L4
Cache
Phase Change
Memory
CPU
M
E
T
H
O
D
O
L
O
G
Y
24
24
Shared L4
Cache
Phase Change
Memory
CPU
Workloads
SPEC2006: High MPKI, rate mode
4 billion instruction slice
DEUCE: Epoch=32; Word size=2B
R
E
S
U
L
T
S
:
B
I
T
F
L
I
P
A
N
A
L
Y
S
I
S
25
25
D
E
U
C
E
e
l
i
m
i
n
a
t
e
s
t
w
o
-
t
h
i
r
d
s
o
f
t
h
e
e
x
t
r
a
b
i
t
f
l
i
p
s
c
a
u
s
e
d
b
y
e
n
c
r
y
p
t
i
o
n
R
E
S
U
L
T
S
:
S
P
E
E
D
U
P
&
P
O
W
E
R
A
N
A
L
Y
S
I
S
26
26
B
i
t
f
l
i
p
r
e
d
u
c
t
i
o
n
i
m
p
r
o
v
e
s
s
p
e
e
d
u
p
a
n
d
E
D
P
+27%
D
E
U
C
E
F
N
W
S
p
e
e
d
u
p
E
n
e
r
g
y
-
D
e
l
a
y
-
P
r
o
d
u
c
t
-43%
U
n
e
n
c
r
y
p
t
e
d
Heavily-written bits still heavily-written with DEUCE
Solution: Zero-cost “Horizontal” Wear Leveling
R
E
S
U
L
T
S
:
L
I
F
E
T
I
M
E
A
N
A
L
Y
S
I
S
27
27
L
i
f
e
t
i
m
e
i
m
p
r
o
v
e
m
e
n
t
o
f
2
x
+100%
D
E
U
C
E
w
i
t
h
H
W
L
O
U
T
L
I
N
E
•
Introduction to PCM and encryption
•
Baseline–Counter-mode Encryption
•
DEUCE
•
Results
•
Summary
28
28
•
Insight: re-encrypt only modified words
•
DEUCE: write-efficient encryption scheme
•
Result: bit flips reduced 50%
23% (
27% speedup)
•
PCM more
vulnerable to attacks
stolen module
•
Secure PCM with encryption
•
Problem:
Encryption increases bit flips
12%
50%
•
Goal: Encrypt PCM without causing 4x bit flips
•
Bit flips expensive
in Phase Change Memory (PCM)
–
Affects Lifetime, Power, and Performance
–
PCM system optimized to reduce bit flips (~12%)
E
X
E
C
U
T
I
V
E
S
U
M
M
A
R
Y
29
29
T
H
A
N
K
Y
O
U
30
30
E
X
T
R
A
S
L
I
D
E
S
31
31
D
E
U
C
E
F
O
R
O
T
H
E
R
N
V
M
•
In-place writing NVM
–
RRAM
–
STT-MRAM
32
32
W
R
I
T
E
S
L
O
T
S
PCM is power-limited
Write-slot of 128 Flip-N-Write-enabled bits (64 bit flips)
33
33
Average number of write slots used per write request. On
average, DEUCE consumes 2.64 slots whereas unencrypted
memory takes 1.92 slots out of the 4 write slots
I
M
P
R
O
V
I
N
G
P
C
M
W
E
A
R
L
E
V
E
L
I
N
G
34
34
•
Vertical Wear Leveling (Start-gap)—Inter-line leveling
•
Horizontal Wear Leveling—Intra-line leveling
Re-use
vertical
wear leveling to level inside line
S
T
A
R
T
A
B
C
0
1
2
3
4
D
S
T
A
R
T
C Rot3
D Rot3
A Rot2
0
1
2
3
4
B Rot2
A Rot
3
D Rot
4
C Rot
4
B Rot
4
B Rot
3
Vertical Wear Leveling
Horizontal Wear Leveling
Q
U
E
S
T
I
O
N
:
I
S
I
T
S
E
C
U
R
E
?
•
Aren’t you re-using the pad?
•
AES-CTR-mode
–
Unique full pad per ever write.
•
DEUCE
–
Epoch start, uses unique full pad
–
Between epochs, uses a unique full pad per write, to re-
encrypt modified words. Unmodified words simply not
touched
whole line is always encrypted, and pads are not re-used
35
35
4
M
I
N
I
M
U
M
R
E
-
E
N
C
R
Y
P
T
36
36
Words
modified
1
2
3
5
7
8
5
5
6
7
7
8
8
8
8
8
8
8
V
a
l
u
e
o
f
L
e
a
d
i
n
g
C
o
u
n
t
e
r
(
E
p
o
c
h
=
4
)
W2
W7
W6
W0, W4,
W5
W0
W0, W3,
W4
0
D
E
U
C
E
R
E
-
E
N
C
R
Y
P
T
37
37
Words
modified
1
2
2
3
3
3
5
6
6
7
7
8
5
5
6
7
7
8
8
8
8
8
8
8
V
a
l
u
e
o
f
L
e
a
d
i
n
g
C
o
u
n
t
e
r
(
E
p
o
c
h
=
4
)
W2
W7
W6
W0, W4,
W5
W0
W0, W3,
W4
Q
U
E
S
T
I
O
N
:
I
S
I
T
S
E
C
U
R
E
?
•
What about information leak?
•
AES-CTR-mode
–
Can tell when a line is modified
•
DEUCE
–
Can tell when a line is modified, and
–
Can sometimes tell when a word is modified
–
Similar information leakage
38
38
C
I
P
H
E
R
B
L
O
C
K
C
H
A
I
N
I
N
G
39
39
C
O
U
N
T
E
R
-
M
O
D
E
E
N
C
R
Y
P
T
I
O
N
40
40
Security bounds no worse than CBC (NIST-approved)
Weakness to input is accepted to due to the underlying
block cipher and not the mode of operation
R
E
S
U
L
T
S
:
B
I
T
F
L
I
P
A
N
A
L
Y
S
I
S
41
41
D
E
U
C
E
e
l
i
m
i
n
a
t
e
s
t
w
o
-
t
h
i
r
d
s
o
f
t
h
e
e
x
t
r
a
b
i
t
f
l
i
p
s
c
a
u
s
e
d
b
y
e
n
c
r
y
p
t
i
o
n
Good morning, I will be talking about “DEUCE: Write-Efficient Encryption for Phase Change Memory.”
I am Vinson Young.
This work is in collaboration with my labmate Prashant Nair and my advisor Moinuddin Qureshi.
Bit flips in Phase Change Memory (PCM) can adversely impact performance, power consumption, and system lifespan. To address this, a write-efficient encryption scheme called DEUCE was developed, which reduced bit flips by 50% and improved speed by 27%. By re-encrypting only modified data, the scheme successfully secured PCM without causing a drastic increase in bit flips. The vulnerability of PCM to attacks like stolen memory and bus snooping underlines the importance of implementing effective encryption techniques to safeguard sensitive data stored in PCM.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
DEUCE: WRITE-EFFICIENT ENCRYPTION FOR PCM March 16th2015 ASPLOS-XX Istanbul, Turkey Vinson Young Prashant Nair Moinuddin Qureshi
EXECUTIVE SUMMARY Bit flips expensive in Phase Change Memory (PCM) Affects Lifetime, Power, and Performance PCM system optimized to reduce bit flips (~12%) PCM more vulnerable to attacks stolen module Secure PCM with encryption Problem: Encryption increases bit flips 12% 50% Goal: Encrypt PCM without causing 4x bit flips Insight: re-encrypt only modified words DEUCE: write-efficient encryption scheme Result: bit flips reduced 50% 23% (27% speedup) 2
PCM AS MAIN MEMORY Phase Change Memory (PCM) Improved scaling + density Non-volatile (no refresh) Key Challenge Writes: Limited endurance (10-100 million writes) Writes: Slow and limited throughput Writes: Power-hungry PCM systems are designed to reduce writes 3
TYPICAL WRITE OPTIMIZATIONS IN PCM Flip-N-Write Data-Comparison-Write Write only flipped bits Invert if too many bit flips Cache Cache Comparison Write Flip-N-Write Optimizations reduce bit-flips per write to 10-12% 4
SECURITY VULNERABILITY OF PCM Non-volatility: Power savings Security More vulnerable to stolen-memory attack Stolen memory attack Bus snooping attack also possible We want to protect PCM from both stolen memory attack and bus snooping attack 5
ENCRYPTION ON PCM Protect PCM using memory encryption Encryption causes 50% bit flips on each write 1 bit flip in line 50% bit flips in encrypted line Cache Encrypted PCM Avalanche Effect Encryption causes 50% bit flips Write-intensive 6
ENCRYPTION ON PCM COSTLY Data-Comparison-Write Flip-N-Write 60% 50% Bit flips per Write (%) 40% 4x 30% 20% 10% 0% No Encryption Encryption Encryption increases bit flips from 12% to 50% (4x!) 7
GOAL: WRITE-EFFICIENT ENCRYPTION Goal: How do we implement memory encryption, without increasing bit flips by 4x? 8
OUTLINE Introduction to PCM and encryption Background on Counter-mode Encryption DEUCE Results Summary 9
WHY PAD-BASED ENCRYPTION? Encrypted Data Encrypted Data PCM PCM XOR in critical path AES in critical path! Pad + Key AES AES AES Key Data Data Cache Cache Direct Decryption Pad-based Decryption Pad-based decryption has low-latency 10
NEED FOR UNIQUE PADS (0000) Pad = Pad PAD PAD + ZEROES ZEROES PAD Attack! Insecure if pad learned PAD PAD + DATA ENCRYPTED ENCRYPTED Secure pad encryption cannot re-use pads 11
COUNTER-MODE ENCRYPTION Different pad per line address PAD1 PAD2 PAD2 PAD1 + Line1 Line2 Line2 Line1 ENCRYPT1 ENCRYPT2 + Different pad per write to same line per-line counter PAD-ctr3 PAD-ctr2 PAD-ctr1 + Line1 Time3 Line1 Time2 Line1 Time1 ENCRYPT1 ENCRYPT2 Pad changes every write 50% bit flips every write 12
OUTLINE Introduction to PCM and encryption Background on Counter-mode Encryption DEUCE Results Summary 13
INSIGHT 1 What if we re-encrypt only modified words? Cache Remains encrypted Encrypted PCM 0 1 0 Re-encrypted Re-encrypted Reduce bit flips by re-encrypting only modified words 14
INSIGHT 2: EFFICIENT IMPLEMENTATION Na ve implementation needs per-word counters/pads 0 0 0 0 0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 1 7 1 2 8 0 0 0 0 1 2 3 4 5 0 0 0 0 0 1 2 3 4 0 0 0 0 0 0 1 2 3 0 0 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 7 Encrypted PCM Reduce storage overhead by using only two counters 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 7 8 0 1 2 3 4 5 6 7 8 0 0 0 0 4 5 6 7 8 0 0 0 0 0 5 6 7 8 0 0 0 0 0 0 6 7 8 0 0 0 3 4 5 6 7 8 0 0 2 3 4 5 6 7 8 Encrypted PCM Do efficient partial re-encryption with only two counters 15
DEUCE: DUAL COUNTER ENCRYPTION Each line has two counters: Leading counter (LeadCTR): incremented every write Trailing counter (TrailCTR): updated every N writes (Epoch) Modified bit per word to choose between counters 16
DEUCE: OPERATION On a write Epoch Start Between Epoch TrailCTR=LeadCTR LeadCTR++ Re-encrypt ALL words Re-encrypt words modified since Epoch Reset modified bits Set modified bits DEUCE re-encrypts only words modified since Epoch 17
DEUCE: EXAMPLE (EPOCH = 4 WRITES) W0 W4 W7 W0 W4 W7 W0 W7 W2 W4 Encrypted Words ALL ALL LCTR TCTR 0 0 1 0 2 0 3 0 4 4 5 4 Get TrailCTR by masking 2 LSB off LeadCTR DEUCE needs only one physical counter per line X W0,W7 W7 W2,W4 W4 Modified Words in Write 1 2 0 3 4 5 DEUCE does partial re-encryption between Epochs 18
DEUCE: HOW TO DECRYPT? DEUCE generates two pads with LCTR and TCTR Which pad to use decided by the Modified bits 1 0 0 1 1 0 0 0 Line counter AES Encrypted Line LCTR Pad - LCTR Mask 4 LSB Pad - TCTR AES TCTR Decrypted Line 19
OUTLINE Introduction to PCM and encryption Background on Counter-mode Encryption DEUCE Results Summary 20
METHODOLOGY Phase Change Memory Shared L4 Cache CPU Core Chip 8 cores, each 4GHz 4-wide core L1/L2/L3 32KB/256KB/1MB 21
METHODOLOGY Phase Change Memory Shared L4 Cache CPU Shared L4 Cache: 64 MB capacity 50 cycle latency 22
METHODOLOGY Phase Change Memory Shared L4 Cache CPU Phase Change Memory [Samsung ISSCC 12] 4 ranks, each 8GB 32GB total Read latency 75ns Write latency 150ns (per 128-bit write slot) 23
METHODOLOGY Phase Change Memory Shared L4 Cache CPU Workloads SPEC2006: High MPKI, rate mode 4 billion instruction slice DEUCE: Epoch=32; Word size=2B 24
RESULTS: BIT FLIP ANALYSIS Encrypted+FNW DEUCE Encrypted+FNW Encrypted+FNW Unencrypted+FNW Unencrypted+FNW 50% 50% 50% 45% 45% 45% Bit flips per Write (%) Bit flips per Write (%) Bit flips per Write (%) 40% 40% 40% 35% 35% 35% 30% 30% 30% 25% 25% 25% 20% 20% 20% 15% 15% 15% 10% 10% 10% 5% 5% 5% 0% 0% 0% DEUCE eliminates two-thirds of the extra bit flips caused by encryption 25
RESULTS: SPEEDUP&POWER ANALYSIS Speedup Energy-Delay-Product 1.6 1 +27% Normalized to Encrypted PCM Normalized to Encrypted PCM 1.4 0.8 1.2 -43% 1 0.6 0.8 0.4 0.6 0.4 0.2 0.2 0 0 DEUCE Unencrypted FNW Bit flip reduction improves speedup and EDP 26
RESULTS: LIFETIME ANALYSIS Heavily-written bits still heavily-written with DEUCE Solution: Zero-cost Horizontal Wear Leveling +100% 2 Normalized to Encrypted PCM 1.5 1 0.5 0 with HWL DEUCE Lifetime improvement of 2x 27
OUTLINE Introduction to PCM and encryption Baseline Counter-mode Encryption DEUCE Results Summary 28
EXECUTIVE SUMMARY Bit flips expensive in Phase Change Memory (PCM) Affects Lifetime, Power, and Performance PCM system optimized to reduce bit flips (~12%) PCM more vulnerable to attacks stolen module Secure PCM with encryption Problem: Encryption increases bit flips 12% 50% Goal: Encrypt PCM without causing 4x bit flips Insight: re-encrypt only modified words DEUCE: write-efficient encryption scheme Result: bit flips reduced 50% 23% (27% speedup) 29
THANK YOU 30
EXTRA SLIDES 31
DEUCE FOR OTHER NVM In-place writing NVM RRAM STT-MRAM 32
WRITE SLOTS PCM is power-limited Write-slot of 128 Flip-N-Write-enabled bits (64 bit flips) Average number of write slots used per write request. On average, DEUCE consumes 2.64 slots whereas unencrypted memory takes 1.92 slots out of the 4 write slots 33
IMPROVING PCM WEAR LEVELING Vertical Wear Leveling (Start-gap) Inter-line leveling Horizontal Wear Leveling Intra-line leveling START A B C D 0 1 2 3 C Rot3 D Rot3 A Rot2 B Rot2 A Rot3 B Rot4 0 1 2 3 C Rot4 START D Rot4 GAP GAP 4 B Rot3 4 Vertical Wear Leveling Horizontal Wear Leveling Re-use vertical wear leveling to level inside line 34
QUESTION: IS IT SECURE? Aren t you re-using the pad? AES-CTR-mode Unique full pad per ever write. DEUCE Epoch start, uses unique full pad Between epochs, uses a unique full pad per write, to re- encrypt modified words. Unmodified words simply not touched whole line is always encrypted, and pads are not re-used 35
MINIMUM RE-ENCRYPT Words modified W2 0 0 0 0 0 0 0 0 Value of Leading Counter (Epoch=4) 1 W7 2 W6 3 4 4 4 4 4 4 4 4 W0, W4, W5 W0 W0, W3, W4 4 5 4 5 4 5 4 6 4 7 4 7 4 7 8 8 8 8 8 8 8 8 36
DEUCE RE-ENCRYPT Words modified W2 0 0 0 0 0 0 0 0 Value of Leading Counter (Epoch=4) 0 1 W7 0 2 0 2 W6 0 3 0 3 0 3 4 4 4 4 4 4 4 4 W0, W4, W5 W0 W0, W3, W4 4 5 4 5 4 5 4 6 4 6 4 6 4 7 4 7 4 7 4 7 8 8 8 8 8 8 8 8 37
QUESTION: IS IT SECURE? What about information leak? AES-CTR-mode Can tell when a line is modified DEUCE Can tell when a line is modified, and Can sometimes tell when a word is modified Similar information leakage 38
COUNTER-MODE ENCRYPTION Security bounds no worse than CBC (NIST-approved) Weakness to input is accepted to due to the underlying block cipher and not the mode of operation 40
RESULTS: BIT FLIP ANALYSIS Encrypted+FNW DEUCE Encrypted+FNW Encrypted+FNW Unencrypted+FNW Unencrypted+FNW 50% 50% 50% 45% 45% 45% Bit flips per Write (%) Bit flips per Write (%) Bit flips per Write (%) 40% 40% 40% 35% 35% 35% 30% 30% 30% 25% 25% 25% 20% 20% 20% 15% 15% 15% 10% 10% 10% 5% 5% 5% 0% 0% 0% DEUCE eliminates two-thirds of the extra bit flips caused by encryption 41
