Channels ▼
RSS

Security

The Twofish Encryption Algorithm

Source Code Accompanies This Article. Download It Now.


Dec98: The Current State of DES

Dr. Dobb's Journal December 1998

The Current State of DES


DES is the Data Encryption Standard, the current standard encryption algorithm. On July 17, 1998 the Electronic Frontier Foundation (EFF) announced the construction of a DES brute-force hardware cracker (http://www.eff.org/ descracker/). This $220,000 device can break a DES key in an average of 4.5 days.

The news here is not that DES is insecure, that hardware algorithm-crackers can be built, nor that a 56-bit key length is too short; cryptographers have been saying it for years. Technological predictions made about the declining costs of such a machine, made in the late 1970s, the 1980s, and the early 1990s, turned out to be dead-on.

The news is how long the government has been denying that these machines were possible. As recently as June 8, 1998, Robert Litt, principal associate deputy attorney general at the Department of Justice, denied that it was possible for the FBI to crack DES. "[It is a myth that] we have supercomputers that can crack anything that is out there," Litt said. "Let me put the technical problem in context: It took 14,000 Pentium computers working for four months to decrypt a single message...We are not just talking FBI and NSA [needing massive computing power], we are talking about every police department." (See the full story at http://www.wired.com/news/news/politics/story/12830.html.)

My comment was that the FBI was either incompetent, or lying, or both. No one uses Pentiums to break DES, except as a demonstration. Anyone could have told Litt that.

EFF's machine is not innovative engineering. It is not state-of-the-art cryptography. It is not cutting-edge technology. The machine uses old, boring chip technologies, simple hardware design, not-very-interesting software, and no cryptography. This is not a marvel of engineering; the only interesting thing is how straightforward the design really is.

Moreover, the machine scales nicely. EFF spent $220,000 on its first machine. They can spend another $220,000, and the double-sized machine will run twice as fast. Now that the basic design work is done, implementation improvements and performance tweaks can increase the performance (or decrease the price) by at least a factor of five. And Moore's Law predicts that the same machine will be either twice as fast or twice as cheap in another 18 months.

The EFF machine broke DES, but it could just as easily have been designed to break any other encryption algorithm. The attack was against the key length, not against the algorithm design (see http://www.counterpane.com/keylength .html). Moreover, a slightly more expensive design would have used FPGAs, allowing the system to work against a variety of algorithms and algorithm variants.

The only solution here is to pick an algorithm with a longer key. DES has a fixed 56-bit key. Triple-DES has a 112-bit key; there isn't enough silicon in the galaxy or enough time before the sun burns out to brute force triple-DES. DES-X and XORing additional key blocks before the first round and after the last round add considerable security to DES, and is much cheaper than triple-DES.

The EFF is a civil liberties group, and this was just a demonstration project. Government agencies like the FBI and the NSA would presumably spend a lot more time engineering a more efficient solution. It is reasonable to assume that any country with an intelligence budget has built this sort of machine, probably one a couple of orders of magnitude faster.

There are undoubtedly many, many technical improvements that can be made to the EFF design to make brute-force search cheaper and faster. But the fact that a civil liberties group can use old technology to build something that the administration has denied can be built -- that's the real news.

-- B.S.


Copyright © 1998, Dr. Dobb's Journal

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video