Searching on Encrypted Data and Timing Attacks Dawn Song dawnsong cs berkeley edu 1 Motivating Example Equality Search on Encrypted Data Searching encrypted e mails on servers Searching encrypted files on servers Searching in encrypted databases Search query Download emails 2 Desired Properties Word search is provably secure Provable encryption properties Server cannot search for arbitrary words Does not leak information about other words Does not reveal query word Efficiency Low computation overhead Low space and communication overhead Low management overhead 3 The Key Idea Wi 1 Wi Wi 1 m bits m bits m bits Si 1 m bits Si Si 1 m bits m bits Ci 1 Ci Ci 1 Wi 1 Wi 1 Wi 1 Search for Wi 1 4 Setup and Notations Document sequence of fixed length words Wi 1 Wi Wi 1 m bits m bits m bits 5 Setup and Notations Document sequence of fixed length words Wi 1 Wi Wi 1 m bits m bits m bits L0 L1 L2 sequence of pseudorandom n bit blocks 6 Setup and Notations Document sequence of fixed length words Wi 1 Wi Wi 1 m bits m bits m bits L0 L1 L2 sequence of pseudorandom n bit blocks Pseudorandom Function FK maps n bits to m n bits 7 Basic Scheme Encryption m bits Li Ri n bits m bits Wi Ci m n bits pseudo random block verification block We xor the word Wi with Li pseudorandom bits Ri FK Li 8 Basic Scheme Decryption m bits Wi Li n bits Ri m n bits m bits Ci Li Ri Wi Li pseudorandom bits Ri FK Li 9 Basic Scheme Searches Search for word W give server W and K m bits Li Ri n bits m bits Wi Ci m n bits W Li n bits Check verification block OK Ri FK Li Yes match false positive rate 1 2m n Ri m n bits verification block 10 Controlled Searches and Query Isolation To keep server from searching for arbitrary words To avoid leaking information about other words In encryption Replace Ri FK Li with Ri FKi Li where Ki F K Wi To search for word W Reveal Kw F K W Enhancements Check only for word occurs at least once in document Check only for word occurs at least N times in document 11 Hidden Queries m bits Wi m bits E m bits E Wi Li Ri n bits Ci m n bits Li pseudorandom bits Ri FKi Li where Ki F K E Wi 12 Final Scheme Encryption m bits Wi E E Wi E1 Wi E2 Wi Li Ri n bits m bits Ci m n bits Li pseudorandom bits Ri FKi Li where Ki F K E1 Wi 13 Summary for Keyword Search on Encrypted Data Symmetric Key Case Provable security Provable secrecy Controlled search Query isolation Hidden queries Simple and efficient O length of document stream cipher block cipher and MAC operations for encryption decryption O length of document MAC operations for search Almost no space and communication overhead Easy to add documents Convenient key management user needs only one master key 14 Administrative Matters Out of town starting Wed My office hour this week will be 5pm Tue John will give a guest lecture on Wed Rusty and Todd will do midterm review next Mon 15 Midterm Scope I Symmetric key encryption Concept One time pad Block cipher modes how they work Public key encryption Concept How does RSA encryption decryption work How does ElGamal encryption decryption work Hash functions Concept of one way pre image resistance 2nd pre image resistance collision resistance Message authentication Concept E g what s the difference between the concept of encryption and message authentication 16 Midterm Scope II Digital signatures Concept E g what s the difference between digital signatures MACs One time signature ElGamal signature RSA signature Secret sharing Concept Threshold secret sharing schemes Zero knowledge proofs Concept ZKP of square roots and other graph based examples 17 Midterm Scope III Authentication and key exchange protocols Identify potential attacks Do not need to know how exactly every message works Random number generator How to generate random numbers in practice Which sources are potentially good bad sources of randomness 18 Side Channel Attacks on Crypto A different attacker model Side channel attacks on Crypto Example RSA in OpenSSL was vulnerable to timing attack Attacker can extract RSA private key by measuring web server response time Exploiting OpenSSL s timing vulnerability One process can extract keys from another Extract web server key remotely Our attack works across Stanford campus 19 Background RSA Decryption RSA decryption gd mod N m d is private decryption exponent N is public modulus Chinese remaindering CRT uses factors directly N pq and d1 and d2 are pre computed from d 1 m1 gd1 mod q 2 m2 gd2 mod p 3 combine m1 and m2 to yield m mod N Goal learn factors of N Kocher s K 96 attack fails when CRT is used 20 RSA Decryption Time Variance Causes for decryption time variation Which multiplication algorithm is used OpenSSL uses both basic mult and Karatsuba mult Number of steps during a modular reduction modular reduction goal given u compute u mod q Occasional extra steps in OpenSSL s reduction alg There are MANY multiplications by input g modular reductions by factor q and p 21 Reduction Timing Dependency Modular reduction given u compute u mod q OpenSSL uses Montgomery reductions M 85 Time variance in Montgomery reduction One extra step at end of reduction algorithm with probability Pr extra step g mod q 2q S 00 22 Pr extra step g mod q 2q Decryption Time q 2q p Value g 23 Multiplication Timing Dependency Two algorithms in OpenSSL Karatsuba fast Multiplying two numbers of equal length Normal slow Multiplying two numbers of different length To calc x g mod q OpenSSL does When x is the same length as g mod q use Karatsuba mult Otherwise use Normal mult 24 Multiplication Summary Decryption Time Karatsuba Multiplication Normal Multiplication g q g q g q 25 Data Dependency Summary Decryption value g q Montgomery effect longer decryption time Multiplication effect shorter decryption time Decryption value g q Montgomery effect shorter decryption time Multiplication effect longer decryption time Opposite effects But one will always dominate 26 Timing Attack High Level Attack 1 Suppose g q for the top i 1 bits and 0 elsewhere 2 ghi g but with the ith bit 1 Then g ghi Goal decide if g q ghi or g ghi q 3 Sample decryption time for g and ghi t1 DecryptTime g t2 DecryptTime ghi 4 If t1 t2 is large else large vs small creates 0 1 gap g and ghi bit i is 0 straddle q don t bit i is 1 straddle q g q ghi g ghi q 27 Timing Attack Details We know what is large and small from attack on previous bits Decrypting just g does not work because of sliding windows Decrypt a neighborhood of values near g Will increase diff between large and
View Full Document
Unlocking...