Are there any deterministic multi-block encryption constructions that have an avalanche effect going both ways?

Question

For common multi-block encryption schemes (CBC, CTR, CFB, stream ciphers, etc), if they are forced to be deterministic, a change in the plaintext will change only the current block and maybe future blocks, but the past blocks are unchanged.

Using DES-CBC as an example, I've fixed the IV as to force it to be deterministic. (DES is used here for the small block size, for convenience)

Input:  0001020304050607 08090a0b0c0d0e0f 1011121314151617 18191a1b1c1d1e1f 2021222324252627 28292a2b2c2d2e2f
Output: 4c72f896d0b5c010 96cafa256bd7bf8c 7f3dfa17eb0721d6 2db73b14cfa32977 e87a8caf18ace662 298640486525ca14

Now to change one bit in the third block.

Input:  0001020304050607 08090a0b0c0d0e0f 1011321314151617 18191a1b1c1d1e1f 2021222324252627 28292a2b2c2d2e2f
                                              ^ Change
Output: 4c72f896d0b5c010 96cafa256bd7bf8c 123ea45b2bc1d45b 876ee075d04e5c61 ea59edd03137781b 57cd1fafa7849fe2
                                   Change ^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^

You'll notice that the first two ciphertext blocks are the same.

Are there any deterministic constructions that allow for any change of any bit in the plaintext to affect every bit of the ciphertext?

Answer 1

I suspect that what you are looking for is either convergent encryption or the SIV mode (pdf).

Convergent encryption is essentially:

1. Hash the message.
2. Encrypt using the hash as key.
3. Encrypt the hash with your cipher.

This is not secure for guessable plaintexts, since you can try generating the ciphertext without knowing the key.

SIV mode is essentially:

1. MAC the message.
2. Encrypt using the MAC as an IV.

With SIV people often also include a per-message nonce to avoid deterministic encryption, but since you want that you should omit it.

(Note that SIV mode is actually more involved due to the inclusion of a header/associated data. Use the construction as defined in the paper of RFC 5297 if you want to be sure and interoperable.)

Answer 2

I know no classical deterministic multi-blocks encryption construction with the desired avalanche property. And a serious problem is that any such construction, simply because it is deterministic, won't pass the formal definition of security under chosen plaintext, which CBC, CTR, CFB, OFB.. with random IV achieve.

So what's asked does not come with a precise definition of security. Given this, I can state anything without risk of contradiction from the standpoint of security. So here is something, essentially two passes of CBC encryption with IV the last block of the previous pass. For encryption:

• Pad de message to an integer number of blocks; e.g.: append a single bit 1, then as few bit(s) 0 (possibly none) as strictly necessary to reach a multiple of the block size.
• Let $b>0$ be the number of blocks of padded plaintext $X$
• If $b=1$, do $X_0\gets E(E(X_0))$ where $E$ is block encryption
• Otherwise repeat for $i$ from $b$ to $3b-1$ (that is, $2b$ times):
  • $X_{i\bmod b}\gets E(X_{i-1\bmod b}\oplus X_{i\bmod b})$
• Output ciphertext $X$

Decryption is:

• Let $X$ be the ciphertext of exactly $b>0$ blocks
• If $b=1$, do $X_0\gets D(D(X_0))$ where $D$ is block decryption
• Otherwise repeat for $i$ from $3b-1$ downto $b$ (that is, $2b$ times):
  • $X_{i\bmod b}\gets X_{i-1\bmod b}\oplus D(X_{i\bmod b})$
• Remove padding; e.g.: while $X$ ends with a zero bit and is non-empty, remove the rightmost 0 bit; then if $X$ is non-empty, remove its last bit.
• Output the plaintext $X$

We can improve diffusion in decryption by using PCBC rather than CBC, make the thing less malleable by throwing an extra $\oplus i$, do more passes, have an extra index hopping into $X$, derive a different key at each pass.. but without a definition of the security goal, that is moot.

Note: as pointed out elsewhere, plaintext changes do not propagate at all in CTR mode, contrary to the question's statement.

Answer 3

I'm not sure if this is a misunderstanding of the avalanche effect, or a misunderstanding of the role of the IV. This is the architecture of AES -CBC:-

Avalanche effect is a demonstrable property of good cryptographic primitives. A cryptographic primitive is the blue block. In the case of the venerable AES, it has a proven avalanche effect otherwise the whole AES concept would be fatally flawed. So as you've shown in your example, a single AES block's output completely changes with a single bit change on the input side. Technically, avalanche is a 50% probability of all the bits being influenced. Fundamentally though, the avalanche effect only makes sense for the blue primitive blocks and not the whole cipher system.

The green IV block is there to prevent your specific example. So the IV is unique to every cipher text, including when you flip a single bit to generate another output. The consequence is that two cipher texts with bits flipped or not, always generate a different unique output (though with a measurable probability of collision that I don't know how to calculate) .

Your whole question is based on an incorrect construction /use of the AES architecture for CBC mode. You're actually deliberately breaking the system with the notion of a fixed IV. Imagine if a few flipped bits were only within the final block and the IV was fixed. You'd be open to breaking your cipher. Your example should never materialise in a well constructed system as flipping a bit must require the regeneration of the IV and the output of another cipher text.

Whilst deliberately breaking AES-CBC, you've highlighted the dangers inherent in putting all this together yourself in a DIY architecture.