8 ms·

Building Searchable Encrypted Databases with PHP and SQL

59 points by CiPHPerCoder 9y ago

cdevs 9y ago
I know this is a I'm going quest and for that reason it annoys me when i see my companies competitors say they encrypt all their users searchable data and I know what they are really doing is using Amazon disk level encryption that's not really helpful if your live database gets dumped.
piotrkaminski 9y ago
Why not just use AES-SIV instead of separate encrypted and HMAC fields?
- CiPHPerCoder 9y ago
  The practical reason: https://3v4l.org/LEar1 https://3v4l.org/LEar1 (No SIV in that list.) It's also not present in libsodium or (shudder) mcrypt. What property are you hoping to extract out of AES-SIV in particular? (And would AEZ, HS1-SIV, AES-SIV-GCM, etc. solve your problem?) From what I understand, SIV mode still uses a nonce, but it doesn't explode if you reuse it for different messages. Are you aiming for nonce-less encryption? The end goal that was being worked towards in the article (Argon2-derived Bloom filters for partial searching) is a little more useful than nonce-less encryption.
  - piotrkaminski 9y ago
    I was specifically after a deterministic encryption scheme that would allow for exact-match comparisons and whose deployment was fairly foolproof (so a non-expert couldn't screw it up too badly), which AES-SIV appears to provide nicely. Another benefit in my case is that I'm using a NoSQL database where separating the encrypted value from its indexed value is not always practical, so having a single value that serves both purposes is highly desirable. I'm not familiar with the other schemes you mentioned, but the practical reason for using AES-SIV is the converse of yours for not using it: there's an implementation for JavaScript. :) It's unlikely there are implementations for the other schemes you listed. I agree that the Bloom filters are a nice natural outcome of your approach, though it would also be possible to combine AES-SIV for primary encryption with a truncated HMAC for partial match Bloom filters.
    - CiPHPerCoder 9y ago
      Here's the killer feature of my approach: Each filter has its own HMAC/Argon2 key, so it becomes less useful for what I like to call crossword puzzle attacks. (I hope that's easier to understand than a wordy explanation of how such an attack would work.)
pg_bot 9y ago
I disagree with the dishonorable mention as you've only considered the naive case which you can build upon to avoid the issues mentioned. Consider a design where everything is AES-256 encrypted in the application and the database just receives an encrypted binary. You can build an in-memory cache for situations where you need to search sensitive information (first name, last name, ssn) by using a tokenizer and using a technology like Erlang term storage. It will be eventually consistent which should be fine for our use case since that type of information does not change that often and the cache recompute can be done asynchronously. From a security standpoint you don't change the threat model for the application. If someone gets unauthorized access to the server you are already screwed since your application can get access to the plain text data in order to serve requests. If you threw away that computation for every request I would agree that it is wasteful but we don't need to do that if we rethink the role of the database in our application.
- CiPHPerCoder 9y ago
  > I disagree with the dishonorable mention as you've only considered the naive case which you can build upon to avoid the issues mentioned. Consider a design where everything is AES-256 encrypted in the application and the database just receives an encrypted binary. You can build an in-memory cache for situations where you need to search sensitive information (first name, last name, ssn) by using a tokenizer and using a technology like Erlang term storage. It will be eventually consistent which should be fine for our use case since that type of information does not change that often and the cache recompute can be done asynchronously. https://tonyarcieri.com/all-the-crypto-code-youve-ever-written-is-probably-broken https://tonyarcieri.com/all-the-crypto-code-youve-ever-writt... https://blog.filippo.io/the-ecb-penguin/ https://blog.filippo.io/the-ecb-penguin/ There are defensible positions for which ECB mode is acceptable. I wouldn't classify the scenario you described as one of them. > If someone gets unauthorized access to the server you are already screwed since your application can get access to the plain text data in order to serve requests. If someone gets unauthorized access to the webserver, yes, it's game over. If someone gets unauthorized access to the database server, and it's a separate machine from the webserver, then your analysis here isn't applicable. That's the threat model alluded to in the beginning of the article, but if it's not your threat model, then you may reach different conclusions about the best way to protect data. (You may not even use encryption, for example.)
