A shoutout for attic https://attic-backup.org/ Attic is one of the new-generation hash-backup tools (like obnam, zbackup, Vembu Hive etc). It provides encrypted incremental-forever (unlike duplicity, duplicati, rsnapshot, rdiff-backup, Ahsay etc) with no server-side processing and a convenient CLI interface, and it does let you prune old backups. All other common tools seem to fail on one of the following points - In…
Sorry, but "Untrusted remote storage" and "No server-side processing" are exactly the opposite of what I need. If the original box is ever compromised, I don't want the attacker to gain any access to the backup. If you use a dumb storage like S3 as your backup server, you need to store your keys on the original box, and anyone who gains control of the original box can destroy your S3 bucket as well. Ditto for any SSH…
But in the modern commercial market, who are you going to trust as your backup box provider? A USA company subject to NSLs? Run your own in a rack somewhere? Having an untrusted server greatly decreases cost and increases the chance that you can actually produce a successful backup infrastructure at all.
It is possible to do it safely.
Since you say you're "willing to live with a significant amount of overhead", i would suggest a two-tier push/pull configuration. Desktop pushes to site A; then site B pulls from site A. This also increases redundancy and spreads out the attack surface.
Append-only is another good solution - i don't believe attic formally supports this today but it should be as simple as patching `attic serve` to ignore delete requests. Good first patch.
(Also if you really trust your backup server, then you don't need encryption anyway and can just run rdiff-backup over ssh.)