ZeroDB, an end-to-end encrypted database
blog.zerodb.io
blog.zerodb.io
I am curious how they intend to let a client run queries against a dataset that the server cannot read without the server having to send all the encrypted data over the wire, or at least an index of all the encrypted data. Which sounds limiting for large datasets.
In our case, the actual computations are done on the client
And a compromise client can still pull data by running query against the server right? So is the primary improvement that one cannot use database tools to easily export the full dataset? If I know correctly isn't database with encryption support also do dumps and other full db operations encrypted too?
Very valid concern. That is the bottleneck, and that was the first thing we've checked.
> Isn't a lot of normal db server side operation now a fetch-from-db + do-calculation-on-client type operation?
Not if you want to find something. Calculation-on-client is probably html rendering etc.
> And a compromise client can still pull data by running query against the server right?
Yes, but it's ok if you have millions of users, each with his own private data. It would probably cost too much to break into each client's computer (imagine a million bitcoin wallers with 0.1 bitcoin each).
Currently available databases, when used with encryption, store the key in memory. So, memory dump or mitm attack could help an attacker to collect the key.
I've been thinking a lot about this and the only way to handle the problem this tries to solve is to:
* treat the database as a collection of events
* let each event have a visibility that matches our concept of privacy (public | shared with X, Y & Z | private)
* have this communication encrypted using already existing OTR protocols (see some of Moxie Marlinspike's posts on it)
* make the database queryable on this aggregate of event data.
It's really just a case of finding the essential complexity and making it as simple, but not simpler, than that.
The annoying thing is that while it's a tough bullet to bite; it's not even that though. Something like Datomic could already get you halfway there.
We don't make such compromises (zero compromises, yes!). The way we do it is to actually traverse encrypted b-trees from the client, while b-trees are on the server. So, we pretty much split it between client and server at the lowest level of how db operates
The server actually knows which pieces of B-Trees you access. But no more than that.
Though, observing access patterns, it could probably deduce which data belong to the tree and some info about ordering (which will hold true until we re-balance the tree, which happens on inserts).
I think, if we change objects each time we do queries, we can prevent this data leak.
A client can batch multiple inserts but the server cannot batch inserts from multiple clients.
Since the system is fully immutable each update would also include the state of the system it is an update to (which can be outdated.)
Essentially you're modelling human communication with each event being equivalent to a human speech act.
For most cases that would offer sufficient conflict resolution and more expensive commit strategies could be used only where more needed; much like how lattice/CALM-based programming languages such as Bloom deal with distribution.
Yes immutable data makes the inserts O(1) but increases the query costs proportionally to the number of producers.
You need to traverse all possible systems states to do a complete lookup.
Encryption also makes server side pruning and garbage collection of old system state difficult unless you just clear everything greater than n days old.
1) As for the query costs; yes they are there. For public data you could still create pre-computed indexes but for privately shared data the recipients/accessors of that data would need to create appropriate indexes.
In general this scheme indeed requires each producer (person/identity) to also maintain their own indexes.
2) I don't get what you mean by doing a complete lookup.
3) Since this would be a fully federated/decentralized system there would not really be such a thing as server side pruning since the 'server' would just be a peer that indexes public data.
Given that data is immutable clients would simply hold on to the data they need for their calculations and could choose to depend on the server to keep a copy for them.
If nobody (wants to pay to) hold onto a copy of some data anymore then it has been garbage collected.
P.S. Have you looked at the Datomic model? It works quite similar to this proposal with regards to things like storage, peering, computing indexes etc.
I was recently reading a number of ORAM papers, considering to implement something as a side-project to play a bit with modern C++. The overhead is significant, but practical, i.e., far less than homomorphic encryption.
But I think proper joins can be implemented with this idea
I find some ideas in MIT mOPE paper similar though
EDIT: Also, you say the server does not know the tree structure. Do you mean it doesn't know the structure until you query, or the structure is always obfuscated (including access patterns and search patterns)?
EDIT2: What is the round complexity of a single query in your protocol?
What is the use case for something like this?
Is this f/oss ... similarly, what are the licensing terms?
Quick comment:
Please don't misuse the word "hack" when you actually mean "security breach". Thanks!
Yes, it will be open source once available
Thanks for the good work guys, best of luck with your project and (ad)venture.
Having the index end-to-end encrypted imposes some limitations though. You have to do several requests when you want to do one query which is obviously slower. Though, still practical.
And since the CPU logic happens on the client, in some cases (many simultaneous clients) the performance can be actually better.
What's the threat here?
SQL Injection? Encryption won't help. Use parameterized queries and least privilege.
Evil admin? They can just monitor the web server instead of the db.
Of course, this requires making sure that the code which the client executes is not malicious
still its more effort and more opportunistic (client needs to actually connect that day) so it is safer/reduces likelihood.
But a lot of work and issues for the security gain compared to db encryption and proper design (even thus, you know, its not a great trade off either!)
In the end I guess we need a truly client-initiated and controlled data handling. HTTP isnt exactly made for that. It tells the client how to handle and control the data, no choice is really made client-side.
That's exactly the use case. The idea is that the data isn't decrypted until the client.
This means that your 'evil admin' case is invalidated since the plaintext data is never available to the host.
Don't play with my heart, ZeroDB. Show us what you've got!
If you were to do that, HIPAA becomes MUCH easier for other healthcare IT startups using your db.
(i'm no encryption expert, just curious)
Having the key derived from your password is also possible, but I think not really that secure.
SpiderOak and Mega deal with this problem as they have e2e encrypted file storage