0x1A Great Papers in Computer Security Vitaly Shmatikov CS 380S http://www.cs.utexas.edu/~shmat/courses/cs380s/slide 2 Attacking Cryptographic Schemes Cryptanalysis • Find mathematical weaknesses in constructions • Statistical analysis of plaintext / ciphertext pairs Side-channel attacks • Exploit characteristics of implementations • Power analysis • Electromagnetic radiation analysis • Acoustic analysis • Timing analysisslide 3 Timing Attack Basic idea: learn the system’s secret by observing how long it takes to perform various computations Typical goal: extract private key Extremely powerful because isolation doesn’t help • Victim could be remote • Victim could be inside its own virtual machine • Keys could be in tamper-proof storage or smartcard Attacker wins simply by measuring response timesslide 4 RSA Cryptosystem Key generation: • Generate large (say, 512-bit) primes p, q • Compute n=pq and (n)=(p-1)(q-1) • Choose small e, relatively prime to (n) – Typically, e=3 (may be vulnerable) or e=216+1=65537 (why?) • Compute unique d such that ed = 1 mod (n) • Public key = (e,n); private key = d – Security relies on the assumption that it is difficult to compute roots modulo n without knowing p and q Encryption of m (simplified!): c = me mod n Decryption of c: cd mod n = (me)d mod n = mslide 5 How RSA Decryption Works RSA decryption: compute yx mod n • This is a modular exponentiation operation Naïve algorithm: square and multiplyslide 6 Kocher’s Observation This takes a while to compute This is instantaneous Whether iteration takes a long time depends on the kth bit of secret exponentExploiting Timing Information Different timing given operands Assumption / heuristic: timings of subsequent multiplications are independent • Given that we know the first k-1 bits of x … Given a guess for the kth bit of x … … Time for remaining bits independent Given measurement of total time can see whether there is correlation between “time for kth bit is long” and “total time is long” Exact timing Exact guess slide 7slide 8 Outline of Kocher’s Attack Idea: guess some bits of the exponent and predict how long decryption will take If guess is correct, will observe correlation; if incorrect, then prediction will look random • This is a signal detection problem, where signal is timing variation due to guessed exponent bits • The more bits you already know, the stronger the signal, thus easier to detect (error-correction property) Start by guessing a few top bits, look at correlations for each guess, pick the most promising candidate and continueD. Brumley and D. Boneh Remote Timing Attacks are Practical (USENIX Security 2003)slide 10 RSA in OpenSSL OpenSSL is a popular open-source toolkit • mod_SSL (in Apache = 28% of HTTPS market) • stunnel (secure TCP/IP servers) • sNFS (secure NFS) • Many more applications Kocher’s attack doesn’t work against OpenSSL • Instead of square-and-multiply, OpenSSL uses CRT, sliding windows and two different multiplication algorithms for modular exponentiation – CRT = Chinese Remainder Theorem – Secret exponent is processed in chunks, not bit-by-bitslide 11 Chinese Remainder Theorem n = n1n2…nk where gcd(ni,nj)=1 when i  j The system of congruences x = x1 mod n1 = … = xk mod nk • Has a simultaneous solution x to all congruences • There exists exactly one solution x between 0 and n-1 For RSA modulus n=pq, to compute x mod n it’s enough to know x mod p and x mod qslide 12 RSA Decryption With CRT To decrypt c, need to compute m=cd mod n Use Chinese Remainder Theorem (why?) • d1 = d mod (p-1) • d2 = d mod (q-1) • qinv = q-1 mod p • Compute m1 = cd1 mod p; m2 = cd2 mod q • Compute m = m2+(qinv*(m1-m2) mod p)*q these are precomputed Attack this computation in order to learn q. This is enough to learn private key (why?)slide 13 Montgomery Reduction Decryption requires computing m2 = cd2 mod q This is done by repeated multiplication • Simple: square and multiply (process d2 1 bit at a time) • More clever: sliding windows (process d2 in 5-bit blocks) In either case, many multiplications modulo q Multiplications use Montgomery reduction • Pick some R = 2k • To compute x*y mod q, convert x and y into their Montgomery form xR mod q and yR mod q • Compute (xR * yR) * R-1 = zR mod q – Multiplication by R-1 can be done very efficientlyslide 14 Schindler’s Observation At the end of Montgomery reduction, if zR > q, then need to subtract q • Probability of this extra step is proportional to c mod q If c is close to q, a lot of subtractions will be done If c mod q = 0, very few subtractions • Decryption will take longer as c gets closer to q, then become fast as c passes a multiple of q By playing with different values of c and observing how long decryption takes, attacker can guess q! • Doesn’t work directly against OpenSSL because of sliding windows and two multiplication algorithmsslide 15 Value of ciphertext c Decryption time q 2q p Reduction Timing Dependencyslide 16 Integer Multiplication Routines 30-40% of OpenSSL running time is spent on integer multiplication If integers have the same number of words n, OpenSSL uses Karatsuba multiplication • Takes O(nlog23) If integers have unequal number of words n and m, OpenSSL uses normal multiplication • Takes O(nm)slide 17 g<q g>q Montgomery effect Longer Shorter Multiplication effect Shorter Longer g is the decryption value (same as c) Different effects… but one will always dominate! Summary of Time Dependenciesslide 18 Decryption time #Reductions Mult routine Value of ciphertext q 0-1 Gap Discontinuity in Decryption Timeslide 19 Normal SSL Handshake Regular client SSL server 1. ClientHello 2. ServerHello (send public key) 3. ClientKeyExchange (encrypted under public key) Exchange data encrypted with new shared keyslide 20 Attacking SSL Handshake SSL server 1. ClientHello 2. ServerHello (send public key) Attacker 3. Record time t1 Send guess g or ghi 4. Alert 5. Record time t2 Compute t2–t1slide 21 Initial guess g for q between 2511 and 2512 (why?) Try all possible guesses for the top few bits Suppose we know i-1 top bits of q. Goal: ith bit. • Set g =<known i-1 bits of q>000000 • Set ghi=<known