Cryptography Reference
In-Depth Information
laid down commandments in the 1940s for secure symmetric-key cryptosystems.
He first echoed Kerchoff's Principle (see page 76). Furthermore, he stipulated
that any secure cipher must include
both
confusion and diffusion techniques, as
does DES, for instance.
Let us now review classical ciphers in this light. Monolaphabetic substitution
ciphers fail Shannon's criterion on both counts since no confusion or diffusion
exists, given that all plaintext symbols are sent to the same ciphertext symbols
and there is no transposition. With polyalphabetic substitution ciphers such as
Vigenere, there is the use of confusion, since plaintext letters do not go to the
same ciphertext letters, but they fail at diffusion since there is no transposition.
Transposition ciphers use diffusion by definition but confusion is not necessarily
employed, certainly not often effectively if it is. Now, we return to to DES.
Double DES
One may strengthen DES by multiple encryptions (which means the applica-
tion of the encryption algorithm several times, in the same fashion as we would
compose functions numerous times). For instance, there is
doubleDES
wherein
we have two keys
k
1
and
k
2
so that encryption is given by
E
k
2
◦
∈
M
E
k
1
(
m
)=
E
k
2
(
E
k
1
(
m
)) =
c
for any
m
,
and decrypt via
D
k
2
(
c
)
.
On the surface, it would seem that the ostensible keylength in the double DES
scheme involves 2
m
=
D
k
1
(
D
k
2
(
c
)) =
D
k
1
◦
56 = 112 bits, which would be a significant increase in
security over DES. However, reality has a way of interfering with expectations.
Double DES has only a 56-bit keylength security level (which makes it only neg-
ligibly better in use than the original DES, which has 55-bit keylength security
due to the complementation property described on page 127). This weakness
of double DES was proved by Merkle and Hellman [161] in 1981. They show
that the security is reduced from 112 bits to 56 bits by making use of the
meet-
in-the-middle attack
, which we now describe in the interest of completeness.
Moreover, this form of attack is closely related to another attack (called the
“birthday attack”, which we will study in Section 7.1).
The meet-in-the-middle attack was introduced in 1977 by Di
0
e and Hellman
[70]. It is based upon the following simple observation. Since
×
E
k
2
(
E
k
1
(
m
)) =
c
, then
D
k
2
(
c
)=
E
k
1
(
m
)
,
given that
D
k
2
◦
E
k
2
is the identity function, by definition. The way the attack
works is that we are given a known plaintext/ciphertext pair (
m
1
,c
1
), and we
set up a table, which we will call
T
1
, of (sorted) values consisting of all 2
56
possible values of
E
k
1
(
m
). Now we start calculating another table consisting of
all possible values of
D
k
2
(
c
), one at a time, checking each one against the values
in table
T
1
. If there is a match, say (
K
1
,K
2
), then we take another known
plaintext/ciphertext pair (
m
2
,c
2
), and check for the equality:
E
K
1
(
m
2
)=
D
K
2
(
c
2
)
.
Search WWH ::
Custom Search