This is an amazing promise, but I was sad this is just a beta signup. I would really love to play around with something like this, and would also like to know how it works.
Don't play with my heart, ZeroDB. Show us what you've got!
This could be a really BIG deal for healthcare if you do it well. I would love to have a completely encrypted db that I could setup dynamic failover and replication. Also an amazing additional feature would be if it contained built-in access logging.
If you were to do that, HIPAA becomes MUCH easier for other healthcare IT startups using your db.
Hi Michael, if you go opensource way, I would be happy to integrate this into my apache licensed project (see my desc). That would give you head start on Java and Java Collections.
This feels like a hollow announcement, given that there's no code or design details to look at.
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.
More than the size of the data read (which I'm not sure how big would actually be) I'm more concerned about the latency. Isn't a lot of normal db server side operation now a fetch-from-db + do-calculation-on-client type operation?
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.
We JUST launched and started working on this but we do want to get code to you all as fast as possible. We'll post a progress update on our blog each week and share it here to keep everyone in the loop.
You've probably seen CryptDB from MIT. They make it possible to do certain types of queries (range etc) by making security compromises (giving some clues to hack encryption).
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
Well, actually the server doesn't know the ordering and how pieces of B-Tree refer to each other, it doesn't even know which data form the index and which are the actual data.
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.
No; each data producer (customer/person/identity) has their own serialized (as in ordered) queue of events.
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.
I'm not at all arguing there's a free lunch here. It's a tough cookie to crack and requires a reimagining of half of computing. I also think it's the only possible way to go.
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.
Look up private information retrieval (PIR) and oblivious RAM (ORAM). EDIT: This particular bit from the announcement "but we're pushing query logic and decryption keys client-side" seems to point to ORAM.
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.
Seems to be similar to ORAM, that's right. And practical enough to be implemented: fulltext search query to aws takes about 0.5 s (not slowing down when multiple clients do these queries in parallel)
Right at the moment, we don't. The prototype is a proof-of-principle. And the first version will probably have index on pre-computed properties used instead of joins.
But I think proper joins can be implemented with this idea
Not sure how they do it, but it has been done before as a research project http://css.csail.mit.edu/cryptdb/. One of the tricks it uses(though by no means the only) is to do a binary search in an index, it actually has the client decrypt a node and compare and then give the server the result.
Re-read their paper about mOPE. Very similar indeed. The difference is that in our case the server doesn't know the tree structure, with cryptdb it does.
Well, actually we don't use determenistic encryption, and the server knows nothing about ordering. It merely stores the trees and returns requested pieces (w/o knowing which piece is that or is it a piece of a tree at all).
I find some ideas in MIT mOPE paper similar though
I didn't ask whether you use deterministic encryption, I asked whether your variant of mOPE is deterministic. It's possible to use randomized encryption for the leaves of mOPE and still construct a deterministic OPF.
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?
I realize that your post was titled "Hello World" so I wouldn't expect too much substance, but a couple quick questions (honest ones, not being sarcastic):
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!
The use-cases could be, for example, payment processors storing customer data, encrypted webmail (where you're able to search w/o downloading all your emails), "encrypted evernote" :-)
Oh, sounds good. So even though you can't get at the data on the server, you are able verify that it is unchanged with correct timestamps, etc. Sounds smart, useful. I presume then that you can support searching on the client side by downloading an encrypted index or something like that?
Thanks for the good work guys, best of luck with your project and (ad)venture.
That's for full text search? This sounds really cool! Excuse the not-very-sophisticated question because I'm not really familiar with the data structures a database typically uses, how do your index sizes compare to a typical sql database or similar indexed similarly for the same sort of queries?
Index sizes are pretty similar (consider the same).
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.
Some technical detail would be much appreciated, like the language you are using on the server side, any dependencies? Road map for when you are open sourcing it (I assume you will do)...
1. Good, all DB data needs to be encrypted
2. That said, the largest security risk is applications (backends) that enable mass access to customer data and allow mass leaks of customer data.
Database encryption doesn't make a whole lot of sense to me. Proper row and column security, and using real database user authentication (not one single, pooled web server user) is real security. A db on its own box, in its own network zone, physically controller by the data owner.
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.
Appications should be architected so that security-critical logic happens on the client. See how Mega and SpiderOak do that. This way, the attacker has to hack every computer of every client instead of one single server.
Of course, this requires making sure that the code which the client executes is not malicious
yeah there are no perfect trade offs:
if you control the application server then you just instruct clients to decrypt/give away their data/encryption key
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.
I can see this being useful for the example you gave, Mega. Currently, the list of files you upload are all downloaded to the client in order to do a search. If the search could happen on the server but the file list remains encrypted, that would make the website less costly for the client.
I think this project could be used to secure against evil admins. Especially if you make CouchDB-style apps (communicate directly with the DB from the browser or desktop/mobile app)
I think the idea is that the data is never decrypted until it returns to the client. i.e. it's encrypted client side while being indexable server side.
This means that your 'evil admin' case is invalidated since the plaintext data is never available to the host.
72 comments
[ 3.1 ms ] story [ 93.5 ms ] threadDon'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 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.
http://en.wikipedia.org/wiki/Homomorphic_encryption
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.
(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
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.