1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ you can't even use simple implicit counters? (1,2,3,4,5,6,....) $\endgroup$
    – SEJPM
    Apr 28, 2015 at 15:45
  • 2
    $\begingroup$ 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 ..? $\endgroup$
    – fgrieu ♦
    Apr 28, 2015 at 16:34
  • 3
    $\begingroup$ 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? $\endgroup$
    – Stephen Touset
    Apr 28, 2015 at 18:22
  • $\begingroup$ @StephenTouset, posted this as answer $\endgroup$
    – SEJPM
    Apr 28, 2015 at 18:22

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Joshua
    Apr 28, 2015 at 18:37
  • $\begingroup$ 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. $\endgroup$
    – SEJPM
    Apr 28, 2015 at 18:53
  • $\begingroup$ Right, but does attacking two blocks known to use the same key & IV reduce the problem? If one of the blocks is known plaintext? $\endgroup$
    – Joshua
    Apr 28, 2015 at 18:59
  • $\begingroup$ $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. $\endgroup$
    – SEJPM
    Apr 28, 2015 at 19:03
  • $\begingroup$ Hmmm. Not true of all ciphers. I presume you're saying it is true of AES. $\endgroup$
    – Joshua
    Apr 28, 2015 at 19:07
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – SEJPM
    Apr 28, 2015 at 16:04
  • $\begingroup$ 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. $\;\;\;\;$ $\endgroup$
    – user991
    Apr 28, 2015 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.