Cryptography: 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.

DES: 56-Bit Key  

•With a key length of 56 bits, there are 256 possible keys, which is approximately 7.2 * 1016 keys.

•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 to break the cipher.

•Assumption of one encryption per microsecond is overly conservative.

•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.

•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.

–And, of course, hardware prices will continue to drop as speeds increase, making DES virtually worthless.

•

DES: 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.