5 ms·

Interesting concept. I disagree with this statement from the "Data confidentiality" section: > Unlike CipherBase [6], our approach doesn’t leak information abo

Interesting concept. I disagree with this statement from the "Data confidentiality" section: > Unlike CipherBase [6], our approach doesn’t leak information about the order of the elements. By observing access patterns, the server can only figure out which buckets are leaf nodes and which are branch nodes, but not whether the child node is located to the left or right of the parent node. The paper correctly notes that when a client does a range query, it leaks information about the total number of blocks returned. However, if I've understood correctly, it also leaks the identities of those blocks. The closer two tree nodes are in order, the more likely they are to be touched by the same request. A passive adversary could use this to extract information about the relative ordering of encrypted nodes. Also, active adversaries cause much worse problems. Let's say I have the ability to cause someone to do queries on the encrypted database, without observing the results. By simply doing separate index lookups on two different fields, I can extract a lot of information by looking at which nodes were touched by both queries. Finally, I noticed that the paper doesn't describe how the B-trees are modified. If the client is the only party that knows how to decrypt nodes, then it's responsible for splitting and merging nodes to keep the tree balanced. Doesn't this require some kind of distributed coordination, so that multiple clients don't trample on each other's changes?

michwill 11y ago
You are right about the identifiers. And that is exactly what makes us concerned about access patterns attacks. They are not as dangerous when queries are rare. But we do explore possibilities to mitigate this attack vector completely using oblivious RAMs which become more and more performance. You are also right about clients updating the b-trees. Currently we use object-level locks to keep data consistent. We may add storing deltas for buckets to keep them on the server when a conflict appears plus use additively homomorphic encryption for counters (BTree.Length object).
michwill 11y ago
Also you cannot do queries on the encrypted db without being able to observe the results. E.g. if you are able to initiate a query on a fraction of the data, you already have access to that fraction of the data. And you cannot initiate a meaningful query if you are a server-side observer. Of course, active adversaries could give wrong results (wrong pieces of the index) back, we didn't quite consider yet which problems that could cause.
- roymurdock 11y ago
  Is there a reason that you did not cite Enigma in your list of notable works? They solve the adversary problem by splitting tasks among a network of nodes that post their intermediate work to a blockchain where it can be verified for accuracy: Very recently, Baum et al. developed a publicly auditable secure MPC system that ensures correctness, even when all computing nodes are covertly malicious, or all but a single node are actively malicious [18]. Their state-of-the-art results are based on a variation of SPDZ (pronounced speedz) [19] and depend on a public append-only bulletin board, which stores the trail of each computation. This allows any auditing party to check the output is correct by comparing it to the public ledger’s trail of proofs. Our system uses the blockchain as the bulletin board, thus our overall security is reduced to that of the hosting blockchain. I'm not a db or crypto expert, but this seems like a promising solution to the active adversary problem if you have an honest, healthy blockchain that is incentivized correctly.
  - michwill 11y ago
    Yeah, actually that is true. Enigma worths mentioning as one of MPC references. Looks like Enigma would have challenges in many practical environments (mainly because it involves a lot of small interactions between nodes, so should be affected by latency). So, it's more like a way to build "Etherium of private computations". But, as you pointed out, it can have good clues how to solve the problem of active adversaries!
- teraflop 11y ago
  > And you cannot initiate a meaningful query if you are a server-side observer. But that's only true if you consider the database in isolation. It's a very bad assumption to make when using it as a component of a larger system! Let's say you build a social networking service which uses ZeroDB to store its data; I'm an attacker who has access to the database server. There are all kinds of ways I can gain indirect control over the requests that users make to the service. What if I convince two different users to open a web page containing something like "<img src='https://supersecuresocialnetwork.com/friend-list.jsp'>" https://supersecuresocialnetwork.com/friend-list.jsp'>"? I've just triggered an operation that will cause the app servers to request tree nodes corresponding to those users' accounts, and those of their friends, at predictable times. I can correlate the requests and determine with some level of confidence whether the users are mutual friends, all without being able to see a single byte of plaintext. If the service is publicly available and I can register my own accounts, that opens up another huge category of attacks. My point is that you're making an awful lot of assumptions about what strategy an attacker will use. If you don't have provable security against an entire class of attacks (e.g. cryptographic properties like IND-CPA) then the burden is on you to be more imaginative than whoever is trying to compromise your system.
