Side-channel attacks on RSA
===========================
Administrivia
Quiz 1 grades, solutions posted.
You can pick up graded quiz 1 at the end of lecture.
Side channel attacks: example setting
A server (e.g., Apache) has an RSA private key.
Server uses RSA private key (e.g., decrypt message from client).
Something about the server's computation is leaked to the client.
Many information leaks have been looked at:
How long it takes to decrypt
How decryption affects shared resources (cache, TLB, branch predictor)
Emissions from the CPU itself (RF, audio, power consumption, ..)
Adversary can analyze information leaks, use it to reconstruct private key.
To understand how this works, first let's look at some internals of RSA..
RSA: high level plan
Pick two random primes, p and q. Let n = p*q.
Pick two exponents d and e, such that m^(e*d) = m (mod n).
A common key length, i.e., |n| or |d|, is 1024 or 2048 bits today.
Encryption will be c = m^e (mod n); decryption will be m = c^d (mod n).
Result: to get m^(e*d) = m (mod n), choose e*d = 1 (mod (p-1)*(q-1)).
Since we know p & q, pick any e, compute d = e^(-1) (mod (p-1)*(q-1)).
In practice, pick small e, to make encryption fast.
Public key is (n, e).
Private key is, in principle, (n, d).
Note: p and q must be kept secret!
Otherwise, adversary can compute d from e, as we did above.
Knowing p and q also turns out to be helpful for fast decryption.
So, in practice, private key includes (p, q) as well.
RSA is tricky to use "securely" -- be careful if using RSA directly!
Some issues: ciphertexts are multiplicative; RSA is deterministic.
Typically solved by "padding" messages before encryption.
Padding includes randomness, as well as fixed bit patterns.
Helps detect tampering (e.g. ciphertext multiplication).
How to implement RSA?
Key problem: fast modular exponentiation.
In general, quadratic complexity.
Multiplying two 1024-bit numbers is slow.
Computing the modulus for 1024-bit numbers is slow (1024-bit divison).
Optimization 1: Chinese Remainder Theorem (CRT).
Suppose we want to compute m = c^d (mod n).
Can compute m1 = c^d (mod p), and m2 = c^d (mod q).
Then use CRT to compute m = c^d (mod n) from m1, m2.
Computing m1 (or m2) is 4x faster than computing m directly (quadratic).
Computing m from m1 and m2 using CRT is ~negligible in comparison.
Optimization 2: Repeated squaring and Sliding windows.
Naive approach to computing c^d: multiply c by itself, d times.
Better approach, called repeated squaring:
c^(2x) = (c^x)^2
c^(2x+1) = (c^x)^2 * c
To compute c^d, first compute c^(floor(d/2)), then use above for c^d.
Recursively apply until the computation hits c^0 = 1.
Number of squarings: |d|
Number of multiplications: number of 1 bits in d
Better yet (sometimes), called sliding window:
c^(2x) = (c^x)^2
c^(32x+z) = (c^x)^32 * c^z
Can pre-compute a table of all necessary c^z powers, store in memory.
The choice of power-of-2 constant (e.g., 32) depends on usage.
Costs: extra memory, extra time to pre-compute powers ahead of time.
Note: only pre-compute odd powers of c (use first rule for even).
OpenSSL uses 32 (table with 16 pre-computed entries).
Optimization 3: Montgomery representation.
Reducing mod p each time (after square or multiply) is expensive.
Typical implementation: do long division, find remainder.
Hard to avoid reduction: otherwise, value grows exponentially.
Idea (by Peter Montgomery): do computations in another representation.
Shift the base (e.g., c) into different representation upfront.
Perform modular operations in this representation (will be cheaper).
Shift numbers back into original representation when done.
Ideally, savings from reductions outweigh cost of shifting.
Montgomery representation: multiply everything by some factor R.
a mod q <-> aR mod q
b mod q <-> bR mod q
c = a*b mod q <-> cR mod q = (aR * bR)/R mod q
Each mul (or sqr) in Montgomery-space requires division by R.
Why is modular multiplication cheaper in montgomery rep?
Choose R so division by R is easy: R = 2^|q| (2^512 for 1024-bit keys).
Because we divide by R, we will often not need to do mod q.
|aR| = |q|
|bR| = |q|
|aR * bR| = 2|q|
|aR * bR / R| = |q|
How do we divide by R cheaply? Only works if lower bits are zero.
Trick: add multiples of q to make the lower bits zero.
Since we only care about value mod q, multiples of q don't matter.
Low bit of q is 1 (q is prime), so can "shoot down" any bits.
To "shoot down" bit k, add 2^k * q
To shoot down low-order bits l, add q*(l*(-q^-1) mod R)
Then, dividing by R means simply discarding low zero bits.
One remaining problem: result will be < R, but might be > q.
If the result happens to be greater than q, need to subtract q.
This is called the "extra reduction".
When computing x^d mod q, Pr[extra reduction] = (x mod q) / 2R.
Here, x is assumed to be already in Montgomery form.
Intuition: as we multiply bigger numbers, will overflow more often.
Optimization 4: Efficient multiplication.
How to multiply 1024-bit numbers?
Representation: break up into 32-bit values (or whatever hardware supports).
Naive approach: pair-wise multiplication of all 32-bit components.
Same as if you were doing digit-wise multiplication of numbers on paper.
Requires O(nm) time if two numbers have n and m components respectively.
O(n^2) if the two numbers are close.
Karatsuba multiplication: if both numbers have same number of components.
O(n^log_3(2)) = O(n^1.585) time.
Meaningfully faster (no hidden big constants)
For 2048-bit keys, "n" here is 32 (1024/32).
n^2 = 1024
n^1.585 = 243
Setup for the attack described in Brumley's paper.
Apache HTTPS web server using OpenSSL, has private key in memory.
Connected to Stanford's campus network.
Adversary controls another machine on campus network.
Adversary sends specially-constructed messages to server,
measures response time.
Uses the response time to guess bits of q.
What causes time variations? Karatsuba vs normal; extra reductions.
Once guessed enough bits of q, can factor n=p*q, compute d from e.
About 1M queries seem enough to obtain 512-bit factors for 1024-bit key.
How does SSL use RSA?
Server's SSL certificate contains public key.
Server must use private key to prove its identity.
Client sends random bits to server, encrypted with server's public key.
Server decrypts client's message, uses these bits to generate session key.
In reality, server also verifies message padding.
However, can still measure time until server responds in some way.
Attack from Brumley's paper.
Let q = q_0 q_1 .. q_N, where N = |q| (say, 512 bits for 1024-bit keys).
Assume we know some number j of high-order bits of q (q_0 through q_j).
Construct two approximations of q, guessing q_{j+1} is either 0 or 1:
g = q_0 q_1 .. q_j 0 0 0 .. 0
g_hi = q_0 q_1 .. q_j 1 0 0 .. 0
Get the server to perform modular exponentiation (g^d) for both guesses.
We know g is necessarily less than q.
If g and g_hi are both less than q, time taken shouldn't change much.
If g_hi is greater than q, time taken might change noticeably.
g_hi mod q is small.
Less time: fewer extra reductions in Montgomery.
More time: switch from Karatsuba to normal multiplication.
Knowing the time taken can tell us if 0 or 1 was the right guess.
How to get the server to perform modular exponentiation on our guess?
Send our guess as if it were the encryption of randomness to server.
One snag: server will convert our message to Montgomery form.
Since Montgomery's R is known, send (g/R mod n) as message to server.
How do we know if the time difference should be positive or negative?
Paper seems to suggest it doesn't matter: just look for large diff.
Figure 3a shows the measured time differences for each bit's guess.
Karatsuba vs normal multiplication happens at 32-bit boundaries.
First 32 bits: extra reductions dominate.
Next bits: Karatsuba vs normal multiplication dominates.
At some point, extra reductions start dominating again.
How does the paper get accurate measurements?
Use processor's timestamp counter (rdtsc on x86).
Measure several times, take the median value (not clear why median).
One snag: relatively few multiplications by g, due to sliding windows.
Solution: get more multiplications by values close to g.
Specifically, probe a "neighborhood" of g (g, g+1, .., g+400).
Why probe a 400-value neighborhood of g instead of measuring g 400 times?
Consider the kinds of noise we are trying to deal with.
1. Noise unrelated to computation (e.g. interrupts, network latency).
This might go away when we measure the same thing many times.
2. "Noise" related to computation.
E.g., g^d takes a little longer because of cache alignment,
processor predictions being better or worse for some g, etc.
Repeated measurements will return the same value.
Will not help determine whether g or g_hi has more reductions.
On the other hand, neighborhood values average out 2nd kind of noise.
Since neighborhood values are nearby, still has ~same # reductions.
Percival's attack.
Two threads (adversary and OpenSSL program) running concurrently on CPU.
CPU is implemented in a way that the two threads share the L1 cache.
128 cache lines, each 64 bytes.
4-way set-associative: organized as 32 sets of 4 ways each.
One thread can measure the time it takes to access memory.
Can infer something about the memory access pattern of the other thread.
Figure 2 from Percival's paper.
Overall cache access pattern reveals computation: square or multiply.
During multiply with sliding windows, can guess which value was used.
How to avoid these attacks?
Timing attack on decryption time: RSA blinding.
Choose random r.
Multiply ciphertext by r^e mod n.
Divide plaintext by r.
About a 10% CPU overhead for OpenSSL according to Brumley's paper.
Make all code paths predictable in terms of execution time.
Hard, compilers will strive to remove unnecessary operations.
Can we take away access to precise clocks?
Yes for single-threaded attackers on a machine we control.
Can add noise to legitimate computation, but attacker might average.
Can quantize legitimate computations, at some performance cost.
For cache attacks, can remove shared resources, if we can change hardware..
Or at least implement an eviction policy that minimizes this problem.
How worried should we be about these attacks?
Relatively tricky to develop an exploit.
Typically not the biggest security vulnerability, in many systems.
Timing attacks: adversary has to be close by (not that big of a problem).
Cache analysis attacks: potentially problematic with "mobile code".
Think XFI modules, Javascript, Flash, etc running on your desktop.