PV181 Laboratory of security
and applied cryptography
Seminar 9:
Crypto-libraries protected against hardware attacks
Łukasz Chmielewski
chmiel@fi.muni.cz
| PV1811
Outline
• Recall + goal of this seminar
– Digital signatures
– RSA vs. ECC
• Side Channel + Fault Injection speed run
• Secured X25519 library: sca25519
– Demo Exercise
• Python Exercise
– Securing RSA execution
• No Assignment this week ☺
2 | PV181
encryption decryption
message
Alice
Public key of Bob
Bob
Adapted Source: Network and
Internetwork Security (Stallings)
Private key of Bob
Encrypted
message
Decrypted
original
message
| PV1813
Recall: Asymmetric cryptosystem
Recall: Digital signature scheme
4 | PV181
Signature
algorithm
Verification
algorithmmessage signed
message
Alice
Public key of Alice
Bob
Source: Network and
Internetwork Security (Stallings)
verified
message
Private key of Alice
Is there a difference?
Recall: RSA vs. ECC
5 | PV181
• exponentiation ≈ scalar
multiplication
• multiplication ≈ points addition
• squaring ≈ point doubling
Why is hardware security important?
6 | PV181
Identity Theft
• Premium
Content Theft
Impersonation
Card / Money Theft
Phone / Money Theft
7 | PV181
Side-
Channel
Analysis
8 | PV181
Cookies Example
9 | PV181
Passive vs Active Side Channels
10 | PV181
Passive: analyze device behavior Active: change device behavior
Recent Practical Attacks
11 | PV181
Side Channels
• Time
• Power
• Electro Magnetic Emanations
• Light
• Sound
• Temperature
• …
12 | PV181
What can be attacked & why?
• Type of device?
• What kind of primitive?
• How much control do you have?
• What can you access?
• What would be the attacker’s goal?
• What is your goal?
• Where is the money?
• …
13 | PV181
Practical Setup Spectrum
14 | PV181
Some Other Practical Setups
15 | PV181
Actual (overcomplicated?) setup
16 | PV181
Example Side Channel Attack:
GPU running NN
17 | PV181
Simple Power Analysis (SPA) on RSA
18 | PV181
1996.
A = 1
for ( i = n-1; i≥0; i− −)
A = A2 mod N
if (di = =1)
A = A*c mod N
end if
end for
Return A = cd mod N
ModExp(c){
}
M M M MS S S …
S
M
… S S S S S S S S S
1 0 1 0 0 0 1 0 0 1 0
Probe
“By carefully measuring the amount of time required to perform
private key operations, attackers may be able to find […] RSA
keys.”
Differential (Correlation) Power Analysis
19 | PV181
1999
1999
2004
random
inputs
…
ntraces
Guess ෡𝒅 bits target state
User:
• HW of a register
• HD between current and previous register state
• ID model (value of a register)
𝑓𝑖 = Selection Function(random inputs, ෡𝒅, target state)
DPA = Difference of Means
𝑓𝑖 = ቊ
0 𝑖𝑓 𝐻𝑊 ≤ 16
1 𝑖𝑓 𝐻𝑊 > 16
𝑓𝑖 = 𝐻𝑊(𝑟𝑒𝑔_𝑠𝑡𝑎𝑡𝑒)
CPA = Pearson correlation
ModExp(𝒅)
Goals of Fault Injection
20 | PV181
• The goal is to change a critical value or to change the flow
of a program.
• Faults can be injected in several ways:
– Power glitches can disturb the power supply to the processor, resulting in
wrong values read from memory.
– Optical glitches with laser can force any elementary circuit to switch,
enabling the attacker to achieve a very specific change of data values or
behavior.
– Clock manipulation by introducing a few very short clock cycles which may
lead to the device misinterpreting a value read from memory.
– Cutting the power to the processor while performing important computations,
hoping to either prevent the system from taking measures against a detected
attack or get the system into a vulnerable state when the power is back.
• Differential Fault Analysis (DFA)
Fault Injection Example:
the “unlooper” device
21 | PV181
Question 0:
Software for PIN code verification
22 | PV181
• What is the problem here?
• What are the execution times of
the process for PIN inputs?
• [0,1,2,3], [5,3,0,2], [5,9,0,0]
• The execution time increases as
we get closer to
• [5,9,0,2]
Task 0 – parity check for DES key
23 | PV181
Task 0 – parity check for DES key cont’d
24 | PV181
Tell me what is the key ☺
Question 1:
faster and more secure modexp - Montgomery ladder
26 | PV181
x0=x; x1=x2
for j=k-2 to 0 {
if dj=0
x1=x0*x1; x0=x0
2
else
x0=x0*x1; x1=x1
2
x1=x1 mod N
x0=x0 mod N
}
return x0
Both branches with the same
number and type of operations
(unlike square and multiply on
previous slide)
Is it constant-time & secure? Why?
Question 2:
even more secure modexp
27 | PV181
x0=x; x1=x2
for j=k-2 to 0 {
b=dj
x(1-b)=x0*x1; xb=xb
2
x1=x1 mod N
x0=x0 mod N
}
return x0
Memory access often is not
constant time!
Especially in the presence of
caches.
Is it constant-time & secure? Why?
Question 3:
even more secure modexp
28 | PV181
x0=x; x1=x2
for j=k-2 to 0 {
b=dj
x(1-b)=x0*x1; xb=xb
2
x1=x1 mod N
x0=x0 mod N
}
return x0
Memory access often is not
constant time!
Especially in the presence of
caches.
Is it constant-time & secure? Why?
Question 4:
even more more secure modexp
29 | PV181
x0=x; x1=x2; sw = 0
for j=k-2 to 0 {
b=dj
cswap(x0,x1,b⊕sw)
sw = sw⊕di
x1=x0*x1; x0=x0
2
x1=x1 mod N
x0=x0 mod N
}
return x0
Constant-time? Depends on the
cswap… but it can be ☺
Other-side channels? Depends 
Is it constant-time & secure? Why?
Question 5:
Arithmetic Cswap – constant-time?
30 | PV181
Question 5:
Arithmetic Cswap – secure against other side-channels?
31 | PV181
sample 𝒕𝒊
⋮
Scalar multiplication trace
255
iterations
⋯
sample index
samplevalue(V)
Apply clustering (e.g. k-means), Template Attack, Deep Learning
to the set of 255 samples:
bits 0 bits 1
255 Samples255 Montgomery iterations
Message and exponent blinding
32 | PV181
𝒄 = 𝒎 𝒅 𝒎𝒐𝒅 𝑵
1. 𝒎 𝒓 = 𝒎. 𝒓−𝒆
𝒎𝒐𝒅 𝑵
2. 𝒅 𝒓 = 𝒅 + 𝒓 ∗ 𝝋(𝒏)
3. 𝒄 𝒓 = 𝒎 𝒓
𝒅 𝒓 𝒎𝒐𝒅 𝒏
4. 𝒄 = 𝒄 𝒓 ∗ 𝒓 𝒎𝒐𝒅 𝒏
message blinding
message “unblinding”
exponent blinding
blinded exponentiation
The sequence of operations (S, M) is related to the exponent bits.
However:
• If d is random: the sequence of exponent bits changes for every RSA execution
• If m is random: Intermediate data is random (masked) → hardly predicted!
DPA is based on the prediction of intermediate data.
Thesis: Any side-channel attack requiring multiple traces are repelled by message and exponent blinding
countermeasures.
For ECC there are corresponding countermeasures: coordinate blinding, scalar blinding, blinded scalar
multiplications, and no unblinding ☺
SCA&FI-protected Elliptic Curve library
• A protected library for ECDH
– key exchange & session key establishment
– It will be published in TCHES2023 volume 1 and
• presented at Ches 2023 in Prague
• Download the library from github
• Useful links:
– https://eprint.iacr.org/2021/1003
– https://github.com/sca-secure-library-sca25519/sca25519
• Taking care of ECDSA:
– https://eprint.iacr.org/2022/1254
– I will add it to the repository later on.
33 | PV181
Seminar Tasks
• Task 1 – analyze the code of the ephemeral
implementation with respect to Questions 1 to 5.
– How is protected?
– Work in pairs and discuss your thoughts.
• Task 2 - compare implementations – what is the
difference?
– Hint: you can have a look at the paper and the repo too.
• Task 3 – how different implementations are
measuring efficiency?
• Task 4 – do you see any fault injection
countermeasures?
34 | PV181
Seminar Tasks Cont’d
• Let’s do the efficiency DEMO.
• (Optional) Tasks 5 – try to perform various
measurements of the efficiency of one (chosen by
you) implementation.
– We have only two boards so people can do it in small
groups and change.
• Task 6: protect the RSA implementation with
exponent blinding! – see the RSA.py
• Super-optional Task 7: protect the implementation
with message blinding! – see the RSA.py
35 | PV181
No Assignment
• ☺
36 | PV181