3 ms·

That doesn’t scale, if you need to delete records pertaining to a specific person and you have a user base of 10M yet alone 100M or 2B users you can’t encrypt e

That doesn’t scale, if you need to delete records pertaining to a specific person and you have a user base of 10M yet alone 100M or 2B users you can’t encrypt each of their records with an individual key.

bottled_poe 5y ago
I think the parent is suggesting discarding keys for all backups after X days. So, anything deleted in the live environment effectively gets removed from the backups after X days.
lucb1e 5y ago
Depends on how you back up. If you copy the raw database files that you also run queries on (e.g. take a zfs snapshot), then you'd need some very special encryption to be able to query across differently-encrypted data. But if your database is just on an encrypted disk but otherwise readable, and you only encrypt the records on an individual level when exporting them to the backup system... that can work. Generating a secure random encryption key after seeding can be as fast as a single AES function call, and symmetric encryption isn't particularly expensive either. Still extra work compared to just copying bytes between memory regions (now everything has to be operated on by the CPU), I'm not saying it's going to be trivial, but it doesn't seem infeasible. Also at 2B users as you mention, which is an extreme example considering we have only a few billion internet users (multiply by one or two bots for every person, but even then), you need huge storage and compute clusters anyway. Storing 16 bytes of key material extra isn't going to be the difference between feasible and infeasible. It doesn't really matter if you're talking 2e2 or 2e9 users in terms of computational or storage overhead.
benlivengood 5y ago
Large companies actually do keep individual master keys per user. Think of it this way, what's an extra 256 bits (32 bytes) stored for every user in a system when their name and email address probably exceeds 32 bytes already? Master keys encrypt the records of a user-key database where user keys are stored. User keys protect unique wrapped keys that are randomly generated at time of encryption (perhaps this is where your logistical argument arose) for individual pieces of data. This is commonly implemented as an encryption service that will encrypt/decrypt blobs of data for services on behalf of a particular user via RPC; the cryptographic keys are never present in normal service code or standard servers and only within the encryption service (which may be an HSA) so there's a much smaller domain to secure. Common ACLs protect calls to the encryption service per user, like they protect access to storage and other resources. Obviously for bulk data encryption this is less tenable so services handling bulk data (many GB) get extra protection and direct access to unwrapped user keys, but must be responsible for respecting privacy/security ACLs internally.
- jandrewrogers 5y ago
  This offers prohibitively poor performance in many cases, you are underestimating the cost. I have 10M inserts per second, collecting data on 100M users, on single EC2 instances. The cost of is not 32-bytes per user if you care about performance at all. In any system with performance as a criteria, you need to keep the entire key schedule in RAM, which is considerably larger than the 32-byte key. This is even more complicated because in systems that care about performance, data is often stored as compressed bit streams, not tidy cryptographic block sizes. Sure, you can make the storage structures convenient for fine-grained cryptography, if you are willing to sacrifice an order of magnitude performance. This also ignores that you have to garbage collect this storage -- it is not remotely as simple as deleting the crypto keys. These database platforms already exist and there is a reason almost no one uses them unless they absolutely have to -- performance extremely poor. As in, you can expect to pay 100x loss of performance versus a highly optimized database that doesn't use cryptography for deletion. Unless you are living in the 1990s, that kind of performance is completely unacceptable and is indefensibly wasteful of computing resources in practical environments. Using encryption to effect deletion in databases is an idea that only makes sense to people that do not know anything about database internals or, alternatively, are willing to expend extraordinary amounts of hardware resources to do ordinary things. That idea has been around for several decades and consistently rejected by people that know anything about database internals. Database kernels optimized for deletion is an interesting research area but also a known Hard Problem. If encryption actually addressed it, it would not have remained a Hard Problem for several decades.
  - tluyben2 5y ago
    You can split and encrypt your backups usually though. Not a full solution for deletion but good enough for most. Your case sounds rather unique: not many people will ever see that volume. Most b2b saas solutions won't be bothered by the performance hazards you mention but yes, it is a tradeoff.
  - viraptor 5y ago
    > I have 10M inserts per second That's a valid concern, but if you have this problem: 1. You're in a quite unique situation. 2. You likely have enough engineers to assign to solving this issue in another way. Encrypting the user data in backups scales to a reasonable extent, but every approach will have some limitations.

