PB173 Domain specific
development: side-channel
analysis
Seminar 10: Work in progress on main goals &
how to install
Łukasz Chmielewski
chmiel@fi.muni.cz, Consultation: A406 Friday 9:00-11:00
FAULT INJECTION ATTACKS:
DIFFERENTIAL FAULT ANALYSIS ON RSA-CRT
Active Side-Channel
2
Passive vs Active Side Channels
Passive: analyze device behavior Active: change device behavior
3
https://escooptics.com/blogs/news/world-space-week-02-lasers
Recall: RSA
• Two primes 𝒑 and 𝒒
• 𝑵 = 𝒑𝒒
• 𝝋 𝑵 = 𝒑 − 𝟏 𝒒 − 𝟏
• 𝒆 = 𝟑, 𝟓, 𝟕, 𝟏𝟕, 𝟐𝟓𝟕, 𝟔𝟓𝟓𝟑𝟕 → 𝐠𝐜𝐝 𝒆, 𝝋 𝑵 = 𝟏
• 𝒅 = 𝒆−𝟏 𝒎𝒐𝒅 𝝋(𝑵)
• Encryption / Verification: 𝒄 = 𝒎 𝒆 𝒎𝒐𝒅 𝑵
• Decryption / Signature: 𝒎 = 𝒄 𝒅 𝒎𝒐𝒅 𝑵
𝒆 𝒅
𝒄/𝒎 𝒎/cModExp()
Modular Exponentiation:
| PB173 Org. & Introduction4
Recall: RSA Exponentiation (1)
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){
}
d=(101)=5
A = 1,
d2=1
A = A2 mod N=1
A = A*c mod N=c
d1=0
A = A2 mod N=c2
d0=1
A = A2 mod N=c4
A = A*c mod N=c5
| PB173 Org. & Introduction5
Recall: Simple Power Analysis on RSA
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.”
| PB173 Org. & Introduction6
RSA in practice: RSA-CRT
7
• Optimization of computing a signature giving about 3 or 4-fold speed-up
• Precompute the following values:
– Find dp = d (mod p-1), computed as dp = e-1 (mod p-1)
– Find dq = d (mod q-1)
– Compute iq = q-1 (mod p)
• Computations using mp = m (mod p) and mq = m (mod q)
• Signature or encryption (forgetting about hashing):
– sp = 𝑚 𝑑 𝑝 (mod p)
– sq = 𝑚 𝑑 𝑞 (mod q)
– Garner’s method (1965) to recombine sp and sq:
• s = sq + q · (iq(sp − sq) (mod p))
• Let us see the slides from Seminar 1!
ORGANIZATIONAL
8
Final Division
• Group 1: Michal, Matus, Filip (?)
– Topic: Align
– GitHub repository: https://github.com/mr-akiio/trs-alignment
• Group 2: Michael T, Lubomir, Richard
– Topic: Standard Processing, Michael might touch also “Parallel
computations with acquisition”
– The group is 3 people since Vendelín left.
– GitHub repository:
https://github.com/LubJur/PB173_standard_signal_processing
• Group 3: Tomas Re, Tomas Ro, Martin
– Topic: Visualization
– GitHub repository: https://github.com/reznakt/pb173-sca-visualization
9
(Modified) Seminars Plan
• 7: today, no points
• 8: evaluation of first steps given last week: 3 points per
group (personalized per person based on Github activity) +
Giving new tasks
• 9: Checking Progress: helping & trying to run your tools
• 10: 3 points per group (personalized per person based
on GitHub) + a short 5-10minuts progress presentation
+ demo (1 point) + Giving new tasks
• 11: Checking Progress [Online]
• 12: Final seminar: final short 5-10minuts presentation (1
point) & grading + grading (3 points for final tasks) + 2
points for activity.
12
Short Presentations: 5min + demo
• What are you solving?
• What language or libraries are you using?
• What do you have now?
• What are you going to do?
• Short demo
13
PRESENTATIONS BY GROUP NUMBER
(GRADING THE PRESENTATION)
14
WHAT WAS DONE + GIVING NEW TASKS
(GRADING THE WORK)
15
Group 1: Installation
• No installation or examples; please add something!
16
Group 1: Work Distribution
17
Group 1: Main Goals
• Main Tasks:
– Test more peak-based alignment
– Correlation-Based Alignments
– Improve Efficiency
– Two from:
• Trace alignment algorithm for suppressing the clock jitter,
see pages 45-50 of: https://ged.biu-
montpellier.fr/florabium/jsp/win_main_biu.jsp?nnt=2014MON20039
&success=%2Fjsp%2Fwin_main_biu.jsp&profile=anonymous
• Elastic alignment algorithm or
• Round Based Alignment
18
Group 1: What to do next
• TODO together
19
Group 2: Installation
20
Group 2: Work Distribution
21
Group 2: Main Goals
• Main Tasks:
– Standard Deviation, Average, FFT
– Spectrogram
– Incremental Correlation:
https://eprint.iacr.org/2022/253.pdf
– Pipelining
– Signal-To-Noise Ratio and other metrics
22
Group 2: What to do next
• TODO together
23
Group 3: Installation
24
Group 3: Work Distribution
25
Group 3: Main Goals
• Main Tasks:
– Displaying Traces
– Moving traces around?
– Selecting part of the trace to run something (any code)?
– Comparison to other libraries
26
Group 3: What to do next
• TODO together
27
WALK-AROUND & HELPING &
DISCUSSIONS
28
Reading
• For interested people
• Side-Channel Analysis – blue book:
– http://dpabook.iaik.tugraz.at/
– The books is available at the uni.
– Look online
• The Hardware Hacking Handbook:
– https://nostarch.com/hardwarehacking
– I have an epub version.
29
30
| PA193 - Programming in the presence of side-channels /
faults
Questions