Assuming you are using AES with CBC, best case you will have to resend every block after and including the first one that changed.
My understanding is that CBC is among the most secure forms of AES encryption because it is essentially impossible to have patterns in data (unlike EBC). Practically speaking then one must assume that it is common to upload most of a file. Any software that boasts this security cannot effectively 'diff' your files.
You don't have to apply the CBC mode to complete files. If it is secure for a 1 MB file, I don't see why it would be insecure for 100 parts of a 100 MB file.
If you manage to merge small files into the same blocks, you even gain some privacy because the server can't even tell the number of files anymore.
[1] also has a discussion of the trade-offs of the different modes of operation for whole disk encryption. That seems related here because nobody wants to rewrite the whole disk after changing the first byte.
There are other modes that are more suitable for random access. For example, TrueCrypt uses XTS mode. Tarsnap uses CTR mode. Either would satisfy the requirement of allowing you to edit one block without rewriting all the blocks that follow.
Comments
Assuming you are using AES with CBC, best case you will have to resend every block after and including the first one that changed.
My understanding is that CBC is among the most secure forms of AES encryption because it is essentially impossible to have patterns in data (unlike EBC). Practically speaking then one must assume that it is common to upload most of a file. Any software that boasts this security cannot effectively 'diff' your files.
EDIT: Formatting
You don't have to apply the CBC mode to complete files. If it is secure for a 1 MB file, I don't see why it would be insecure for 100 parts of a 100 MB file.
If you manage to merge small files into the same blocks, you even gain some privacy because the server can't even tell the number of files anymore.
[1] also has a discussion of the trade-offs of the different modes of operation for whole disk encryption. That seems related here because nobody wants to rewrite the whole disk after changing the first byte.
1: https://en.wikipedia.org/wiki/Disk_encryption_theory
I understand now. that is a clever idea; I like it a lot.
There are other modes that are more suitable for random access. For example, TrueCrypt uses XTS mode. Tarsnap uses CTR mode. Either would satisfy the requirement of allowing you to edit one block without rewriting all the blocks that follow.