Cryptography Reference
In-Depth Information
((0)
28
(01)
14
,
(0)
28
(10)
14
)
,
and
((1)
28
(01)
14
,
(1)
28
(10)
14
)
.
Each of these 56-bit key pairs will encipher plaintext to identical ciphertext. In
other words, one key in the pair can decipher messages enciphered with the other
key in the pair. Hence, these key pairs generate only two different subkeys, each
of which is used eight times in the DES algorithm. They have to be avoided.
Another weakness of DES is the
complementation property
, described as
follows. Let
c
(
k
) denote the bitwise complementation of an input key
k
in
DES. In other words, replace all 0's with 1's and all 1's with 0's. DES satisfies
the following, which the reader may verify by trying this complementation on
Diagram 3.1 on page 117.
DES Complementation Property
E
c
(
k
)
(
c
(
m
)) =
c
(
E
k
(
m
))
.
In plain words, if one enciphers the complement of the plaintext with
the complement of the key (the left side of the equation), then one
gets the complement of the original ciphertext (the right side of the
equation).
This says that complementation of the plaintext yields complementation in
the ciphertext, and this means that a chosen-plaintext attack
3.4
against DES
only has to test half of the keyspace of 2
56
keys, namely, 2
55
of them.
As mentioned in Chapter 2 (see page 98), DES reached the end of its abil-
ity to deliver as a secure cryptosystem by the end of the twentieth century,
and, of course, S-DES isaaweakerversion intended only to display the basic
principles behind its construction. In Section 3.5, we study its successor, the
Advanced Encryption Standard (AES). For now, we need to look more deeply
into the design principles underlying DES since they are important from several
perspectives for an understanding of symmetric-key block ciphers.
Feistel Ciphers
A
Feistelcipher
is a block cipher that inputs a plaintext pair (
L
0
,R
0
), where
both halves
L
0
and
R
0
have bitlength
b
∈
N
and outputs a ciphertext pair
(
R
r
,L
r
), where
R
r
and
L
r
have bitlength
b
, according
to an iterative process, making it what is called an
iterated block cipher
.A
∈
N
for each
r
∈
N
3.4
A
chosen-plaintext attack
means that a cryptanalyst chooses plaintext, is then given the
corresponding ciphertext, and analyzes the data to determine the encryption key. One of the
best-known chosen plaintext attacks against iterated block ciphers is
differential cryptanalysis
(DC). The original idea was developed by Murphy [175] in 1990, as an attack on another block
cipher. It was improved and perfected by Biham and Shamir [23] and [24] in 1993, who used it
to attack DES. DC involves the comparisons of pairs of plaintext with pairs of ciphertext, the
task being to concentrate on ciphertext pairs whose plaintext pairs have certain “differences”.
Some of these differences have a high probability of reappearing in the ciphertext pairs. Those
which do are called “characteristics”, which DC uses to assign probabilities to the possible
keys, with an end-goal being the location of the most probable key.
Search WWH ::
Custom Search