THE
STRENGTH OF DES
Since its adoption as a federal standard, there have been
lingering concerns about the level of security provided by DES. These concerns,
by and large, fall into two areas: key size and the nature of the algorithm.
The Use of 56-Bit Keys
With a key length of 56 bits, there are 256 possible keys, which
is approximately 7.2 * 1016 keys. Thus, on the face of it, a brute-force
attack appears impractical. Assuming that, on average,
half the key space has to be searched, a single machine performing one DES encryption per microsecond would
take more than a thousand years (see Table 2.2) to break the cipher.
However,
the assumption of one encryption per microsecond is overly conser- vative.
As far back as 1977, Diffie and Hellman
postulated that the technology existed to build a parallel machine
with 1 million encryption devices,
each of which could perform one
encryption per microsecond [DIFF77]. This would
bring the average search time
down to about 10 hours. The authors estimated that the cost would be about $20 million in 1977 dollars.
DES finally
and definitively proved
insecure in July 1998, when the Electronic Frontier Foundation (EFF) announced that it
had broken a DES encryption using a special-purpose “DES cracker”
machine that was built for less than $250,000. The attack
took less than three days. The EFF has published a detailed description of the machine, enabling others to build their own cracker [EFF98]. And, of course,
hard- ware prices will continue to drop as speeds increase, making DES virtually
worthless.
It is important to note that there is more to
a key-search attack than simply running through all possible keys. Unless known plaintext is provided, the analyst must be
able to recognize plaintext as plaintext. If the message is just plain text in English, then the result pops
out easily, although the task of recognizing English would have to be automated. If the text message has been compressed
before encryption, then recognition is more difficult. And if the message is some more gen- eral type
of data, such as a numerical file, and this has been compressed, the prob-
lem becomes even more difficult to automate. Thus,
to supplement the brute-force
approach, some degree of knowledge about the expected plaintext is needed,
and some means of automatically distinguishing
plaintext from garble is also needed.
The EFF approach addresses this issue as
well and introduces some automated techniques that would be effective in many
contexts.
Fortunately, there are a number of alternatives to DES, the most important of which are AES
and triple DES, discussed in
Chapters 5 and 6, respectively.
The Nature of the DES Algorithm
Another concern is the possibility that cryptanalysis is possible by exploiting the characteristics of the DES algorithm. The focus of concern has been on the eight substitution tables, or S-boxes, that are used in each iteration. Because the design criteria for these boxes, and indeed for the entire algorithm, were not made public, there is a suspicion that the boxes were constructed in such a way that cryptanalysis is possible for an opponent who knows the weaknesses in the S-boxes. This assertion is tantalizing, and over the years a number of regularities and unexpected behaviors of the S-boxes have been discovered. Despite this, no one has so far succeeded in discovering the supposed fatal weaknesses in the S-boxes.9
Timing Attacks
We discuss timing attacks in more detail in Part Two, as they relate to public-key algorithms. However, the issue may also
be relevant for symmetric
ciphers. In essence, a timing attack is one in which information about the key or the plaintext
is obtained by observing how
long it takes a given
implementation to perform decryptions on various ciphertexts. A timing attack exploits the fact that an encryp- tion
or decryption algorithm often takes
slightly different amounts of time on different inputs. [HEVI99] reports
on an approach that yields the Hamming
weight (number of bits equal to one) of the secret
key. This is a long way from knowing
the actual key, but it is an
intriguing first step. The authors
conclude that DES appears to be fairly resistant to a successful timing attack but suggest
some avenues to explore. Although
this is an interesting line of attack,
it so far appears unlikely
that this technique will ever be
successful against DES or more powerful symmetric ciphers such as triple DES and AES.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.