@Simon
The per-block encryption you describe would only work if the blocks stay aligned. If you prepend one byte to a file, no block hashes will match, the more efficient approach is to use rolling checksums. I know all this because I'm one of the independent competitors to these mentioned products (my app is S3 Backup) and currently implementing the block-level differential scheme as well.