DES 1-bit changes to inputs: why when I change two inputs by only one bit I get predictable results?

Question

I expected a 1-bit change to two inputs (same key) would provide differences to 50 per cent of the output bits (on average). But this is not the case when I tested it. However, for two 'identical' inputs but with keys different by one bit, the differences 'were' as expected. Why is this so?

Example 1 (same key, two inputs different by only 1 bit)

Key:    0123456789ABCDEF
Input:  0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF
Output: 56CC09E7CFDC4CEF56CC09E7CFDC4CEF56CC09E7CFDC4CEF

Key:    0123456789ABCDEF
Input:  1123456789ABCDEF0123456789ABCDEF0123456789ABCDEF
Output: 236617CA247292D156CC09E7CFDC4CEF56CC09E7CFDC4CEF

The two outputs are identical from the 17th character onward.

Example 2: (keys different by 1 bit, inputs identical)

Key:    0123456789ABCDEF
Input:  0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF
Output: 56CC09E7CFDC4CEF56CC09E7CFDC4CEF56CC09E7CFDC4CEF

Key:    1123456789ABCDEF
Input:  0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF
Output: 472C14ED890C7CB5472C14ED890C7CB5472C14ED890C7CB5

Here the outputs are completely different. As one would expect.

Answer 1

DES block size is 64 bits, your input is 3 DES blocks, you change 1 bit in the first input block only and encrypt the whole input in ECB mode without padding; the first output block is completely different after the change, the 2nd and 3rd blocks are the same, as it should be.

Here's the ECB mode of operation:

Answer 2

DES does have the avalanche effect, and it's visible in your experiment.

Key:    0123456789ABCDEF
Input:  0123456789ABCDEF
Output: 56CC09E7CFDC4CEF

Key:    0123456789ABCDEF
Input:  1123456789ABCDEF
Output: 236617CA247292D1

This changes 38 bits out of 64, which is close enough to the average of 32.

The problem with your first experiment is that you didn't run DES — you ran an algorithm that builds on DES. DES is a block cipher, with a block size of 64 bits: the encryption function maps a 56-bit key¹ and a 64-bit input (one input block) into a 64-bit output (one output block). If you want to encrypt or decrypt a string that is shorter or longer than one block, then DES alone doesn't do it. To build a cipher that can work on arbitrary-size messages, you need to plug the block cipher into a mode of operation.

You used the mode of operation ECB, which works only for inputs that are a multiple of the block size, and encrypts each block independently. ECB does not have the avalanche effect — that should be obvious given that by construction the content of one input block only affects the content of the corresponding output block.

ECB is not a suitable mode of operation for security, except in some very rare circumstances where you need to encrypt data whose size is exactly one block. It's only offered by crypto libraries because it's occasionally useful to build a mode of operation that the library doesn't support, but then you should pass input that consists of a single block.

The most common modes of operation for data confidentiality (i.e. encryption that works) are CBC with some padding (CBC by itself requires input that's a multiple of the block size, padding modes specify how to work with input that isn't a multiple of some block size), and CTR. DES-CBC-PKCS#7, DES-CBC-X.923 and DES-CTR are three example of ciphers that can work on arbitrary³ message sizes, and they all have the avalanche effect.

¹ _{For historical reasons, the standard representation of this 56-bit key uses 64 bits, with a parity bit in each byte. There is no cryptographical reason for this², it's just a historical accident.}
² _{In fact, it's highly likely that DES was reduced to 56 bits instead of the original 64-bit design specifically to make it weaker to brute-force attacks.}
³ _{More precisely, any number of bytes (even any number of bits for CTR) up to a maximum that's a little less than $2^{2^n} \cdot 2^n$ bits where $n$ is the block size in bits — basically, you need to be able to fit the number of blocks in one block. That's not a problem in practice.}