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.

• you can't even use simple implicit counters? (1,2,3,4,5,6,....) – SEJPM Apr 28 '15 at 15:45
• Can you expand on " but we have no room to store IVs "? Do you mean you can't afford the bandwidth to transfer an IV? Or you have no reliable TRNG at hand to generate a random IV? Or you equate IV to permanent counter, and do not have permanent memory for that? Or it is too much trouble (or slow, hardware-wearing..) making that memory permanent-enough facing an adversary, or just Murphy pulling the plug? Or ..? – fgrieu Apr 28 '15 at 16:34
• Based on your clarification about disk writes, it sounds like you're trying to reinvent disk encryption. Why not use a preexisting mode purpose-built for this use-case, such as XTS? – Stephen Touset Apr 28 '15 at 18:22
• @StephenTouset, posted this as answer – SEJPM Apr 28 '15 at 18:22

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.

• Well they pretty much are. I just asked the question more generally. I can't tell from what I can get specifically if AES will survive IV reuse as different data written to the same block at different times ends up with the exact same IV. – Joshua Apr 28 '15 at 18:37
• well the IV will be different but the data as well, leading to different ciphertexts (because AES isn't applied as streamcipher). The IV is only used to hide patterns. (note: AES by itself resists all known attacks including known-plaintext, chosen-plaintext and chosen-ciphertext) If my intuition is right (as I can't think of an attack), XTS-security should reduce to block-cipher security. You may also want to read the wikipedia article about XTS. – SEJPM Apr 28 '15 at 18:53
• Right, but does attacking two blocks known to use the same key & IV reduce the problem? If one of the blocks is known plaintext? – Joshua Apr 28 '15 at 18:59
• $C_1=E_K(P_1 \oplus X)\oplus X$ and $C_2=E_K(P_2 \oplus X) \oplus X$ (with $X$ being some constructed pseudorandom value. Even if $X,K$ stay the same I can't think of any attack against it (even with more pairs) - without breaking the cipher or knowing the key. – SEJPM Apr 28 '15 at 19:03
• Hmmm. Not true of all ciphers. I presume you're saying it is true of AES. – Joshua Apr 28 '15 at 19:07

Yes.
They're called Format-Preserving Encryption schemes,
and this is the best known construction of that.

• isn't format-preserving encryption meant to receive some formatted input and output some (random) input in the same format? How does this help if he doesn't have a format? How does this prevent the standard known-plaintext attacks which are mitiagated by an IV? – SEJPM Apr 28 '15 at 16:04
• No; they're supposed to output some (random) output in the same format. $\:$ If "he doesn't have a format" then this doesn't help. $\:$ (The OP's formats are string lengths.) $\:$ This doesn't "prevent the standard known-plaintext attacks which are mitiagated by an IV", since his setting provably does not allow preventing them. $\:$ However, it does prevent all other known-plaintext attacks. $\;\;\;\;$ – user991 Apr 28 '15 at 16:13