Re: PROTOCOLS: Re: Hashed Hash

[Ben.Goren@asu.edu]

At 10:54 PM 7/17/94, wcs@anchor.ho.att.com
(bill.stewart@pleasantonca.ncr.com +1-510 wrote:
>> I'm planning on implementing the "cryptographic protection of databases"
>> on page 61 of Schneier, to create a directory of a professional
>> organization that would be useless to telemarketers.
>> [hash last name to get DES key and location of encrypted data in list.]

Not quite; the last name would at least be the foundation of the
key--otherwise, just use the first field to decrypt the second. Location is
either 132 or 160 bytes from the start of the hash; all else is obscurity
that wouldn't be all that effective. Remeber, anybody can do individual
lookups, or else I'd just use some secure method to get it into people's
hands. If you can do individual lookups, you can do a lot (all) of them;
the best I can hope for is to slow that down, preferably in a
cryptographically secure way.

>> [ problems of brute-force and popular-last-names attacks ]
>
>If you're only concerned about telemarketers, this amount of obscurity
>may be enough - anybody competent enough to hash a list of, say,
>10000 last names x 1000 first names into your database is at
>least an *interesting* telemarketer :-)

All it takes is some ambitious employee with connections to somebody with a
medium-sized workstation with a fair amount of idle time, like overnight. A
cheapie Alpha would do very nicely. Let it work--at no cost other than
initial setup and electricity--for a month or three, and you've got an
awful lot of names, even if you don't have the whole database.

There's not much obscurity here. Just write a minimal wrapper to the
existing (supplied) decryption code, unless my "security" relies on
non-cryptographic stalling, like counting to a million before doing
anything. I sure don't want to rely on that.

And a company such as Microsoft wouldn't even notice the effort. Think
about it: a database of musicians (the group I'm doing this for is the Phi
Mu Alpha Sinfonia, the men's professional fraternity in music) known to be
technically inclined--after all, their database is cryptographically
protected. Who better to target for their musical instrument CD?

>If you're concerned about telemarkers from the NSA/FBI/KGB,
>then the algorithm isn't enough anyway [. . .]

If any TLA wants the unencrypted database, they can have it from me for the
price of a warrant--and that's just to be sure that they're not imposters.
Our membership rolls are alerady public.

>An intermediate variant is to use a password as part of the hash;
>if everybody has their own password, the table size is N**2, or you can
>give everyone the same password without increasing the table size,
>and still be able to distribute the list on FTP.
>[. . .]

Nice idea. If there is demand for a program such as this after I've written
the basic version for Sinfonia, I'll code that, as well.

>On the question of whether there are functions I(m) = H(H(m)) for popular
>hashes, by definition there are, since H(H(m)) is one.

Well, by that definition, DES is a group....

>For most of
>the cryptographically useful functions, though, there aren't any that
>are faster than running the hash function twice.  Some exceptions are
>hashes like a**x mod p, x**a mod p, and obviously (a*x+c) mod p.
>But DES is known not to be a group, and MD5 is ugly enough it probably
>isn't group-like either.

Any chance you (or anybody else) can point me in the direction of sources
that would state this definitively? I'd much rather do multiple hashes than
use some sort of kludge with multiple DES encryptions, but I won't unless I
can find something in the literature. "A job worth doing...."

>                        Bill

Thanks for your help.

b&

--
Ben.Goren@asu.edu, Arizona State University School of Music
 net.proselytizing (write for info): Protect your privacy; oppose Clipper.
 Voice concern over proposed Internet pricing schemes. Stamp out spamming.
 Finger ben@tux.music.asu.edu for PGP 2.3a public key.