The New York times
Friday, July 17, 1998

U.S. Data-Scrambling Code Cracked With Homemade Equipment

by John Markoff

SAN FRANCISCO -- In a 1990s variant of a John Henry-style competition between man and machine, researchers using a homemade supercomputer have cracked the government's standard data-scrambling code in record time -- and have done it by out-calculating a team that had harnessed thousands of computers, including some of the world's most powerful.

That breakthrough, in a contest sponsored by a Silicon Valley computer-security software company, is being hailed by critics of U.S. export policy for data-scrambling technology as proof that a well-heeled group of terrorists or other criminals could easily break the code used by many banks, financial institutions and even government agencies.

The government has long sought to keep the most powerful scrambling, or encryption, software out of the hands of foreign criminals or terrorists by setting limits on the strength of such software that can be licensed for export. Critics of that policy have argued that not only is more powerful encryption technology already available from foreign producers, but the government-approved version is too weak to truly protect legitimate business users.

The code was cracked using a mere $250,000 worth of equipment.

The type of encryption that was broken, known as DES, for Data Encryption Standard, has traditionally been used by banks and other financial institutions for protecting the transmission of funds and other transactions requiring high security. It has also been used in certain instances by the U.S. military. The form of DES that was broken uses a 56-bit key, far more secure than the 40-bit keys that the government allows to be exported.

Because of concerns about security, however, many business users are increasingly employing a more robust form, called Triple DES, in which the length of the digital key that unlocks the scrambled data is only three times as large but exponentially more secure. Triple DES has never been broken.

"This is more evidence that the government's crypto policy has been overtaken by technology", said Marc Rotenberg, director of the Electronic Privacy Information Center, a privacy-rights group in Washington. "It's about time to end the limits on strong encryption techniques."

The winners of the $10,000 prize -- given by the contest's sponsor, RSA Data Security Inc. -- were John Gilmore, a computer privacy and civil liberties activist, and Paul Kocher, a 25-year old cryptographer who has gained notoriety in recent years for clever attacks on security systems, including those designed to protect smart cards and Internet software.

Gilmore and Kocher were able to unscramble the key to unlock and read a single block of scrambled data in 56 hours. Their home-made machine beat a network of almost 20,000 computers, ranging from desktop PCs to multimillion-dollar supercomputers working cooperatively in a scheme known as distributed processing.

Under almost all encryption schemes, each message is scrambled in a different way. Thus, breaking the key to the contest message did not give them access to other messages scrambled with DES.

The government has long asserted that it would not be possible for a terrorist or other criminal group to design and make a computer capable of cracking DES.

To prove that building a supercomputer would be within the means of many sinister groups, Gilmore assembled his computer for $250,000 from thousands of customized chips capable of testing more than 90 billion different keys each second.

"The real news here is how long the government has been denying that these machines were possible", said Bruce Schneier, a cryptography consultant and president of Counterpane Systems in Minneapolis.

The effort was financed by the Electronic Frontier Foundation, a San Francisco-based civil liberties and privacy organization that has sparred with government and industry over the impact of new technologies on traditional civil liberties.

Gilmore, who was a co-founder of the foundation and who for years has been active in promoting privacy and civil liberties issues on the Internet, was the first employee of Sun Microsystems Inc., a computer company founded in 1984. In recent years he has been an outspoken advocate for traditional privacy rights in cyberspace, which he believes are threatened by the potential for government abuse of powerful new technologies.

The computer was designed by Gilmore and Kocher, who ultimately assembled a team of about a dozen computer researchers to build the machine from more than 1,000 chips, each designed to test millions of the mathematical keys that can unlock a scrambled message.

The chips and the circuit boards on which they were mounted -- 27 boards each holding 64 chips -- were installed in several old Sun computer chassis. The boards were linked by a simple cable to a standard personal computer that controlled the entire process.

In recent years the growing power of personal computers and the ability to hook inexpensive computers together has made cracking DES far less daunting to organizations with limited resources.

In 1997, RSA Data Security Inc., a Silicon Valley software company, offered a prize to the first person or organization that successfully cracked a DES scrambled message. The prize was claimed within five months by a loosely connected group of computers scattered around the Internet. In early 1998, the prize was offered again, and it was claimed in 39 days.

Gilmore named his custom chip Deep Crack, a tongue-in-cheek allusion to IBM's chess-playing Deep Blue. Each Deep Crack chip is a collection of 21 special units capable of performing a DES encryption on a character millions of times a second. After each unit completes a scrambling operation it checks its result against a table to determine if it has found an "interesting result" -- that is, a letter or a number that could possibly be part of a complete message.

On Wednesday evening, after checking billions of keys, the computer was able to determine that the message that had been hidden by the RSA judges was: "It's time for those 128-, 192-, and 256-bit keys."

To unscramble the message, it had to try 17,902,806,669,197,312 keys, or about 25 percent of all the possible combinations.

Copyright © 1998 by The New York Times Company. All Rights Reserved. Reprinted with permission.