Cryptography Reference
In-Depth Information
L
i
+ 1
. The right-hand half of the next cipher,
R
i
+ 1
, how-
ever, is a complex function,
L
i
+
f
(
R
i
,
K
i
+ 1
), of a subset of
the key bits,
K
i
+ 1
, and of the entire preceding intermediate
cipher. The essential feature to the security of the DES is
that f involves a very special nonlinear substitution—i.e.,
f
(
A
) +
f
(
B
)
≠
f
(
A
+
B
)—speciied by the Bureau of Standards
in tabulated functions known as S boxes. This process is
repeated 16 times. This basic structure, in which at each
iteration the cipher output from the preceding step is
divided in half and the halves transposed with a complex
function controlled by the key being performed on the
right half and the result combined with the left half using
the “exclusive-or” from logic (true or “1” only when exactly
one of the cases is true) to form the new right half, is called
a Feistel cipher and is widely used—and not just in the
DES. One of the attractive things about Feistel ciphers—
in addition to their security—is that if the key subsets are
used in reverse order, repeating the “encryption” decrypts
a ciphertext to recover the plaintext.
The security of the DES is no greater than its work
factor—the brute-force effort required to search 2
56
keys.
That is a search for a needle in a haystack of 72 quadril-
lion straws. In 1977 that was considered an impossible
computational task. In 1999 a special-purpose DES search
engine combined with 100,000 personal computers on
the Internet to find a DES challenge key in 22 hours. An
earlier challenge key was found by the distributed Internet
computers in 39 days and by the special-purpose search
engine alone in 3 days. For some time it has been apparent
that the DES, though never broken in the usual cryptana-
lytic sense, was no longer secure. A way was devised that
effectively gave the DES a 112-bit key—ironically, the key
size of the Lucifer algorithm originally proposed by IBM
in 1974. This is known as “triple DES” and involves using
two normal DES keys. As proposed by Walter Tuchman
