[FYI] Subject: PixelFlow Cracks Codes

[Horns@t-online.de (Axel H. Horns)]

http://jya.com/pixelflow.htm

--------------------------------- CUT -------------------------------

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.

-- 
Eric Michael Cordian 0+
O:.T:.O:. Mathematical Munitions Division
"Do What Thou Wilt Shall Be The Whole Of The Law"

--------------------------------- CUT -------------------------------