From: John Deters <jad@dsddhc.com>
Date: Thu, 18 Jul 1996 12:29:48 +0800
To: cypherpunks@toad.com
Subject: Re: Word lists for passphrases
Message-ID: <2.2.32.19960716220138.00341fec@labg30>
MIME-Version: 1.0
Content-Type: text/plain


At 10:33 AM 7/15/96 -0700, David Sternlight wrote:
>At 12:45 AM -0700 7/15/96, Bill Stewart wrote:
>>At 09:43 PM 7/8/96 -0700, ??? wrote:
>>>If the purpose is for use with "Crack" or some similar program, it might be
>>>better than you would think.  You won't get the "unusual" words, but you
>>>will also get the words in common usage that do not appear in dictionaries.
>>>(Such as fnord, jedi, killfile, and the like...)
>>
>>"fnord" is in _my_ dictionary - can't you find it in yours?  :-)
>>
>>>Another thing to look for when choosing dictionaries/wordlists for crack is
>>>not sticking to english.  If you have a userbase that is known to have a
>>>certain percentage of people of a non-english background, you will want to
>>>find lists of words from that background.  (I had a sysadmin asking me about
>>>Yiddish and Hebrew wordlists for just that reason.)  These can be a bit
>>>harder.  (Especially for unusual languages.)
>>
>>Grady Ward has his Moby Words databases with some of this kind of information.
>>In addition to the usual sets of languages, it's useful to include any
>>available lexicons of Elvish, Klingon, Unix, and other popular
>>hacker-languages,
>
>It is pretty easy to defend against dictionary attacks by using an expanded
>character set--mixed caps and lower case; numbers substituted for some
>letters according to easily-remembered personal rules.

Then I caution you to review the program 'Crack'.  Crack comes with two sets
of  rules with which it mutates the words from two separate dictionaries.
Things like:  replace 'i' with 'y', 's' with '$', 'e' with '3', change
capitalization to pattern AbCdE, etc.  Typically, there is an extensive set
of rules (I remember 47) that perform more "morphing" of a shorter "hot"
dictionary list, followed by a common subset of the rules applied to the
entire dictionary.  The shorter dictionary list I remember seeing contained
an extensive list of female first names, common computer "words" such as
foo, bar, etc., and even some Klingon and Elvish words.  These words were
subjected to extensive letter shifting, case changing, and substitutions.
The balance of the dictionary was subjected to the simpler subset of rules
(22, I believe) regarding substitution, reversal of letters, capitalizing
the first and/or last letters, suffixing a single non-alpha character, etc.

I know a rather paranoid sa who used to think he had secure passwords
because he'd look around for some "word" of some random object nearby, then
transmogrify some letter (typically substituting 'y' for 'i').  Crack found
him out in very short order.

The reason I post this is that these word lists are invaluable to the Crack
operator.  *ANY* knowledge that reduces the search space can render the
security useless.  For example, if a Crack operator learns that you once had
a password of "any0ne", he or she will make sure to include a rule
substituting zero for 'o' in both dictionaries, they will probably make an
effort to emphasize letter-to-number substitutions of the words in their
dictionary, and maybe even focus less (or at least test last) on other
attacks, such as case-changing or number-suffixing.  Those
"easily-remembered personal rules" to which you refer can catch you pretty
quickly.

>"Da5id" in "Snow Crash" by Neal Stephenson is an obvious example, since the
>"v" is a roman numeral 5. Another is the "Compuserve method" of inserting
>punctuation characters between words making up a password or key. Since the
>length of the words used is unknown to the cracker, this makes his job
>harder.

Harder is not NP-hard.  It's a very very long way away from NP-hard.

>That is--a dictionary which accomodates such things as the above will be
>pretty large. With the number rule, there would have to be 10 additional
>versions of the one-letter word, 10 versions of each leading character
>making up a two letter word, and then it starts increasing combinatorially.
>Might as well use brute force.

A "pretty large" dictionary is still much! smaller than brute force.  And
even if it is the precursor to brute-force, it's still a better starting
point than 
0x00000000000000, if you have reason to believe that it's based on an ASCII
password.

Just remember the old joke:  entropy ain't what it used to be.  And every
generation of faster processor that arrives makes this statement more
relevant to cryptanalysis.

John
--
J. Deters  "Captain's log, stardate 25970-point-5.  I am nailed to the hull."
+-------------------------------------------------------+
| NET:   jad@dsddhc.com (work)    jad@pclink.com (home) |
| PSTN:  1 612 375 3116 (work)    1 612 894 8507 (home) |
| ICBM:  44^58'33"N by 93^16'42"W Elev. ~=290m (work)   |
| PGP Key ID:  768 / 15FFA875                           |
+-------------------------------------------------------+