FITUG e.V.
Förderverein Informationstechnik und Gesellschaft
FITUG e.V.Förderverein Informationstechnik und Gesellschaft |
|
15 January 1999
From: Eric Cordian <emc@wire.insync.net>
Subject: PixelFlow Cracks Codes
To: cypherpunks@cyberpass.net
Date: Thu, 14 Jan 1999 19:38:25 -0600 (CST)
Durham, NC -- Duke University computer science researchers found that using an experimental computer, they could "crack" within an average 3.75 hours the encryption that protects such privately held information as credit card account numbers on the Internet.
With the same equipment and "brute force" technique, Gershon Kedem, a Duke associate computer science professor, and graduate student Yuriko Ishihara of Nagano, Japan, were also able to compromise many of the more commonplace passwords that guard access to UNIX-based computer networks.
Ishihara conducted the research for her masters thesis. For more information on their technique, access their Duke website at
http://kedem.cs.duke.edu/CipherFlow/index.html
According to Kedem, computer-savvy criminals, governments, or companies embarked on industrial espionage could design, build and test even better computers to target such codes for $6 million to $10 million. Copies of such machines could subsequently be manufactured for little as $60,000, he estimated.
The pair's experimental break-ins were done with a powerful graphics computer called PixelFlow, designed by computer scientists at the University of North Carolina at Chapel Hill.
The fact that such a machine - while itself experimental but not designed to decipher secret codes -- could so easily penetrate popular security systems underscores the vulnerability of current computer encryption standards, Kedem said in an interview.
"This is a particularly serious security threat," added Kedem, whose interests include computer security and cryptography. "Statements that computer products are encrypted, and therefore are secure, should certainly be viewed with a very large grain of salt."
Kedem said Internet browsers such as Netscape Navigator and Microsoft Internet Explorer use 40-bit series of digits as the secret solutions for unraveling encrypted information. "Bit" is an abbreviation for "binary digit," the standard unit of computer information.
The identity of a solution - called the "key" - is supposed to be known only to the sender and receiver of a scrambled communication. Software manufacturers have been using the 40-bit key standard to comply with United States export restrictions, even though they know the U.S. government has powerful-enough technology to decipher it, he said.
Kedem and Ishihara proved the 40-bit key is vulnerable to more than government sleuthing by subjecting the 40-bit key to an attack with the "massively parallel" PixelFlow computer. The 18-board PixelFlow configuration they used satisfies the requirement for this type of "brute force" cryptoanalysis because it harnessed 147,456 separate processing units, all executing the same set of instructions at the same time, Kedem said.
"If you have a very fast computer like this one, you can either try and search all the possible keys and see if you can find one that matches, or at least you can search a large enough numbers of possible keys that your probability of finding the right one is reasonably high," he explained.
In the case of a 40-bit key, the total number of possibilities is 2 to the power of 40 - 2 multiplied by itself 40 times - which is 1,099,511,627,776 different combinations of 0 or 1 binary digits, he said.
The UNIX password, a more-formidable challenge, allows users to specify up to 5,132,188,731,375,620 combinations of letters, numbers or symbols. "The machine we had access to doesn't quite have enough computing power," Kedem acknowledged. "I think it would take us almost a year to break a UNIX password outright.
"But it turns out that we didn't really have to try all possible passwords, as long as we tried all likely passwords."
The most secure passwords are made up of truly random combinations, but "people are not very good at remembering a lot of random symbols from the keyboard," he added. "So most passwords are letters, usually lower case, or maybe one or two digits or punctuation marks.
"An important fact to remember is that PixelFlow was built with early-1990s technology," he said. "If that machine were reimplemented in today's technology, we could probably crack a 56-bit key in less than 10 hours."
Kedem said the United States government just announced a new policy allowing the export of encryption technology with 56-bit keys. But most banks and Internet browsers, he added, currently use shorter 40-bit private keys like those he and Ishihara cracked.
The private keys they targeted were specified by the RC4 encryption algorithm that comes with popular browser software, he said. Kedem emphasized that PixelFlow's processors "were not designed with encryption in mind," Kedem noted. "They were designed to do graphics. So they are missing some instructions that would have made them much more effective for doing cryptography.
"It should be very easy to build a massively parallel machine specifically for brute force cryptoanalysis that would make any encryption algorithm now commonly used totally insecure," he predicted.
"I would say that anything less than 80-bit keys probably could be broken," he added, noting that governments and some other security minded organizations already use still longer keys that will be immune from brute force attacks for the foreseeable future.
"It would take $6 million to $10 million dollars to develop such a machine, but the cost of each unit might end up being just $60,000 to $100,000," Kedem said. For that outlay, some unscrupulous entity with access to cash "could crack a lot of codes in practice today in the commercial world," he speculated.
Kedem said he decided to use PixelFlow to test the security of on-line encryption at the suggestion of John Poulton, a UNC-Chapel Hill computer science professor who is a major architect of the graphics computer, built in collaboration with the Hewlett-Packard Corp.