From: Ben Goren <ben@Tux.Music.ASU.Edu>
Date: Sat, 16 Jul 94 13:52:27 PDT
To: cypherpunks@toad.com
Subject: Hashed hash
Message-ID: <Pine.3.89.9407161315.B9512-0100000@Tux.Music.ASU.Edu>
MIME-Version: 1.0
Content-Type: text/plain


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.

There's a problem, though: a brute-force attack is agonizingly easy. If 
the hash algorithm runs at the same speed as DES, then an MC68040 could 
break all eight-letter last names in about three months. Only those who 
have twelve-letter last names would have even the security of DES against 
brute-force, and all this goes out the window if the attacker has any 
brains at all and uses the "telephone-book" attack Bruce mentions.

So, my question: for any of the popular hash algorithms H(m), is it known if 
there is or is not an algorithm I(m) such that I(m)=H(H(m))? Are the hash 
algorithms groups or not?

If not, then I can hash the name field as many times as I like for as much
of a strength v speed compromise as I want. If they are groups, then I
either have to figure out some other method of slowing things down--and I
haven't yet thought of anything that isn't either trivial or security
through obscurity--or decide if I can live with the fact that it's still
about as hard to get the information by a cryptographic attack as by
scanning in the printed book. 

Of course, should the electronic version be much more secure, then perhaps 
I can talk the organization into stopping printed publication, and it 
would be useful to organizations which haven't yet published their 
membership lists over fears of abuse.

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.