From: Jim Gillogly <jim@acm.org>
Date: Sat, 2 Jul 94 10:01:13 PDT
To: cypherpunks@toad.com
Subject: Re: Password Difficulties
In-Reply-To: <199407020841.AA23083@world.std.com>
Message-ID: <9407021700.AA16651@mycroft.rand.org>
MIME-Version: 1.0
Content-Type: text/plain



> kentborg@world.std.com (Kent Borg) writes:
> joshua@cae.retix.com writes:
> Besides, your sample phrase might not have as many bits in it as you
> think.

> >Rare steak tastes good when it is cooked over a wood fire. better
> >chicken. better than fish. good with worcestershire sauce.

> 22 words, a good start.  But all will appear in a short dictionary
> list, 4 gramatical sentences, sentences with related meaning.  Not so

I think it's quite likely to have 128 bits worth of keyfulness (no, that's
not a Term of Art).  Shannon estimated from experiments (people guessing
the next letter in connected standard English text) that English contains
about one bit of information per character.  The ungrammatical structures
and missing caps would add more bits to the data in those areas, so the
120 or so characters would yield more than 120 bits of information.
Guessing a long passphrase from a dictionary attack doesn't work, as you
can tell from some simple arithmetic: 22 words out of a 1,000-word
dictionary is like 10^66 possibilities, and 'worcestershire' wouldn't be
in the 1,000-word dictionary.  Note also that guessing keyphrases using
some kind of Markov algorithm isn't going to be easy, because unlike the
Shannon experiment you don't get any feedback on your trials until you
have every bloody bit right.  It requires enumerating all legal 128-byte
English sequences and testing each in turn.

It's much easier to use an attack like Tim suggested than to break even
a weakish passphrase (well, not as weak as "quick brown fox").  One example
would be infiltrating Cypherpunk PGP key-signing parties: write a TSR or
custom COMMAND.COM that will capture all keystrokes typed on your laptop,
and offer it to others for signing your key and others'.  Don't forget to
have any command that accesses the floppy disk check for a file called
"secring.pgp" and copy it to your hard drive under the name
c:\scratch\junk17.foo.  Remember, you're signing keys to verify that you
know who they are... not that you trust them.

	Jim Gillogly
	9 Afterlithe S.R. 1994, 16:57