Looking for encryption algorithm not subject to known-plaintext attack with IV reuse 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.
Well, your requirements sound pretty much like standard disk encryption ones.

Assuming you can assign IDs (0,1,2...) to each 4kiB sector implicitely.In this case you could simply use XTS-mode of encryption using AES.
You'd then iterate through the 4kiB block using the inner counter and iterate through all sectors using the outer counter.

This should give you best possible security, as the same plaintexts are mapped to different ciphertexts (because of the counters) and there's no keystream to break.

I hope this is a solution to your problem.