# Proper encryption algorithm to use when encrypting data before backing it up to untrusted hosts?

I'm writing a (non production/proof of concept) backup program that takes files from your computer, splits them into blocks, and then has other peers store those blocks to create an offsite backup.

Those peers could be other parties that you would not want to disclose the contents of your backup to.

These peers work in a peer to peer fashion, allowing them to get a copy of a block from anyone who has a copy. This means that a peer that is replicating a backup could connect to the machine that is being backed up and request a block from the middle of the file.

So, it seems like it would be good for the machine that is being backed up to locally encrypt, with a symmetric cipher, the data before it is sent off as a block to a peer.

Normally, I would think "use AES". But I'm vaguely aware that there are modes, like CBC. And I'm thinking that chained modes like that would make it very hard to efficiently open a file, seek to a position somewhere near the middle, read a piece of data, encrypt it, and come up with the same cipher text as if it started at the beginning of the file and encrypted all the blocks in order up to that position.

How do the people who do whole disk encryption do this? Is something similar to what they use available for Python (3.x if that matters)?

• FDE programs use the XTS mode which allows for random-access. However you also want those blocks to be authenticated so that a malicious peer can't tamper them without you noticing it (there's a chance you won't notice it with XTS because it's unauthenticated). – SEJPM Feb 12 '17 at 10:58
• The chief claim-to-fame for XTS is that it does not expand the ciphertext; the encrypted block is exactly the same length as the plaintext block. This is important for disk encryption (as disks are commonly formatted to have fixed length sectors which are exactly the same length as the OS expects, so there's no space to store any extra data). However, that benefit comes with drawbacks; if you encrypt the same text twice, you'll come up with the same ciphertext, if someone modifies the ciphertext, you'll decrypt without detecting it; hence if you can tolerate expansion, you don't want XTS – poncho Feb 12 '17 at 15:37
• @poncho Ok, this system uses SHA256 over each block, and the whole object already. So I think that may help some, but trying to mix the two and then trying to make a claim of security off that sounds like something best left to the (crypto) experts. I don't want to double the size of the backup, but some metadata would be fine -- I'm already storing hashes. One constraint is that as a backup system, the metadata would be stored with untrusted parties, and the only thing you could count on having to restore the backup is a key or two. – Azendale Feb 12 '17 at 15:49
• You will need probably about 16 bytes for the verification tag and maybe 12 bytes for the nonce (you could make this implicit as random_value_per_file + block_index) and then you also associate a bunch of implicit bytes with each block (filename, ...) – SEJPM Feb 12 '17 at 20:52
• The command line "sudo apt-get install rsyncrypto" on Ubuntu already seems to work for me. (I agree that Python scripting would be nice). – David Cary Feb 14 '17 at 2:02

Why not gpg? The libraries are already written and open sourced, so you don't have to recreate the wheel.

Split the file into blocks, then add a control file adding whatever metadata you need to keep the files together and belonging to the correct person. Encrypt each block with the user's key, and put it on an untrusted host. He will then be the only person who can decrypt the files. Assuming the untrusted host doesn't delete the blocks.

• Engineering a secure system out of gpg as a part is considerably more difficult than engineering a secure system out of, e.g., NaCl compositions as parts. It's glib to advise people against reinventing the wheel, but the comparison here is between a rusty relic of '90s crypto engineering badly designed for human use, and a modern crypto engineering library that is widely available. Note that, whether with gpg or with NaCl, getting chunk streaming right is tricky; see miscreant for an example of how to try it. – Squeamish Ossifrage Aug 29 '17 at 4:52

Disk encryption and online backups have a different thread model. What's appropriate for one isn't necessarily appropriate for the other.

Disk encryption typically only protects against one threat: theft of the disk. With this threat, the attacker gains one version of the data in encrypted form, and the goal is to maintain the confidentiality of the data.

An online backup system needs to defend against two other important threats. If the attacker gains access to the server where the backups are stored, they can access multiple versions of the encrypted data. So it's important that the difference between successive ciphertexts doesn't reveal too much about the plaintext. Furthermore, when you restore from the backup, it's absolutely crucial to verify that the backup is genuine. An attacker who has access to the server might have corrupted the ciphertext even if they weren't able to decipher it.

Disk encryption often uses XTS mode. XTS encrypts each disk block independently. Successive versions of a block are encrypted with the same key and IV, which can reveal a common prefix, but not much more. (XTS isn't very malleable, unlike, say, CTR, where repeating a counter value is an instant fail.) XTS does not protect the data's authenticity at all. Disk encryption typically makes no attempt to verify authenticity or integrity because it isn't necessary in the usual threat model and it has a high impact on performance¹.

For an online backup, you need some form of authenticated encryption. Authenticated encryption protects two things:

• The data's confidentiality: without the key, all the attacker knows is the approximate size. With successive versions of the same data, the attacker can know approximately what parts of the data have changed.
• The data's authenticity: when you read back some data and it verifies as correct, you know that the data is genuine. There's a subtlety here: genuine data could still be misplaced — it could be from a different location on the disk, or from a different version.

To make sure that the data is genuine without having to authenticate and read it all back as a single message, you can use a hash tree structure. Each block of data (or each file, depending on how you structure the data) has an authentication tag, and the blocks/files are organized in sets for which there is an authentication tag, and the sets are organized in supersets and so on until you get to the root. To verify that a block is genuine, you need to:

• verify that its authentication tag is correct;
• read the set containing that block and check that it contains the correct authentication tag;
• calculate and verify the authentication tag of the set;
• read the superset containing the set, and so on until the root.

With these verifications, you can retrieve files individually (plus a small overhead to retrieve the parent sets), and be confident that an attacker didn't substitute confidential_data.txt for public_mailing.txt. You can also be confident that the attacker didn't arrange to return database_schema.txt from last month with database.db from last week. There's still a limitation: the attacker could arrange to return a stale backup, as long as they return consistent data. To avoid that you need to remember the date or version of the last backup.

¹ If you need authenticity protection, you can't pipeline reads: you have to read a whole data block and verify it before you can serve the first byte to the reader. Furthermore, to protect against block reordering or version mix-and-matching, you have to verify that the ciphertext is the correct one for this position on the disk and is the correct version, which means that writes need to update more metadata.

You can encrypt each block independently with it's own IV or you could use CTR mode and then you can have an IV per file or even larger encryption task(if you give an order to the files). You may also want to think about leaking information about directory structure file names or sizes. All of these may be valuable.

• Note that using only CTR mode most likely won't allow you to detect any malicious modifications made to the data. – SEJPM Jun 13 '17 at 22:24
• Yes for integrity you will need to add macs on some level(file/block) and if you are breaking up this way with so each block has it's mac you might as well give it an IV as well. – Meir Maor Jun 14 '17 at 3:48

I'd suggest AES GCM with IV, and simply encrypt block by block (you don't encrypt the whole file, but each block separately, and able to transmit each block as a separate container).