File: c50-faq.html

package info (click to toggle)
crack 5.0a-19
links: PTS, VCS
area: main
in suites: forky, sid
size: 9,248 kB
sloc: ansic: 7,445; perl: 1,375; sh: 1,066; makefile: 216
file content (582 lines) | stat: -rw-r--r-- 16,707 bytes
parent folder | download | duplicates (9)
<HTML>

<HEAD>
<TITLE>Crack Password Cracker FAQ</TITLE>
</HEAD>

<BODY BGCOLOR=#FFFFFF>

<HR>
<H1>FAQ for Crack v5.0a</H1>
<I>
Copyright (c) Alec Muffett, 1999, 2000, 2001 <BR>
Revised: Wed Mar 21 02:38:38 GMT 2001
</I>

<P>

<HR>
<H1>Download</H1>

<UL>
<LI><I>Where can I go to download Crack?</I>
<P>

Last time I checked: (12 June 2000) <BR>

<A HREF="ftp://ftp.cerias.purdue.edu/pub/tools/unix/pwdutils/crack">ftp://ftp.cerias.purdue.edu/pub/tools/unix/pwdutils/crack</A><BR>
<A HREF="ftp://ftp.cert.dfn.de/pub/tools/password/Crack/">ftp://ftp.cert.dfn.de/pub/tools/password/Crack/</A>
<P>

With more dictionaries/wordlists available at: <BR>

<A HREF="ftp://ftp.cerias.purdue.edu/pub/dict">ftp://ftp.cerias.purdue.edu/pub/dict</A><BR>
<A HREF="ftp://ftp.ox.ac.uk/pub/wordlists">ftp://ftp.ox.ac.uk/pub/wordlists</A>
<P>

A PGP signature to validate the contents of any download you might find, is
<A HREF="c50a.tgz.asc">available here</A>. My key is on the keyservers.

<P>

<LI><I>Can you send me the README for Crack?</I>

<P>

Better yet, there's a copy of it <A HREF="c50a.txt">right here</A>.  Read it yourself.

<P>

<LI><I>I can't download Crack!  Will you please e-mail it to me?</I>

<P>

Sorry, but no.  It's too big for me to be mailing it to people who
invariably then tell me that it's in the wrong format for them anyway,
or who want to use it on Microsoft Windows.  (see below)

<P>

</UL>

<HR>
<H1>Trolls <A HREF="crack-users.txt">[MORE]</A></H1>

<UL>
<LI><I>How can I run Crack on a Win98/WinNT/MS-DOS system?</I>

<P>

You can't.  Crack is Unix software, written for Unix systems and
running primarily <b>on</b> Unix systems, and if you don't know what
Unix is, then you don't need to know about Crack.

<P>

<LI><I>Can you hack this guy's account/password/computer for me?</I>

<P>

Probably, but I am not going to; now be a good little trog and run
along and report yourself to your local police authorities, please...

<P>

<LI><I>Can you give me a Crack for TombRaider/Carmageddon/FinalFantasy?</I>

<P>

Oh, go away and get a life, you horrible little oik.

<P>


<LI><I>H3Y D00D - WAr3 KaN 1 BuY CRACK?!?!!</I>

<P>

I am reliably informed that the answer to this is <I>"any
street-corner in Oakland"</I> - but being based in the UK I cannot
vouch for the accuracy of this statement.

<P>

</UL>

<HR>
<H1>Technical</H1>

<UL>

<LI><I>When I run Crack, it says "Done." and exits immediately, and
there are no results when I run the Reporter script; why is
this?</I>

<P>

<TT>Crack</TT> is an unusual Unix program - it runs the actual cracking process
in the "background"; when you type:

<P>

<PRE>
 Crack passwd.txt
</PRE>

<P>

...or whatever, the <TT>Crack</TT> wrapper-script launches a
background process called <TT>crack-pwc</TT>, and it is <I>this</I>
which guesses passwords.

<P>

It is <TT>crack-pwc</TT> that will run for a long time, and if you do:

<P>

<PRE>
 ps -auxww <I>...or...</I>
 ps -ef
</PRE>

<P>

...after running <TT>Crack</TT>, then you should see a copy of
<TT>crack-pwc</TT> running merrily in the background; ideally you
should only have 1 copy of <TT>crack-pwc</TT> running, for each CPU in
your machine.

<P>

<LI><I>How long does crack-pwc run for?</I>

<P>

Hard to say, since this will depend upon the number of passwords that
are being cracked, and the speed of your machines.

<P>

The short answer is: <I>at least hours, probably days, possibly weeks.</I>

<P>

The longest single continuous <TT>Crack</TT> run I have ever done, lasted a
little under seven months non-stop on a little-used Sun 4/330, back in
1991.  With faster CPUs available nowadays, things are less-bad.

