Beowulf in Enterprise Environments

Robert G. Brown rgb at phy.duke.edu
Thu Jun 19 10:08:04 EDT 2003


On Thu, 19 Jun 2003, Karl Podesta wrote:

> The author seems to be talking about parallelising the actual crypt()
> algorithm, to do a single crack accross many CPUs, and maintains it's
> like 9 women trying to produce 1 baby in 1 month :-)
> 
> So perhaps a bit of mis-information on his side about parallelising 
> operations? When he could simply run multiple instances of crack accross
> a network like you describe, a good oul bit of data/domain decomposition, 
> maybe put an MPI wrapper round it to collate results or nicey it up 
> for running it from a head node accross a cluster - that's maybe what
> people were requesting from him and he mis-understood.  

You got me.  As the crack README clearly states, it has been programmed
to run (nearly EP) over a network from very early versions of crack.
Crack works by applying rules and transformations to dictionaries to
generate a trial password, crypting the trial password, and comparing
the crypted result to the crypts in the passwd file, which is why the
crypts were split off in public-unreadable /etc/shadow and made md5 to
significantly increase the work required to generate the crypt. IIRC,
the network version works by taking the ruleset to be tested and farming
(chunks of) the ruleset out round-robin in a master-slave paradigm, in
which the slaves return all the crypt hits they encounter to the master
for cumulation.  In some ways, it is a lovely model parallel application
for relatively trivial parallelism -- a short message plus startup
overhead to get a slave going, a short (well, one HOPES short:-) return
from the slave, a whole lot of slave computation in between -- quite
similar to the way a mandelbrot set generator is parallelized but
without the baggage of PVM or MPI, scaling efficiency out to the high
90's for quite a few nodes in spite of the inefficiency of lots of rsh
spawns.

Parallelizing MD5 or libcrypt itself, well, that's just plain silly...
like parallelizing a single threaded random number generator.  Quite a
lot like it, actually.  Why, almost identical:-) Let's insert a really,
really high latency network IPC hit in between ordinary arithmetic
instructions in a single thread with innate sequential dependencies...
hmmm.

I don't know the timing because I can't remember when crack was first
parallelized, but (to come back to the original thread about enterprise
parallel applications) I'd bet that it preceded (and possibly inspired)
even the venerable RC5 challenge etc. as one of the very first if not
the first widely distributed and commonly used truly network parallel
application programs, used in many an enterprise long before the
"beowulf" per se was invented.  I have no idea if the parallelization
was done by black hats or white hats (or even both:-) -- the program was
in pretty common use by both, back in the good old days when the ypx
program could often as not provide you with a complete copy of any NIS
domain's passwd file and crack could often as not give you a half dozen
passwd hits from that file in the first four or five minutes of NON
parallel operation on a 4 MFLOP Sun workstation.  Or crackers would
snoop a passwd from a telnet or rsh connection from some grad student
logging back in to check mail over the summer and would then proceed to
copy the local passwd file (pre-shadow) to work on at their liesure.
Either you (as a white hat) ran crack on your passwd files and whomped
users who thought their userid twice or a word like "unbreakable" was a
"good password" upside the head or the black hats would cheerfully do it
for you...:-)

Needless to say, been there, coped with that.  One of many reasons I'm a
shameless advocate of eliminating rsh altogether from the world of
programming.  telnet can stay as a nice little daemon debugging tool, as
long as telnetd is staked to an anthill along with rshd...

    rgb

-- 
Robert G. Brown	                       http://www.phy.duke.edu/~rgb/
Duke University Dept. of Physics, Box 90305
Durham, N.C. 27708-0305
Phone: 1-919-660-2567  Fax: 919-660-2525     email:rgb at phy.duke.edu



_______________________________________________
Beowulf mailing list, Beowulf at beowulf.org
To change your subscription (digest mode or unsubscribe) visit http://www.beowulf.org/mailman/listinfo/beowulf



More information about the Beowulf mailing list