Let's build an end-to-end encrypted data store | Hacker News Reader

Let's build an end-to-end encrypted data store

bulwark.id

75 pointscmdli19 comments

This is interesting. I designed a similar system a few years ago, although the company ran out of runway. We made many of the same design choices.

A few small observations:

1) GCM encryption is limited to 64GB under the same key/IV. Files bigger than that may need splitting up.

2) GCM is broken if you reuse an IV with the same key. So be very careful here.

3) I don't see anything about how synchronisation works. When multiple clients can read or update a central store, clients really need to know which is the latest. We used vector clocks for this to get event ordering. Some care is needed to preserve privacy and integrity and performance when adding in additional metadata.

As a key:value store this makes sense.

However modern data stores need to do more than just store values with known keys. The most popular stores support some sort of query system that implies the database itself can make sense of the data. However when the data is encrypted this is no longer possible as the data store cannot make any sense if the stored information.

I’d love to see something that could support queries on encrypted data without comprising privacy. I just don’t know how that would be possible.

If you know what you are indexing by, you can use a bloom filter. However, this gives an attacker information they otherwise wouldn’t have. It’s trade offs, as usual.

How can you do range queries with a bloom filter?

Ie show me all records created between two specific dates

Hash the dates you are looking for and do a binary OR. It becomes unreasonable to search beyond n-dates, so arbitrary searches are probably out of the question. It also depends on how you are storing the filter (I’m thinking of a scheme I worked on for work in GDPR anonymization which suffers the same sort of problems)

Sure you can do a binary OR but you need to examine all of the data in the table which effectively becomes a full table scan. The beauty of indices is that you only need to scan a subset of the data to find the information you're looking for.

You can store columns for each bit in the filter, so a binary OR wasn’t a full table scan, just an index lookup for certain columns.

> something that could support queries on encrypted data

Assuming you're talking about client-specified queries (database-specified are impossible by definition of "encrypted"), the keyword you want is "fully homomorphic encryption". AFAIK, there aren't any fully working systems yet, although they're pretty close and should be available Real Soon Now.

The main restriction is that for any given query you have a response of a fixed (and known-to-the-attacker) size, so you can't do open-ended queries like "all records between 2021-01-01 and 2021-12-31". Instead you'd get something like a fixed-size mapreduce/foldMap interface, and queries would look something like "total number of records (modulo UINT_MAX+1) matching predicate x and first N such records according to ordering y", where N, sizeof x, and sizeof y - but not x and y themselves - are known by the database/attacker.

This is not necessarily true. It depends on your security model. You can use a bloom filter on each row. When the client does the encryption it encodes properties about the encrypted value into a bloom filter. The filter’s construction can be scrambled according to the user (salted) using regular means (xor). An attacker would need to unsalt the filter and know how to query the filter in order to derive any useful information. Arbitrary querying of all users data is computationally impossible. The client can even do the salting and pass the salt to the server to support server-side querying, thus allowing a user to consent to a server to know information it otherwise wouldn’t know.

There are things like cryptdb:

https://m-cacm.acm.org/magazines/2012/9/154574-cryptdb-proce...

Update: It's been a while since I've looked into encrypted databases. They do a reasonable job, but they are limited in various ways. Private Information Retrieval is also interesting.

https://en.m.wikipedia.org/wiki/Private_information_retrieva...

I spent a long time trying to build a privacy-preserving database. The challenge is that a persistent attacker (a honest, but curious server hosting your data) can defeat the encryption by observing the access pattern. This happens because issuing the same query twice will access the same encrypted data, and the same amount of encrypted data. Naively one would think that this is of no use, and such patterns can be trivially obfuscated, but any statistical correlation can be fatal, and ensuing that they do not occur is costly.

If you would download the entire database for each query that would be private, but also have a linear communication overhead. You could rewrite data to a new location after you read it, which is what ORAM does, and it has at least a logarithmic communication overhead. This is where the buck stops, logarithmic is a theoretical minimum cost even for the weakest computational access pattern privacy guarantees. With differential privacy guarantees a double logarithmic overhead is possible, but it is not clear when such guarantees are useful. Fully homomorphic encryption would only allow to push the overhead from communication to computation.

On the practical side there are symmetric searchable encryption schemes with forward and backward privacy. They are reasonably functional, with reasonable leakage, without any guarantees. They tend to be vulnerable to sophisticated adversaries with knowledge about the queries or the documents. These schemes often have to deal with more than just access pattern privacy, because they not all passive (where the server is only a storage device, the client selects the documents to access). They have to worry about the search tokens presented to the server, which is now running code. Some of these schemes have to deal with a malicious server breaking protocol.

Really glad to see experiments in this direction. I was working on something similar writing https://github.com/xeoncross/typecrypt a couple years ago if someone wants to see a basic wrapper around https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypt...

What if you could create an iterable blob storage (prefix searches, range searches, date searches, etc..) and use that as the backbone for a social network/inbox system? It was a work in progress, I never finished it, but would like pick it back up when I have time.

In the same space is the key-value store underlying Got: GotKV. https://github.com/gotvc/got/tree/master/pkg/gotkv

It stores encrypted blobs in any content-addressed store, and provides a copy-on-write key-value store API.

Love the idea of encrypting and owning my own data. But here's my question. My encrypted data needs to be unencrypted and read by third parties eventually. What's to stop those third parties from just copying and saving my data, then selling it later to a data broker, who then goes out and resells it on an open or black market?

Can someone clarify use cases for these encrypted services? Otherwise, it seems a lot like when RIAA tried to stop users from distributing MP3s. Once the cat is outta the bag, can't really put it back in. Zeroes and ones are trivial to copy.

I think this maybe a use-case for "Homomorphic" encryption.

https://en.wikipedia.org/wiki/Homomorphic_encryption

Nice! Hadn't heard of this before. It seems like this is the type of encryption that would be used when a third party needs to verify your data, but you wouldn't want to share it unencrypted.

Perhaps you can limit the exposure by only providing aggregated data to trusted third parties.

I don't understand the question. 1) Why does my data have to be unencrypted by third parties eventually? Most of my data is for me. 2) When I actively decide to give people data, why do we propose they are so untrustworthy as to sell it to a data broker? I am very confident none of my friends are actively selling the data I give them to anyone. 3) Even if one of them did, they would only have access to the data they were given, not all of my data I have ever given to everyone else.

2) this assumes there aren't any third parties on your friend's machine. You're trusting not only your friend, but likely Apple/Microsoft, Chrome/Firefox, and any browser extensions they might be running, which would definitely become more aggressive and pervasive if this scheme became common practice.

Reply on news.ycombinator.com