From: grady@netcom.com (1016/2EF221)
Date: Sat, 17 Apr 93 08:18:53 PDT
To: cypherpunks@toad.com
Subject: fuzzy grep available
Message-ID: <9304171519.AA27926@netcom.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain



"agrep" version 2.0.4 available via anonymous FTP
from sunsite.unc.edu (including source) has a
feature of cryptographic interest: fuzzy searches.

For example, agrep -2 cypherpunks newsgroupspooldirectory

would find all occurrence of"cypherpunks" or any such
pattern with up to two errors of substitution, addition
or deletion.  cpyherpunks, cyphernks cipherapunks would
all be found, fer instance.  And the thing is Boyer-Moore
sublinear FAST.  Also has egrep features looking for up
to 30,000 (yes, thirty thousand) patterns simultaneously
with Boyer-Moore speed.

For the NSA the applications are obvious: look for a bounch
of keys words like revolution Timothy May NSA quickly.

For us a good initial use might be to screen out "bad" passwords
that are to simply a variant of a normal word.  For example,
if agrep -3 <prospective password/phrase> usr/dict/words
or the lyric library, or the star trek location list or whatever,
if anything were found then that password FAILS.  This is
a lot easier to use than other available tools.


Like, MacPGP2.2 source, I will mail this on request IF you
cannot do anonymous FTP from where you are.

Grady Ward