geoelectric 11y ago
Worth noting one of the previous posts, https://news.ycombinator.com/item?id=9262846 https://news.ycombinator.com/item?id=9262846 I raised some questions there related to your last concerns. I'm really interested to go through the current state and see how things have evolved to mitigate them.
swordswinger12 11y ago
Another thing from that same section that worried me was their discussion of inference attacks on first and last names. Their results assume names will be queried based on a particular distribution instead of an arbitrary (maybe even adversarially-chosen) one. This is a very, very weak model of security that categorically eliminates realistic attacks.
- michwill 11y ago
  The thing is that anybody who is able to initiate queries has access to that data. No need to do inference attacks over there :-) So, an adversary cannot query data based on particular distribution b/c it cannot initiate meaningful queries. If an active server-side adversary can trick the client into doing certain queries is another question though.
  - swordswinger12 11y ago
    You're not understanding my problem. You modeled security against a certain attack by picking one particular distribution of queries and saying "we resist this attack this much with this query distribution". An attacker doesn't need to choose the query distribution for your result to not apply, it just needs to be any other possible distribution than the one you chose.

michwill 11y ago

You are right about the identifiers. And that is exactly what makes us concerned about access patterns attacks. They are not as dangerous when queries are rare. But we do explore possibilities to mitigate this attack vector completely using oblivious RAMs which become more and more performance. You are also right about clients updating the b-trees. Currently we use object-level locks to keep data consistent. We may add storing deltas for buckets to keep them on the server when a conflict appears plus use additively homomorphic encryption for counters (BTree.Length object).

michwill 11y ago

Also you cannot do queries on the encrypted db without being able to observe the results. E.g. if you are able to initiate a query on a fraction of the data, you already have access to that fraction of the data. And you cannot initiate a meaningful query if you are a server-side observer. Of course, active adversaries could give wrong results (wrong pieces of the index) back, we didn't quite consider yet which problems that could cause.

roymurdock 11y ago
Is there a reason that you did not cite Enigma in your list of notable works? They solve the adversary problem by splitting tasks among a network of nodes that post their intermediate work to a blockchain where it can be verified for accuracy: Very recently, Baum et al. developed a publicly auditable secure MPC system that ensures correctness, even when all computing nodes are covertly malicious, or all but a single node are actively malicious [18]. Their state-of-the-art results are based on a variation of SPDZ (pronounced speedz) [19] and depend on a public append-only bulletin board, which stores the trail of each computation. This allows any auditing party to check the output is correct by comparing it to the public ledger’s trail of proofs. Our system uses the blockchain as the bulletin board, thus our overall security is reduced to that of the hosting blockchain. I'm not a db or crypto expert, but this seems like a promising solution to the active adversary problem if you have an honest, healthy blockchain that is incentivized correctly.
- michwill 11y ago
  Yeah, actually that is true. Enigma worths mentioning as one of MPC references. Looks like Enigma would have challenges in many practical environments (mainly because it involves a lot of small interactions between nodes, so should be affected by latency). So, it's more like a way to build "Etherium of private computations". But, as you pointed out, it can have good clues how to solve the problem of active adversaries!
teraflop 11y ago
> And you cannot initiate a meaningful query if you are a server-side observer. But that's only true if you consider the database in isolation. It's a very bad assumption to make when using it as a component of a larger system! Let's say you build a social networking service which uses ZeroDB to store its data; I'm an attacker who has access to the database server. There are all kinds of ways I can gain indirect control over the requests that users make to the service. What if I convince two different users to open a web page containing something like "<img src='https://supersecuresocialnetwork.com/friend-list.jsp'>" https://supersecuresocialnetwork.com/friend-list.jsp'>"? I've just triggered an operation that will cause the app servers to request tree nodes corresponding to those users' accounts, and those of their friends, at predictable times. I can correlate the requests and determine with some level of confidence whether the users are mutual friends, all without being able to see a single byte of plaintext. If the service is publicly available and I can register my own accounts, that opens up another huge category of attacks. My point is that you're making an awful lot of assumptions about what strategy an attacker will use. If you don't have provable security against an entire class of attacks (e.g. cryptographic properties like IND-CPA) then the burden is on you to be more imaginative than whoever is trying to compromise your system.

geoelectric 11y ago

Worth noting one of the previous posts, https://news.ycombinator.com/item?id=9262846 https://news.ycombinator.com/item?id=9262846 I raised some questions there related to your last concerns. I'm really interested to go through the current state and see how things have evolved to mitigate them.

swordswinger12 11y ago

Another thing from that same section that worried me was their discussion of inference attacks on first and last names. Their results assume names will be queried based on a particular distribution instead of an arbitrary (maybe even adversarially-chosen) one. This is a very, very weak model of security that categorically eliminates realistic attacks.

michwill 11y ago
The thing is that anybody who is able to initiate queries has access to that data. No need to do inference attacks over there :-) So, an adversary cannot query data based on particular distribution b/c it cannot initiate meaningful queries. If an active server-side adversary can trick the client into doing certain queries is another question though.
- swordswinger12 11y ago
  You're not understanding my problem. You modeled security against a certain attack by picking one particular distribution of queries and saying "we resist this attack this much with this query distribution". An attacker doesn't need to choose the query distribution for your result to not apply, it just needs to be any other possible distribution than the one you chose.