The new Cray and Unix passwords

[David Farber <farber () central cis upenn edu>]

Date: Fri, 19 Aug 1994 19:29:19 -0400
From: pcw () access digex net (Peter Wayner)


There has been a bit of news in the business sections about the new NSA
contract given to Cray to develop a hybrid machine that combined the
best of the old Cray vector approach with the best of the old Thinking
Machine CM-1/CM-2 architecture. It is somewhat ironic that this was
released in the same time frame that Thinking Machines went into Chapter
11, but it may turn out that this marriage really brings out the best
in both approaches. Some of the news stories concentrated on the
quasi-Chrysler-like bailout of an important technological treasure,
but that is a question for political scientists who cleave to moldy debates
about the relationship between private enterprise and the state.


The biggest question for citizens of the techno-tribe of cyberspace, though,
is what does this mean for digital privacy. Will the NSA be able to crack
passwords with abandon? Will they be able to cut through the protection of
DES like it was butter? Any speculation is, of course, pure speculation.
But it is possible to make some educated guesses about the machine.


News reports and other research states that this machine will include 512,000
processors that contain 256 bits of memory apiece. Each processor contains
an ALU and three one bit registers. It really isn't a processor as much as
a programmable logic gate that will take three inputs and spit out one of
the 8 possible outputs. The architecture is supposed to borrow heavily from
a neat machine called the Processor-In-Memory (PIM aka TeraSys) developed
by the Supercomputer Research Center, a semi-public branch of the NSA.


I happened to play with a very similar architecture several years ago
developed by a company called Coherent Research Inc in Syracuse, NY. It turns
out that it does a pretty good job of breaking DES.  One hypothetical machine
with 1 billion processors should be able to test all 2^(55) possible keys for
DES in 1 day.


How long should it take the Cray/SRC? The Cray/SRC processors are supposed to
run at 2.08 ns/cycle. The Coherent Chips ran at 50MHz or 20 ns/cycle.  This
means the Cray/SRC is about 10 times faster. This is a very rough estimate,
though, because it is not clear how many cycles it takes the Cray to complete
each operation. The Coherent Processor took 2-4 cycles per operation. This
would imply that the Cray/SRC could knock off all 2^{55} possible keys in 100
days.


Given that DES may still be used extensively in financial transactions that
move billions of dollars, it becomes clear that it might be worth it to
spend $10 or so million on a machine and let it crank for a bit. (That's my
wild estimate on the price. I think it could be as low as $2-3 million).


But even if most of us don't have $100 million to steal, we still have
reason to wonder about the effects of this machine. UNIX security systems
use DES to encrypt the passwords 25 times before comparing them to a
encrypted version stored in the central password file. A popular attack on
the systems is to grab this central file and encrypt all of the words in
the dictionary looking for a match. This is easy to do with a garden
variety RISC machine today which is why many decent system administrators
require gibberish passwords with numbers.


How long would it take to attack gibberish passwords with this new
Cray/SRC? I extrapolated some earlier work of David Feldmeirer and Phil
Karn to show that a 64k processor version could knock off all 6 character
passwords in about half of a day. (6 characters drawn from the set
A-Z,a-z,0-9) If the 512k processor Cray/SRC can really run 10 times faster,
then it could knock off these 6 character passwords in less that 15
minutes. All seven character UNIX-style passwords would take less than 2
days and all eight could searched in less than four months.


There is one interesting side-effect of this approach. It takes about the
same amount of time to attack 1000 passwords as it does to attack 1. After
the 512k processors complete their encryption, they check to see if they've
got a match. The encryption process was about 10,000 times slower than the
matching on my design. So if you could grab a password file for a computer
with 1000 users it would still take you about 15 minutes to find the one
sucker with a 6 digit password.


This means that even the maximum-sized 8-character UNIX-style passwords are
really on the edge of obsolesence. It is really time for a new system to be
developed.  16 characters might be best. But who can remember that many?  Sure
some know millions of digits of pi, but a bunch of politicians tried to
shorten it to plain 3.  This means we need to rethink many of the modes of
protecting machines.


   [I presume that when Peter wrote "a plain 3" he was implying just 3
   digits, as opposed to the old mathematical physicists' joke about pi
   being equal to 3 for small values of pi and large values of 3.  PGN]


All of what I've written falls into the realm of informed speculation. You
can read about my design in a paper which was presented at Crypto 92. Mail
me if you want a TeX version of it. I suggest that you dig up conference
proceedings about the PIM/Terasys machine to get a better estimate of the
new Cray/SRC's machine's performance.