4 ms·

> protect against someone with access to the OS or hypervisor. > I haven't heard that they were successful. Isn't it rather trivial to prove that a database c

> protect against someone with access to the OS or hypervisor. > I haven't heard that they were successful. Isn't it rather trivial to prove that a database can't be secure if the OS or hypervisor is compromised? (I mean, how could it be, since the OS/hypervisor can read/write all memory, pause execution, alter execution, etc. by its very nature?)

swordswinger12 9y ago
The original goal of the academic "encrypted database" proposals like CryptDB was security against this kind of adversary. The idea was that if all the data is encrypted even when you're querying it, you get some security against a compromised OS. Unfortunately, in this paper we showed even this "always encrypted" approach has many subtle flaws that leave the data vulnerable to inference attacks.
- Ar-Curunir 9y ago
  It's much better than what is out there in industry, however: plaintext data. Usually the attacker when you upload data to the cloud isn't the cloud provider, but outside intruders. I feel it's not constructive to claim that solutions that provide intermediate security are useless; schemes that provide strong security (eg. ORAM based schemes) are far from practicality, and so these intermediate security solutions are the best we've got.
  - swordswinger12 9y ago
    To be clear: nowhere in this paper did we claim any particular solution is useless. However, the degree to which these systems are useful, and what situations they are useful for, is not well-understood. Prior work has shown that the encryption used in many of these systems is breakable (i.e. the plaintext is recoverable with near-perfect accuracy) with simple attacks. See, for example, this recent paper (https://eprint.iacr.org/2016/895 https://eprint.iacr.org/2016/895) on cryptanalysis of order-revealing encryption. Respectfully, I find this "more secure stuff is slow so we have to live with what we've got" argument to be specious. There simply is no evidence that a fast encrypted database must also provide very weak confidentiality guarantees.
    - Ar-Curunir 9y ago
      The evidence lies in the failure of the cryptographic community to provide a solution with strong security properties that is performant. For example, nobody has even attempted an ORAM-based database system. We also do not have schemes that can efficiently provide an intermediate level of security, between "weak" and "strong" systems. Either way, as I said earlier, it's a question of threat models. Most cloud users trust Google and Amazon. These companies also have strong intrusion detection capabilities, so with non-negligible probability an outside attacker would be detected within a reasonable amount of time. In such a scenario, it is better to have some protection than none at all.
      - swordswinger12 9y ago
        The failures of the academic cryptography community to provide solutions to real-world problems in general are well-documented, and I will not belabor them here (q.v. Rogaway's "The Moral Character of Cryptographic Work"). I will only say that I don't think this problem (strong security + performance) has been on the minds of very many people for very long, and this work is really still in its infancy.
falcolas 9y ago
Better (any) in-memory encryption would help (especially against swap or hibernation attacks), but won't completely mitigate the risk due to the encryption key being stored in memory as well.
rdmsr 9y ago
Not without CPU support. Intel SGX, AMD SEV (sort of), and ARM trustzone (if you want to do a lot of work) make this possible.
- swordswinger12 9y ago
  It's worth pointing out that trusted execution for individual queries does not, in general, rule out the attacks discussed in this paper. If the database collects (for example) frequency information about queries, inference attacks can still be used to recover plaintext. EDIT: The fundamental problem is that trusted hardware doesn't hide the access pattern by itself. Trusted hardware can be used to hide some kinds of access patterns, but it's highly nontrivial and has only been demonstrated in some limited settings. For example, there was a paper at NSDI this year called "Opaque" which showed how to use SGX to hide access patterns for some kinds of Spark queries.
  - deleted 9y ago
    [deleted]
  - deleted 9y ago
    [deleted]
  - rdmsr 9y ago
    I should really read that paper, since I'm sort of confused by the threat model. Arbitrary queries seem like they would defeat the point. So I'm assuming this "using a secure, authenticated channel to communicate out, while still being monitored by the OS" model. That's a high bar for software not designed for SGX. I presume it's relying on the paging behavior of SGX? (Either page faults or dirty bits).

swordswinger12 9y ago

The original goal of the academic "encrypted database" proposals like CryptDB was security against this kind of adversary. The idea was that if all the data is encrypted even when you're querying it, you get some security against a compromised OS. Unfortunately, in this paper we showed even this "always encrypted" approach has many subtle flaws that leave the data vulnerable to inference attacks.

Ar-Curunir 9y ago
It's much better than what is out there in industry, however: plaintext data. Usually the attacker when you upload data to the cloud isn't the cloud provider, but outside intruders. I feel it's not constructive to claim that solutions that provide intermediate security are useless; schemes that provide strong security (eg. ORAM based schemes) are far from practicality, and so these intermediate security solutions are the best we've got.
- swordswinger12 9y ago
  To be clear: nowhere in this paper did we claim any particular solution is useless. However, the degree to which these systems are useful, and what situations they are useful for, is not well-understood. Prior work has shown that the encryption used in many of these systems is breakable (i.e. the plaintext is recoverable with near-perfect accuracy) with simple attacks. See, for example, this recent paper (https://eprint.iacr.org/2016/895 https://eprint.iacr.org/2016/895) on cryptanalysis of order-revealing encryption. Respectfully, I find this "more secure stuff is slow so we have to live with what we've got" argument to be specious. There simply is no evidence that a fast encrypted database must also provide very weak confidentiality guarantees.
  - Ar-Curunir 9y ago
    The evidence lies in the failure of the cryptographic community to provide a solution with strong security properties that is performant. For example, nobody has even attempted an ORAM-based database system. We also do not have schemes that can efficiently provide an intermediate level of security, between "weak" and "strong" systems. Either way, as I said earlier, it's a question of threat models. Most cloud users trust Google and Amazon. These companies also have strong intrusion detection capabilities, so with non-negligible probability an outside attacker would be detected within a reasonable amount of time. In such a scenario, it is better to have some protection than none at all.
    - swordswinger12 9y ago
      The failures of the academic cryptography community to provide solutions to real-world problems in general are well-documented, and I will not belabor them here (q.v. Rogaway's "The Moral Character of Cryptographic Work"). I will only say that I don't think this problem (strong security + performance) has been on the minds of very many people for very long, and this work is really still in its infancy.

falcolas 9y ago

Better (any) in-memory encryption would help (especially against swap or hibernation attacks), but won't completely mitigate the risk due to the encryption key being stored in memory as well.

rdmsr 9y ago

Not without CPU support. Intel SGX, AMD SEV (sort of), and ARM trustzone (if you want to do a lot of work) make this possible.

swordswinger12 9y ago
It's worth pointing out that trusted execution for individual queries does not, in general, rule out the attacks discussed in this paper. If the database collects (for example) frequency information about queries, inference attacks can still be used to recover plaintext. EDIT: The fundamental problem is that trusted hardware doesn't hide the access pattern by itself. Trusted hardware can be used to hide some kinds of access patterns, but it's highly nontrivial and has only been demonstrated in some limited settings. For example, there was a paper at NSDI this year called "Opaque" which showed how to use SGX to hide access patterns for some kinds of Spark queries.
- deleted 9y ago
  [deleted]
- deleted 9y ago
  [deleted]
- rdmsr 9y ago
  I should really read that paper, since I'm sort of confused by the threat model. Arbitrary queries seem like they would defeat the point. So I'm assuming this "using a secure, authenticated channel to communicate out, while still being monitored by the OS" model. That's a high bar for software not designed for SGX. I presume it's relying on the paging behavior of SGX? (Either page faults or dirty bits).