Side-Channel Attack

12/2/2014
Introduction to Cryptographic Side‐Channel Attacks
Yinqian Zhang
Postdoctoral Research Associate
UNC‐Chapel Hill
Side‐Channel Attack
 Obtaining information from the unintended communication channels introduced in the design or implementation of a system
2
1
12/2/2014
Cryptographic Side‐Channel Attacks
 Side‐channel attacks against cryptographic systems
• Attacks based on information gained from the physical implementation of a crypto system
 Targets of attacks
• Cryptographic keys, plaintext of a given ciphertext
• Asymmetric Encryption: RSA, ElGamal, etc.
• Symmetric Encryption: AES, DES, etc.
3
Today’s Topic:
 Taxonomy of cryptographic side‐channel attacks
 Explanation of several types of side‐channel attacks against RSA encryptions.
• Cache‐based access‐driven attacks
• Remote timing attacks
• Power analysis attacks*
• Acoustic attacks*
4
2
12/2/2014
RSA Encryption and Decryption
 Public key (e, N); private key (d, N)
• N = p × q, where p and q are prime numbers
• gcd(e, Φ(N)) = 1 , where Φ(N) = (p‐1) × (q‐1)
• d ≡ e‐1 mod Φ(N)  RSA encryption, plaintext m, ciphertext c
• c ≡ me mod N  RSA decryption
•
m ≡ cd
mod N
Modular exponentiation with big numbers is SLOW!
5
Square‐and‐Multiply Algorithms
/* x = cd mod N */
Modular Exponentiation (c, d, N):
let dn … d1 be the bits of d
x ← 1
for di in {dn …d1}
x ← x2 mod N if di = 1 then x ← x × c mod N
return x What is of interest to an attacker?
3
12/2/2014
Taxonomy of Side‐Channel Attacks
 Internal side‐channel attacks
• Attacker controls a process/application/virtual machine in a shared computing device
Cloud computing, grid computing, mobile computing
 External side‐channels attacks
• Attacker physically possesses a computing device
• Attacker remotely connects to a computer server
7
Internal Side‐Channel Attacks
 According to security isolation
• Cross‐process side‐channel attacks
• Cross‐VM side‐channel attacks
 According to the shared media
• L1 data cache
• L1 instruction cache
• Prediction units in CPUs
• Function units in CPUs 8
4
12/2/2014
Internal Side‐Channel Attacks
 According to security domains
• Cross‐process side‐channel attacks
• Cross‐VM side‐channel attacks
 According to shared media
• L1 data cache
• L1 instruction cache
• Prediction units in CPUs
• Function units in CPUs 9
Cross‐Process Attacks
 Requires the attacker to control an unprivileged process on the shared system on which the victim cryptographic operation runs
Process
Process
Memory/file access
Attacker
Side channels
Shared Operating System
Victim
Secret Keys
10
5
12/2/2014
Prime‐Probe Protocols
PRIME
PRIME‐PROBE Interval
PROBE
Time
4‐way set associative L1 data cache
Cache Set
Square‐and‐Multiply Algorithms
/* x = ae mod N */
Modular Exponentiation (a, e, N):
let en … e1 be the bits of e
x ← 1
for ei in {en …e1}
x ← x2 mod N (Square)
if ei = 1 then x ← x × a mod N (Multiply)
return x
ei = 1 → Square + Multiply
ei = 0 → Square
6
12/2/2014
Prime‐Probe Results
13
Internal Side‐Channel Attacks
 According to security domains
• Cross‐process side‐channel attacks
• Cross‐VM side‐channel attacks
 According to shared media
• L1 data cache
• L1 instruction cache
• Prediction units in CPUs
• Function units in CPUs 14
7
12/2/2014
External Side‐Channel Attacks
 Against remote servers
• Timing (side) channels
 Against physically possessed devices
• Timing (side) channels
• Power (side) channels
• Acoustic (side) channels
15
External Side‐Channel Attacks
 Against remote servers
• Timing (side) channels
 Against physically possessed devices
• Timing (side) channels
• Power (side) channels
• Acoustic (side) channels
16
8
12/2/2014
Timing Attacks against Smartcards
 [Kocher, 1996] Timing attacks on implementations of Diffie‐Hellman, RSA, DSS and other systems
 Performance characteristics of a cryptosystems (e.g., a smartcard) depend on both the encryption key and the input data
• The computation time of a private‐key operation is known to the attacker
• Chosen‐ciphertext attack
17
Square‐and‐Multiply Algorithm
/* x = cd mod N */
Modular Exponentiation (c, d, N):
let dn … d1 be the bits of d
Attack Step 1: xn+1 ← 1
Guess the value for di in {dn …d1}
of di in order of xi ← xi+12 mod N dn …d1. One bit at a time.
if di = 1 then xi ← xi × c mod N
return x1
Attack Step 2: For each di in {dn …d1}, select c so that xi × c is VERY slow. If the overall exponentiation is unaffected, di = 0
9
12/2/2014
External Side‐Channel Attacks
 Against remote servers
• Timing (side) channels
 Against physically possessed devices
