[RFC] Updatable Encryption / Master-Key Migration

[cyphar]

At the moment restic doesn't have a way of changing the master key of a restic repository. Each individual subkey is just an encrypted copy of the masterkey. This means that if one of the keys/... is compromised (not just the passphrase but the keyfile too), there is no way to recover in the post-compromise state. You could re-create the backups manually into a new restic repository -- but that would be quite time consuming, and you're no better off if your key gets compromised again.

The naive solution to this problem would be to just have a restic change-master-key command that will generate a new repository key, and then decrypt each old object with the old key and create a new object (in a new repository presumably) with the new key. However, this scheme would require you to create your new key on a new system and then download all of your data and then re-upload all the blobs again -- on your "trusted system". While this might not be a problem in Europe or America, in Australia we have horrific upload speeds. An upload of 50GB can take up to 1 week (and this maxes out your internet connection). Ideally I would like to be able to spin up a VPS that has a much better internet connection than me, and then do the re-encryption that way. However, this would require me to give access to my master key to a third-party server (which isn't good).

One possible (though still theoretically new) solution to this problem is to use "upgradable encryption". Unfortunately this would require changing the on-disk encryption format, which I understand would be quite worrying for most users of restic. There was a recent paper about RISE that explains in better theoretical details how "upgradable encryption" works. The general idea is that you can provide an untrusted third-party a "token" which they can use to re-encrypt all ciphertexts created with the old key to use your new key (and this token doesn't give them any way to get information about the plaintext).

If there is no interest in using "upgradable encryption" (which is understandable), then I still believe that restic should provide some sort of tool for handling post-compromise (like restic change-master-key or restic migrate master-key or something like that).

[cyphar]

This is tangentially related to #187, as asymmetric backups would require changing the encryption schema as well.

[fd0]

Thanks for taking the time to suggest this feature. I don't see that we have the resources to think about something so advanced as upgradable encryption (at least not short- or medium-term), the use case for that is IMHO limited and there's so much other work to do.

For your other feature request (changing the master keys for the repo): Can you please describe the attacker model?

[cyphar]

I don't see that we have the resources to think about something so advanced as upgradable encryption ... the use case for that is IMHO limited and there's so much other work to do.

Sure that's fair enough -- the computer science is also quite new as well, so probably best to wait until it matures anyway. 😸

For your other feature request (changing the master keys for the repo): Can you please describe the attacker model?

Sure. Imagine that an attacker has gained full access to your backups, and has also managed to break the passphrase protecting one of the keys for the repo. Naturally, all of your historical data is now exposed to the attacker, and there isn't much you can do about it. However, let's say you've come to terms with the data breach and you want to continue using restic with your existing repository -- but of course you want to remove the attackers' ability to decrypt your backups with the old key. (This attack scenario also applies if the attacker got a copy of a really old version of your repository.)

At this point, the attacker has a copy of the master-key for the entire repository, so removing the particular passphrase-protected "subkey" they used to get the master key doesn't add any protection (they can still decrypt the blobs themselves or create a new subkey because they have the master). You could just create a new restic repository, but now you've lost the ability to access any old snapshots you may have.

So, at this point, having a way for a user to completely re-encrypt all of the blobs by generating a new master key would be really useful. Another nice thing about this is that it could be used to upgrade the keysize (or encryption scheme if more are added in the future) if the user becomes concerned. Users could also do regular re-encryption of their repositories (though this would be pretty insane) to provide a kind of "perfect forward secrecy" for their backups as new snapshots would only ever have been available using newer keys.

[fd0]

Thanks for the detailed description of the use case.

This could be achieved with a copy command discussed in #323.

[cyphar]

The core logic would be the same as with copy, but you might want to be able to do it in-place as well (which would just involve doing the copy and then deleting everything that doesn't belong to the new repository).

[matthijskooijman]

Also see #320, which requested a similar thing before. I just added a comment there (before finding this issue), essentially making the same points as @cyphar.

One additional thought is that the current key management allows using a per-machine key/password. This suggests that, when a machine is compromised, you can just remove its key and your backups are secure again, which is not currently the case. I think think means that the key management feature only serves to allow multiple users of one repo to use their own password (e.g. it protects their passwords from each other), it does not protect the data form each other. This might be more of a documentation issue, I guess.

[MichaelEischer]

Just for the record: Everything except the in-place reencryption is possible in restic 0.10.0 by using restic init --copy-chunker-params --repo2 old-repo -r new-repo and restic copy -r old-repo --repo2 new-repo.