1Searching on Encrypted Data and Timing AttacksDawn [email protected] Example: Equality Search on Encrypted Data• Searching encrypted e-mails on servers• Searching encrypted files on servers• Searching in encrypted databasesSearch queryDownload emails3Desired 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 overhead4The Key IdeaWi -1m bitsWim bitsWi+1m bits……Si-1m bitsSim bitsSi+1m bits……Ci -1Ci Ci+1……⊕Wi+1Wi+1Wi+1⊕Search for Wi+15Setup and Notations• Document: sequence of fixed length wordsWi -1m bitsWim bitsWi+1m bits…… 6Setup and Notations• Document: sequence of fixed length words• L0, L1, L2, …–sequence of pseudorandom n-bit blocksWi -1m bitsWim bitsWi+1m bits……7Setup and Notations• Document: sequence of fixed length words• L0, L1, L2, …–sequence of pseudorandom n-bit blocks• Pseudorandom Function FK– maps n bits to (m-n) bitsWi -1m bitsWim bitsWi+1m bits……8Basic Scheme (Encryption)m bitsWi⊕m bitsCiWe xor the word Wiwithm-n bitsRiRi←FK ( Li )verification blockn bitsLiLi ←pseudorandom bitspseudo-random block9Basic Scheme (Decryption)m bitsn bits⊕m-n bitsm bitsWiLiRiCiLiRi⊕WiLi ←pseudorandom bitsRi←FK ( Li )10Basic Scheme (Searches)Search for word W, give server W and KCheck: verification block OK?Ri'= FK(Li') ? Yes ⇒ match, false positive rate = 1 / 2m-nW⊕m bitsn bits⊕m-n bitsm bitsWiLiRiCiLi'Ri'n bits m-n bitsverification block11Controlled Searches and Query Isolation• To keep server from searching for arbitrary words &To avoid leaking information about other words• In encryption:ReplaceRi← FK ( Li )withRi← 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 document12Hidden QueriesLin bitsRim-n bitsWim bitsE(Wi)m bitsE(.)where Ki= F'K( E( Wi ))⊕Cim bitsLi ←pseudorandom bitsRi←FKi( Li )13Final Scheme (Encryption)Lin bits⊕Cim bitsRim-n bitsWim bitsE(Wi)E(.)E1(Wi)E2(Wi)where Ki= F'K( E1( Wi ))Li ←pseudorandom bitsRi←FKi( Li )14Summary 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 key15Administrative 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 Mon16Midterm 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, 2ndpre-image resistance, collision resistance• Message authentication– Concept» E.g., what’s the difference between the concept of encryption and message authentication?17Midterm 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 examples18Midterm 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 randomness19Side-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.20Background: RSA Decryption• RSA decryption: gdmod 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 = gd1mod q2. m2 = gd2mod p3. combine m1 and m2 to yield m (mod N)• Goal: learn factors of N.– Kocher’s [K’96] attack fails when CRT is used.21RSA 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)22Reduction 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 algorithmwith probabilityPr[extra step] ≈ (g mod q) [S’00]2q23Pr[extra step] ≈ (g mod q)2qValue gDecryption Timeq2qp24Multiplication 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.25Multiplication Summaryg < qDecryption TimeqNormal MultiplicationKaratsubaMultiplicationgg > q26Data 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 timeOpposite effects! But one will always dominate27Timing AttackHigh Level Attack:1) Suppose g=q for the top i-1 bits, and 0 elsewhere.2) ghi= g,
View Full Document
Unlocking...