11/24/20091Dynamic Authenticated Index Structures for Outsourced Databases1Feifei Li, Marios Hadjieleftheriou, George Kollios, Leonid ReyzinBoston University AT&T Labs‐ResearchPresenter : Nima NajafianOutline☺ The Model☺ Motivation☺ Problem☺ Solution☺ Background☺ Papers contributions☺ Experimental validationOutsourced Database ModelOwner: publish dataServers: host the data and provide query servicesClients: query the owner’s data through serversSD3ownerserversclientsMotivation• Advantages– The data owner does not need the hardware / software / personnel to run a DBMS–Theownerachieveseconomies of scaleThe ownerachieveseconomies of scale– The client enjoys better quality of service A main challenge– The service provider is not trusted, and may return incorrect query resultsProblem☺ Un‐trusted ServersUn‐trusted server• Lazy: incentives to perform less• Curious: incentives to acquire information• Malicious–Incorrect results ( could be bugs)– Possibly compromised11/24/20092Problem 1: InjectionSDSelect * from T where 5<A<11Returns 7, 8, 9ownerclient7ABr1………ri-14ri7ri+19ri+211ABr1………ri-14ri7ri+19ri+2117, 8, 9serverProblem 2: DropSDSelect * from T where 5<A<11Returns 7ownerclient8ABr1………ri-14ri7ri+19ri+211ABr1………ri-14ri7ri+19ri+211server9ri+1Solution☺ The Model☺ Motivation☺ Problem☺ Ability to authenticate without trusting the servery g(Query Authentication)Query Authentication: (the dimensions)• Query Correctnessresults do exist in the owner's database ~ injection• Query Completenessno records ha ve been omitted from the result ~ droph★10• Query Freshness★results are based on the most current version of the database ( this will bring a third problem into the picture ) ~omissionGeneral ApproachABr1………Authenticated StructuresVerification Object (VO)SD11ownerserversclientsri-14ri7Query resultsBackground☺Cryptographic essentials11/24/200931: Collision‐resistant hash functions• It is computational hard to find x1and x2 s.t. h(x1)=h(x2)• Computational hard? Based on well established assumptions such as discrete logarithms SHA113•SHA1 • Observations:– variable input size 20 bytes – Computation cost: 2‐3 μs (for up to 500 bytes input)– Storage cost: 20 bytes– Under Crypto++ [crypto] and OpenSSL [openssl]2: Public key digital signature schemesSenderRecipientmInsecure Channel14RecipientKeyGen →(SK, PK)σVer(m, PK, σ) → valid?mσSKSign(m, SK) →σ2: Public Key Digital Signature Schemes• Formally defined by [GMR88] – The message has not been changed in any way– The message is indeed from the sender (corresponding to the public key)– No one except the secret key owner could produce a signature• One such scheme: RSA [RSA78]• Observations–Computation cost: about 3‐4 ms for signing and more than 100μsfor15–Computation cost: about 3‐4 ms for signing and more than 100 μsfor verifying– Storage cost: 128 bytes– Checking one aggregated signature is almost as fast as an individual signature3: Signature Aggregation (Condensed RSA)4: Merkle Hash Tree[M89]-Amortizing Signature Costh1..4h5..8h1..8σSign(h1..8,SK)h5..8h1..4h1..8Ver(h1..8, σ ,pK)=valid?σCollision resistant hash function any change in the tree will lead to a different hash value for the rootDigital signature of the root no one except the ownercould produce the signatureHash function is publicly knownSingle signature to sign many messages16m1m2m3m4m5m6m7m8h1h2h3h4h5h6h7h8h12h34h56h78h12=H(h1|h2)m6h78h5h6m5h56Correctness and Completeness• Correctness, Completeness:– Any change in the tree will lead to different hash– Relative position of values is authenticatedAth ti ti17•Authentication: – Signing the root with SKContributions☺ Proposed authenticated structures Getting to know B+ trees The idea of changingASB Tree (based onexisting work)ASB Tree (based on existing work) MB tree (based on existing work) EMB treeFreshness (third dimension of query Authentication)11/24/20094B+ ‐ Tree Structure• A typical node contains up to n –1 search key values K1, K2,…, Kn‐1, and n point ers P1, P2,…, Pn. The search key values are kept in sorted order.• The pointer Pi can point to either a file record or a 19bucket of pointers which each poin t to a file record.P1 K1 P2 … Pn-1 Kn-1 PnB+ ‐ Tree File OrganizationIn a B+ ‐ Tree file organization, the leaf nodes of the tree stores the actual record rather than storing pointers to records.20()iisig h r=Produced by the ownerSent to the clientcorrectness but NOTcompleteness !!!Range Authentication –A Simple Approach1r2r3r4r5r6r7r8r9r10r11r12r13r14r15r16rQ3sig4sig5sig6sigiiSent to the client along with 3456,,,rrrrSignature‐Based Approach: ASB Tree based on [PJR05]B+ Tree22S(r1|r2) S(r2|r3) … … S(n‐2|rn‐1) S(rn‐1|rn)1. order database tuples w.r.t query attribute2. sign consecutive pairs3. build B+ tree on top of it4. return tuples [a‐1, b+1] together with signatures in [a‐1, b]. (query is [a, b]) (a, b here are index)5. verify any two consecutive pairsCondensed RSA (NDSS’04)• Server:– Selects records matching posed query– Multiplies corresponding RSA signatures– Returns single signature to querierSQi23Given t record signatures:{σ1, σ2… σt} , compute combined signature σ1,t = Πσi mod n Send σ1,t to the querierServerσ1,tGiven t messages:{m1,m2… mt} and σ1,t verify combined signature:(σ1,t)e = ? = Π h(mi) (mod n)QuerierN is RSA modulus of the public key from the ownerComparing Cryptographic OP• one hashing takes 2‐3 μs– Modular Multiplication ‐100 times slower– Verifying ‐1000 times slowerSigning10000 times slower24–Signing ‐10000 times slowertHashing<tmod_M<tver<tSign11/24/20095Reduce S/C communication Cost • Aggregation Signature: Condensed RSA m1mkm1mk25σ1σkσσ=combine(σ1,…, σk) Overhead: computation cost of modular multiplication with big modular base number, close to 100 μs• A heavy burden on the owner to produce the signatures• Overhead on the client to verify the aggregated signatureSignature Chaining Issues• Storage overhead at the server to store the signatures (which potentially leads to higher computational cost to retrieve them)• High communication overhead on both the server and the owner, in order to exchange the signaturesMerkle B(MB) Tree: Natural Extension for Range Query•
View Full Document
Unlocking...