Cryptography Reference
In-Depth Information
The term 'linear expression in bits
b
1
,...,b
n
' actually means nothing more than
selecting a few bits (corresponding to a multiplication by constants, which can
only be either 0 or 1) and subsequently XORing them.
Why are such linear expressions of interest? Because block methods that rep-
resent only linear expressions in the plaintext bits and key bits can be cracked
by solving a system of equations. Assume the key consists of
n
bits,
s
i
. Further
assume that the ciphertext bits,
c
i
, can be calculated from the plaintext bits
p
i
,
as follows:
c
1
=
p
i
11
s
*
j
11
p
i
21
s
j
21
*
...
...
c
m
=
p
i
1
m
*
s
j
1
m
p
i
2
m
*
s
j
2
m
...
We know the indices,
i
kl
and
j
kl
, and if we additionally know
p
i
, then this is a
linear system of equations in the key bits,
s
i
, except that it uses unusual arith-
metic operations. Of course, 'knowing
p
i
' means that we carry out a plaintext
attack. This is very effective: if the block length is
N
, and
k
is large enough
so that
kN
≥
n
(where
n
is the key length) holds, then knowing
k
different
plaintext blocks might suffice to recover the key.
We can see that linear methods are very sensitive to plaintext analysis. The
Vigenere cipher is a trivial example of linear methods, but for cryptanalyzing
them, we don't need that much theory, while still being able to mount successful
ciphertext attacks.
The DES algorithm without S-boxes (but with a fixed compression permutation
instead) discussed in Section 4.4.2 is more interesting. It is not too hard to
derive from Figures 4.7 and 4.9 that each output bit can be represented as a
XOR of plaintext bits and key bits. The indices of all these bits, i.e., their
positions in the plaintext block or in the key, are known — that's the most
important thing. One single known plaintext block may be enough for us to
compute the key!
Now the comment that the S-boxes introduce a 'non-linear element' to DES is
easier to understand. They are really decisive for the method's security.
Linear Cryptanalysis on DES
Schneier [SchnCr, 12.4] writes about linear cryptanalysis: 'This attack uses
linear approximations to describe the function of a block cipher'. We know
what linear mapping on the number field with the elements 0 and 1 is, but how
can a linear approximation be defined where only two distances, 0 and 1, are
