Does XOR have diffusion properties?

Question

Does the XOR operator provide diffusion if the right side of plain text is XORed against a round key which is then XORed against the left side to produce that side of cipher text, for example in a Feistel cipher.

Answer 1

Let's take the definition from Wikipedia:

Diffusion means that if we change a single bit of the plaintext, then (statistically) half of the bits in the ciphertext should change, and similarly, if we change one bit of the ciphertext, then approximately one half of the plaintext bits should change.

Now, what ever the XOR operation does, it works on 2 bits, 1 bit of the key and one bit of the plaintext. So no, XOR cannot provide diffusion by itself.

In your example, if you change a single bit of plaintext then then the output will only change with a single bit as well. If you applied the output to another bit then you'd still have the same situation (as the two bits flip at the same time).

If the Feistel function itself provides diffusion used with XOR in the steps is a different matter, of course. But XOR won't have provided the diffusion.

Answer 2

The other answer is excellent; however, I thought that a picture might be helpful. As a tractable example, I give you a SIMON32/64 graphical output (original paper), which is just slightly better than no encryption at all. In SIMON32/64, you have 32 rounds, and very simple logic. I happen to use this cipher, and my tools let me create pretty pictures.

The diffusion is not a property of the XOR, but a property of the complete structure. The shifts, XORs and rounds cause the diffusion. To illustrate this, let's start with the equation for the 4 block key for Simon, which is

$$k_{i+m} = c\oplus\left(z_j\right)_i\oplus k_i \oplus\left(I\oplus S^{-1}\right)\left(S^{-3}k_{i+3}\oplus k_{i+1}\right), m=4$$

In the equation above, you will notice the XORs, $\oplus$, and combined with the shifts. As a block diagram, this looks as:

As a key is shifted out serially, the feedback is updated. This is why the rounds matter. Starting with a 64-bits of zero, we would have a key that was all 0's for the first 4 rounds. In this case, we'd have a key expansion that looks like this:

In the image above, "white" boxes are "1" and the colored boxes are "0". The key evolves over the rounds due to the feedback from the XOR logic. (The $Z_i$ term adds some more non-linearity. This key is what is used to XOR against the data.

Further diffusion is added by the structure of the key schedule, which is also a function of XORs, Shifts and an AND, which is

$$R_k\left(x,y\right)=\left(y \oplus \left(S^1x \land S^8x\right) \oplus S^2x \oplus k, x\right),$$

where $k$ is the round key. As a block diagram, this look like:

The data register starts with 32-bits of zero, and then is modified by the state of the key. The evolution of the data looks as:

If you look at the cryptotext that starts at all 0's for a few rounds, it needs a few rounds for the key expansion to no longer be zero. The original paper for Simon and Speck will give you the details about this cipher.