If a column is encrypted using standard encryption (like AES-GCM) then the values are non-deterministic and fully randomized. That means that if you encrypt the same value twice, you'll get 2 different ciphertexts.
So the query:
select * where secret_col == 10
Would actualy be:
select * where secret_col == encrypt_aes(10);
And values in secret_col will never match (because the output of encrypt_aes will be different every time, even for the same input).
A common way around this is to use deterministic encryption which eliminates the randomization at the cost of a slightly weaker security model. What leaks is the ability to see if any 2 plaintexts are equal (because they have the same ciphertext) - what you actually want in the case of search.
You have to be careful implementing deterministic encryption though: don't use AES-GCM with a fixed nonce because the scheme completely breaks. You can use CBC mode but then you lose authenticity. We use AES-GCM-SIV (synthetic IV which retains authentication but is secure under a fixed nonce) and HMAC (keyed hashing).
But there are approaches to solving queries like:
-- range/order
SELECT * FROM foo WHERE x > 10;
SELECT * FROM foo ORDER BY x;
-- fuzzy text
SELECT * FROM foo WHERE name ~ "dan";
Thanks Dan, this is very interesting. From someone deeply involved in privacy I see the benefits of the auditability and risk mitigation in cases like SQL injection.
What does the risk profile look like in a full leak of the encrypted database?
If you had a column of integers are you able to order them without decrypting? Check that values are the same? Identify null values?
> What does the risk profile look like in a full leak of the encrypted database?
We actually have a number of different schemes which trade leakage for performance/storage overhead/compatibility. Each one has its own type in Postgres so you just create a column with whatever type you want.
The weakest (most leakage) is OPE - order preserving encryption. We use an encoding scheme that works like scientific notation so an attacker with a DB snapshot would learn relative order but not the size of the gaps between values. Its major benefit is compatibility - it works everywhere.
The strongest is Block ORE - Order Revealing Encryption. A DB snapshot reveals nothing more than standard randomized encryption (IND-CPA2 semantic security).
The tradeoff is that BlockORE values are much bigger: 32-bit integer goes to 384 bytes. On Postgres its still very fast and works with standard B-trees.
> If you had a column of integers are you able to order them without decrypting?
Yes. For either scheme, its just an EQL function:
SELECT * FROM foo ORDER by eql_v3.ord_term(x);
> Check that values are the same?
-- $1: encrypt(query)
SELECT * FROM foo WHERE eql_v3.eq_term(x) = eql_v3.eq_term($1);
> Identify null values?
NULL is just like any value for OPE/ORE - encrypt it and use that to query
-- $1: encrypt(NULL)
SELECT * FROM foo WHERE eql_v3.eq_term(x) = eql_v3.eq_term($1);
NULL values can be encrypted with either scheme. Very safe to do so with the ORE scheme (fully randomized values). If encrypting strings, NULLs would reveal length but you can always pad if not leaking value length is important to your security model.
In the OPE scheme, NULL would encrypt deterministically so if you expect a lot of NULLs in your data this could leak the distribution.
We are working on a capability now called Leakage Tuned Domains. The goal here is not to eliminate leakage but scope it to a specific data type (e.g. birthdays) such that any leakage cannot be an advantage to an attacker. Think k-anonymisation or differential-privacy on steroids.
Don’t use deterministic encryption unless your data is already highly random.
Any adversary who knows the distribution of the plaintext data can guess what your encrypted values are, with accuracy that improves as your sample size increases.
There were a bunch of papers on this 10-12 years ago. (Full disclosure: I was an author on some of them.)
Searchable encryption means you can have encryption and queries (from apps etc) still work for authorized users.
This is all started when I was the CTO of a health-tech and the engineers all had access to patient data. They needed DB access (data migrations, managing backups, reading non-sensitive fields) but not access to the sensitive values. 10m+ patient records - it made me nervous.
Row-level Security (RLS) was a nightmare, it was slow, easy to mess up and could be overridden by DBAs anyway. Plus the application connected to the DB using a service account so RLS was useless for end-user access control.
CipherStash solves the following:
* Hide sensitive data from direct database accessors (authorized or not!)
My original use-case. Direct access to the DB doesn't reveal sensitive data (unless the user also has permission to decrypt a specific record).
* Support or even replace application access controls
Decryption happens in the application layer and is based on end-user identity. That means a gap in application defenses is mitigated by the encryption. If the user can't decrypt the value then they can't access the data.
* Access auditing
Every sensitive data access is recorded (and by who) which is very useful for compliance and incident response. SQL query auditing is great for knowing what queries were run but it doesn't tell you what data was actually returned. Its also blind once data actually leaves the DB and can inadvertently leak sensitive data itself. Using key accesses with non-identifying value IDs to audit decryptions makes the auditing more reliable and super granular.
We have customers who use the tech to prove to their users (often large enterprise) that no internal staff can access the data.
* Agent access to data
The encryption shifts access control decisions down to the data layer on a per-value basis. This is incredibly useful for gating access to agents that need access to data. Every decryption requires authentication (e.g via Supabase Auth, Auth0 etc) and combining it with agent identities (creds issued to agents) means you can not only limit what agents can access, you can also audit exactly what _was_ accessed.
The searchable encryption is the enabler: value level encryption is what makes all of this possible. Searchable encryption means you can have encryption and queries (from apps etc) still work for authorized users.
Hope that helps! I'm so in the weeds I don't know if I explain things that well sometimes!
CipherStash - specifically the key service. There is a lot of data for sure but we only record an identifier for each value and (optionally) the user ID. It compresses well.
Explanation:
The identifier is actually for the key that encrypts the value (1 unique key per value).
1. When the value is encrypted for the first time, it gets an ID.
2. When its decrypted, the application requests the key for that ID from the key-server (key-server records that the data was accessed)*
3. When updating, the same data key is used so the ID is persistent*
* Technically the key server doesn't return a key, it generates partial key material that can be used to derive the data key in the app. It can do this at up to 10,000 keys per second.
* You can also tag each value with the table/column name and the row-id to link everything together
The 3 values form the "descriptor" of a value: `table/column/id`.
What does all this actually solve? Presumably SQL injection might still decrypt contents and order by/where clause enumeration would still be possible regardless. Keys must be stored in memory, on-disk or via a secret server meaning column encryption would not mitigate the impact of RCE/full shell compromise. Add in the cost of column level encryption when querying large volumes of data, this seems to be entirely angled at gold plated compliance security theatre rather than solving any actual problem.
Keys are not stored in the database or in the application.
Every data key is derived at query time via a 2-party system:
1. by the key server which manages root-key material (stored in an HSM or traditional KMS)
2. keys derived via a user credential at the time of the query
SQL Injection case:
An adversary signs up to your app, pulls of a SQLi and you might think that the app will just decrypt the values. It won't because the adversary's auth cred can't derive keys to decrypt anything but the data they are explicitly allowed to access.
RCE/shell compromise:
Because keys are derived on demand these kinds of attacks are largely inert. If the attacker could read memory from the running app on-demand then they could conceivably see credentials in flight but each key only ever decrypts one value so the blast radius is limited.
On the cost of decryption:
Queries typically only return a subset of the values in a table and, importantly, don't need to decrypt anything at all. Querying and decryption are independent.
If you DO need to decrypt a large volume of data, CipherStash can do it at 10,000 values per second.
Query performance is under 1ms for simple queries and no-more than 200-300ms for more complex queries.
No security tool is perfect, nor "gold plated" but this tech meaningfully reduces blast area of attacks, makes many attacks inert and gives you an incredibly reliable audit trail.
If the keys are derived on demand and you have remote shell, you can derive them. If they’re salted with the users password, then it becomes impossible to decrypt them without the user being present which is problematic also.
I’m not a cryptographer and I can see flaws in your proposed system, I imagine someone qualified could poke some pretty glorious holes in your snake oil.
No, to derive a key you need a client key (controlled by the app) and key-seeds for each value which can only be retrieved from the key server with a valid JWT. The JWT is time bound (15 mins).
Now, if an attacker could gain access to the client key AND a valid JWT then they would be able to decrypt until the JWT expired. Blast radius reduced but we don't stop the attack entirely. An attacker with that much advantage is pretty hard to stop dead. But note that 2 things are required for the adversary to do this - where as in most systems, getting a JWT or a decryption key alone would be enough.
If you're not a cryptographer, then I'd suggest you reserve judgement about what flaws you think might be in the system. We have cryptographers on our team, have connections with universities in the US and Australia and our work is based on published, peer-reviewed papers. E.g. Lewi-Wu 2016 and Syalim et al 2011 and 2021.
It sounds like someone has discovered a side-channel, made a project around it, and forget/did not know what side-channel originally means. And then someone at Supabase who does not know crypto, is a victim of their marketing.
One would hope that only users who can already decrypt the data can perform the queries. In that case, it would give much faster query performance without allowing inference attacks on the data.
If not, then a lot of the data could be easily reconstructed.
you're probably only allowed a subset of the query language to talk to an encrypted table. E.g. only range queries that target a sample size > 5% of rows, etc., with exceptions for searches that hit an exact index such as looking up by id.
If a column is encrypted using standard encryption (like AES-GCM) then the values are non-deterministic and fully randomized. That means that if you encrypt the same value twice, you'll get 2 different ciphertexts.
So the query: select * where secret_col == 10
Would actualy be: select * where secret_col == encrypt_aes(10);
And values in secret_col will never match (because the output of encrypt_aes will be different every time, even for the same input).
A common way around this is to use deterministic encryption which eliminates the randomization at the cost of a slightly weaker security model. What leaks is the ability to see if any 2 plaintexts are equal (because they have the same ciphertext) - what you actually want in the case of search.
You have to be careful implementing deterministic encryption though: don't use AES-GCM with a fixed nonce because the scheme completely breaks. You can use CBC mode but then you lose authenticity. We use AES-GCM-SIV (synthetic IV which retains authentication but is secure under a fixed nonce) and HMAC (keyed hashing).
But there are approaches to solving queries like: -- range/order SELECT * FROM foo WHERE x > 10; SELECT * FROM foo ORDER BY x; -- fuzzy text SELECT * FROM foo WHERE name ~ "dan";
These capabilities are all based on public research: For example, order/range uses: https://eprint.iacr.org/2016/612.pdf
Our docs are quite limited at the moment (fixing as quickly as we can!) but you can see the current list of supported queries here: https://cipherstash.com/docs/stack/cipherstash/encryption/qu...