Cryptography Reference
In-Depth Information
The only effect permutations have is that the position of the changed bit changes
within the block. Also, nothing sensational happens with the XOR operation on
the key: though the change to a bit can change the direction, e.g., from 1 to 0
instead of from 0 to 1, the position remains the same. Expressed mathematically:
if
P
and
S
are bit sequences with equal length (where
S
stands for 'key'), and
if the
i
th bit (and only this one) is changed in
P
, then the
i
th bit (and only
this one) will also change in
P
⊕
S
.
Things get a bit more interesting when linking the left and right block halves
in a Feistel network (Figure 4.7). Though a changed bit in
L
i
influences only
one bit in
R
i
+
1
, if the bit is in
R
i
, it changes two bits in the result of that round:
one bit each in
L
i
+
1
and in
R
i
+
1
. These two bits have the same positions in
L
i
+
1
and
R
i
+
1
, i.e., the change does not propagate further.
With the expansion permutation, such a change can 'split itself up'. Figure 4.8
shows that this happens with every fourth bit and each of the following ones. It
depends on our fictitious compression permutation (which replaces the S-boxes)
whether or not this change will have an impact on all bits after a sufficient
number of rounds.
(Bear this method in mind. We will get back to it in Section 4.4.4 and see that
it offers no security at all against a plaintext attack despite its complexity.)
Let's summarize: if we change a plaintext bit, then
which
of the ciphertext bits
will also change does
not
depend on the key. The reason is that the key is
simply XOR-embedded in the round.
DES With S-Boxes
We will now bring the S-boxes back into play. They alone make the interaction
of the key with the algorithm complex; they are the non-linear element in DES
(see Section 4.4.4) and increase the avalanche effect.
On account of the S-boxes, which of the ciphertext bits will be influenced by
one single plaintext bit will now depend essentially on the key. Even more:
for
certain well-defined sets of changed bits in block R
i
you can observe a statistical
dependence of the S-box output on the key
. This statement is inexact; we will
formulate it in a more mathematically exact way in a moment.
We have been talking of 'changed bits' so far. In differential cryptanalysis,
however, we speak of 'differences'. The meaning is virtually the same, except
