I've encountered an interesting problem where we can basically say the following:
- We need to encrypt messages, but we have no room to store IVs. We can synthesize IVs; however an attacker would be able to observe different blocks encrypted with the same IV.
- We can detect message tampering directly. That is, we don't have to care about somebody injecting blocks to change plaintext. They will be caught.
- Large amounts of plaintext are known to any would-be attacker.
Are there any known block cipher secure against data-reading attacks with these constraints?
The problem comes in disk atomicity. 4096 bytes can be written atomically, 4096 + N bytes cannot be. Using simple sequential IVs was my plan, but someone seeing the disk twice would be able to exploit that.