3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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:

Key schedule

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:

Simon 32/64 Key Expansion

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:

enter image description here

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:

Simon 32/64 data evolution

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.

$\endgroup$
  • $\begingroup$ Those are nice pictures but I'm missing the connection with the question. Could you maybe make that a bit more obvious maybe? $\endgroup$ – Maarten - reinstate Monica Feb 18 '17 at 21:13
  • $\begingroup$ The SIMON structure is a really good example for what was asked and basically a visual representation of your answer. I'll expand it tonight to make what is here more obvious. $\endgroup$ – b degnan Feb 18 '17 at 21:22
  • $\begingroup$ @MaartenBodewes Hopefully, this is better. I can always delete it, but I was trying to show how diffusion is actually implemented, and I've found that showing these bit-grids from my tools are helpful. Although I didn't find an explicit question that matched the original post, the number one newbie question regarding Feistel ciphers seems to be the question of diffusion and XORs. $\endgroup$ – b degnan Feb 18 '17 at 21:48
  • $\begingroup$ Ah, OK, now the word XOR is clearly included in the answer and the relation should be clear. $\endgroup$ – Maarten - reinstate Monica Feb 18 '17 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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