Here's an interesting article on how encryption works:
From U.S.News & World Report magazine.
Science 9/14/98
Jimmying the Internet
Why the U.S. encryption standard is very vulnerable
BY RICHARD FOLKERS
Encryption, the conversion of numbers or text into secure code, is much more than a cold war spy game. Today it's the province of shoppers using credit cards on the World Wide Web and corporations protecting confidential memos. From banks to brokers, businesses that transmit data across the globe via computer networks and the Internet favor moving toward a new national encryption standard that is tougher to crack. So do privacy advocates and consumer groups.
The National Institute of Standards and Technology, aware that the present U.S. standard, which dates back to 1977, is long in the tooth, late last month revealed 15 new encoding formulas, one of which will eventually be chosen by the Commerce Department as a 21st-century standard.
Law-enforcement officials don't oppose robust encryption standards; however, FBI Director Louis Freeh argues that federal law enforcement should hold the key to the code, since it could take code-breaking crime busters months, and thousands of cooperating computers, to crack just one message--at least that was the case until this summer.
In July, a group of researchers in San Francisco using a custom $250,000 computer took just 56 hours to crack the government's Data Encryption Standard (DES). The machine sorted through a little more than a quarter of a possible 72,057,594,037,927,936 DES answer keys at a rate of 90 billion per second, until it turned up the answer. Paul Kocher, 25, president of the San Francisco firm Cryptography Research, designed both the machine and its processing chips. The 1,800 chips run several times slower than those in a decent home computer, and it cracked the code by using dedicated chips, rather than pure processor speed. More money, Kocher says, could easily make a faster chip, speeding up the process. The chips try potential keys, passing on "interesting" results to computer software, which winnows out the false positives until it finds the right answer. If a message is known to be text, an "interesting" result, for example, would be one that contains letters. Previous DES crackers relied principally on software, which takes much more time. Kocher and his colleagues won a $10,000 bounty for their feat, paid by RSA Data Security of San Mateo, Calif.
Digital dough. Despite the seeming simplicity of the researchers' attack, cracking DES is extremely taxing on the brains of people and computers alike. Computers make words, pictures, and answer keys through long strings of zeroes and ones. Each "bit," the basic building block of computer language, is a zero or a one. DES encodes a message 64 bits (equal to about eight characters of written text) at a time, adding the text to the secret key and kneading them into a digital dough. Those message bits, when scrambled with the 56-bit answer key, make a seemingly unintelligible message.
In the "initial permutation," the 64 bits of a message are reordered into "left" and "right" halves. In the 16 rounds of mixing that follow, the right half is mixed with part of the answer key, then recombined with the left half, and divided again for the next round. Each time, the 32-bit right portion is expanded by 16 bits and mixed with 48 bits of the key. The resultant string of bits, containing both message and key, is divided into eight parts, which are then fed through a series of eight mathematical reference tables that mix and reduce the data, yielding eight 4-bit chunks. They are then mixed with the 32 bits of the left half. The right and left halves are swapped, and the mixing process is repeated 15 more times. At the end, with one final bit rearrangement, you have a completely encrypted message. To decode the message, perform all of the above steps in reverse. All this is repeated for every 64 bits of the message.
A cracked code. Just because Paul Kocher's team cracked the DES code, that doesn't mean that your E-mailed love letter will show up on every bulletin board in town. But it does prove that the electronic commerce system can't depend on 20-year-old encryption standards. "The government has tried to get people to use bad cryptography," Kocher says. "American infrastructure is very vulnerable to attack" from computer-savvy terrorists.
Another weakness of DES is that it relies on a "secret" key, which both sender and recipient must share. It could be delivered on paper, or both parties could agree on a secret formula, encoding the key. But if the key is stolen, encryption is useless. One solution is "public key" cryptography, in which a message is encoded with a publicly accessible key but deciphered with a key only the recipient holds. However, this cryptography is technically demanding and slower than secret-key cryptography.
Civil libertarians are fighting government access to any keys, saying it's part of a disturbing trend toward erosion of privacy on the Internet. The Russian government, for instance, is ready to implement regulations that will permit it, without warrants, to monitor all electronic mail and Internet communications. "The Russian proposal is a return to the surveillance society of the KGB," says Barry Steinhardt, president of the Electronic Frontier Foundation.
However it is to be decrypted, adding just one data bit to a message's key doubles the amount of time it takes to break the code, Kocher says. Many believe a 128-bit key, twice as long as DES, would take at least 20 years to break with today's technology. But Kocher is worried about tomorrow's computers. He warns, "To keep data secure for a very long time, you need a very long key." Or, as the message Kocher decoded read: "It's time for those 128-, 192-, and 256-bit keys." |
