Cryptography Reference
In-Depth Information
possible? The meaning is taken from the theory of probability. For example, if
we know there is a 90 % probability that the following equations hold between
the key bits,
s
i
, the bits of the plaintext block,
p
i
, and the bits of the ciphertext
block,
c
i
:
s
2
⊕
p
15
⊕
s
6
⊕
p
7
=c
2
⊕
p
5
⊕
c
7
s
2
⊕
p
8
⊕
s
6
=c
5
⊕
c
6
then, knowing
p
i
and
c
i
, we can recover the two key bits,
s
2
and
s
6
, with equal
probability for a statistically sufficient number of plaintexts almost for sure.
In general, when mounting a linear cryptanalysis, you exploit the fact that there
is a linear relationship (which the attacker has to find) with a probability
other
than 50 %. This is a deviation from 'pure randomness' and can give clues on
the key bits. In our example, once we have studied a sufficient number of
plaintext - ciphertext pairs, we will have revealed the values for key bits that
tend to occur preferentially (only with a probability of exactly 50 % we can't).
How does this look specifically with DES? First, we will only look at one DES
round and omit the input and output permutations for the sake of simplicity
(since they only cause more typing and don't change anything in the study
itself).
S-box number 5 seems to offer the best vulnerability. That's the reason why
this box was chosen for Figure 4.9. The thing is that, among the 64 possible
inputs (corresponding to 6 bits), the second input bit equals the sum (i.e., the
XOR) of the four output bits in only 12 cases — we would expect 32 cases.
Shamir discovered this back in 1985, but wasn't able to exploit it.
The second input bit of S-box number 5 came into being by XORing bit
s
26
of the round's key with bit 26 of the expanded right half block which, in turn,
was formed from bit
r
17
of the unexpanded half block. Due to the subsequent
P-box permutation, the four output bits of the S-box land in positions 3, 8, 14,
and 25. These are four bits in the functional value
f
S,
1
(R
1
)
in equation (1),
Section 4.2. We can compute this functional value from the ciphertext:
f
S
,
1
(R
1
)
=R
2
⊕
L
1
