4 ms·

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

75 points by cmdli 4y ago

bognition 4y ago
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.
- withinboredom 4y ago
  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.
  - bognition 4y ago
    How can you do range queries with a bloom filter? Ie show me all records created between two specific dates
    - withinboredom 4y ago
      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)
      - deleted 4y ago
        [deleted]
      - bognition 4y ago
        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.
        withinboredom 4y ago
        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.
    - deleted 4y ago
      [deleted]
- a1369209993 4y ago
  > 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.
  - withinboredom 4y ago
    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.
- MattPalmer1086 4y ago
  There are things like cryptdb: https://m-cacm.acm.org/magazines/2012/9/154574-cryptdb-processing-queries-on-an-encrypted-database/fulltext 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_retrieval https://en.m.wikipedia.org/wiki/Private_information_retrieva...
- Comevius 4y ago
  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.
brendoncarroll 4y ago
In the same space is the key-value store underlying Got: GotKV. https://github.com/gotvc/got/tree/master/pkg/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.
Xeoncross 4y ago
Really glad to see experiments in this direction. I was working on something similar writing https://github.com/xeoncross/typecrypt 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/SubtleCrypto 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.
charlie0 4y ago
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.
- jmprspret 4y ago
  I think this maybe a use-case for "Homomorphic" encryption. https://en.wikipedia.org/wiki/Homomorphic_encryption https://en.wikipedia.org/wiki/Homomorphic_encryption
  - charlie0 4y ago
    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.
- CameronNemo 4y ago
  Perhaps you can limit the exposure by only providing aggregated data to trusted third parties.
- saurik 4y ago
  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.
  - karpierz 4y ago
MattPalmer1086 4y ago
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.

75 points by cmdli 4y ago

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.

withinboredom 4y ago
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.
- bognition 4y ago
  How can you do range queries with a bloom filter? Ie show me all records created between two specific dates
  - withinboredom 4y ago
    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)
    - deleted 4y ago
      [deleted]
    - bognition 4y ago
      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.
      - withinboredom 4y ago
        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.
  - deleted 4y ago
    [deleted]
a1369209993 4y ago
> 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.
- withinboredom 4y ago
  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.
MattPalmer1086 4y ago
There are things like cryptdb: https://m-cacm.acm.org/magazines/2012/9/154574-cryptdb-processing-queries-on-an-encrypted-database/fulltext 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_retrieval https://en.m.wikipedia.org/wiki/Private_information_retrieva...
Comevius 4y ago
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.

brendoncarroll 4y ago

In the same space is the key-value store underlying Got: GotKV. https://github.com/gotvc/got/tree/master/pkg/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.

Xeoncross 4y ago

Really glad to see experiments in this direction. I was working on something similar writing https://github.com/xeoncross/typecrypt 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/SubtleCrypto 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.

charlie0 4y ago

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.

jmprspret 4y ago
I think this maybe a use-case for "Homomorphic" encryption. https://en.wikipedia.org/wiki/Homomorphic_encryption https://en.wikipedia.org/wiki/Homomorphic_encryption
- charlie0 4y ago
  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.
CameronNemo 4y ago
Perhaps you can limit the exposure by only providing aggregated data to trusted third parties.
saurik 4y ago
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.
- karpierz 4y ago

MattPalmer1086 4y ago

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.