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.