From: "Timothy C. May" <tcmay@got.net>
Date: Sat, 16 Nov 1996 14:46:17 -0800 (PST)
To: cypherpunks@toad.com
Subject: Re: Passwords as Galaxies, and Status of the Archives
In-Reply-To: <v03007804aeb31c5c2260@[207.167.93.63]>
Message-ID: <v03007801aeb3f542de2d@[207.167.93.63]>
MIME-Version: 1.0
Content-Type: text/plain


At 12:49 AM -0800 11/16/96, Lucky Green wrote:
>I think it was "Passwords are galaxies in hyperspace". I may be wrong.
>Either way, this was an excellent tread.
>

Dale Stimson found it, and sent it to me. It's included below. It dated
from June of 1995, not 1996. I don't know why I thought it did.


From: tcmay@netcom.com (Timothy C. May)
Message-Id: <199506081711.KAA09665@netcom8.netcom.com>
Subject: Passwords as Galaxies in Hyperspace
To: sandfort@crl.com (Sandy Sandfort)
Date: Thu, 8 Jun 1995 10:11:19 -0700 (PDT)
Cc: cypherpunks@toad.com
In-Reply-To: <Pine.SUN.3.91.950608081241.3725A-100000@crl12.crl.com> from
"Sandy Sandfort" at Jun 8, 95 08:41:22 am
Sender: owner-cypherpunks@toad.com

Sandy Sandfort wrote:

> I've never really questioned the statements that knowledgeable
> C'punks have enunciated about passphrase entropy.  I've just
> accepted the "rules" on faith.  I choose long "nonsense"
> passphrases with quirky spelling, characters and punctuation.

Adam Shostack just gave a good response, based on how programs like
"crack" will try various substitutions on names, common phrases, etc.

I want to give an explanation that is more "hyperdimensional" (you'll
see what I mean in a moment).

> The question I have, is "quessability" all that important a
> consideration?  For example, let us say I started out with the
> following phrase as a "seed":
>
> 	the quick red fox jumped over the lazy brown dog
>
> To convert it into a passphrase, what if I only changed "dog"
> to "d0g"?  Though it would obviously be easy for me to remember,
> I don't see how it would be any easier for an attacker to guess
> this passphrase than it would be if the passphrase were an
> equally long string of randomly generated characters.  The

Because a program can store the most common names and phrases and then
generate a whole bunch of one-character or one-word variants. That is,
the phrase above can be stored and then perhaps 1000 variants can be
tried...missing characters, "blue" instead of "brown," "snazzy"
instead of "quick," etc. This sounds like a lot of variants to try,
but remember that we're talking about a search space that is 10^75
bytes or higher! Anything that helps reduce this search space is useful.

> reason I (I'm sure naively) think this is so, is that to the
> best of my understanding, passphrases are all or nothing--you
> have to guess it 100% correctly or it doesn work.  Even if an
> attacker tries my "seed" because it is a common typing practice,
> it hardly puts him any closer to guessing which one of the
> zillions of ways I may have modified that phrase, if indeed, I
> used that phrase at all.

Oh, but it puts him a _lot_ closer!

> So I guess what I'm asking is:  if my passphrase is very long,
> and I add at least some randomness, is the fact that my original
> famous quote might be tried as part of a "Bartlet's attack, all
> that much of a threat?

Imagine all passwords and passphrases (same thing, actually) occupying
a high-dimensional space...I won't get into what the dimensions are
here--see any good book on information theory, especially Pierce's
"Symbols, Signals and Noise."

The "points" in this space are the passwords/phrases. With a
old-generation 8-character max on passwords, for example, this space
has something like 26^8 = 2 X 10^12 points in it, if only single-case
alphabetic characters are used. If both upper- and lower-case
characters can be used and standard punctuation marks can be used, the
space explodes in size to roughly 75^8 = 10^16 points.

In this space, there are "galaxies" or "clusters" of points
surrounding such points as "sandy" and "tim." Smart cracking programs
will start with thousands or even millions of these points and then
explore the "nearby" variants, as these nearby variants are what
people will often pick as passwords, thinking they are "outsmarting"
the computers!

Extending this to 30-character or even 50-character pass _phrases_ has
identical math, except the numbers are _much_ larger, and the
"universe" is much vaster.

Somewhere in that universe is the phrase "the quick red fox.....",
surrounded by a large cloud of points a short Hamming distance away:
"the quick red fob...," "the quick red fux...," etc. And in that same
galaxy, albeit a little furhter away, are the variants on entire
_words_. Still further out from the "galactic core" are such phrases
as "the quickest red cat...."

Searching in these galaxies still beats searching the entire space. In
any case, if one is to try searching the entire space, starting in the
galaxies makes more sense.

(In practice, an entire 10^75 point space will not be searched by
brute force, I am sure. And, in practice, I have no idea how far out
in the "arms" of the "galaxies" the NSA's supercomputers will
venture....)

A question one might ask is what gives "shape" to this universe? Why
do I say there's a "galaxy" of points surrounding "sandy" or "the
quick red fox...."? Why not a galaxy around "g*E@ks)hc"?

This gets to the culture-dependent aspects of "randomness" and
"entropy."

Fact is, just as Sandy thinks starting with "the quick red fox..." or
some other easily memorizable phrase is a good strategy, so too will
computers. All a matter of entropy.


I hope this explanation helps. I'm partial to geometrical and
space-oriented descriptions, and reading Pierce's explanation of
Shannon's Theorem in terms of n-dimensional spaces was one of the
highpoints of my high-school experience, lo those almost 30 years ago.

(The n-dimensional model neatly explains a lot of things, including
signal-to-noise ratios, the effects of signal power, correlation
between signals, and error-correcting codes. Great stuff!)

--Tim May



--
..........................................................................
Timothy C. May         | "I am not now, nor have I ever been, a member of
tcmay@netcom.com       |  a militia group."
Corralitos, CA         |  --Tim May's statement before the 1995 Hearings
                       |    of the House Un-American Activities Committee
The "Crypto Anarchy" sig will soon return.

"The government announcement is disastrous," said Jim Bidzos,.."We warned IBM
that the National Security Agency would try to twist their technology."
[NYT, 1996-10-02]
We got computers, we're tapping phone lines, I know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Higher Power: 2^1,257,787-1 | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."