4 ms·

Back up encrypted data and discard keys selectively to delete data from the archive

by paulsutter 5y ago

bottled_poe 5y ago
This is an excellent solution. I don’t see why it couldn’t be the industry standard.
- Silhouette 5y ago
  It's a solution that looks clever at first sight but the devil is in the details. Sometimes it's difficult to determine what data is subject to erasure in the first place, for example if there are multiple parties involved or the obligation to erase conflicts with other obligations that might require retention of some of the personal data. If you're going with the encryption and key management strategy, your design must accommodate all possible scenarios both now and in the future including those where the rules change between now and then. For anything but the simplest cases that seems unlikely.
  - bottled_poe 5y ago
    Seems easy to me. 30 days, delete backup keys. What’s the problem? You still have 29 day old backups?
    - Silhouette 5y ago
      Maybe we're talking about slightly different things here. The suggestion to use individual keys to encrypt personal data is usually made so that deleting a key has effectively and immediately destroyed all copies of the data including any historical ones. That way you're definitely fully compliant with any right to be forgotten requests with one simple act. Even if you do have some older backups or archives kept around or the backup data isn't truly irretrievable from the physical media where it was stored after being marked for deletion, that data instantly becomes random noise without the key (which you obviously don't store and backup in the same way in this kind of scheme). In other words, it's not really about whether keeping backups for a few days or a few weeks before they are "deleted" would be considered acceptable by regulators, it's about making all such questions irrelevant while otherwise being able to continue with business as usual. It would be a clever and useful solution to the regulatory compliance problem in this area, if it worked in practice.
- jandrewrogers 5y ago
  It doesn't work in real systems because it is extremely costly to the point of being infeasible. This has been known for decades and rejected because it doesn't actually work. If a technical solution is "obvious" and no one is using it, it tends to imply that it has serious flaws that are obvious to domain experts. Using encryption for deletion is known to be deeply flawed for unavoidable technical reasons. These databases actually exist. Almost no one uses them because the performance is exceptionally poor to the point of being nearly unusable for practical things.
  - bottled_poe 5y ago
    I disagree. Why doesn’t time-bounded deletion of backup keys work?
dogma1138 5y ago
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.
contravariant 5y ago
This might be appropriate for some cases, but is dangerously similar to just not making backups in the first place.
SnowHill9902 5y ago
If I use a 16 bit key does it count as deleted data?
- lucb1e 5y ago
  Roughly equivalent to hashing a small-ish number like a phone numbers, so based on [1] I'd say yes! Marketing can now say with a straight face that through this technical operation, basically sprinkling some magic pixie dust over your data, it is now incomprehensible and no longer leads back to you. [1] 7:05 - 7:58 https://projectbullrun.org/surveillance/2015/video-2015.html#bernstein https://projectbullrun.org/surveillance/2015/video-2015.html... (2015)
twhitmore 5y ago
It just moves the problem, to how do you delete the keys & manage backups of the keys. You have to backup the keys, since a system outage would otherwise leave you unable to function. My shot from the hip: encryption/keying is irrelevant except for highly sensitive data (credit cards, crypto wallets). Plain deletion from production databases should be sufficient, backups should be "at arms length" but otherwise should not need to be treated specially. Another shot from the hip: System outage & RPO loss of a requested deletion is an act of God and no worse (indeed probably less important) than losing the other business transactions in that time period. I don't see special handling being needed for deletion.

Back up encrypted data and discard keys selectively to delete data from the archive

bottled_poe 5y ago

This is an excellent solution. I don’t see why it couldn’t be the industry standard.

Silhouette 5y ago
It's a solution that looks clever at first sight but the devil is in the details. Sometimes it's difficult to determine what data is subject to erasure in the first place, for example if there are multiple parties involved or the obligation to erase conflicts with other obligations that might require retention of some of the personal data. If you're going with the encryption and key management strategy, your design must accommodate all possible scenarios both now and in the future including those where the rules change between now and then. For anything but the simplest cases that seems unlikely.
- bottled_poe 5y ago
  Seems easy to me. 30 days, delete backup keys. What’s the problem? You still have 29 day old backups?
  - Silhouette 5y ago
    Maybe we're talking about slightly different things here. The suggestion to use individual keys to encrypt personal data is usually made so that deleting a key has effectively and immediately destroyed all copies of the data including any historical ones. That way you're definitely fully compliant with any right to be forgotten requests with one simple act. Even if you do have some older backups or archives kept around or the backup data isn't truly irretrievable from the physical media where it was stored after being marked for deletion, that data instantly becomes random noise without the key (which you obviously don't store and backup in the same way in this kind of scheme). In other words, it's not really about whether keeping backups for a few days or a few weeks before they are "deleted" would be considered acceptable by regulators, it's about making all such questions irrelevant while otherwise being able to continue with business as usual. It would be a clever and useful solution to the regulatory compliance problem in this area, if it worked in practice.
jandrewrogers 5y ago
It doesn't work in real systems because it is extremely costly to the point of being infeasible. This has been known for decades and rejected because it doesn't actually work. If a technical solution is "obvious" and no one is using it, it tends to imply that it has serious flaws that are obvious to domain experts. Using encryption for deletion is known to be deeply flawed for unavoidable technical reasons. These databases actually exist. Almost no one uses them because the performance is exceptionally poor to the point of being nearly unusable for practical things.
- bottled_poe 5y ago
  I disagree. Why doesn’t time-bounded deletion of backup keys work?

dogma1138 5y ago

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.

contravariant 5y ago

This might be appropriate for some cases, but is dangerously similar to just not making backups in the first place.

SnowHill9902 5y ago

If I use a 16 bit key does it count as deleted data?

lucb1e 5y ago
Roughly equivalent to hashing a small-ish number like a phone numbers, so based on [1] I'd say yes! Marketing can now say with a straight face that through this technical operation, basically sprinkling some magic pixie dust over your data, it is now incomprehensible and no longer leads back to you. [1] 7:05 - 7:58 https://projectbullrun.org/surveillance/2015/video-2015.html#bernstein https://projectbullrun.org/surveillance/2015/video-2015.html... (2015)

twhitmore 5y ago

It just moves the problem, to how do you delete the keys & manage backups of the keys. You have to backup the keys, since a system outage would otherwise leave you unable to function. My shot from the hip: encryption/keying is irrelevant except for highly sensitive data (credit cards, crypto wallets). Plain deletion from production databases should be sufficient, backups should be "at arms length" but otherwise should not need to be treated specially. Another shot from the hip: System outage & RPO loss of a requested deletion is an act of God and no worse (indeed probably less important) than losing the other business transactions in that time period. I don't see special handling being needed for deletion.