6 ms·

One-time-pads effectively save you here. The application knows zipcode 1234 == "AWER", but the database doesn't and there isn't any way to derive that without o

One-time-pads effectively save you here. The application knows zipcode 1234 == "AWER", but the database doesn't and there isn't any way to derive that without outside information. The technique is a pseudo-anonymization technique, not encryption.

kbolino 2y ago
Assuming you want "find all users in zipcode 12345" to be a supported query, it does not matter what encryption scheme you use, you will have one of these two problems: On the one hand, you can require that 12345 always maps to AWERQ, in which case an attacker can use frequency analysis, metadata chaining, etc. to determine with some confidence that AWERQ = 12345. Calling this "pseudo-anonymization" is definitely more accurate than calling it "encryption", but you might as well just use a one-way hash function instead. It doesn't do anything against determined attackers with prolonged or broad exposure to the data; I don't see the value except perhaps for compliance with poorly thought out or outdated regulations. On the other hand, you can require that 12345 always maps to a different string every time, but that means you need a different key/salt/IV/nonce for every row or cell, defeating indexing and aggregation, and so all queries become full table scans. This significantly frustrates an attacker, but also significantly frustrates legitimate operations.
- withinboredom 2y ago
  With something like zip codes, so long as all the data is encrypted, there's very little chance someone can work out what that zipcode is (and if there isn't any information in the column name, even less). The only way someone could determine that it is a zipcode is by looking at commonality with known decrypted data. Even if they were to determine that it was a zipcode, they would only know which zipcode it was for the users they had decrypted. In other words, the blast radius is very small and compartmentalized, while still allowing searches.
  - kbolino 2y ago
    If an attacker has a full data dump, they probably have a recent/frequent queries dump too. Column name obfuscation won't go very far. Zipcodes are short. If not given extra padding, their ciphertexts will still be short. Zipcodes are also low cardinality. Unless you use multiple salts/nonces/IVs/keys, the frequency of ciphertexts will match the frequency of plaintexts. In many situations, a prepared attacker will be able to insert their own data beforehand, allowing them to perform a chosen-plaintext attack and potentially decipher much of the data. The best protection against this is to not reuse salts/nonces/IVs/keys and thus again defeat performant searches. None of this is to necessarily say it's not worth it but rather to keep in mind the article's point: know your threat model.

kbolino 2y ago

Assuming you want "find all users in zipcode 12345" to be a supported query, it does not matter what encryption scheme you use, you will have one of these two problems: On the one hand, you can require that 12345 always maps to AWERQ, in which case an attacker can use frequency analysis, metadata chaining, etc. to determine with some confidence that AWERQ = 12345. Calling this "pseudo-anonymization" is definitely more accurate than calling it "encryption", but you might as well just use a one-way hash function instead. It doesn't do anything against determined attackers with prolonged or broad exposure to the data; I don't see the value except perhaps for compliance with poorly thought out or outdated regulations. On the other hand, you can require that 12345 always maps to a different string every time, but that means you need a different key/salt/IV/nonce for every row or cell, defeating indexing and aggregation, and so all queries become full table scans. This significantly frustrates an attacker, but also significantly frustrates legitimate operations.

withinboredom 2y ago
With something like zip codes, so long as all the data is encrypted, there's very little chance someone can work out what that zipcode is (and if there isn't any information in the column name, even less). The only way someone could determine that it is a zipcode is by looking at commonality with known decrypted data. Even if they were to determine that it was a zipcode, they would only know which zipcode it was for the users they had decrypted. In other words, the blast radius is very small and compartmentalized, while still allowing searches.
- kbolino 2y ago
  If an attacker has a full data dump, they probably have a recent/frequent queries dump too. Column name obfuscation won't go very far. Zipcodes are short. If not given extra padding, their ciphertexts will still be short. Zipcodes are also low cardinality. Unless you use multiple salts/nonces/IVs/keys, the frequency of ciphertexts will match the frequency of plaintexts. In many situations, a prepared attacker will be able to insert their own data beforehand, allowing them to perform a chosen-plaintext attack and potentially decipher much of the data. The best protection against this is to not reuse salts/nonces/IVs/keys and thus again defeat performant searches. None of this is to necessarily say it's not worth it but rather to keep in mind the article's point: know your threat model.