Is DES breakable? Of course
by Ray Kaplan
Day two of the second annual RSA Data Security Data Security Conference in Redwood City, CA (January 15, 1993) was packed full of great sessions. Right out of the can in the cryptographer's track was Dr. Martin Hellman presenting a talk entitled DES Revisited. The Data Encryption Standard (DES) was first approved in January 1977, so it is now 16 years old. NIST did approve extending it at least once since then, but Rthe DESS (as crypto insiders seem to refer to it) is due for a look-see. Since Dr. Hellman has been involved with DES from its beginning, I trust his critical academic appraisal - especially since he and Whit Diffie were embattled with NBS over questions of key size and the existence of trap doors when DES was being introduced. In the question of DES breakability, I like his approach. They designed an attack on DES that is based on the most intensive cryptanalysis: exhaustive search. The beauty of this theoretical DES solution machine is that is can be used for plain text, ciphertext and chosen text attacks on the algorithm. Solve the hardest problems first and the easy ones follow quickly, I say.
He presented their 1976 design for an exhaustive DES solution engine and updated it to 1993. Since the DES algorithm is roughly equivalent to 6,000 gates, it is about the complexity of a Z80 microprocessor to implement in silicon. DES uses a 64 bit key with 8 bits reserved for parity and that means that there are 2**56 (10**17) possible DES keys for any given DES encoding. Building the exhaustive search machine in 1976 would have required 1,000,000 special DES search engine ICs and would have cost $20 million. Today, this would be10,000 special DES search engine ICs since IC's are about 100x denser than in 1976. Dr, Hellman points out that the $20M cost figure has been criticized as optimistic and he indicates that his estimate may have been a bit low. $50M is a safer figure and doesn't change his basic argument about how you go about breaking the DES. In 1976, their solution machine yielded one DES solution per day at a cost of $10,000 each. Updating this to 1993 costs and computing speeds, the capital cost of such an exhaustive search DES solution machine that would yield one DES solution per day would be between $1 and $10 million dollars. This nets a cost per DES solution of only $100. Dr. Hellman points out that the $10M figure is a relatively safe one that includes the design cost. The $1M figure is optimistic if it includes design cost, but is safe if it is the replication cost after design. This, should one want to build more than one machine - quite possible depending on who one is and how many messages he would like to read. He also indicated the replication cost might go as low as $100k per machine. The $100 figure per solution was an order of magnitude estimate. It could be as high as $1,000 (using the $10M figure) or as low as $10 (using the $100k figure).
Such a special DES search engine ICs would be about as complex as a modern 386 microprocessor and cost about as much as a Z80 to design. The whole machine has 10,000 such search chips. The reason: the 1976 design (comparable to a Z80) is replicated 128 times on the chip, but only needs to be designed once. Using 128 search engines per IC (plus spares) and a common data bus (considering the very low I/O level), the DES solution machine has only about 10,000 ICs. Past the fascinating technical details of his machine were his summary comments about DES. It has many honors: world's most widely used, cheapest and public cryptosystem. Despite major incentives, it has not been publicly broken. For those who remember him as a combatant 15 years ago, it might be helpful to mention that he indicated that he has recognized that in the heat of previous battle, he tended to overlook arguments that supported NSA/NBS and was trying now, with the benefit of age and a relative peace, to summarize the pros and cons in a more unbiased fashion.
His concerns: 1) the 56 bit key size allows exhaustive searches by dedicated opponents at a capital cost of between $1 and $10 million, 2) Biham and Shamir's differential cryptanalysis can break an 8 round DES implementation and 3) DES's design principals are secret (despite the fact that the algorithm itself is public) and may allow trap doors. His conclusions: there is probably no trap door in DES, but the 56 bit key size and decades of experience in production cryptanalysis probably give the NSA and its foreign counterparts a crude trap door. According to Dr. Hellman, this needs a bit of explanation since these two ideas two sound counter to one another. He indicated that, while he was very concerned about a possible trap door in the 70's, direct denial of NSA pressure on S-box design from relevant IBM personnel caused him to doubt their presence for some time. However, he says he could be wrong, hence the "may allow" in his statement about possible trap doors. The key appears to be that it is all speculation since the design principals of DES (not the algorithm itself) are carefully guarded. In summary: DES protected data is probably secure against all commercial attacks today, but is almost surely vulnerable to attack by a major power. DES will continue to dominate the market for a decade. He recommends immediate triple encryption (the use of a 48 round algorithm - Rstandard DESS uses a 16 round algorithm.) to defeat differential cryptanalysis. Continued federal support of DES is critical to vendors and users.
In the end, he admonished NIST/NSA to stop dragging their feet on a public key exchange standard but suggests that perhaps a de facto standard is better (in which case it doesn't matter if NIST/NSA do anything since RSA and Diffie-Hellman are filling this de facto role). Adding some humor, he softened the harsh "dragging their feet" in his talk by noting that NIST's Dennis Branstad credited his ruckuses for two promotions and indicated that Branstad had asked him to help him with a third. As is usually the case, the hallway conversations were best. We speculated on cheap DES solution machine technology. The fact is that for about $5,000 you can buy a gate array programmer and at a cost of about $250 per part, you could build your own DES solution machine without the cost and complexity of a custom silicon implementation. Scary, huh? Yes. But, the higher higher cost per part translates into a higher cost per solution so you'd have to check the speed, density, etc. and see what the associated cost would be.
I asked Hellman how in the hell a layman could possibly keep up with this crypto technology and come to trust it. His answer was revealing: read and study it - get politically involved and, it will yield to your efforts. He suggests that you contact your congressional rep and let them know you are unhappy at DoD (NSA) messing around with your personal privacy (e.g. medical records are protected by DES) when Commerce is supposed to be setting standards with regard to commercial and individual needs, rather than NSA's needs. He said that a reasonably trained EE or CS type can understand the technical details and you have a responsibility to help keep the technology on track and to help answer some of the hard questions surrounding its use. Go find a trusted member of the community to talk with about these important issues.
We also had a spirited discussion of Dr. Hellman's involvement with the Russian Institute for Problems of Information Transmission (IPPI after the Russian name Institut Problem Peredachi Informatsii) in his efforts to help some old friends of his and help the budding democratic movement in the former Soviet Union. I agree with him that we need to help them. I was comforted to find that this world-class crypotgrapher is quite a humanitarian. I agree that we do have a responsibility to help - lest we see our technology (such as cryptography) protect and nurture backward and barbaric customs. Consider that white supremacist groups such as the KKK and the Aryan Nation are a similar threat to our humanity right here in our own back yard. Heady stuff. The IPPI is interested in hard currency (e.g.: dollar vs. ruble) contracts for work. They are reported to be quite a bit less expensive that other alternatives. If you are interested in hiring them, you can contact Deputy Director Dr. Josef Ovseyevitch at IPPI via Email at ovseev@ippi.msk.su. They are interested in error correcting/detecting codes, data compression, crypto, signal processing, computer and communications networks, computational linguistics and machine translation, and experimental data processing.
My thanks to Dr. Hellman for help in writing up this account of his talk and to Jim Bidzos from RSA for inviting Dr. Hellman to speak at the RSA Data Security Conference.
A lawyer who specializes in data privacy and security law should be as easy to find as when cybersecurity issues arise. This legal field is rapidly growing to combat cyber crime.
Copyright Ray Kaplan 1993 - All rights attempting to be reserved. Ray Kaplan is a principle in the Tucson, Arizona-based independent consulting firm Kaplan, Kovara and Associates. They specialize in systems and network management, and security with an emphasis on Open VMS, UNIX, DECnet and TCP/IP. They are currently producing a series of audio teleconferences on contemporary security-related topics. For a catalog of their offerings, contact them at P.O. Box 42650 - Tucson, AZ 85733 - FAX (602) 791-3325 - (602) 885-2807. They'll be conducting live audio teleconferences on encryption and authentication which will include a live interviews and Q/A sessions with Dr. Hellman and other experts on April 7 and 8, 1992.