<P>

<LI><I>How do I add a list of my own words to the Crack dictionaries?</I>

<P>

Move the file containing the list of words into the <TT>dicts/1</TT>
directory and do <TT>make rmdict</TT> in the <TT>Crack</TT> home
directory; the words will be merged, the next time you run
<TT>Crack</TT>.

<P>

That's all you have to do; you may choose to <I>compress</I> or
<I>gzip</I> your wordlist file, if you like - <TT>Crack</TT> will
automatically unpack it when it needs it - but it is not essential.

<P>

<LI><I>What are all the ".dwg" extensions on the Crack dictionary
files for?</I>

<P>

<TT>Crack</TT> has a custom, built-in dictionary compression tool
called DAWG (Directed Acyclic Word Graph) which preprocesses sorted
lists of words to remove redundancy and make tools like <I>gzip</I>
more effective.

<P>

Don't worry about it - it's not something that's likely to ever be
needed by you in normal <TT>Crack</TT> usage.

<P>

<LI><I>Where can I get more wordlists?</I>

<P>

Last time I checked: <BR>

<A href="ftp://ftp.ox.ac.uk/pub/wordlists/">ftp://ftp.ox.ac.uk/pub/wordlists/</A>

<P>

<LI><I>On RedHat-based Linux distributions, Crack doesn't run, and I
get messages like this:</I>

<P>