johnbro 9y ago
If I understand this correctly, you basically store HMAC or password hash as a separate field and index on it? That may work for SSNs (which are unique), but it won't work for other things you commonly need to encrypt, such as personally identifiable data (in healthcare scenarios). If you (for example) encrypt first names of people (or any other data point that is not unique per entry) using this scheme, then HMAC will reveal all the rows that have the same first name. You can then use frequency analysis to determine with high probablity what the encrypted names are.
- CiPHPerCoder 9y ago
  > If you (for example) encrypt first names of people (or any other data point that is not unique per entry) using this scheme, then HMAC will reveal all the rows that have the same first name. You can then use frequency analysis to determine with high probablity what the encrypted names are. This is where things get difficult to explain, because most health care programs are going to care about compliance first and foremost. So with that in mind: 1. You probably don't need to encrypt their first name to be e.g. HIPAA compliant, but... 2. Using a very short Bloom filter increases the odds of false positive collisions. Combine this with Argon2 and aggressive rate limiting, and now you've frustrated frequency analysis and chosen plaintext attacks greatly. Given the threat model that we've given (database is not the same machine as the webserver, and the database server is what gets compromised), I can't see a better solution.
- danieltillett 9y ago
  This would depend on how large the database was. If the names in the database were non-representative of the general population then frequency analysis is not going to help much.
big_spammer 9y ago
How is this different than CryptDB? https://css.csail.mit.edu/cryptdb/ https://css.csail.mit.edu/cryptdb/
- CiPHPerCoder 9y ago
  From what /r/crypto says, they leak metadata to the database server. https://www.reddit.com/r/crypto/comments/6e5jjz/building_searchable_encrypted_databases_with_php/di8n26v/?context=2 https://www.reddit.com/r/crypto/comments/6e5jjz/building_sea...
deleted 9y ago
[deleted]
tyingq 9y ago
Can someone explain why it's not simple to brute force the hash in the blind index? Since SSNs only have 9 digits, that's a billion possibilities. Is this just a hash that's too slow to iterate over the billion? Is each row salted differently? Edit: I'm asking because I don't know, not because I'm saying it's possible. Edit2: Also, it appears there was a pattern to SSN issuance prior to 2011, so the problem space may be far short of a billion. No numbers start with 00 for example. Also, there's a listing of numbers not ever issued[1], and a table of "highest assigned"[2]. Since SSN's issued after 2011 are children now, they can be safely skipped, as they aren't as interesting for fraud. Also, if the State of residence is cleartext, you can search that space first if you assume a large number of people live in their birth state. [1]https://www.ssa.gov/employer/stateweb.htm https://www.ssa.gov/employer/stateweb.htm [2]https://www.ssa.gov/employer/ssnvhighgroup.htm https://www.ssa.gov/employer/ssnvhighgroup.htm
- CiPHPerCoder 9y ago
  > Can someone explain why it's not simple to brute force the hash in the blind index? You're not bruteforcing H(m) here. You're trying to bruteforce H(m, k) without knowing k. To make matters worse, k is a random string of 128+ bits, generated by a CSPRNG.
  - tyingq 9y ago
    Hrm. Ok. This is assuming I've compromised the database client side, right? Doesn't the client have to know 'k' to do the query? k is $indexKey, right? Edit: Thanks, got it now. A database dump on it's own gives nothing useful. The client side is vulnerable, but has to be since it's ultimately serving up plaintext SSNs anyway.
    - CiPHPerCoder 9y ago
      This is assuming that: - The webserver and database server are on separate bare-metal - The database gets compromised, not the webserver
ge96 9y ago
yay PHP/SQL (stack I work with, well MySQL)
deleted 9y ago
[deleted]
Quiark 9y ago
I agree that the HMAC approach is better but a proper deterministic encryption would work just fine, wouldn't it? You're comparing your method with ECB mode which is a bit unfair.
- CiPHPerCoder 9y ago
  What are some constructions you'd consider "fair"?
  - Quiark 9y ago
    AEAD cipher with nonce generated from plaintext? That would have equivalent security properties except for being needlessly complicated?
    - CiPHPerCoder 9y ago
      So you mean something like this? $nonce = sodium_crypto_generichash($message, '', 24); $ciphertext = $nonce . sodium_crypto_aead_xchacha20poly1305_ietf_encrypt( $message, $nonce, $nonce, $key ); That solves the literal search problem, but none of the others. However, in my experience[1], when it comes to deterministic encryption, most PHP developers will use ECB mode, or CBC mode with a NULL IV. [1]: https://meta.stackoverflow.com/q/293930/2224584 https://meta.stackoverflow.com/q/293930/2224584
kakoni 9y ago
Here's a (naive) ruby implementation. https://gist.github.com/kakoni/399e5324611db9f89806172124549aa7 https://gist.github.com/kakoni/399e5324611db9f89806172124549...

