1
$\begingroup$

For a cloud storage upload client I want to encrypt files during upload, so that they cannot be read by the cloud service provider or anyone who gains access to the account. I would like to use some standard format, instead of rolling my own crypto, but I couldn't find anything that does what I want.

The main problem is that I want to split large files and upload them in parallel to maximize bandwidth. If uploading of a part fails, I might have to go back and upload the same part again. Therefore, I need an encryption scheme which allows encrypting only some parts within a file. Also, a full authentication pass before uploading should be avoided.

After a lot of reading in the past two days I came up with the following scheme: Split the file into fixed sized (few KB) blocks. Calculate the SHA-1 hash of each individual block and append it to the plaintext. Encrypt the plaintext and the following hash using AES in CBC mode with a random IV for every block. This is similar to what RFC 4880 specifies for symmetric encryption, just with blocks. This provides authentication for every individual block. To protect the file as a whole, an additional last block with a concatenation of all block hashes is processed using the same technique.

From the RFC 4880 document it's already clear that this only provides modest security against modifications. So I'm thinking about further improvements. The use of a simple hash function could be replaced with a HMAC. From this document it's clear, that authenticate-then-encrypt is not generically secure. However, for CBC mode this doesn't apply, so I would like to keep authenticate-then-encrypt, since it allows easy checking of the encryption key, without decrypting the whole file. I'm also not very happy about, the last block which repeats all the previous hashes. Maybe a HMAC off all previous hashes would suffice? I hope someone can shed some light on the practical security of this technique.

I also stumbled across GCM, which seems exactly what I want. However, I understand that there is a limit of ~68GB, which can be encrypted for a given IV/key pair. Is it safe to approach this limit, or should one stay far below? Also, I didn't find any good Python library which actually allows parallel encryption using GCM.

$\endgroup$
  • $\begingroup$ A HMAC of "all previous hashes would suffice" if [[number of blocks] times [length of HMAC]] never equaled your block size. ​ (It might suffice even if they can equal each other; I didn't try to work that out.) ​ ​ ​ ​ $\endgroup$ – user991 Apr 21 '16 at 21:14
  • $\begingroup$ (where "number of blocks" refers to "number of blocks in the file", not "total number of blocks you've encrypted") ​ ​ $\endgroup$ – user991 Apr 21 '16 at 21:15
  • $\begingroup$ I'm not sure if I understand you correctly. Say I have a block size of 128 byte and MD5 for the HMAC (I'm not actually going to use that), then with 8 blocks in a file I would have violated your equation. Why does this relation matter? $\endgroup$ – sebi707 Apr 21 '16 at 21:26
  • $\begingroup$ I don't see how CBC allows "checking of the encryption key, without decrypting the whole file". Yes, you can use a Merkle or hash tree to create a hash over hashes or a MAC over other MAC's. Generally I would prefer a HMAC over a hash, and I don't see why you would not be using encrypt-then-mac in that case. You could use EAX mode. $\endgroup$ – Maarten Bodewes Apr 21 '16 at 21:54
  • $\begingroup$ After encrypting a single block, I get the plaintext and a hash of that plaintext. So I can verify if both still match. Decrypting with the wrong key would very likely result in a mismatch. $\endgroup$ – sebi707 Apr 21 '16 at 22:02
0
$\begingroup$

To answer your ideas of:

  • "I use hash-then-encrypt" with CBC + SHA-1
  • "I use MAC-then-encrypt" with CBC + HMAC
  • "I won't use GCM because of unclear usage guidance"

First, hash-then-encrypt is a really bad idea. You really should avoid it if possible. Details are explained in this related question on Crypto.SE.

Second, MAC-then-encrypt is a concept you also should avoid. Not only do generic compositional security proofs don't generally hold, but it also allows for padding oracle attacks in some circumstances, so encrypt-then-MAC is better and there's no significant advantage to use authenticate-then-encrypt over the more generically secue encrypt-then-authenticate. Also see our canonical question on this subject.

Third : GCM. You indeed only should encrypt than less than 60GiB of data under a given key-nonce pair. However, you could assign (ascending) nonces to your data chunks (of a few kBs each) and authenticated encrypt them each using a different nonce. This way you stay way below the 60GB limit and you generate your nonces deterministically (using counter incrementation) which will also quite reliably protect you against nonce re-use based on nonce collisions. Upon retrieval of the data you could just check then whether all chunks are valid and whether a chunk is missing (because there's a gap in the nonces) and maybe you'd want to encode the number of chunks into each chunk to allow proper verification.

$\endgroup$
  • $\begingroup$ Meh, for file based encryption I don't really see how padding oracle attacks apply (unless you try and download the encrypted file many times if the MAC verification fails, which would not be the smart thing to do). $\endgroup$ – Maarten Bodewes Apr 21 '16 at 21:56
  • $\begingroup$ GCM on smaller sized blocks looks like a nice and clean solution. The total number of packets can also be included in the non ecrypted part of it. $\endgroup$ – sebi707 Apr 21 '16 at 22:23
0
$\begingroup$

You can use CCM or EAX mode. EAX mode is not standardized by NIST, but it uses AES + AES-CMAC as underlying primitive, implementing a secure authentication mode. You could use AES-CMAC (or EAX mode without any ciphertext and just Additional Authenticated Data) to calculate an authentication tag over the authentication tags of the blocks. Advantage of EAX mode is that it doesn't really have the tricky requirements that GCM has.

GCM may be faster though if implemented correctly. CCM is also an option (packet based encryption, and you define packets, kind of). CCM is however also not that easy to use (actually, I'd go a bit further than that and call it a major PITA).

$\endgroup$
  • $\begingroup$ I might try those, but at the moment I prefer GCM. I've already found a nice Python library which uses OpenSSL as a backend and supports GCM, but not CCM or EAX. $\endgroup$ – sebi707 Apr 21 '16 at 22:27
  • $\begingroup$ Well, you can always use an 8 byte salt per file and use a KBKDF to derive a key per file. Then you could use GCM to encrypt the blocks. Note that you don't need a parallel GCM implementation. You can use just use multiple instances of the same cipher. Your problem is already embarrassingly parallel, so the underlying algorithm doesn't need to be. I presume that - in general - your files won't be much over 60 GB, right? $\endgroup$ – Maarten Bodewes Apr 21 '16 at 22:30
  • $\begingroup$ Yes, I just realized that. Somehow I didn't think of this earlier. Files might actually be quite large. I've uploaded several 10GB files so far. $\endgroup$ – sebi707 Apr 21 '16 at 22:35
  • $\begingroup$ Well you can always device a protocol that derives a new key with a new salt after 50GB. It would be a bit more complex though. If you're paranoid you could opt for a larger salt, say up to 128 bytes. $\endgroup$ – Maarten Bodewes Apr 21 '16 at 22:37
  • 1
    $\begingroup$ I think the solution proposed by SEJPM is the way to go. Just GCM on smaller blocks with ascending nonces. Using a proper key derivation function with salt should guarantee different keys for each file, so I don't get a nonce/key collision. $\endgroup$ – sebi707 Apr 21 '16 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.