• Timing (side) channels
• Power (side) channels
• Acoustic (side) channels
19
Remote Timing Attacks
 [Brumley and Boneh, 2003] Remote timing attacks are practical
 Extend Kocher’s attack: • Attacking remote SSL servers • “State‐of‐the‐art” OpenSSL implementation
Chinese Remainder Theorem
Montgomery reduction
Karatsuba multiplication
20
10
12/2/2014
Chinese Remainder Theorem
 Pre‐compute dp and dq
• dp = d mod φ(p)
• dq = d mod φ(q)
 Pre‐compute qinv = 1/q mod p
 To calculate m ≡ cd mod N
• mp = cd mod p
• mq = cd mod q
• h = qinv × (mp – mq) mod p
• m = mq + h × q
p
q
21
Factorization of N given dp and dq
 Given dp and a pair {c, m}, c ≡ me mod N  Calculate mp ≡ cd mod N
 p = gcd (m‐mp, N), because
p
• m ≡ cd mod p ≡ cdp + k(p‐1) mod p ≡ cdp c k(p‐1) mod p
≡ cdp mod p
 Calculate q similarly
22
11
12/2/2014
Montgomery Reduction
 A modular reduction (multi‐precision division & returning the remainder) is very expensive
 OpenSSL needs to do one modular reduction after every multiplication or squaring
 Peter Montgomery (1985):
• Modular arithmetic is performed fast with large number
c ≡ a × b mod N is faster in Montgomery form
• Transform a number into Montgomery form, do modular arithmetic computation, convert back. 23
Montgomery Reduction Examples
Example: calculate c = a × b mod q
 Transform into Montgomery form
• aR mod q
• bR mod q
 Compute the product as integers
• aR × bR = abR = cR
 Fast Montgomery reduction
2 2
• cR2 × R‐1 = cR mod q
• Extra reduction if cR > q
 Transform from Montgomery form
• cR × R‐1 mod q = c mod q
24
12
12/2/2014
Number of Extra Reductions
 [Schindler, 2000]: calculate gd mod q
• Pr(Extra Reduction) = (g mod q) / 2R
25
Karatsuba Multiplication
 Fast multiplication algorithm: multiplication of two n‐digit numbers takes time O(nlog23), rather than O(n2).
 OpenSSL uses Karatsuba multiplication (faster) when multiplies two numbers with equal size.
 OpenSSL uses normal multiplication (slower) when multiplies two numbers with unequal size.
26
13
12/2/2014
Square‐and‐Multiply Algorithms
Convert g and q /* x = gd mod q */
into Montgomery Modular Exponentiation (g, d, q):
form
let dn … d1 be the bits of d
xn+1 ← 1
Extra reduction
for di in {dn …d1}
xi ← xi+12 mod q if di = 1 then xi ← xi × g mod q
return x1
Convert x1 back
Karatsuba multiplication
or normal multiplication
Timing Differences
 When g approaches q from below:
• More extra reductions in Montgomery reduction
• Faster Karatsuba multiplication
 When g is just over q:
• Fewer extra reductions in Montgomery reduction
• g mod q is very small ‐‐‐ slower multiplications
 The two effects are opposite to each other
 When g approaches q from below and grows just over q ‐‐‐ drastic timing difference!
28
14
12/2/2014
Timing Attacks on Exponents
 Chosen‐ciphertext attacks on gd mod q
• Select g to guess q
• Guess one bit at a time from MSB to LSB
 When the top i‐1 bits of q is known, let g be an integer with top i‐1 bits same as q and remaining bits as 0, let g’ be the same value of g, except ith bit is 1: g < g’ and g < q
• q = {1, 0, 1, qn‐3, qn‐4, …, q1}
• g = {1, 0, 1, 0, 0, …, 0}
• g’ = {1, 0, 1, 1, 0, …, 0}
29
Timing Attacks on Exponents
To recover the ith bit of q:
 Compute u = gR‐1 mod N and u’ = g’R‐1 mod N
 Decrypt u and u’
• t = DecryptTime(u)
• t’ = DecryptTime(u’)
 If |t – t’| is large: g < q < g’ • bit i of q is 0
 If |t – t’| is small: g < g’ < q
• bit i of q is 1
30
15
12/2/2014
External Side‐Channel Attacks
 Against remote servers
• Timing (side) channels
 Against physically possessed devices
• Timing (side) channels
• Power (side) channels
• Acoustic (side) channels
31
External Side‐Channel Attacks
 Against remote servers
• Timing (side) channels
 Against physically possessed devices
• Timing (side) channels
• Power (side) channels
• Acoustic (side) channels
32
16
12/2/2014
Simple Power Analysis
33
Simple Power Analysis
34
17
12/2/2014
External Side‐Channel Attacks
 Against remote servers
• Timing (side) channels
 Against physically possessed devices
• Timing (side) channels
• Power (side) channels
• Acoustic (side) channels
35
Differentiating CPU Operations
36
18
12/2/2014
Differentiating Bits in Exponents
 Bits in exponents can be differentiated between frequency 34~39kHz
37
Summary
 Internal side‐channel attacks
• CPU caches
• CPU function units
 External side‐channels attacks
• Timing channels
• Power channels
• Acoustic channels
 RSA, AES, DES, DH, DSS, …
38
19

Download Report