59 points by CiPHPerCoder 9y ago

I know this is a I'm going quest and for that reason it annoys me when i see my companies competitors say they encrypt all their users searchable data and I know what they are really doing is using Amazon disk level encryption that's not really helpful if your live database gets dumped.

piotrkaminski 9y ago

Why not just use AES-SIV instead of separate encrypted and HMAC fields?

CiPHPerCoder 9y ago
The practical reason: https://3v4l.org/LEar1 https://3v4l.org/LEar1 (No SIV in that list.) It's also not present in libsodium or (shudder) mcrypt. What property are you hoping to extract out of AES-SIV in particular? (And would AEZ, HS1-SIV, AES-SIV-GCM, etc. solve your problem?) From what I understand, SIV mode still uses a nonce, but it doesn't explode if you reuse it for different messages. Are you aiming for nonce-less encryption? The end goal that was being worked towards in the article (Argon2-derived Bloom filters for partial searching) is a little more useful than nonce-less encryption.
- piotrkaminski 9y ago
  I was specifically after a deterministic encryption scheme that would allow for exact-match comparisons and whose deployment was fairly foolproof (so a non-expert couldn't screw it up too badly), which AES-SIV appears to provide nicely. Another benefit in my case is that I'm using a NoSQL database where separating the encrypted value from its indexed value is not always practical, so having a single value that serves both purposes is highly desirable. I'm not familiar with the other schemes you mentioned, but the practical reason for using AES-SIV is the converse of yours for not using it: there's an implementation for JavaScript. :) It's unlikely there are implementations for the other schemes you listed. I agree that the Bloom filters are a nice natural outcome of your approach, though it would also be possible to combine AES-SIV for primary encryption with a truncated HMAC for partial match Bloom filters.
  - CiPHPerCoder 9y ago
    Here's the killer feature of my approach: Each filter has its own HMAC/Argon2 key, so it becomes less useful for what I like to call crossword puzzle attacks. (I hope that's easier to understand than a wordy explanation of how such an attack would work.)

pg_bot 9y ago

I disagree with the dishonorable mention as you've only considered the naive case which you can build upon to avoid the issues mentioned. Consider a design where everything is AES-256 encrypted in the application and the database just receives an encrypted binary. You can build an in-memory cache for situations where you need to search sensitive information (first name, last name, ssn) by using a tokenizer and using a technology like Erlang term storage. It will be eventually consistent which should be fine for our use case since that type of information does not change that often and the cache recompute can be done asynchronously. From a security standpoint you don't change the threat model for the application. If someone gets unauthorized access to the server you are already screwed since your application can get access to the plain text data in order to serve requests. If you threw away that computation for every request I would agree that it is wasteful but we don't need to do that if we rethink the role of the database in our application.

CiPHPerCoder 9y ago
> I disagree with the dishonorable mention as you've only considered the naive case which you can build upon to avoid the issues mentioned. Consider a design where everything is AES-256 encrypted in the application and the database just receives an encrypted binary. You can build an in-memory cache for situations where you need to search sensitive information (first name, last name, ssn) by using a tokenizer and using a technology like Erlang term storage. It will be eventually consistent which should be fine for our use case since that type of information does not change that often and the cache recompute can be done asynchronously. https://tonyarcieri.com/all-the-crypto-code-youve-ever-written-is-probably-broken https://tonyarcieri.com/all-the-crypto-code-youve-ever-writt... https://blog.filippo.io/the-ecb-penguin/ https://blog.filippo.io/the-ecb-penguin/ There are defensible positions for which ECB mode is acceptable. I wouldn't classify the scenario you described as one of them. > If someone gets unauthorized access to the server you are already screwed since your application can get access to the plain text data in order to serve requests. If someone gets unauthorized access to the webserver, yes, it's game over. If someone gets unauthorized access to the database server, and it's a separate machine from the webserver, then your analysis here isn't applicable. That's the threat model alluded to in the beginning of the article, but if it's not your threat model, then you may reach different conclusions about the best way to protect data. (You may not even use encryption, for example.)

johnbro 9y ago

If I understand this correctly, you basically store HMAC or password hash as a separate field and index on it? That may work for SSNs (which are unique), but it won't work for other things you commonly need to encrypt, such as personally identifiable data (in healthcare scenarios). If you (for example) encrypt first names of people (or any other data point that is not unique per entry) using this scheme, then HMAC will reveal all the rows that have the same first name. You can then use frequency analysis to determine with high probablity what the encrypted names are.

