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"