<PRE>
 ../../run/bin/linux-2-unknown/dictfilt dictfilt.c elcid.o
 .../../run/bin/linux-2-unknown/libc5.a
 cc: elcid.o : No such file or directory
 make[1]:***[../../run/bin/linux-2-unknown/dictfilt] Error 1
 make[1]: Leaving directory `/crack/c50a/src/util'
 make[1]:*** [utils] Error 1
</PRE>

<P>

It's a known problem: unfortunately the crypt() routine has now been
unbundled from <i>libc</i> in many operating systems, and linkers tend
to be more strict (or perhaps boneheaded?) than they used to be.

<P>

Here is a <A HREF="c50-linux-util-makefile.txt">replacement</A> for
<tt>src/util/Makefile</tt> which <i>should</i> alleviate the problem.
Like all Makefiles, it requires preservation of its TAB structure to
work properly, so if your "make" program complains about:

<P>

<tt> *** missing separator. Stop.</tt>

<P>

...or similar, please try <b>saving the file properly using your
browser function</b>, and not just cutting and pasting out of the
browser window.

<P>

<LI><I>I want to produce reports of crackable passwords which do not
actually contain the plaintext password itself.  How do I do
this?</I>

<P>

This is easily achieved by tweaking the "Reporter" script in Crack5.0;
a little examination of the code, and it should be obvious what to do.

<P>

<LI><I>I want to compose my own rulesets; where can I find documentation?</I>

<P>

Documentation on the rulesets is a bit scanty, but this
<A href="c50-rules.txt">file</A> should be of help.

<P>

<LI><I>I want to use Crack to check users' passwords when they are
changing them; can I do this?</I>

<P>

Yes, however you ought to be looking at my <TT>CrackLib</TT> software
which does this, and not <TT>Crack</TT> itself.

<P>

<LI> <I>Crack 4.x used to have this really neat feature where it would
store passwords that it had <B>not</B> managed to guess, and it would
not bother to attack them again next time.  Why doesn't 5.x do this?
I want this functionality back! </I>

<P>

I removed this functionality because many Crack users were not
bothering to clear out the history of so-called <I>"unguessable"</I>
passwords every few months; the point was that a password that was
<I>unguessable</I> one month, might become <I>guessable</I> the next
month, when other updates/additions might have been added to the
password map, providing more guessing material for Crack.

<P>

People who want to reduce Crack runtime by only running it against new
additions and changes to the password file, are encouraged to explore
the opportunities that are afforded by the Unix commands <TT>sort</TT>
and <TT>comm</TT>, which can enable equivalent functionality in a
matter of seconds.

<P>

Keeping a <TT>sort</TT>ed copy of the last password file you cracked,
and running <TT>comm</TT> against it and a <TT>sort</TT>ed copy of the
new password file, will print any differences.  Save these, and run
Crack on that data.

<P>

Users are still recommended to try Cracking the whole password file,
in one big chunk, changed or unchanged, at least occasionally.
<P>

</UL>

<HR>
<H1>Miscellany</H1>

<UL>

<LI><I>Is Crack supported?</I>

<P>

I fix bugs as/when I may, and occasonally post new revs to the net.
Given how stupid people generally are regarding computer security, I
can forsee doing this until the day I die.  I can usually be persuaded
to answer questions for beer.

<P>

<LI><I>Is Crack Y2K Compliant?</I>

<P>

Probably.  If it isn't, I am sure I'll find out eventually.

<P>

<LI><I>We'd like to use Crack for inclusion in a commercial product or
software distribution; is that OK?</I>

<P>

Please ensure that you have read the software LICENSE file, and
double-check with me via e-mail if necessary.

<P>

<LI><I>We'd like to license Crack for inclusion in a commercial
product; we'd like you to sign this disclaimer and contract and
mail/fax it back trans-atlantic to our legal department in California,
because it's obviously to your benefit that you do so.</I>

<P>

Thank you for the contract documents.  I shall frame them and put them
on the wall with the others in the toilet.  Now kindly go read the
LICENSE file, and e-mail me if you have any questions, although be
aware that your response may be delayed by my rolling on the floor in
hysterical laughter.

<P>



<LI> <I>Would you consider enhancing Crack to run {on a cluster, in an
SMP or threaded environment, using MPI, PVM, POSIX threads, or alike}?</I>
<P>

Ah, this old chestnut; there is a note in the Crack5 distribution
about this.  Basically: because of the nature of the data being
cracked, there is no real advantage in threading the code.  It's
easiest as one-process-per-CPU.
<P>

Consider: most of the point of threading and/or vector operations
and/or parallelisation is to take advantage of many/optimised CPUs to
do the same computational task in parallel/simultaneously/in one
operation.
<P>

The function of Crack is to try as efficiently as possible (ie: once
only) each of several million possible password guesses against the
distinct ciphertexts of several thousand users.
<P>

<B>ie:</b> to do several billion computationally *distinct* things.
<P>

It is (regrettably) in the nature of cryptography that generation of
each password hash (ie: call to <TT>crypt()</TT>) is of a
mostly-computationally-distinct nature, and that the only way to use
parallelization to speed this up would involve writing a highly
architecture-specific parallel-<TT>crypt()</TT> implementation, which
is not economically viable to create when compared to equivalent
serial password-cracking programs.
<P>

in short: if a one woman can make a baby in nine months, this does
*not* mean that nine women can make one baby in one month.
<P>

instead: nine women make nine babies in nine months, and all of those
nine babies arrive simultaneously at the *end* of the nine months.
<P>

of course, if we *could* parallelise baby-creation, we would get one
baby per month for nine months, but the problems of locking, surgery,
gene-splicing and baby-fragment-reassembly would drag down the time,
raise overheads and costs, and in the end yield exactly the same end-result as
the serial-baby-creation-method.  8-)
<P>


<LI> <I>Oh go on - surely there must be some way to parallelise
cracking operations? </I>
<P>

Well, it depends on what I/you mean by "making it parallel"; if by
that you mean "creating a password hashing algorithm that makes
effective use of multiple CPUs to speed the essentially linear
<TT>crypt()</TT> mechanism" - then no, I don't believe it'd be viable
(without specialist hardware) because the process of getting a
password from an un-hashed state (say: Utah) to a hashed one (say:
California) is most quickly achieved by dropping the data onto a
single CPU (say: a Porsche 911) and driving non-stop.
<P>

The only overhead here is (of course) in tuning your algorithm for
your specific CPU architecture, to most closely resemble a Porsche 911.
<P>

Nowadays, with locking overhead and synchronisation, using traditional
multi-cpu parallelisation and threading would be more akin to
hitch-hiking the length of the trip.
<P>

That said: there exists a technique called "bitslicing" which alas is
complicated to do unless you're a crypto geek, but which basically
involves packing as many people as feasible into your Porsche and
occasionally stopping in order to rotate their positions.
<P>

In other words: on a 32-bit architecture you use bit-1 of your
datapath to do encryption operations that are pertinent to one
encryption, and you use bit-2 in order to do a second, bit-3 in order
to do a third, and so forth, achieving parallelism of up to 32
crypt-calls this way...  on a 64-bit architecture, of course you do 64
at once.
<P>

<I>(This technique was first written up by Biham several years ago,
but I may have thought of the idea first, though I never managed to
finish implementing it.  I called the idea "polycrypt", conceived on a
bus trip returning from a bash in London with Paul Leyland, and it was
the main reason that I introduced the ELCID interface into Crack5; the
date on my code is mid-1994 but i don't know when the bitslicing paper
was conceived.  Either way, I never did anything with it - I got
swamped by what to do with S-boxes - so what the hell...)</I>
</I>
<P>

You may realise now why I got out of the business of binding a
specific crypt() algorithm into Crack as early as possible.
In-between this sort of bit manipulation and/or issues of pipelining,
branch-delay slots, and use/avoidance of bizzare multimedia CPU
instructions to do the hard work for you in hardware, I came to
conclude that hacking crypt() routines was a game for masochists.
<P>


<LI><I>How does the DAWG dictionary-compression algorithm work?</I>
<P>

Essentially it is a preprocessor for <TT>gzip</TT> that removes
redundancy from a sorted list of words, and typically shrinks an input
wordlist by some 50% without negatively impacting <TT>gzip</TT>'s
ability to further compress the file.
<P>

In the new version of the DAWG code - slightly improved over the
version that ships with Crack v5.0, but fundamentally the same -
all you need do is:
<P>

<OL>
<LI> sort the wordlist into normal Unix order.  (beware localization!)
<LI> for each word that the DAWG preprocessor reads...
<LI> count how many leading characters it shares with the previous word that was read...
<LI> encode that number as a character from the set <TT>[0-9A-Za-z]</TT> for values 0..61
     (if the value is >61 then stop there)
<LI> print said character (the encoded number) and the remaining stem of the word
<LI> end-for-loop
</OL>
<P>

eg:
<P>

<TABLE BORDER=1> <!-- cols=1 rows=6 -->
<TR ALIGN=LEFT VALIGN=MIDDLE> <!-- row 1 -->
<TD> <TT>foo</TT> </TD>
</TR>
<TR ALIGN=LEFT VALIGN=MIDDLE> <!-- row 2 -->
<TD> <TT>foot</TT> </TD>
</TR>
<TR ALIGN=LEFT VALIGN=MIDDLE> <!-- row 3 -->
<TD> <TT>footle</TT> </TD>
</TR>
<TR ALIGN=LEFT VALIGN=MIDDLE> <!-- row 4 -->
<TD> <TT>fubar</TT> </TD>
</TR>
<TR ALIGN=LEFT VALIGN=MIDDLE> <!-- row 5 -->
<TD> <TT>fub</TT> </TD>
</TR>
<TR ALIGN=LEFT VALIGN=MIDDLE> <!-- row 6 -->
<TD> <TT>grunt</TT> </TD>
</TR>
</TABLE>
<P>

compresses to:
<P>

<TABLE BORDER=1> <!-- cols=2 rows=7 -->
<TR ALIGN=CENTER VALIGN=MIDDLE> <!-- row 1 -->
<TD ALIGN=LEFT> <TT>#!xdawg</TT> </TD>
<TD> <i>magic header</i> </TD>
</TR>
<TR ALIGN=CENTER VALIGN=MIDDLE> <!-- row 2 -->
<TD ALIGN=LEFT> <TT>0foo</TT> </TD>
<TD> <i>first word has no letters in common with anything</i> </TD>
</TR>
<TR ALIGN=CENTER VALIGN=MIDDLE> <!-- row 3 -->
<TD ALIGN=LEFT> <TT>3t</TT> </TD>
<TD> <i>next has three letters in common, and a 't'</i> </TD>
</TR>
<TR ALIGN=CENTER VALIGN=MIDDLE> <!-- row 4 -->
<TD ALIGN=LEFT> <TT>4le</TT> </TD>
<TD> <i>"foot" + "le"</i> </TD>
</TR>
<TR ALIGN=CENTER VALIGN=MIDDLE> <!-- row 5 -->
<TD ALIGN=LEFT> <TT>1ubar</TT> </TD>
<TD> <i>"f" + "ubar"</i> </TD>
</TR>
<TR ALIGN=CENTER VALIGN=MIDDLE> <!-- row 6 -->
<TD ALIGN=LEFT> <TT>3</TT> </TD>
<TD> <i>"fub" + "" => truncation</i> </TD>
</TR>
<TR ALIGN=CENTER VALIGN=MIDDLE> <!-- row 7 -->
<TD ALIGN=LEFT> <TT>0grunt</TT> </TD>
<TD> <i>back to nothing in common</i> </TD>
</TR>
</TABLE>
<P>

Inspiration for using DAWG in Crack came from Paul Leyland back in the
early 1990s, who mentioned something similar being used to encode
dictionaries for crossword-puzzle solving programs; we continue to be
astonished at how effective DAWG is on sorted inputs without
materially impacting subsequent compression (ie: <TT>gzip</TT>); a
gzipped-DAWG file is <I>also</I> typically about 50% of the size of
the gzipped non-DAWGed file.
<P>

Just goes to prove that knowledge of the sort of input you'll be
dealing with, can beat a general-purpose program hands-down; there are
also interesting conclusions that can be drawn regarding the entropy
of human languages after sorting.
<P>

</UL>
<HR>
<IMG SRC="/cgi-bin/webcount?length=6">
</BODY>
</HTML>