bottled_poe 5y ago

I think the parent is suggesting discarding keys for all backups after X days. So, anything deleted in the live environment effectively gets removed from the backups after X days.

lucb1e 5y ago

Depends on how you back up. If you copy the raw database files that you also run queries on (e.g. take a zfs snapshot), then you'd need some very special encryption to be able to query across differently-encrypted data. But if your database is just on an encrypted disk but otherwise readable, and you only encrypt the records on an individual level when exporting them to the backup system... that can work. Generating a secure random encryption key after seeding can be as fast as a single AES function call, and symmetric encryption isn't particularly expensive either. Still extra work compared to just copying bytes between memory regions (now everything has to be operated on by the CPU), I'm not saying it's going to be trivial, but it doesn't seem infeasible. Also at 2B users as you mention, which is an extreme example considering we have only a few billion internet users (multiply by one or two bots for every person, but even then), you need huge storage and compute clusters anyway. Storing 16 bytes of key material extra isn't going to be the difference between feasible and infeasible. It doesn't really matter if you're talking 2e2 or 2e9 users in terms of computational or storage overhead.

benlivengood 5y ago

Large companies actually do keep individual master keys per user. Think of it this way, what's an extra 256 bits (32 bytes) stored for every user in a system when their name and email address probably exceeds 32 bytes already? Master keys encrypt the records of a user-key database where user keys are stored. User keys protect unique wrapped keys that are randomly generated at time of encryption (perhaps this is where your logistical argument arose) for individual pieces of data. This is commonly implemented as an encryption service that will encrypt/decrypt blobs of data for services on behalf of a particular user via RPC; the cryptographic keys are never present in normal service code or standard servers and only within the encryption service (which may be an HSA) so there's a much smaller domain to secure. Common ACLs protect calls to the encryption service per user, like they protect access to storage and other resources. Obviously for bulk data encryption this is less tenable so services handling bulk data (many GB) get extra protection and direct access to unwrapped user keys, but must be responsible for respecting privacy/security ACLs internally.

jandrewrogers 5y ago
This offers prohibitively poor performance in many cases, you are underestimating the cost. I have 10M inserts per second, collecting data on 100M users, on single EC2 instances. The cost of is not 32-bytes per user if you care about performance at all. In any system with performance as a criteria, you need to keep the entire key schedule in RAM, which is considerably larger than the 32-byte key. This is even more complicated because in systems that care about performance, data is often stored as compressed bit streams, not tidy cryptographic block sizes. Sure, you can make the storage structures convenient for fine-grained cryptography, if you are willing to sacrifice an order of magnitude performance. This also ignores that you have to garbage collect this storage -- it is not remotely as simple as deleting the crypto keys. These database platforms already exist and there is a reason almost no one uses them unless they absolutely have to -- performance extremely poor. As in, you can expect to pay 100x loss of performance versus a highly optimized database that doesn't use cryptography for deletion. Unless you are living in the 1990s, that kind of performance is completely unacceptable and is indefensibly wasteful of computing resources in practical environments. Using encryption to effect deletion in databases is an idea that only makes sense to people that do not know anything about database internals or, alternatively, are willing to expend extraordinary amounts of hardware resources to do ordinary things. That idea has been around for several decades and consistently rejected by people that know anything about database internals. Database kernels optimized for deletion is an interesting research area but also a known Hard Problem. If encryption actually addressed it, it would not have remained a Hard Problem for several decades.
- tluyben2 5y ago
  You can split and encrypt your backups usually though. Not a full solution for deletion but good enough for most. Your case sounds rather unique: not many people will ever see that volume. Most b2b saas solutions won't be bothered by the performance hazards you mention but yes, it is a tradeoff.
- viraptor 5y ago
  > I have 10M inserts per second That's a valid concern, but if you have this problem: 1. You're in a quite unique situation. 2. You likely have enough engineers to assign to solving this issue in another way. Encrypting the user data in backups scales to a reasonable extent, but every approach will have some limitations.