CiPHPerCoder 9y ago
> If you (for example) encrypt first names of people (or any other data point that is not unique per entry) using this scheme, then HMAC will reveal all the rows that have the same first name. You can then use frequency analysis to determine with high probablity what the encrypted names are. This is where things get difficult to explain, because most health care programs are going to care about compliance first and foremost. So with that in mind: 1. You probably don't need to encrypt their first name to be e.g. HIPAA compliant, but... 2. Using a very short Bloom filter increases the odds of false positive collisions. Combine this with Argon2 and aggressive rate limiting, and now you've frustrated frequency analysis and chosen plaintext attacks greatly. Given the threat model that we've given (database is not the same machine as the webserver, and the database server is what gets compromised), I can't see a better solution.
danieltillett 9y ago
This would depend on how large the database was. If the names in the database were non-representative of the general population then frequency analysis is not going to help much.

big_spammer 9y ago

How is this different than CryptDB? https://css.csail.mit.edu/cryptdb/ https://css.csail.mit.edu/cryptdb/

CiPHPerCoder 9y ago
From what /r/crypto says, they leak metadata to the database server. https://www.reddit.com/r/crypto/comments/6e5jjz/building_searchable_encrypted_databases_with_php/di8n26v/?context=2 https://www.reddit.com/r/crypto/comments/6e5jjz/building_sea...

deleted 9y ago

[deleted]

tyingq 9y ago

Can someone explain why it's not simple to brute force the hash in the blind index? Since SSNs only have 9 digits, that's a billion possibilities. Is this just a hash that's too slow to iterate over the billion? Is each row salted differently? Edit: I'm asking because I don't know, not because I'm saying it's possible. Edit2: Also, it appears there was a pattern to SSN issuance prior to 2011, so the problem space may be far short of a billion. No numbers start with 00 for example. Also, there's a listing of numbers not ever issued[1], and a table of "highest assigned"[2]. Since SSN's issued after 2011 are children now, they can be safely skipped, as they aren't as interesting for fraud. Also, if the State of residence is cleartext, you can search that space first if you assume a large number of people live in their birth state. [1]https://www.ssa.gov/employer/stateweb.htm https://www.ssa.gov/employer/stateweb.htm [2]https://www.ssa.gov/employer/ssnvhighgroup.htm https://www.ssa.gov/employer/ssnvhighgroup.htm

CiPHPerCoder 9y ago
> Can someone explain why it's not simple to brute force the hash in the blind index? You're not bruteforcing H(m) here. You're trying to bruteforce H(m, k) without knowing k. To make matters worse, k is a random string of 128+ bits, generated by a CSPRNG.
- tyingq 9y ago
  Hrm. Ok. This is assuming I've compromised the database client side, right? Doesn't the client have to know 'k' to do the query? k is $indexKey, right? Edit: Thanks, got it now. A database dump on it's own gives nothing useful. The client side is vulnerable, but has to be since it's ultimately serving up plaintext SSNs anyway.
  - CiPHPerCoder 9y ago
    This is assuming that: - The webserver and database server are on separate bare-metal - The database gets compromised, not the webserver

ge96 9y ago

yay PHP/SQL (stack I work with, well MySQL)

deleted 9y ago

[deleted]

Quiark 9y ago

I agree that the HMAC approach is better but a proper deterministic encryption would work just fine, wouldn't it? You're comparing your method with ECB mode which is a bit unfair.

CiPHPerCoder 9y ago
What are some constructions you'd consider "fair"?
- Quiark 9y ago
  AEAD cipher with nonce generated from plaintext? That would have equivalent security properties except for being needlessly complicated?
  - CiPHPerCoder 9y ago
    So you mean something like this? $nonce = sodium_crypto_generichash($message, '', 24); $ciphertext = $nonce . sodium_crypto_aead_xchacha20poly1305_ietf_encrypt( $message, $nonce, $nonce, $key ); That solves the literal search problem, but none of the others. However, in my experience[1], when it comes to deterministic encryption, most PHP developers will use ECB mode, or CBC mode with a NULL IV. [1]: https://meta.stackoverflow.com/q/293930/2224584 https://meta.stackoverflow.com/q/293930/2224584

kakoni 9y ago

Here's a (naive) ruby implementation. https://gist.github.com/kakoni/399e5324611db9f89806172124549aa7 https://gist.github.com/kakoni/399e5324611db9f89806172124549...