At 12:19 AM 7/17/94, Kent Borg wrote:
Ben.Goren@asu.edu foolishly says:
I'm planning on implementing the "cryptographic protection of databases"
And wonders about the hash being too fast to compute, that a brute-force traversal of the database would be too easy. The idea is then to hash a bunch of times to burn CPU cycles, but what if the hash is a group, extra hashing could be reversed quickly. (Did I get that right?)
On the nose.
Well, as the LOUD proponent of making secret keys s-l-o-w-e-r to decrypt, I have thought about this a bit, and have a suggestion:
Hash once, then do a zillion encryptions of the hash with a non-group cypher like DES.
I'll probably do just that. First thought, subject to revision: hash the name, feed it to DES with the output of a deterministic RNG (need not be secure, but the slower the better--BBS? (not that BBS is incesure)) as the key; repeat as needed. Hmmm...perhaps I'll adapt an earlier idea of mine: split the hash into two parts, a and b, and compute (a^(1/b))-1, and use some or all bits after the leading zeros.
Another idea (something I have thought less about): send every legit user of the database a custom version with the parts encrypted with that user's public key--and do the trick mailing list companies use, scatter some dummy info in the list. When a dummy (not just me) gets a junk mailing, go beat up on the user who's copy had to have supplied the junk [. . . .]
Nice idea, but there's neither the available resources to do that, nor, I think, the desire to beat up on careless users. Berzerk suggests a 0.1 S/N ratio (and in an earlier note a couple useable algorithms for the multiple encryption process); that would not be practical for any decent sized database, and I might have 100K or so people to deal with. But I almost certainly will mix in at least some random padding. I imagine that the database will always be the same length, even as people are added and/or removed with time. And the records, of course, will be premuted randomly.
-kb, the Kent who doesn't want to be thought of as only a card player
Then here's a suggestion for you: develop some other primitives, like rolling dice, and you could implement just about any other game you like. Monopoly would need (aside from licensing issues) the dice, two decks of special cards, and some ecash. (Surely MM used as Monopoly Money isn't subversive? After all, it's teaching our young 'uns to be good capitalists.) Scrabble would need a deck of cards, each of which contains only a letter, with many duplicates. Trivial Pursiut is just a huge deck of cards; they'd probably be index positions to the database of questions, so special editions are just a file switch away. These are among the most popular games in the US, and probalby abroad. Build your primitives right, and these games are as simple as specifing paramaters (how many sides to the dice, what info the cards contain, etc.). And maybe you could license the stuff, each and every independent game, to the current owners of the games that aren't PD. So how about becomming "kb, the Kent who digitized the American family evening"? Go for it! And drop me a line when you want beta testers (sometime Thursday?).
Kent Borg +1 (617) 776-6899
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.