Are there any deterministic multi-block encryption constructions that have an avalanche effect going both ways? 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?
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&gt;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&gt;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.