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 requiremen

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.