New world -- host untrusted!
- Program: wants security guarantees
- Host: untrusted
Tamper-proof doesn't exist
Types
- Smart card: credit card size, slow CPU, low memory, $2-3
- tamper-resistant brick: "card" plugs into PC's expansion bus. $500, performance of 8-year old PC
Trusted path issue: Often, no secure way for T-R device to communicate with user
Kuhn + Anderson
- tamper-resistant device easier to defeat than expected
- devices often leaked secrets, without physical attack
Details
- non-physical attack (doesn't open device)
- extracts RSA private key.
- Explots fact that running time of RSA varies depending on (input value, key). Break RSA by looking at phys. property of computation (heat, electricity). Look at time for code to run.
x to the yth power
Int exp( int x, int y){
int s = x, r = 1
for (k = 0; k < n bits; k++){
b = y & (1 << k)
if (b)
r *= s;
s = s*s;
}
return r;
}
You can analyze how long it took to run something... (notice r *= s only taken if bit = 1).
Kuhn + Andersen, 1997: r is accumulator for what you are encrypting (recall RSA algorithm uses exponetiation).
~1000 random encryptions, extract private key. CMOS: use more energy if state flips.
Same method works for time, power, heat
Need to change code to use constant time, energy. Can do by randomg "blinding" (multiply by random factor, then divide it out).
Fixable, but broke entire generation of T-R devices.
Idea: induce error in crypto computation, analyze erroneous output.
Surprise: works, even if adversary doesn't control when or where error occurs (can find key)!
To cause error: power glitch, blast x-rays, heat up CPU, lower supply voltage, glitch clock.
Model: attacker causes a single register to get scrambled. Doesn't know which reg, when or how scrambled.
RSA with Chinese Remainder Theorem [recall: RSA mod N = pq]. d,N are private key.
RSA(d,N)[x] = x^d mod pq = A(x^d mod p) + B(x^d mod q)
A mod p = 1 A mod q = 0
B mod p = 0 B mod q = 1
Above statements true by the theorem
Find A,B (precompute). Reason: p and q smaller than p*q. Less computation (exponentiation). Save a factor of 4 (4x faster).
Say error happens in
x^d mod p -> x^d mod p + delta
delta is the non-zero error factor
Almost all running time caused by beefy exponentiations, so likely for error to happen here.
Adversary: pick random value V, encrypts to get V^e mod pq ( x = v^e mod pq )
Ask for decryption with error:
bad result = A( V^ed mod p + delta ) + B( V^ed mod q ) [error only happened once, in A part]
= A( V^ed mod p) + B( V^ed mod q) + A*delta
= V^ed mod pq + A*delta
= V + A*delta
bad result - V = A * delta
Adversary computes
gcd(A*delta, N) = gcd(z*q*delta, pq) [ A mod q = 0, so A = z * q ]
= q * gcd(z*delta, p) [factor out q]
= q [p is prime, so gcd = 1]
Now, you know q, can guess p, have cracked RSA.
Assume that delta not a multiple of p (most likely it is not). Having gotten q, want to see if it is a prime factor of N. Keep trying until you get
Works against most encryption algorithms (could double-check answer, but it's another thing you have to worry about).
Differential power analysis: watch power consumption, graph of power usage. Very effective.
3 attacks in 3.5 years to defeat entire generation of T-R devices.
- Assume device can't keep secret from someone who has physical possession of it
- device should be ally of person who has it
- Carefully bound the possible loss if device is compromised. Limit power device has, velocity control, posessor knows quickly when stolen
