Cryptography Reference
In-Depth Information
the first term is more expressive, while the second can be used to compute. If
we XOR two equally long blocks,
A
and
A
:
A=A
⊕
A'
then exactly the bits in which
A
and
A
differ are set in
A
. Since the XOR
operation behaves like a usual addition of numbers (except in a number field
that consists only of equally long sequences of zeros and ones), we also refer
to
A
as the
difference
of the two blocks.
We denote the transformation defined by the S-boxes as
SB
and the 48-bit
key of an arbitrary DES round as
S
. For two 48-bit blocks,
A
and
A
, which
emerged from the expansion permutation, DES computes the 32-bit blocks as
C = SB(A
⊕
S) and C' = SB(A'
⊕
S)
Again, we denote the difference,
C
,as
C
=
C
⊕
C
. We can now formulate
the above statement more exactly as follows:
The values of
C depend on the key, S, for certain values of
A.
How can this be exploited? There are values,
P
, for plaintext pairs (
P
,
P
), for which certain differences,
C
, of the corresponding ciphertext pairs
(
C
,
C
) have a higher probability than expected. Such pairs of differences are
called
characteristics
, and plaintext pairs with the distinguished values for
P
are called
right pairs
. However, the higher probability mentioned above will
decrease as the number of rounds increases.
We can determine the characteristics for a 15-round DES. By encrypting a
sufficiently large number of right pairs, we eventually obtain probable values
for the key of the last round. This supplies us with 48 bits out of 56 key bits.
We find the last 8 bits by brute force (don't take it too literally, though).
This sounds neat and practicable if it weren't for the problem that the chosen
plaintext pairs will have to somehow be foisted on the code writer. But as
we got worked up we forgot the specific data, for the catch is: 'we eventually
obtain probable values for the key of the last round'. How do we determine
such probable values? By comparing the frequencies, that's for sure. But we
would have to acquire 2
48
frequencies. They correspond to about 280 trillion
